Application of Circulant Matrices to the Construction and Decoding of Linear Codes

Abstract

An rXr matrix A =[a,iy] over a field F is called circulant if aij = a0,(j-i)mod r. An [n = 2r,k = r] linear code over F = GF(q) is called double-circulant if it is generated by a matrix of the form [I A], where A is an r × r circulant matrix. In this work we first employ the Fourier transform technique to analyze and construct several families of double-circulant codes. The minimum distance of the resulting codes is lower-bounded by [Formula omited] and can be decoded easily employing the standard BCH decoding algorithm or the majority-logic decoder of Reed-Muller codes. Second, we present a decoding procedure for Reed-Solomon codes, 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 proposed decoding procedure makes use of the encoding circuit together with a reduced version of Blahut’s decoder. © 1990 IEEE