American Institute of Mathematical Sciences

Advanced
May  2016, 10(2): 413-427. doi: 10.3934/amc.2016015

On the error distance of extended Reed-Solomon codes

Yujuan Li 1, and  Guizhen Zhu 2,

1. 

Science and Technology on Information Assurance Laboratory, Beijing, China
2. 

Data Communication Science and Technology Research Institute, Beijing, China

Received  September 2014 Revised  November 2015 Published  April 2016

It is well known that the main problem of decoding the extended Reed-Solomon codes is computing the error distance of a word. Using some algebraic constructions, we are able to determine the error distance of words whose degrees are $k+1$ and $k+2$ to the extended Reed-Solomon codes. As a corollary, we can simply get the results of Zhang-Fu-Liao on the deep hole problem of Reed-Solomon codes.
Keywords: equation system., error distance, decoding, Reed-Solomon code, Coding theory.
Mathematics Subject Classification: 94B35;11C0.
Citation: Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
References:
[1]

E. Berlekamp and L. Welch, Error correction of algebraic block codes, US Patent Number 4633470, 1986. Google Scholar

[2]

A. Cafure, G. Matera and M. Privitelli, Singularities of symmetric hypersurfaces and an application to Reed-Solomon codes, Adv. Math. Commun., 6 (2012), 69-94. doi: 10.3934/amc.2012.6.69.  Google Scholar

[3]

Q. Cheng, J. Li and J. Zhuang, On determining deep holes of generalized Reed-Solomon codes, in Algorithms and Computation, Springer, Berlin, 2013, 100-110. doi: 10.1007/978-3-642-45030-3_10.  Google Scholar

[4]

Q. Cheng and E. Murray, On deciding deep holes of Reed-Solomon codes, in Proc. TAMC 2007, Springer, 2007, 296-305. doi: 10.1007/978-3-540-72504-6_27.  Google Scholar

[5]

Q. Cheng and D. Wan, On the list and bounded distance decodability of Reed-Solomon codes, SIAM J. Comput., 37 (2007), 195-209. doi: 10.1137/S0097539705447335.  Google Scholar

[6]

Q. Cheng and D. Wan, Complexity of decoding positive-rate Reed-Solomon codes, IEEE Trans. Inf. Theory, 56 (2010), 5217-5222. doi: 10.1109/TIT.2010.2060234.  Google Scholar

[7]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45 (1995), 1757-1767. doi: 10.1109/18.782097.  Google Scholar

[8]

V. Guruswami and A. Vardy, A Maximum-likelihood decoding of Reed-Solomon codes is NP-Hard, IEEE Trans. Inf. Theory, 51 (2005), 2249-2256. doi: 10.1109/TIT.2005.850102.  Google Scholar

[9]

Y. J. Li and D. Wan, On error distance of Reed-Solomon codes, Sci. China Math., 51 (2008), 1982-1988. doi: 10.1007/s11425-008-0066-3.  Google Scholar

[10]

J. Y. Li and D. Wan, On the subset sum problem over finite fields, Finite Fields Appl., 14 (2008), 911-929. doi: 10.1016/j.ffa.2008.05.003.  Google Scholar

[11]

Q. Liao, On Reed-Solomon Codes, Chinese Ann. Math. Ser. B, 32 (2011), 89-98. doi: 10.1007/s11401-010-0622-3.  Google Scholar

[12]

R. Lidl and H. Niederreiter, Finite Fields, 2nd edtion, Cambridge Univ. Press. 1997.  Google Scholar

[13]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound , J. Complexity, 13 (2007), 180-193. doi: 10.1006/jcom.1997.0439.  Google Scholar

[14]

R. Wu and S. Hong, On deep holes of generalized Reed-Solomon codes,, preprint, ().   Google Scholar

[15]

J. Zhang, F. W. Fu and Q. Y. Liao, Deep holes of generalized Reed-Solomon codes (in Chinese), Sci. Sin. Math., 43 (2013), 727-740. Google Scholar

[16]

G. Zhu and D. Wan, Computing error distance of Reed-Solomon codes, in Theory and Applications of Models of Computation, Springer, Berlin, 2012, 214-224. doi: 10.1007/978-3-642-29952-0_24.  Google Scholar

show all references

References:
[1]

E. Berlekamp and L. Welch, Error correction of algebraic block codes, US Patent Number 4633470, 1986. Google Scholar

[2]

A. Cafure, G. Matera and M. Privitelli, Singularities of symmetric hypersurfaces and an application to Reed-Solomon codes, Adv. Math. Commun., 6 (2012), 69-94. doi: 10.3934/amc.2012.6.69.  Google Scholar

[3]

Q. Cheng, J. Li and J. Zhuang, On determining deep holes of generalized Reed-Solomon codes, in Algorithms and Computation, Springer, Berlin, 2013, 100-110. doi: 10.1007/978-3-642-45030-3_10.  Google Scholar

[4]

Q. Cheng and E. Murray, On deciding deep holes of Reed-Solomon codes, in Proc. TAMC 2007, Springer, 2007, 296-305. doi: 10.1007/978-3-540-72504-6_27.  Google Scholar

[5]

Q. Cheng and D. Wan, On the list and bounded distance decodability of Reed-Solomon codes, SIAM J. Comput., 37 (2007), 195-209. doi: 10.1137/S0097539705447335.  Google Scholar

[6]

Q. Cheng and D. Wan, Complexity of decoding positive-rate Reed-Solomon codes, IEEE Trans. Inf. Theory, 56 (2010), 5217-5222. doi: 10.1109/TIT.2010.2060234.  Google Scholar

[7]

V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45 (1995), 1757-1767. doi: 10.1109/18.782097.  Google Scholar

[8]

V. Guruswami and A. Vardy, A Maximum-likelihood decoding of Reed-Solomon codes is NP-Hard, IEEE Trans. Inf. Theory, 51 (2005), 2249-2256. doi: 10.1109/TIT.2005.850102.  Google Scholar

[9]

Y. J. Li and D. Wan, On error distance of Reed-Solomon codes, Sci. China Math., 51 (2008), 1982-1988. doi: 10.1007/s11425-008-0066-3.  Google Scholar

[10]

J. Y. Li and D. Wan, On the subset sum problem over finite fields, Finite Fields Appl., 14 (2008), 911-929. doi: 10.1016/j.ffa.2008.05.003.  Google Scholar

[11]

Q. Liao, On Reed-Solomon Codes, Chinese Ann. Math. Ser. B, 32 (2011), 89-98. doi: 10.1007/s11401-010-0622-3.  Google Scholar

[12]

R. Lidl and H. Niederreiter, Finite Fields, 2nd edtion, Cambridge Univ. Press. 1997.  Google Scholar

[13]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound , J. Complexity, 13 (2007), 180-193. doi: 10.1006/jcom.1997.0439.  Google Scholar

[14]

R. Wu and S. Hong, On deep holes of generalized Reed-Solomon codes,, preprint, ().   Google Scholar

[15]

J. Zhang, F. W. Fu and Q. Y. Liao, Deep holes of generalized Reed-Solomon codes (in Chinese), Sci. Sin. Math., 43 (2013), 727-740. Google Scholar

[16]

G. Zhu and D. Wan, Computing error distance of Reed-Solomon codes, in Theory and Applications of Models of Computation, Springer, Berlin, 2012, 214-224. doi: 10.1007/978-3-642-29952-0_24.  Google Scholar

[1]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[2]

Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057
[3]

Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69
[4]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[5]

José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467
[6]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[7]

Radosław Kurek, Paweł Lubowiecki, Henryk Żołądek. The Hess-Appelrot system. Ⅲ. Splitting of separatrices and chaos. Discrete & Continuous Dynamical Systems, 2018, 38 (4) : 1955-1981. doi: 10.3934/dcds.2018079
[8]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[9]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149
[10]

Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala. Hilbert quasi-polynomial for order domains and application to coding theory. Advances in Mathematics of Communications, 2018, 12 (2) : 287-301. doi: 10.3934/amc.2018018
[11]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[12]

Sébastien Court. Stabilization of a fluid-solid system, by the deformation of the self-propelled solid. Part II: The nonlinear system.. Evolution Equations & Control Theory, 2014, 3 (1) : 83-118. doi: 10.3934/eect.2014.3.83
[13]

Sébastien Court. Stabilization of a fluid-solid system, by the deformation of the self-propelled solid. Part I: The linearized system.. Evolution Equations & Control Theory, 2014, 3 (1) : 59-82. doi: 10.3934/eect.2014.3.59
[14]

Paweł Lubowiecki, Henryk Żołądek. The Hess-Appelrot system. I. Invariant torus and its normal hyperbolicity. Journal of Geometric Mechanics, 2012, 4 (4) : 443-467. doi: 10.3934/jgm.2012.4.443
[15]

Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331
[16]

El Miloud Zaoui, Marc Laforest. Stability and modeling error for the Boltzmann equation. Kinetic & Related Models, 2014, 7 (2) : 401-414. doi: 10.3934/krm.2014.7.401
[17]

Georgy L. Alfimov, Pavel P. Kizin, Dmitry A. Zezyulin. Gap solitons for the repulsive Gross-Pitaevskii equation with periodic potential: Coding and method for computation. Discrete & Continuous Dynamical Systems - B, 2017, 22 (4) : 1207-1229. doi: 10.3934/dcdsb.2017059
[18]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[19]

Yvan Martel, Tiễn Vinh Nguyến. Construction of 2-solitons with logarithmic distance for the one-dimensional cubic Schrödinger system. Discrete & Continuous Dynamical Systems, 2020, 40 (3) : 1595-1620. doi: 10.3934/dcds.2020087
[20]

Mario Bukal. Well-posedness and convergence of a numerical scheme for the corrected Derrida-Lebowitz-Speer-Spohn equation using the Hellinger distance. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3389-3414. doi: 10.3934/dcds.2021001

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (162)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences