On the weight distribution of the cosets of MDS codes

Alexander A. Davydov; Stefano Marcugini; Fernanda Pambianco

doi:10.3934/amc.2021042

Article Contents

2023, Volume 17, Issue 5: 1115-1138. Doi: 10.3934/amc.2021042

This issue Previous Article Cryptographic multilinear maps using pro-p groups Next Article Optimal quinary negacyclic codes with minimum distance four

On the weight distribution of the cosets of MDS codes

1.
Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, Moscow, 127051, Russian Federation
2.
Department of Mathematics and Computer Science, University of Perugia, Perugia, 06123, Italy

^* Corresponding author: Alexander A. Davydov
^* Corresponding author: Alexander A. Davydov

Received: January 2021

Revised: June 2021

Early access: September 2021

Published: October 2023

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

The weight distribution of the cosets of maximum distance separable (MDS) codes is considered. In 1990, P.G. Bonneau proposed a relation to obtain the full weight distribution of a coset of an MDS code with minimum distance $ d $ using the known numbers of vectors of weights $ \le d-2 $ in this coset. In this paper, the Bonneau formula is transformed into a more structured and convenient form. The new version of the formula allows to consider effectively cosets of distinct weights $ W $. (The weight $ W $ of a coset is the smallest Hamming weight of any vector in the coset.) For each of the considered $ W $ or regions of $ W $, special relations more simple than the general ones are obtained. For the MDS code cosets of weight $ W = 1 $ and weight $ W = d-1 $ we obtain formulas of the weight distributions depending only on the code parameters. This proves that all the cosets of weight $ W = 1 $ (as well as $ W = d-1 $) have the same weight distribution. The cosets of weight $ W = 2 $ or $ W = d-2 $ may have different weight distributions; in this case, we proved that the distributions are symmetrical in some sense. The weight distributions of the cosets of MDS codes corresponding to arcs in the projective plane $ \mathrm{PG}(2,q) $ are also considered. For MDS codes of covering radius $ R = d-1 $ we obtain the number of the weight $ W = d-1 $ cosets and their weight distribution that gives rise to a certain classification of the so-called deep holes. We show that any MDS code of covering radius $ R = d-1 $ is an almost perfect multiple covering of the farthest-off points (deep holes); moreover, it corresponds to an optimal multiple saturating set in the projective space $ \mathrm{PG}(N,q) $.

Keywords:

Mathematics Subject Classification: Primary: 94B05; Secondary: 51E21, 51E22.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	E. F. Assmus and H. F. Mattson, The weight-distribution of a coset of a linear code, IEEE Trans. Inform. Theory, 24 (1978), 497-497. doi: 10.1109/tit.1978.1055903.
[2]	S. Ball, Finite Geometry and Combinatorial Applications, London Math. Soc. Student Texts 82, Cambridge Univ. Press, Cambridge, UK, 2015. doi: 10.1017/CBO9781316257449.
[3]	S. Ball and M. Lavrauw, Arcs in finite projective spaces, EMS Surveys in Math. Sciences, 6 (2019), 133-172. doi: 10.4171/EMSS/33.
[4]	D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points with small density from projective geometry, Adv. Math. Commun., 9 (2015), 63-85. doi: 10.3934/amc.2015.9.63.
[5]	D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Further results on multiple coverings of the farthest-off points, Adv. Math. Commun., 10 (2016), 613-632. doi: 10.3934/amc.2016030.
[6]	D. Bartoli, A. A. Davydov, S. Marcugini and F. Pambianco, On the smallest size of an almost complete subset of a conic in PG(2, q) and extendability of Reed–Solomon codes, Probl. Inform. Transmiss., 54 (2018), 101-115. doi: 10.1134/S0032946018020011.
[7]	D. Bartoli, A. A. Davydov, S. Marcugini and F. Pambianco, On planes through points off the twisted cubic in G(3, q) and multiple covering codes, Finite Fields Appl., 67 (2020), paper 101710, 25 pp. doi: 10.1016/j.ffa.2020.101710.
[8]	D. Bartoli, M. Giulietti and I. Platoni, On the covering radius of MDS codes, IEEE Trans. Inform. Theory, 61 (2015), 801-811. doi: 10.1109/TIT.2014.2385084.
[9]	R. E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley, Reading, 1983.
[10]	R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves, Cambridge Univ. Press, Cambridge, 2008. doi: 10.1017/CBO9780511543401.
[11]	A. Blokhuis, R. Pellikaan and T. Szönyi, The extended coset leader weight enumerator of a twisted cubic code, preprint, arXiv: 2103.16904.
[12]	P. G. Bonneau, Weight distribution of translates of MDS codes, Combinatorica, 10 (1990), 103-105. doi: 10.1007/BF02122700.
[13]	P. Charpin, T. Helleseth and V. A. Zinoviev, The coset distribution of triple-error-correcting binary primitive BCH codes, IEEE Trans. Inform. Theory, 52 (2006), 1727-1732. doi: 10.1109/TIT.2006.871605.
[14]	K.-M. Cheung, More on the decoder error probability for Reed-Solomon codes, IEEE Trans. Inform. Theory, 35 (1989), 895-900. doi: 10.1109/18.32169.
[15]	K.-M. Cheung, Identities and approximations for the weight distribution of q-ary codes, IEEE Trans. Inform. Theory, 36 (1990), 1149-1153. doi: 10.1109/18.57216.
[16]	K.-M. Cheung, On the decoder error probability of block codes, IEEE Transactions on Communications, 40 (1992), 857-859. doi: 10.1109/26.141450.
[17]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Math. Library, 54, Elsevier, Amsterdam, The Netherlands, 1997.
[18]	A. A. Davydov, S. Marcugini and F. Pambianco, On integral weight spectra of the MDS codes cosets of weight 1, 2, and 3, preprint, arXiv: 2007.02405.
[19]	A. A. Davydov, S. Marcugini and F. Pambianco, On cosets weight distributions of the doubly-extended Reed-Solomon codes of codimension 4, IEEE Trans. Inform. Theory, 67 (2021), 5088-5096. doi: 10.1109/TIT.2021.3089129.
[20]	P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Inform. Control, 23 (1973), 407-438. doi: 10.1016/S0019-9958(73)80007-5.
[21]	P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips Res. Rep. Supplements, vol. 10. Centrex Publishing Co., Eindhoven, The Netherlands, 1973.
[22]	P. Delsarte and V. I. Levenshtein, Association schemes and coding theory, IEEE Trans. Inform. Theory, 44 (1998), 2477-2504. doi: 10.1109/18.720545.
[23]	T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350. doi: 10.1007/s10623-015-0156-5.
[24]	M. F. Ezerman, M. Grassl and P. Solé, The weights in MDS codes, IEEE Trans. Inform. Theory, 57 (2011), 392-396. doi: 10.1109/TIT.2010.2090246.
[25]	E. M. Gabidulin and T. Kløve, The Newton radius of MDS codes, in Proc. Inf. Theory Workshop (ITW 1998) (Cat. No.98EX131), Killarney, Ireland, Jun. 1998, 50–51. doi: 10.1109/ITW.1998.706412.
[26]	T. Helleseth, The weight distribution of the coset leaders of some classes of codes with related parity-check matrices, Discrete Math., 28 (1979), 161-171. doi: 10.1016/0012-365X(79)90093-1.
[27]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2 edition, Oxford Univ. Press, Oxford, 1998.
[28]	J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: Update 2001, in (eds. A. Blokhuis, J. W. P. Hirschfeld, D. Jungnickel and J. A. Thas), Finite Geometries (Proc. 4th Isle of Thorns Conf., July 16-21, 2000), Develop. Math., 3, Kluwer, Dordrecht, (2001), 201–246. doi: 10.1007/978-1-4613-0283-4_13.
[29]	J. W. P. Hirschfeld and J. A. Thas, Open problems in finite projective spaces, Finite Fields Appl., 32 (2015), 44-81. doi: 10.1016/j.ffa.2014.10.006.
[30]	S. Hong and R. Wu, On deep holes of generalized Reed-Solomon codes, AIMS Math., 1 (2016), 96-101. doi: 10.3934/Math.2016.2.96.
[31]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003. doi: 10.1017/CBO9780511807077.
[32]	R. Jurrius and R. Pellikaan, The coset leader and list weight enumerator, in (eds. G. Kyureghyan, G. L. Mullen, A. Pott), Contemporary Math., 632, Topics in Finite Fields American Mathematical Society, Providence, RI, USA, (2015), 229–251. doi: 10.1090/conm/632/12631.
[33]	J. Justesen and T. Høholdt, Bounds on list decoding of MDS codes, IEEE Trans. Inform. Theory, 47 (2001), 1604-1609. doi: 10.1109/18.923744.
[34]	K. Kaipa, Deep holes and MDS extensions of Reed-Solomon codes, IEEE Trans. Inform. Theory, 63 (2017), 4940-4948. doi: 10.1109/TIT.2017.2706677.
[35]	T. Kasami and S. Lin, On the probability of undetected error for the maximum distance separable codes, IEEE Trans. Commun., 32 (1984), 998-1006. doi: 10.1109/TCOM.1984.1096175.
[36]	T. Kløve, Codes for Error Detection, World Scientific Publ., Singapore, 2007. doi: 10.1142/9789812770516.
[37]	I. Landjev and L. Storme, Galois geometry and coding theory, in Current Research Topics in Galois geometry, (eds. J. De Beule and L. Storme), Chapter 8, NOVA Academic, New York, (2011), 187–214.
[38]	J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell Syst. Tech. J., 42 (1963), 79-94. doi: 10.1002/j.1538-7305.1963.tb04003.x.
[39]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, 3^rd edition, North-Holland, Amsterdam, The Netherlands, 1981.
[40]	J. Riordan, Combinatorial Identities, Willey, New York, 1968.
[41]	R. Roth, Introduction to Coding Theory, Cambridge Univ. Press, Cambridge, 2006. doi: 10.1017/CBO9780511808968.
[42]	J. R. Schatz, On the weight distributions of cosets of a linear code, American Math. Month., 87 (1980), 548-551. doi: 10.1080/00029890.1980.11995087.
[43]	L. Storme, Completeness of normal rational curves, J. Algebraic Combin., 1 (1992), 197-202. doi: 10.1023/A:1022428405084.
[44]	X. Xu and Y. Xu, Some results on deep holes of generalized projective Reed-Solomon codes, AIMS Math., 4 (2019), 176-192. doi: 10.3934/math.2019.2.176.
[45]	J. Zhang, D. Wan and K. Kaipa, Deep holes of projective Reed-Solomon codes, IEEE Trans. Inform. Theory, 66 (2020), 2392-2401. doi: 10.1109/TIT.2019.2940962.