Technical Report CS0535

Title: Application of Circulant Matrices to the Construction and Decoding of Linear Codes
Authors: R.M. Roth and A. Lempel
Abstract: A kXk matrix A=[aij] over a field F is called circulant if aij=a(j-i) modk. A[2k,k] 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 a circulant matrix. In this work we ftrst 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 2*sqrt(k) 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion