[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Algebraic Decoding of Cyclic Codes Using Partial Syndrome Matrices

Published: 01 February 2018 Publication History

Abstract

Cyclic codes have been widely used in many applications of communication systems and data storage systems. This paper proposes a new procedure for decoding cyclic codes up to actual minimum distance. The decoding procedure consists of two steps: 1) computation of known syndromes and 2) computation of error positions and error values simultaneously. To do so, a matrix whose all entries are syndromes is called syndrome matrix. A matrix whose entries are either syndromes or the elements of a finite field is said to be partial syndrome matrix. In this paper, two novel methods are presented to determine error positions and error values simultaneously and directly. The first method uses a new partial syndrome matrix along with Gaussian elimination. The partial syndrome matrices for binary (respectively, ternary) cyclic codes of lengths from 69 to 99 (respectively, 16 to 37) are tabulated. For some cyclic codes, the partial syndrome matrices contain unknown syndromes; the second method constructs a matrix from a system of equations, which is generated by the determinants of different partial syndrome matrices and makes use of Gaussian elimination to determine its row rank. Many more cyclic codes beyond the Bose–Chaudhuri–Hocquenghem bound can be decoded with these methods.

References

[1]
E. R. Berlekamp, Algebraic Decoding Theory . New York, NY, USA: McGraw-Hill, 1968.
[2]
J. Massey, “ Shift-register synthesis and BCH decoding,” IEEE Trans. Inf. Theory, vol. Volume IT-15, no. Issue 1, pp. 122–127, 1969.
[3]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes . Amsterdam, The Netherlands: North-Holland, 1977.
[4]
R. W. Hamming, “ Error detecting and error correcting codes,” Bell Syst. Tech. J., vol. Volume 29, no. Issue 2, pp. 147–160, 1950.
[5]
M. J. E. Golay, “ Notes on digital coding,” Proc. IEEE, vol. Volume 37, p. pp.657, 1949.
[6]
M. Elia, “ Algebraic decoding of the (23, 12, 7) Golay code,” IEEE Trans. Inf. Theory, vol. Volume IT-33, no. Issue 1, pp. 150–151, 1987.
[7]
I. S. Reed, X. Yin, and T.-K. Truong, “ Algebraic decoding of the (32, 16, 8) quadratic residue code,” IEEE Trans. Inf. Theory, vol. Volume 36, no. Issue 4, pp. 876–880, 1990.
[8]
I. S. Reed, T. K. Truong, X. Chen, and X. Yin, “ The algebraic decoding of the (41, 21, 9) quadratic residue code,” IEEE Trans. Inf. Theory, vol. Volume 38, no. Issue 3, pp. 947–985, 1992.
[9]
X. Chen, I. S. Reed, and T. K. Truong, “ Decoding the (73, 37, 13) quadratic residue code,” IEE Proc.-Comput. Digit. Techn., vol. Volume 141, no. Issue 5, pp. 253–258, 1994.
[10]
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. Volume 37, no. Issue 6, pp. 1716–1723, 1991.
[11]
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. Volume 40, no. Issue 5, pp. 1364–1374, 1994.
[12]
K. K. Shen, C. Wang, K. K. Tzeng, and B. Z. Shen, “ Generation of matrices for determining minimum distance and decoding of cyclic codes,” IEEE Trans. Inf. Theory, vol. Volume 42, no. Issue 2, pp. 653–657, 1996.
[13]
R. He, I. S. Reed, T.-K. Truong, and X. Chen, “ Decoding the (47, 24, 11) quadratic residue code,” IEEE Trans. Inf. Theory, vol. Volume 47, no. Issue 3, pp. 1181–1186, 2001.
[14]
Y. Chang, T.-K. Truong, I. S. Reed, H. Y. Cheng, and C. D. Lee, “ Algebraic decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes,” IEEE Trans. Commun., vol. Volume 51, no. Issue 9, pp. 1463–1473, 2003.
[15]
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. Volume 54, no. Issue 11, pp. 5005–5011, 2008.
[16]
T.-K. Truong, Y. Chang, Y.-H. Chen, and C. D. Lee, “ Algebraic decoding of (103, 52, 19) and (113, 57, 15) quadratic residue codes,” IEEE Trans. Commun., vol. Volume 53, no. Issue 5, pp. 749–754, 2005.
[17]
E. Orsini and M. Sala, “ Correcting errors and erasures via the syndrome variety,” J. Pure Appl. Algebra, vol. Volume 200, nos. Issue 1</issue>–<issue>2, pp. 191–226, 2005.
[18]
E. Orsini and M. Sala, “ General error locator polynomials for binary cyclic codes with <inline-formula><tex-math notation=LaTeX>$t\leq 2$</tex-math></inline-formula> and <inline-formula><tex-math notation=LaTeX>$n<63$</tex-math></inline-formula>,” IEEE Trans. Inf. Theory, vol. Volume 53, no. Issue 3, pp. 1095–1107, 2007.
[19]
J. F. Humphreys, “ Algebraic decoding of the ternary (13,7,5) quadratic residue code,” IEEE Trans. Inf. Theory, vol. Volume 38, no. Issue 3, pp. 1122–1125, 1992.
[20]
R. J. Higgs and J. F. Humphreys, “ Decoding the ternary Golay code,” IEEE Trans. Inf. Theory, vol. Volume 39, no. Issue 3, pp. 1043–1046, 1993.
[21]
R. J. Higgs and J. F. Humphreys, “ Decoding the ternary (23, 12, 8) quadratic residue code,” IEE Proc.-Commun., vol. Volume 142, no. Issue 3, pp. 129–134, 1995.
[22]
T. Baicheva, S. Dodunekov, and R. Koetter, “ On the performance of the ternary {13, 7, 5} quadratic-residue code,” IEEE Trans. Inf. Theory, vol. Volume 48, no. Issue 2, pp. 562–564, 2002.
[23]
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. Volume 61, no. Issue 3, pp. 1179–1187, 2015.
[24]
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. Volume 64, no. Issue 7, pp. 2719–2731, 2016.
[25]
C. Marcolla, E. Orsini, and M. Sala, “ Improved decdoing of affine-variety codes,” J. Pure Appl. Algebra, vol. Volume 216, no. Issue 7, pp. 1533–1565, 2012.
[26]
G. Promhouse and S. E. Tavares, “ The minimum distance of all binary cyclic codes of odd lengths from 69 to 99,” IEEE Trans. Inf. Theory, vol. Volume IT-24, no. Issue 4, pp. 438–442, 1978.
[27]
C.-L. Chen, “ Computer results on the minimum distance of some binary cyclic codes,” IEEE Trans. Inf. Theory, vol. Volume IT-16, no. Issue 3, pp. 359–360, 1970.
[28]
R. Larson and B. H. Edwards, Elementary Linear Algebra, 4th ed. New York, NY, USA: Houghton Mifflin, 2000.
[29]
S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, 2nd ed. Upper Saddle River, NJ, USA: Prentice-Hall, 2004.

Cited By

View all
  • (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
  • (2018)New Locator Polynomials for Cyclic Codes2018 International Symposium on Information Theory and Its Applications (ISITA)10.23919/ISITA.2018.8664367(678-682)Online publication date: 28-Oct-2018

Recommendations

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 64, Issue 2
February 2018
734 pages

Publisher

IEEE Press

Publication History

Published: 01 February 2018

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (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
  • (2018)New Locator Polynomials for Cyclic Codes2018 International Symposium on Information Theory and Its Applications (ISITA)10.23919/ISITA.2018.8664367(678-682)Online publication date: 28-Oct-2018

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media