TABLE OF CONTENTS The procedures for decoding linear block codes are also applicable to cyclic codes. However, the algebraic structure of cyclic codes allows for some significant simplifications on decoder implementation. The syndrome calculation consists just of computing the remainder of the division of the received n-tuple in polynomial form by the generator polynomial. The syndrome polynomial is denoted by s( x). If s( x) = 0, the received n-tuple is accepted as a valid code word, otherwise, i.e. if s( x) ? 0, the decoder declares the occurrence of errors. It follows that a circuit to implement error-detection with cyclic codes is indeed very simple. Error location in a received n-tuple, however, is in general a more difficult task to solve in practice. The most important algebraic decoding techniques are those based on the Berlekamp Massey (BM) algorithm (Massey, 1969) and on the Euclidean algorithm (Clark and Cain, 1981).
In terms of implementation complexity, encoding and decoding are in general very asymmetric operations, with decoding being far more complex than encoding. For practical reasons, very often a suboptimum coding scheme is chosen by taking into consideration that performance is satisfactory and the decoder implementation is amenable. Strictly algebraic decoding algorithms (Berlekamp, 1968, Massey, 1969) that are efficient to handle hard-decision errors have proved very hard to adapt to perform soft-decision decoding.
The BM algorithm was discovered by Elwyn Berlekamp in...
