Application of circulant matrices to the construction and decoding of linear codes
Ron M. Roth, Abraham Lempel · IEEE Transactions on Information Theory · 1990
The Fourier transform technique is used to analyze and construct several families of double-circulant codes. The minimum distance of the resulting codes is lower-bounded by 2 square root r and can be decoded easily employing the standard BCH decoding algorithm or the majority-logic decoder of Reed-Muller codes. A decoding procedure for Reed-Solomon codes is presented, based on a representation of the parity-check matrix by circulant blocks. The decoding procedure inherits both the (relatively low) time complexity of the Berlekamp-Massey algorithm and the hardware simplicity characteristic of Blahut's algorithm. The procedure makes use of the encoding circuit together with a reduced version of Blahut's decoder.>