Transform Techniques for Error Control Codes

Abstract

By using the theory of finite field Fourier transforms, the subject of error control codes is described in a language familiar to the field of signal processing. The many important uses of spectral techniques in error control are summarized. Many classes of linear codes are given a spectral interpretation and some new codes are described. Several alternative encoder/decoder schemes are described by frequency domain reasoning. In particular, an errors-and-erasures decoder for a BCH code is exhibited which has virtually no additional computations over an errors-only decoder. Techniques for decoding BCH, RS, and alternant codes (Goppa codes) a short distance beyond the designed distance are discussed. Also, a modification to the definition of a BCH code is described which reduces the decoder complexity without changing the code's rate or minimum distance.