On the error distance of extended Reed-Solomon codes

Previous Article
Coherence of sensing matrices coming from algebraic-geometric codes
AMC Home
This Issue
Next Article
Nearly perfect sequences with arbitrary out-of-phase autocorrelation

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

Abstract
Related Papers

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	Q. Liao, On Reed-Solomon Codes, Chinese Ann. Math. Ser. B, 32 (2011), 89-98. doi: 10.1007/s11401-010-0622-3.
[12]	R. Lidl and H. Niederreiter, Finite Fields, 2nd edtion, Cambridge Univ. Press. 1997.
[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.
[14]	R. Wu and S. Hong, On deep holes of generalized Reed-Solomon codes,, preprint, ().
[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.
[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.

show all references

References:

[1]	E. Berlekamp and L. Welch, Error correction of algebraic block codes, US Patent Number 4633470, 1986.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	Q. Liao, On Reed-Solomon Codes, Chinese Ann. Math. Ser. B, 32 (2011), 89-98. doi: 10.1007/s11401-010-0622-3.
[12]	R. Lidl and H. Niederreiter, Finite Fields, 2nd edtion, Cambridge Univ. Press. 1997.
[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.
[14]	R. Wu and S. Hong, On deep holes of generalized Reed-Solomon codes,, preprint, ().
[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.
[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.

[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 and 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 and 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$₄-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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems, 2020, 40 (3) : 1595-1620. doi: 10.3934/dcds.2020087
[20]	Orazio Muscato, Wolfgang Wagner. A stochastic algorithm without time discretization error for the Wigner equation. Kinetic and Related Models, 2019, 12 (1) : 59-77. doi: 10.3934/krm.2019003

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Yujuan Li Guizhen Zhu
on Google Scholar
Yujuan Li Guizhen Zhu

[Back to Top]