On the covering radius of Reed-Solomon codes. (English) Zbl 0790.94019
Summary: For doubly-extended Reed-Solomon codes over \(\text{GF}(q)\) with minimum distance \(d\) the covering radius \(\rho\) is either \(d-1\) or \(d-2\). For \(3\leq d\leq q\), it is proved that \(\rho=d-2\) if and only if the \((q+1)\)- arc consisting of the points of a normal rational curve in \(\text{PG}(d- 2,q)\) is complete. For \(\rho=d-1\) a characterization of the deep holes of the sphere packing in Hamming space defined by the code is given in terms of their syndromes.
MSC:
| 94B05 | Linear codes (general theory) |
Keywords:
doubly-extended Reed-Solomon codes; minimum distance; covering radius; normal rational curve; sphere packing in Hamming space; syndromesReferences:
| [1] | Bruen, A. A.; Thas, J. A.; Blokhuis, A., On M.D.S. codes, arcs in PG(n,q) with \(q\) even, and a solution of three fundamental problems of B. Serge, Invent. Math., 92, 441-459 (1988) · Zbl 0654.94014 |
| [2] | Cohen, G. D.; Karpovsky, M. G.; Mattson, H. F.; Schatz, J. R., Covering radius-survey and recent results, IEEE Trans. Inform. Theory, 31, 328-343 (1985) · Zbl 0586.94014 |
| [3] | Dür, A., The automorphism groups of Reed-Solomon codes, J. Combin. Theory Ser. A, 44, 69-82 (1987) · Zbl 0621.94010 |
| [4] | Dür, A., On linear MDS codes of length \(q+1\) over GF \((q)\) for even \(q\), J. Combin. Theory Ser. A, 49, 172-174 (1988) · Zbl 0649.94017 |
| [5] | Dür, A., The decoding of extended Reed-Solomon codes, Discrete Math., 90, 21-40 (1991) · Zbl 0726.94010 |
| [6] | Hill, R., A First Course in Coding Theory (1986), Clarendon Press: Clarendon Press Oxford · Zbl 0616.94006 |
| [7] | Janwa, H., Some optimal codes from algebraic geometry and their covering radii, European J. Combin., 11, 249-266 (1990) · Zbl 0705.94014 |
| [8] | C.D. Jensen and J.P. Pedersen, Cyclic and pseudo-cyclic MDS codes of length \(q+1\), Mat-Report 1989-18, Math. Inst., Technical Univ. of Denmark.; C.D. Jensen and J.P. Pedersen, Cyclic and pseudo-cyclic MDS codes of length \(q+1\), Mat-Report 1989-18, Math. Inst., Technical Univ. of Denmark. · Zbl 0744.94014 |
| [9] | Kaneta, H.; Maruta, T., An elementary proof and an extension of Thas’s theorem on \(k\)-arcs, Math. Proc. Cambridge Philos. Soc., 105, 459-462 (1989) · Zbl 0688.51007 |
| [10] | Krishna, A.; Sarwate, D. V., Pseudocyclic maximum-distance-separable codes, IEEE Trans. Inform. Theory, 36, 880-884 (1990) · Zbl 0707.94012 |
| [11] | Macdonald, I. G., Symmetric Functions and Hall Polynomials (1979), Clarendon Press: Clarendon Press Oxford · Zbl 0487.20007 |
| [12] | MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1981), North-Holland: North-Holland Amsterdam · Zbl 0369.94008 |
| [13] | Serge, B., Curve razionali normali e \(k\)-archi negli spazi finiti, Ann. Mat. Pura Appl., 39, 4, 357-379 (1955) · Zbl 0066.14001 |
| [14] | Seroussi, G.; Roth, R. M., On MDS extensions of generalized Reed—Solomon codes, IEEE Trans. Inform Theory, 32, 349-354 (1986) · Zbl 0594.94017 |
| [15] | Storme, L., Note on completeness of normal rational curves, (Seminar of Geometry and Combinatorics (1991), State University of Ghent), Preprint · Zbl 0771.51005 |
| [16] | Storme, L.; Thas, J. A., MDS codes and arcs in PG(n,q) with \(q\) even: an improvement of the bounds of Bruen, Thas and Blokhuis, (Seminar of Geometry and Combinatorics (1990), State University of Ghent), Preprint · Zbl 0771.51006 |
| [17] | Storme, L.; Thas, J. A., Generalized Reed-Solomon codes and normal rational curves: an improvement of results by Seroussi and Roth, (Hirschfeld, J. W.P.; Hughes, D. R.; Thas, J. A., Advances in Finite Geometries and Designs (1991), Oxford University Press: Oxford University Press Oxford), 369-389 · Zbl 0732.51009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
