More Web Proxy on the site http://driver.im/

research-article

Algebraic Decoding of Some Quadratic Residue Codes With Weak Locators

Authors:

Trieu-Kien Truong,

Yaotsu ChangAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 61, Issue 3

Pages 1179 - 1187

https://doi.org/10.1109/TIT.2015.2388753

Published: 01 March 2015 Publication History

Abstract

In this paper, an explicit expression of the weak-locator polynomial for p-ary quadratic residue codes is presented by a modification of the Feng-Tzeng matrix method. The differences between the modified version and the original Feng-Tzeng matrix are that in the new matrix, not every entry is a syndrome, and every syndrome entry is a known syndrome. By utilizing this technique, an algebraic decoding of the ternary (61, 30, 12) quadratic residue code is proposed. This new result has never been seen in the literature to our knowledge. An advantage of the proposed decoding algorithm is that in general the obtained weak-locator polynomials can decode efficiently not only all the error patterns of weights four and five, but also some error patterns of weight six.

References

[1]

R. T. Chien and V. Y. Lum, “On Golay’s perfect codes and step-by-step decoding (Corresp.),” IEEE Trans. Inf. Theory, vol. 12, no. 3, pp. 403–404, Jul. 1966.

Digital Library

[2]

S.-W. Wei and C.-H. Wei, “Complete decoding algorithm of (11, 6, 5) Golay code,” Electron. Lett., vol. 25, no. 17, pp. 1191–1192, Aug. 1989.

[3]

M. Elia and E. Viterbo, “Algebraic decoding of the ternary (11, 6, 5) Golay code,” Electron. Lett., vol. 28, no. 21, pp. 2021–2022, Oct. 1992.

[4]

R. J. Higgs and J. F. Humphreys, “Decoding the ternary Golay code,” IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 1043–1046, May 1993.

Digital Library

[5]

J. Rifà, “A new algebraic algorithm to decode the ternary Golay code,” Inf. Process. Lett., vol. 68, no. 6, pp. 271–274, Dec. 1998.

Digital Library

[6]

J. F. Humphreys, “Algebraic decoding of the ternary (13, 7, 5) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 38, no. 3, pp. 1122–1125, May 1992.

Digital Library

[7]

T. Baicheva, S. Dodunekov, and R. Koetter, “On the performance of the ternary [13, 7, 5] quadratic-residue code,” IEEE Trans. Inf. Theory, vol. 48, no. 2, pp. 562–564, Feb. 2002.

Digital Library

[8]

R. J. Higgs and J. F. Humphreys, “Decoding the ternary (23, 12, 8) quadratic residue code,” IEE Proc.-Commun., vol. 142, no. 3, pp. 129–134, Jun. 1995.

[9]

M. Elia and J. Carmelo Interlando, “Quadratic-residue codes and cyclotomic fields,” Acta Appl. Math., vol. 93, nos. 1–3, pp. 237–251, Sep. 2006.

[10]

J. Carmelo Interlando, “Decoding the ternary (23, 11, 9) quadratic residue code,” Res. Lett. Commun., vol. 2009, Jan. 2009, Art. ID.

[11]

J. Carmelo Interlando, “Algebraic decoding of the ternary (37, 18, 11) quadratic residue code,” Int. J. Inf. Coding Theory, vol. 2, no. 1, pp. 59–65, 2011.

[12]

G.-L. Feng and K. K. Tzeng, “Decoding cyclic and BCH codes up to actual minimum distance using nonrecurrent syndrome dependence relations,” IEEE Trans. Inf. Theory, vol. 37, no. 6, pp. 1716–1723, Nov. 1991.

Digital Library

[13]

G.-L. Feng and K. K. Tzeng, “A new procedure for decoding cyclic and BCH codes up to actual minimum distance,” IEEE Trans. Inf. Theory, vol. 40, no. 5, pp. 1364–1374, Sep. 1994.

Digital Library

[14]

E. Orsini and M. Sala, “Correcting errors and erasures via the syndrome variety,” J. Pure Appl. Algebra, vol. 200, nos. 1–2, pp. 191–226, Aug. 2005.

[15]

E. Orsini and M. Sala, “General error locator polynomials for binary cyclic codes with $t$ ≤ 2 and $n$ < 63,” IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1095–1107, Mar. 2007.

Digital Library

[16]

Y. Chang and C.-D. Lee, “Algebraic decoding of a class of binary cyclic codes via lagrange interpolation formula,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 130–139, Jan. 2010.

Digital Library

[17]

M. Giorgetti and M. Sala, “A commutative algebra approach to linear codes,” J. Algebra, vol. 321, no. 8, pp. 2259–2286, Apr. 2009.

[18]

C. Marcolla, E. Orsini, and M. Sala, “Improved decoding of affine-variety codes,” J. Pure Appl. Algebra, vol. 216, no. 7, pp. 1533–1565, Jul. 2012.

[19]

C.-D. Lee, “Weak general error locator polynomials for triple-error-correcting binary Golay code,” IEEE Commun. Lett., vol. 15, no. 8, pp. 857–859, Aug. 2011.

[20]

R. He, I. S. Reed, T.-K. Truong, and X. Chen, “Decoding the (47, 24, 11) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1181–1186, Mar. 2001.

Digital Library

[21]

T.-K. Truong, P.-Y. Shih, W.-K. Su, C.-D. Lee, and Y. Chang, “Algebraic decoding of the (89, 45, 17) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 54, no. 11, pp. 5005–5011, Nov. 2008.

Digital Library

[22]

D. Coppersmith and G. Seroussi, “On the minimum distance of some quadratic residue codes (Corresp.),” IEEE Trans. Inf. Theory, vol. 30, no. 2, pp. 407–411, Mar. 1984.

Digital Library

[23]

J. M. Wozencraft and I. M. Jacobs, Principles of Communication Engineering. New York, NY, USA: Wiley, 1965.

Cited By

Lee C(2019)Radical-Locator Polynomials and Row-Echelon Partial Syndrome Matrices With Applications to Decoding Cyclic CodesIEEE Transactions on Information Theory10.1109/TIT.2018.287554665:6(3713-3723)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TIT.2018.2875546

Index Terms

Algebraic Decoding of Some Quadratic Residue Codes With Weak Locators

Index terms have been assigned to the content through auto-classification.

Recommendations

Algebraic decoding of the (41, 21, 9) Quadratic Residue code

In this paper, an algebraic decoding algorithm is proposed to correct all patterns of four or fewer errors in the binary (41, 21, 9) Quadratic Residue (QR) code. The technique needed here to decode the (41, 21, 9) QR code is different from the ...
Algebraic Decoding of the (31, 16, 7) Quadratic Residue Code by Using Berlekamp-Massey Algorithm
CMC '10: Proceedings of the 2010 International Conference on Communications and Mobile Computing - Volume 02

An algebraic decoding of the (89, 45, 17) quadratic residue code suggested by Truong et al. (2008) has been designed that uses the inverse-free Berlekamp-Massey (BM) algorithm to determine the error-locator polynomial and applies a verification method ...
Decoding the (47,24,11) quadratic residue code using bit-error probability estimates

A new algorithm is developed to facilitate faster decoding of the (47,24,11) Quadratic Residue (QR) code. This decoder, based on the idea first developed by Reed in a 1959 MIT Lincoln Laboratory Report, uses real channel data to estimate the individual ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Information Theory

IEEE Transactions on Information Theory Volume 61, Issue 3

March 2015

356 pages

ISSN:0018-9448

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Press

Publication History

Published: 01 March 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee C(2019)Radical-Locator Polynomials and Row-Echelon Partial Syndrome Matrices With Applications to Decoding Cyclic CodesIEEE Transactions on Information Theory10.1109/TIT.2018.287554665:6(3713-3723)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TIT.2018.2875546

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents