4.2 Cyclic Codes

Cyclic codes are among the most important codes for practical applications in engineering (Lin and Palais, 1986). Cyclic codes have been used as part of many communication protocols, in music CDs, in magnetic recording (Immink, 1991), etc. The preference for cyclic codes is a consequence of their mathematical structure based on discrete mathematics, which allows a considerable simplification in the implementation of encoders and decoders for such codes. A formal mathematical treatment of q-ary cyclic codes relies on polynomial rings (Peterson and Weldon, 1972), modulo x ⁿ ? 1, with coefficients in the Galois field GF( q), in which n denotes the code block length (Berlekamp, 1968).

Thus, for example, if v = ( v _{0 ,} v _{1 ,} v _{2 , ,} v _{n ?1}) is a code word and is right-shifted cyclically by i positions, then v ⁱ = ( v _{n ? i ,} v _{n ? i + 1 , ,} v _{0 ,} v _{1 ,} , v _{n ? i ? 1}) is also a code word, in which the indices are reduced modulo n. An n-tuple, e.g. v, can be represented by a...