Ressource pédagogique : 3.2. Combinatorial Solutions: Exhaustive Search and Birthday Decoding

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

In this session, I will detail two combinatorial solutions to the decoding problem. The first one is the Exhaustive Search. To find our w columns, we will simply enumerate all the tuples j1 to jw and check whether the corresponding column plus the syndrome is equal to zero modulo 2. In detail here is how we will do. We have w loops enumerating the indices from j1 to jw, and in the innermost loop, we add the w columns plus the syndrome and either we test the value of the syndrome or we store it depending on what is our need. The cost of this algorithm is at most w(n,w) column additions plus a certain number of tests. In practice, the cost for the test is negligible and we will just ignore that term, and we have this cost for the algorithm. But we can do better. Instead, we may keep track of partial sums. In the first loop, line 1, we add the syndrome to the first column. In the second loop, we add the first partial sum to the second column. We obtain a second partial sum and so on until, in the inner loop, we add the previous partial sum to the last column. If we do this, since each line i is executed (n,i) times, we have a total of column additions which is given here. And this cost is dominated by (n,w), when w is not too large. So, the total cost for the Exhaustive Search is (n,w) column operations. And for that cost, we obtain all the solutions to our problem. We can do better with the Birthday Decoding. In this algorithm, we split the matrix into two equal parts and we will enumerate all solutions by enumerating those two lists using error pattern of weight w/2. If the intersection of those two lists is not empty, then we have a solution to our problem. Here is the algorithm. We first enumerate all errors of weight w/2, compute the syndrome and store each of the computed values. This will cost (n/2,w/2), that is the size of the first list. At this point, we may check the intersection of the two lists, L1 and L2. This last part of the algorithm will cost (L1 * L2)/2 to the size of the syndrome. Coming back to the Birthday Decoding slide, the cost of the above enumeration will be given by the formula here with binomial coefficient which can also be written as 2L + (L²/2^(n-k)) where L is the size common to the two lists. To measure the exact complexity of this algorithm, we have to take into account that an error pattern of weight w splits evenly between the two halves of the matrix with a probability P which may be smaller than one.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Thème(s)