SyndromeDecoder with parameter for number of errors

Syndrome decoding is the following:

Precompute a "Coset leadertable": Go through all vectors in the ambient space and compute their syndromes. For each syndrome, remember the vector with this syndrome which has the smallest weight. This is the smallest error which can result in that syndrome. When getting a received word r, one simply computes its syndrome and return r + e, where e is the cached vector for syndrome(r).

When building the coset leader table, we should go through the vectors in increasing order of hamming weight, and then stop as soon as all syndromes have been matched. This improves precomputation time to at worst binom(n,n-k) * q^(n-k).

This method thus takes binom(n, n-k) * q^(n-k) precomputation and n*q^(n-k) memory to store the coset leaders. But it is an ML decoder.

If one is satisfied with correcting up to t < n-k errors, one can just go through the errors of weight at most t and build a partial Coset leader table from this. Thus, more or less exactly the same algorithm as before, just parameterised, and it could easily be contained in the same general implementation.

This could simplify some other code, such as the 1-error decoding of Hamming codes (which is a special case of t=1 syndrome decoding)

Comments (1)