Keywords: coding theory, root finding, decoding, fast algorithms
Prerequisites: 01405: Algebraic Coding Theory
In hardware implementations of BCH decoders, error location is bottleneck, i.e. finding the error-locator polynomial and afterwards, the roots of the error locator polynomial. In high-density optical transmission, one would like to be able to correct up to 5 errors as fast as possible. In this project we will consider the following question:
How can we perform decoding for a 5-error-correcting BCH code as fast as possible?
A strategy to answer this question is the following: To speed up finding the error-locator polynomial, one can precompute a so-called generic error-locator polynomial, i.e. one can find an expression containing the syndromes as additional variables, such that for each actual value of the syndromes one obtains the correct error-locator polynomial from the generic error-locator polynomial by substituting the syndrome values.
Such expressions are too lengthy in general, but if the number of errors one needs to correct is modest this is more feasible.. To find the roots of the polynomial of degree 5, the strategy is to use suitably chosen transformations to bring any given polynomial in a standard form. Tricks similar (but algebraically more interesting) to completing the square are generalized and used for this purpose. Afterwards a strategy will be developed to solve the remaining standard cases, among others using table lookup for special cases.
