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

On the error distance of extended Reed-Solomon codes

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.
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, (4633). 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. 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, (2013), 100. 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, (2007), 296. 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. 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. 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. 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. 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. 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. 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. doi: 10.1007/s11401-010-0622-3. Google Scholar

[12]

R. Lidl and H. Niederreiter, Finite Fields,, 2nd edtion, (1997). Google Scholar

[13]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound ,, J. Complexity, 13 (2007), 180. 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. Google Scholar

[16]

G. Zhu and D. Wan, Computing error distance of Reed-Solomon codes,, in Theory and Applications of Models of Computation, (2012), 214. 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, (4633). 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. 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, (2013), 100. 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, (2007), 296. 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. 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. 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. 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. 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. 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. 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. doi: 10.1007/s11401-010-0622-3. Google Scholar

[12]

R. Lidl and H. Niederreiter, Finite Fields,, 2nd edtion, (1997). Google Scholar

[13]

M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound ,, J. Complexity, 13 (2007), 180. 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. Google Scholar

[16]

G. Zhu and D. Wan, Computing error distance of Reed-Solomon codes,, in Theory and Applications of Models of Computation, (2012), 214. 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]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[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]

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

[12]

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

[13]

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

[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]

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

[16]

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

[17]

Orazio Muscato, Wolfgang Wagner. A stochastic algorithm without time discretization error for the Wigner equation. Kinetic & Related Models, 2019, 12 (1) : 59-77. doi: 10.3934/krm.2019003

[18]

L. Dieci, M. S Jolly, Ricardo Rosa, E. S. Van Vleck. Error in approximation of Lyapunov exponents on inertial manifolds: The Kuramoto-Sivashinsky equation. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 555-580. doi: 10.3934/dcdsb.2008.9.555

[19]

Jérôme Coville, Juan Dávila. Existence of radial stationary solutions for a system in combustion theory. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 739-766. doi: 10.3934/dcdsb.2011.16.739

[20]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]