Application of circulant matrices to the construction and decoding of linear codes

Author

Roth, Ron M. ; Lempel, Abraham

Author_Institution

IBM Almaden Res. Center, San Jose, CA, USA

Volume

36

Issue

5

fYear

1990

fDate

9/1/1990 12:00:00 AM

Firstpage

1157

Lastpage

1163

Abstract

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√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

Keywords

decoding; encoding; error correction codes; BCH decoding algorithm; Berlekamp-Massey algorithm; Blahut´s algorithm; Fourier transform technique; Reed-Muller codes; Reed-Solomon codes; circulant matrices; decoding; double-circulant codes; hardware simplicity; linear codes; majority-logic decoder; minimum distance; parity-check matrix; time complexity; Circuits; Conferences; Decoding; Encoding; Fourier transforms; Hardware; Information theory; Linear code; Parity check codes; Reed-Solomon codes;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/18.57218

Filename

57218