The Fourier Transform and Cyclic Codes
Richard E. Blahut · Cambridge University Press eBooks · 2001
Error-control codes are now in widespread use in many applications such as communication systems, magnetic recording systems, and optical recording systems. The compact disk and the digital video disk are two familiar examples of such applications. We shall discuss only block codes for error control. A block code for error control is a set of n -tuples in some finite alphabet, usually the finite field GF ( q ). The reason for choosing a field as the alphabet is to have a rich arithmetic structure so that practical codes can be constructed and encoders and decoders can be designed as computational algorithms. The most popular block codes are linear. This means that the componentwise sum of two codewords is a codeword, and any scalar multiple of a codeword is a codeword. So that a large number of errors can be corrected, it is desirable that codewords be very dissimilar from each other. This dissimilarity will be measured by the Hamming distance. The most important class of block codes, the Reed–Solomon codes , will be described as an exercise in the complexity of sequences and of Fourier transform theory. Another important class of block codes, the BCH codes , will be described as a class of subcodes of the Reed–Solomon codes, all of whose components lie in a subfield. The BCH codes and the Reed–Solomon codes are examples of cyclic codes, which themselves form a subclass of the class of linear block codes.