The algebraic decoding of the (41, 21, 9) quadratic residue code

Author

Reed, Irving S. ; Truong, T.K. ; Chen, Xuemin ; Yin, Xiaowei

Author_Institution

Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA

Volume

38

Issue

3

fYear

1992

fDate

5/1/1992 12:00:00 AM

Firstpage

974

Lastpage

986

Abstract

A new algebraic approach for decoding the quadratic residue (QR) codes, in particular the (41, 21, 9) QR code, is presented. The key ideas behind this decoding technique are a systematic application of the Sylvester resultant method to the Newton identities associated with the syndromes to find the error-locator polynomial, and next a method for determining error locations by solving certain quadratic, cubic, and quartic equations over GF(2^m) in a new way which uses Zech´s logarithms for the arithmetic. The logarithms developed for Zech´s logarithms save a substantial amount of computer memory by storing only a table of Zech´s logarithms. These algorithms are suitable for implementation in a programmable microprocessor or special-purpose VLSI chip. It is expected that the algebraic methods developed can apply generally to other codes such as the BCH and Reed-Solomon codes

Keywords

decoding; error correction codes; polynomials; (41, 21, 9) QR code; BCH codes; GF(2^m); Newton identities; Reed-Solomon codes; Sylvester resultant method; Zech´s logarithms; algebraic decoding; cubic equations; error locations; error-locator polynomial; quadratic equations; quadratic residue code; quartic equations; syndromes; Arithmetic; Computer errors; Decoding; Equations; Galois fields; Microprocessors; Polynomials; Reed-Solomon codes; Very large scale integration;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/18.135639

Filename

135639