On the error distance of extended Reed-Solomon codes

Yujuan  Li; Guizhen  Zhu

doi:10.3934/amc.2016015

Article Contents

2016, Volume 10, Issue 2: 413-427. Doi: 10.3934/amc.2016015

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

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
2.
Data Communication Science and Technology Research Institute, Beijing

Received: August 31, 2014

Revised: October 31, 2015

Published: April 2016

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 94B35;11C08.

Citation:

Related Papers

Cited by

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, arXiv:1205.7016
[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.