Error Correction Coding Receivers - Part 1

Error correction coding is a method of encoding a message for transmission over a noisy channel so that the message can be correctly received even if it has been corrupted by up to some number of errors. A good introduction can be found in a text on digital communications, such as
Digital Communications Fundamentals and Applications by Bernard Sklar, which is available on scribd. This text introduces the overall idea of error correction coding, and some important concepts such as Hamming distance, block codes, and generator polynomials. But it only scratches the surface. When it comes to a practical implementation, a more rigorous algebraic description is needed.

A Hamming code is fairly simple to decode. It is structured to be able to correct one error per message block. The encoded message is decoded by running it through a linear feedback shift register (LFSR) described by a certain generator polynomial. The remainder is the contents of the shift register, and this is called the syndrome. The syndrome maps to a location in the encoded message where a bit error occurred. If no errors were detected, the syndrome will be zero. In hardware, this can be realized with a Meggitt decoder. A good description of such a decoder can be found here [pdf].

More challenging is a decoder that can detect multiple errors, such as for a BCH code. The texts on this delve deeply into abstract algebra, which presents a challenge to someone who is more engineer than mathematician. Fortunately the problem has been reduced to an algorithm that should work for any BCH code, and this can be realized in hardware. Stay tuned for Part 2.