New Locator Polynomials for Cyclic Codes
Pages 678 - 682
Abstract
Cyclic codes, which are an important class of error-correcting codes, have wide applications in communication systems and data storage systems. This paper defines a new type of locator polynomial, called radical-locator polynomials, for the algebraic decoding of cyclic codes. These polynomials can be obtained by expanding the determinant of a newly proposed partial syndrome matrix. The sparse representation for the resulting polynomials is theoretically demonstrated. A complete decoding algorithm for cyclic codes is also provided.
References
[1]
R. W. Hamming, “Error detecting and error correcting codes,” Bell Syst. Tech. J., vol. 29, pp. 147-160, 1950.
[2]
M. J. E. Golay, “Notes on digital coding,” Proc. IRE, vol. 37, p. 67, 1949.
[3]
R. C. Bose and D.K. Ray-Chaudhuri, “On a class of error correcting binary group codes,” Inf. and Control, vol. 3, no. 1, pp. 68-79, Mar. 1960.
[4]
A. Hocquenghem, “Codes correcteurs d’erreurs,” Chiffres (in French), Paris, vol. 2, pp. 147-156, Sep. 1959.
[5]
I. S. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” IRE Trans. Inf. Theory, vol. 4, no. 4, pp. 38-49, Sep. 1954.
[6]
I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” J. Society for Industrial and Applied Mathematics (SIAM), vol. 8, no. 2, pp. 300-304, Jun. 1960.
[7]
W. W. Peterson, “Encoding and error-correction procedures for the Bose-Chaudhuri codes,” IRE Trans. Inf. Theory, vol. 6, no. 4, pp. 459-470, Sep. 1960.
[8]
E. R. Berlekamp, Algebraic Decoding Theory. New York: McGraw-Hill, 1968.
[9]
J. L. Massey, “Shift register synthesis and BCH decoding,” IEEE Trans. Inf. Theory, vol. 15, no. 1, pp. 122-127, Jan. 1969.
[10]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam, The Netherlands: North-Holland, 1977.
[11]
R. Chien, “Cyclic decoding procedures for Bose-Chaudhuri-Hocquenghem codes,” IEEE Trans. Inf. Theory, vol. 10, no. 4, pp. 357-363, Oct. 1964.
[12]
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.
[13]
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.
[14]
F. Caruso, E. Orsini, M. Sala, and C. Tinnirello, “On the shape of the general error locator polynomial for cyclic codes,” IEEE Trans. Inf. Theory, vol. 63, no. 6, pp. 3641-3657, Jun. 2017.
[15]
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.
[16]
C. D. Lee, Y. H. Chen, T. K. Truong, and Y. Chang, “Algebraic decoding of some quadratic residue codes with weak locators,” IEEE Trans. Inf. Theory, vol. 61, no. 3, pp. 1179-1187, Mar. 2015.
[17]
T. C. Lin, C. D. Lee, Y. H. Chen, and T. K. Truong, “Algebraic decoding of cyclic codes without error-locator polynomials,” IEEE Trans. Commun., vol. 64, no. 7, pp. 2719-2731, Jul. 2016.
[18]
C. D. Lee, “Algebraic decoding of cyclic codes using partial syndrome matrices,” IEEE Trans. Inf. Theory, vol. 64, no. 2, pp. 952-971, Feb. 2018.
[19]
T. C. Lin, C. D. Lee, T. K. Truong, and Y. Chang, “The use of multivariate weak-locator polynomials to decode cyclic codes up to actual minimum distance,” IEEE Trans. Inf. Theory. 10.1109/TIT.2018.2811502.
[20]
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.
[21]
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.
[22]
B. T. Le-Ngoc and V. K. Bhargava, “A microprocessor based decoder for BCH codes,” Can. Elec. Eng. J., vol. 4, no. 4, pp. 29-32, 1979.
[23]
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.
[24]
C. D. Lee, Y. Chang, M. H. Jing, and J. H. Chen, “Decoding binary cyclic codes with irreducible generator polynomials up to actual minimum distance,” IEEE Commun. Lett., vol. 14, no. 11, pp. 1050-1052, Nov. 2010.
Index Terms
- New Locator Polynomials for Cyclic Codes
Index terms have been assigned to the content through auto-classification.
Recommendations
Cyclic codes over Z4, locator polynomials, and Newton's identities
Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes ...
Quasi-cyclic LDPC codes: an algebraic construction
This paper presents two new large classes of QCLDPC codes, one binary and one non-binary. Codes in these two classes are constructed by array dispersions of row-distance constrained matrices formed based on additive subgroups of finite fields. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Oct 2018
756 pages
Copyright © 2018.
Publisher
IEEE Press
Publication History
Published: 28 October 2018
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 08 Mar 2025