3.2. Combinatorial Solutions: Exhaustive Search and Birthday Decoding

In this session, I willdetail two combinatorial solutions to the decoding problem. The first one isthe Exhaustive Search. To find our w columns,we will simply enumerate all the tuples j1 tojw and check whether the corresponding columnplus the syndrome is equal to zero modulo 2. In detailhere 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 andeither we test the value of the syndrome or we store itdepending on what is our need. The cost of thisalgorithm is at most w(n,w) column additions plus acertain number of tests. In practice, the costfor the test is negligible and we will just ignorethat term, and we have this cost for the algorithm. But we can do better. Instead, we may keeptrack of partial sums. In the first loop, line 1,we add the syndrome to the first column. In thesecond loop, we add the first partial sum to the second column. We obtain a second partialsum and so on until, in the inner loop, we add theprevious partial sum to the last column. If we dothis, since each line i is executed (n,i)times, we have a total of column additionswhich is given here. And this cost isdominated by (n,w), when w is not too large. So, thetotal cost for the Exhaustive Search is (n,w) column operations. And for that cost, we obtainall the solutions to our problem. We can do better withthe Birthday Decoding. In this algorithm, wesplit the matrix into two equal parts and we willenumerate all solutions by enumerating those twolists using error pattern of weight w/2. If theintersection of those two lists is not empty, then we havea solution to our problem.
Here is the algorithm. We first enumerate allerrors of weight w/2, compute the syndrome and store each of the computed values. Thiswill cost (n/2,w/2), that is the size of the first list. At this point, we may check the intersection of thetwo lists, L1 and L2. This last part of thealgorithm will cost (L1 * L2)/2 to the size of the syndrome. Coming back to theBirthday Decoding slide, the cost of the aboveenumeration will be given by the
formula here with binomialcoefficient which can also be written as 2L + (L²/2^(n-k)) where L is the size common to the two lists. To measure the exactcomplexity of this algorithm, we have to take into accountthat an error pattern of weight w splits evenly between thetwo halves of the matrix with a probability P whichmay be smaller than one.