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]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020276

[2]

Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168

[3]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[4]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[5]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[6]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[7]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[8]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[9]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020273

[10]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049

[11]

Peter Poláčik, Pavol Quittner. Entire and ancient solutions of a supercritical semilinear heat equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 413-438. doi: 10.3934/dcds.2020136

[12]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[13]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[14]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075

[15]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[16]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[17]

Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447

[18]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[19]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[20]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]