New infinite families of uniformly packed near-MDS codes and multiple coverings, based on the ternary Golay code

Alexander A. Davydov; Stefano Marcugini; Fernanda Pambianco

doi:10.3934/amc.2025050

Article Contents

2026, Volume 21: 192-211. Doi: 10.3934/amc.2025050

This volume Previous Article Binary cyclic codes from three classes of sequences Next Article Some combinatorial aspects of pedal sets

New infinite families of uniformly packed near-MDS codes and multiple coverings, based on the ternary Golay code

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

^*Corresponding author: Fernanda Pambianco
^*Corresponding author: Fernanda Pambianco

Received: June 2025

Early access: October 22, 2025

Published online: October 22, 2025

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

We present five new infinite families of linear near-MDS codes uniformly packed in the wide sense (UPWS). These codes are also almost perfect multiple coverings of the deep holes or farthest-off points (APMCF), i.e. the vectors lying at distance $ R $ (covering radius) from the code. The families are constructed by $ m $-lifting when one takes a starting code $ C $ over the ground Galois field $ \mathbb{F}_q $ with a parity check matrix $ H(C) $ and then considers the codes $ C_m $ over $ \mathbb{F}_{q^m} $, $ m\ge2 $, with the same parity check matrix $ H(C) $. As starting codes we used the ternary perfect Golay code and codes obtained by its extension and puncturing. To prove the needed combinatorial properties (UPWS and APMCF), we used the $ m $-lifting of the dual codes and features of near-MDS codes. A general theorem on infinite families of UPWS near-MDS codes is proved.

Keywords:

Mathematics Subject Classification: Primary: 94B25, 94B60; Secondary: 94B05.

Citation:

Full Text(HTML)

Table 1. Codes $ \mathscr{G}_{12, m} $, $ \mathscr{G}_{11, m} $, $ \mathscr{G}_{11, m}^\bot $, $ m\ge1 $, as multiple coverings

code $ C $	$ s^\bot $	U	$ b_R $	$ \mathcal{A}_R $	$ \mathcal{A}_{R+1} $	$ N $	$ \lambda $	$ \gamma_\lambda $	$ (R, \lambda) $-...MCF
$ \mathscr{G}_{12, 1}= $$ [12, 6, 6]_33 $	3	$ \bullet $	1	4	9	440	4	1	(3, 4)-PMCF
$ \mathscr{G}_{12, 2}= $	6	$ \blacktriangledown $	4	3	48	63360	3	1.28	(4, 3)-MCF
$ [12, 6, 6]_94 $				3	54	190080
				5	44	142560
				6	48	23760
$ \mathscr{G}_{12, 3}= $	6	$ \blacktriangledown $	$ \ge3 $	18	747		$ \le18 $	$>1 $	$ (5, \le18) $-MCF
$ [12, 6, 6]_{27}5 $				24	732
				36	702				not finished
$ \mathscr{G}_{11, 1}= $	2	$ \bullet $	1	1	6	220	1	1	(2, 1)-PMCF
$ [11, 6, 5]_32 $
$ \mathscr{G}_{11, 2}= $	5	$ \blacktriangledown $	1	30	240	7920	30	1	(4, 30)-APMCF
$ [11, 6, 5]_94 $
$ \mathscr{G}_{11, 3}= $	5	$ \blacktriangledown $	$ \ge4 $	5	388	2160	$ \le5 $	$>1 $	$ (4, \le5) $-MCF
$ [11, 6, 5]_{27}4 $				10	380	6480
				15	372	3900
				30	348	291			not finished
$ \mathscr{G}_{11, 1}^\bot= $	5	$ \bullet $	1	66	0	2	66	1	(5, 66)-APMCF
$ [11, 5, 6]_35 $
$ \mathscr{G}_{11, 2}^\bot= $	7	$ \blacktriangledown $	5	21	270	5280	21	1.48	(5, 21)-MCF
$ [11, 5, 6]_95 $				30	216	528
				30	243	10560
				33	234	31680
				66	0	8

| Show Table

DownLoad: CSV

Table 2. Codes $ \mathscr{G}_{n, m} $, $ \mathscr{G}_{n, m}^\bot $, $ n = 10, 9, 8 $, $ m\ge1 $, as multiple coverings

code $ C $	$ s^\bot $	U	$ b_R $	$ \mathcal{A}_R $	$ \mathcal{A}_{R+1} $	$ N $	$ \lambda $	$ \gamma_\lambda $	$ (R, \lambda) $-...MCF
$ \mathscr{G}_{10, 1}= $	2	$ \bullet $	1	3	12	60	3	1	(2, 3)-PMCF
$ [10, 6, 4]_32 $
$ \mathscr{G}_{10, 2}= $	4	$ \blacktriangledown $	2	8	142	2160	8	1.24	(3, 8)-MCF
$ [10, 6, 4]_93 $				12	123	1920
$ \mathscr{G}_{10, 3}= $	4	$ \bullet $	1	180	5724	112320	180	1	(4, 180)-APMCF
$ [10, 6, 4]_{27}4 $
$ \mathscr{G}_{10, 1}^\bot= $	7	$ \blacktriangledown $	1	36	0	4	36	1	(5, 36)-APMCF
$ [10, 4, 6]_35 $
$ \mathscr{G}_{10, 2}^\bot= $	7	$ \blacktriangledown $	1	180	360	48	180	1	(6, 180)-APMCF
$ [10, 4, 6]_96 $
$ \mathscr{G}_{9, 1}= $	2	$ \bullet $	1	9	18	8	9	1	(2, 9)-APMCF
$ [9, 6, 3]_32 $
$ \mathscr{G}_{9, 2}= $	3	$ \bullet $	1	72	702	48	72	1	(3, 72)-APMCF
$ [9, 6, 3]_93 $
$ \mathscr{G}_{9, 3}= $	3	$ \bullet $	1	72	2970	11856	72	1	(3, 72)-APMCF
$ [9, 6, 3]_{27}3 $
$ \mathscr{G}_{9, 1}^\bot= $	7	$ \blacktriangledown $	1	18	0	6	18	1	(5, 18)-APMCF
$ [9, 3, 6]_35 $
$ \mathscr{G}_{9, 2}^\bot= $	7	$ \blacktriangledown $	1	72	108	144	72	1	(6, 72)-APMCF
$ [9, 3, 6]_96 $
$ \mathscr{G}_{8, 1}= $	1	$ \bullet $	1	2	13	8	2	1	(1, 2)-PMCF
$ [8, 6, 2]_31 $
$ \mathscr{G}_{8, 2}= $	2	$ \bullet $	1	24	360	48	24	1	(2, 24)-APMCF
$ [8, 6, 2]_92 $
$ \mathscr{G}_{8, 3}= $	2	$ \bullet $	1	24	1368	624	24	1	(2, 24)-APMCF
$ [8, 6, 2]_{27}2 $
$ \mathscr{G}_{8, 1}^\bot= $	7	$ \blacktriangledown $	1	8	0	16	8	1	(5, 8)-APMCF
$ [8, 2, 6]_{3}5 $
$ \mathscr{G}_{8, 2}^\bot= $	7	$ \blacktriangledown $	1	24	24	1344	24	1	(6, 24)-APMCF
$ [8, 2, 6]_{9}6 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Barg, At the dawn of the theory of codes, Math. Intelligencer, 15 (1993), 20-26. doi: 10.1007/BF03025254.
[2]	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.
[3]	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.
[4]	L. A. Bassalygo and V. A. Zinoviev, Remark on uniformly packed codes, Probl. Inform. Transmission, 13 (1977), 178-180.
[5]	L. A. Bassalygo, G. V. Zaitsev and V. A. Zinoviev, Uniformly packed codes, Probl. Inform. Transmission, 10 (1974), 9-14.
[6]	J. Bierbrauer, Introduction to Coding Theory, 2$^{nd}$ edition, CRC Press, Taylor & Francis Group, Boca Raton, 2017.
[7]	J. Borges, J. Rifa and V. A. Zinoviev, On $q$-ary linear completely regular codes with $\rho = 2$ and antipodal dual, Adv. Math. Commun., 4 (2010), 567-578. doi: 10.3934/amc.2010.4.567.
[8]	J. Borges, J. Rifa and V. A. Zinoviev, On completely regular codes, Probl. Inform. Transmission, 55 (2019), 1-45. doi: 10.1134/S0032946019010010.
[9]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[10]	R. A. Brualdi, S. Litsyn and V. Pless, Covering radius, in (eds. V.S. Pless and W.C. Huffman) Handbook of Coding Theory, vol. 1, Elsevier, Amsterdam, The Netherlands, 1998,755-826.
[11]	P. J. Cameron and J. H. van Lint, Graph Theory, Coding Theory and Block Designs, London Math. Soc. Lecture Note Ser., No. 19, Cambridge University Press, Cambridge-New YorkMelbourne, 1975.
[12]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Mathematical Library, vol. 54. Elsevier, Amsterdam, The Netherlands, 1997.
[13]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Linear nonbinary covering codes and saturating sets in projective spaces, Adv. Math. Commun., 5 (2011), 119-147. doi: 10.3934/amc.2011.5.119.
[14]	A. A. Davydov, S. Marcugini and F. Pambianco, On the weight distribution of the cosets of MDS codes, Adv. Math. Commun., 17 (2023), 1115-1138. doi: 10.3934/amc.2021042.
[15]	A. A. Davydov and L. M. Tombak, Number of minimal-weight words in block codes, Problems Inform. Transmiss., 24 (1988), 7-18. Available from: https://www.researchgate.net/publication/268716136
[16]	M. A. De Boer, Almost MDS codes, Des. Codes Cryptogr., 9 (1996), 143-155. doi: 10.1007/BF00124590.
[17]	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.
[18]	C. Ding and C. Tang, Infinite families of near MDS codes holding $t$-designs, IEEE Trans. Inform. Theory, 66 (2020), 5419-5428. doi: 10.1109/TIT.2020.2990396.
[19]	S. Dodunekov and I. Landgev, On near-MDS codes, J. Geom., 54 (1995), 30-43. doi: 10.1007/BF01222850.
[20]	S. Dodunekov and I. Landjev, Near-MDS codes over some small fields, Discrete Math., 213 (2000), 55-65. doi: 10.1016/S0012-365X(99)00168-5.
[21]	D. Elimelech, M. Firer and M. Schwartz, The generalized covering radii of linear codes, IEEE Trans. Inform. Theory, 67 (2021), 8070-8085. doi: 10.1109/TIT.2021.3115433.
[22]	D. Elimelech, H. Wei and M. Schwartz, On the generalized covering radii of Reed-Muller codes, IEEE Trans. Inform. Theory, 68 (2022), 4378-4391. doi: 10.1109/TIT.2022.3158762.
[23]	A. Faldum and W. Willems, Codes of small defect, Des. Codes Cryptogr., 10 (1997), 341-350. doi: 10.1023/A:1008247720662.
[24]	J. M. Goethals and H. C. A. van Tilborg, Uniformly packed codes, Philips Res. Rep., 30 (1975), 9-36.
[25]	M. J. E. Golay, Notes on digital coding, Proc. IRE, 37 (1949), 657.Available from: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1698056
[26]	H. Hämäläinen, I. Honkala, S. Litsyn and P. Östergård, Football pools – a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588. doi: 10.1080/00029890.1995.12004624.
[27]	H. Hämäläinen and S. Rankinen, Upper bounds for football pool problems and mixed covering codes, J. Comb. Theory, Ser. A, 56 (1991), 84-95. doi: 10.1016/0097-3165(91)90024-B.
[28]	W. C. Huffman and V. S. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, Cambridge, 2003.
[29]	R. Jurrius and R. Pellikaan, The coset leader and list weight enumerator, in (eds. G.M. Kyureghyan, G.L. Mullen and A. Pott) Topics in Finite Fields Proc. 11-th Int. Conf. Finite Fields and their Applications), AMS, Contemporary Mathematics Series, 632 (2015), 229-252. Available from: https://www.win.tue.nl/ruudp/paper/71.pdf doi: 10.1090/conm/632/12631.
[30]	I. Landjev and A. Rousseva, The main conjecture for near-MDS codes, in (eds. A. Canteaut, G. Leurent and M. Naya-Plasencia) WCC2015 (Proc. 9th Int. Workshop Coding Cryptogr.), Apr 2015, Paris, France, (2015), hal-01276222. Available from: https://inria.hal.science/hal-01276222/document
[31]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Math. Library, Vol. 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
[32]	A. Neumaier, Completely regular codes, Discrete math., 106/107 (1992), 353-360. doi: 10.1016/0012-365X(92)90565-W.
[33]	J. Rifa and V. A. Zinoviev, On lifting perfect codes, IEEE Trans. Inform. Theory, 57 (2011), 5918-5925. doi: 10.1109/TIT.2010.2103410.
[34]	R. M. Roth, Introduction to Coding Theory, Univ. Press, Cambridge, 2006.
[35]	N. V. Semakov, V. A. Zinoviev and G. V. Zaitsev, Uniformly packed codes, Problems Inform. Transmiss., 7 (1971), 38-50.
[36]	T. M. Thompson, From Error-Correcting Codes through Sphere Packings to Simple Groups, Carus Math. Monogr., 21, The Mathematical Association of America, Washington, DC, 1983.
[37]	H. C. A. van Tilborg, Uniformly Packed Codes, Ph.D thesis, Eindhoven University of Technology, 1976. Available from: https://research.tue.nl/files/1736336/162111.pdf
[38]	G. J. M. van Wee, G. D. Cohen and S. N. Litsyn, A note on perfect multiple coverings of the Hamming space, IEEE Trans. Inform. Theory, 37 (1991), 678-682. doi: 10.1109/18.79931.