Almost MDS, almost Griesmer quasi-perfect codes with Griesmer dual codes

Conghui Xie; Hao Chen; Tingting Wu

doi:10.3934/amc.2026046

Article Contents

2026, Volume 25: 183-191. Doi: 10.3934/amc.2026046

This volume Previous Article A direct construction of 2D-CCC with arbitrary array size and flexible set size using multivariable function Next Article Binary cyclic codes from three classes of sequences

Almost MDS, almost Griesmer quasi-perfect codes with Griesmer dual codes

1.
Hetao Institute of Mathematics and Interdisciplinary Sciences, Shenzhen, Guangdong, 518033, China
2.
College of Information Science and Technology, Jinan University, Guangzhou, Guangdong, 510632, China
3.
School of Information and Artificial Intelligence, Anhui Agricultural University, Hefei, Anhui, 230036, China

^*Corresponding author: Conghui Xie
^*Corresponding author: Conghui Xie

Received: November 6, 2025

Revised: March 11, 2026

Published online: May 27, 2026

The research of Conghui Xie was supported by the NSFC Grant 12526523. The research of Hao Chen was supported by the NSFC Grant 62032009.

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

Abstract

Constructions of infinite families of almost MDS codes, Griesmer codes or quasi-perfect codes are challenging problems in coding theory. In this paper, we construct an infinite family of distance-optimal cyclic $ [q^{2m}-1, q^{2m}-3m-2, 4]_q $ codes over $ \mathbf{ F}_q $, where $ q $ is an arbitrary prime power. When $ m = 1 $, this family of almost MDS cyclic codes with Griesmer dual codes was constructed by Heng, Wang and Ding in their paper published in IEEE Trans. Inf. Theory, 2020. We prove that the covering radius of these almost MDS codes is three. Then we obtain many infinite families of their extended almost Griesmer and almost MDS $ [q^2, q^2-4, 4]_q $ codes. Their dual codes are almost Griesmer or Griesmer. Moreover, we prove that any almost MDS code with the minimum distance $ 3 $ and the length $ n \geq q+2 $ is quasi-perfect and the almost MDS $ [q^2+1, q^2-3, 4]_q $ code is quasi-perfect. This provides the first infinite family of almost MDS, almost Griesmer quasi-perfect codes with Griesmer dual codes.

Keywords:

Mathematics Subject Classification: Primary: 94B05, 94B15.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	T. Baicheva, I. Bouyukliev, S. Dodunekov and V. Fack, Binary and ternary linear quasi-perfect codes with small dimensions, IEEE Trans. Inf. Theory, 54 (2008), 4335-4339. doi: 10.1109/TIT.2008.928277.
[2]	S. Ball, P. Govaerts and L. Storme, On ovoids of parabolic quadrics, Des. Codes Cryptogr., 38 (2006), 131-145. doi: 10.1007/s10623-005-5666-0.
[3]	D. Bartoli, G. Faina, S. Marcugini and F. Pambianco, A construction of small complete caps in projective spaces, J. Geom., 108 (2017), 215-246. doi: 10.1007/s00022-016-0335-1.
[4]	M. A. de Boer, Almost MDS codes, Des. Codes Cryptogr., 9 (1996), 143-155. doi: 10.1007/BF00124590.
[5]	R. C. Bose and K. A. Bush, Orthogonal arrays of strength two and three, Ann. Math. Stat., 23 (1952), 508-524. doi: 10.1214/aoms/1177729331.
[6]	C. Camarero and C. Martínez, Quasi-perfect Lee codes of radius two and arbitrarily large dimensions, IEEE Trans. Inf. Theory, 62 (2016), 1183-1192. doi: 10.1109/TIT.2016.2517069.
[7]	M. Ceria, A. Cossidente, G. Marino and F. Pavese, On near-MDS codes and caps, Des. Codes Cryptogr., 91 (2023), 1095-1110. doi: 10.1007/s10623-022-01141-0.
[8]	H. Chen, Many non-Reed-Solomon type MDS codes from arbitrary genus algebraic curves, IEEE Trans. Inf. Theory, 70 (2024), 4856-4864. doi: 10.1109/TIT.2023.3348146.
[9]	G. D. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Mathematical Library, vol. 54. Elsevier, Amsterdam, 1997.
[10]	A. A. Davydov, S. Marcugini and F. Pambianco, Complete caps in projective spaces $PG(n, q)$, J. Geom., 80 (2004), 23-30. doi: 10.1007/s00022-004-1778-3.
[11]	C. Ding and T. Helleseth, Optimal ternary cyclic codes from monomials, IEEE Trans. Inf. Theory, 59 (2013), 5898-5904. doi: 10.1109/TIT.2013.2260795.
[12]	C. Ding and C. Tang, Designs from Linear Codes, 2$^{nd}$ edition, World Scientific, Singapore, 2022.
[13]	C. Ding and C. Tang, Combinatorial $t$-designs from special functions, Cryptogr. Commun., 12 (2020), 1011-1033. doi: 10.1007/s12095-020-00442-2.
[14]	S. Dodunekov, Some quasi-perfect double error correcting codes, Probl. Control Inform. Theory, 15 (1986), 367-375.
[15]	T. Etzion, Perfect Codes and Related Structures, World Scientific, Singapore, 2022.
[16]	T. Etzion and B. Mounits, Quasi-perfect codes with small distance, IEEE Trans. Inf. Theory, 51 (2005), 3938-3946. doi: 10.1109/TIT.2005.856944.
[17]	X. Geng, M. Yang, J. Zhang and Z. Zhou, A class of almost MDS codes, Finite Fields Appl., 79 (2022), 101996, 10 pp. doi: 10.1016/j.ffa.2022.101996.
[18]	M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4, IEEE Trans. Inf. Theory, 53 (2007), 1928-1935. doi: 10.1109/TIT.2007.894688.
[19]	D. Han and C. Fan, Roth-Lempel NMDS codes of non-elliptic-curve type, IEEE Trans. Inf. Theory, 69 (2023), 5670-5675. doi: 10.1109/TIT.2023.3272384.
[20]	Z. Heng, Q. Wang and C. Ding, Two families of optimal linear codes and their subfield codes, IEEE Trans. Inf. Theory, 66 (2020), 6872-6883. doi: 10.1109/TIT.2020.3006846.
[21]	Z. Heng and C. Ding, The subfield codes of some $[q+1, 2]$ MDS codes, IEEE Trans. Inf. Theory, 68 (2022), 3643-3656. doi: 10.1109/TIT.2022.3151721.
[22]	Z. Heng, C. Li and X. Wang, Constructions of MDS, near MDS and almost MDS codes from cyclic subgroups of $\mathbb{F}_{q^2}^$, IEEE Trans. Inf. Theory*, 68 (2022), 7817-7831. doi: 10.1109/TIT.2022.3194914.
[23]	Z. Hu, N. Li, X. Zeng, L. Wang and X. Tang, A subfield-based construction of optimal linear codes over finite fields, IEEE Trans. Inf. Theory, 68 (2022), 4408-4421. doi: 10.1109/TIT.2022.3163651.
[24]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, U.K., 2003.
[25]	L. Jin and H. Kan, Self-dual near MDS codes from elliptic curves, IEEE Trans. Inf. Theory, 65 (2019), 2166-2170. doi: 10.1109/TIT.2018.2880913.
[26]	C. Li and T. Helleseth, Quasi-perfect linear codes from planar and APN functions, Cryptogr. Commun., 8 (2016), 215-227. doi: 10.1007/s12095-015-0132-y.
[27]	J. H. van Lint, Introduction to Coding Theory, Third Edition, Graduate Texts in Mathematics, vol. 86. Springer-Verlag, Berlin, 1999.
[28]	Y. Liu, C. Ding and C. Tang, Shortened linear codes over finite fields, IEEE Trans. Inf. Theory, 67 (2021), 5119-5132. doi: 10.1109/TIT.2021.3087082.
[29]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, vol. 16. North-Holland, Amsterdam, 1977.
[30]	T. Maruta, On the minimum length of $q$-ary linear codes of dimension four, Geom. Dedicata, 54 (1995), 263-266.
[31]	E. Prange, Cyclic Error-Correcting Codes in Two Symbols, TN-57-013, Air Force Cambridge Research Center, 1957.
[32]	T. Wagner, A search technique for quasi-perfect codes, Inform. and Control, 9 (1966), 94-99. doi: 10.1016/S0019-9958(66)90128-8.
[33]	X. Wang, D. Zheng and C. Ding, Some punctured codes of several families of binary linear codes, IEEE Trans. Inf. Theory, 67 (2021), 5133-5148. doi: 10.1109/TIT.2021.3088146.
[34]	Y. Wu, Z. Heng, C. Li and C. Ding, More MDS codes of non-Reed-Solomon type, preprint, arXiv: 2401.03391.
[35]	T. Wu, L. Liu and L. Li, Several classes of optimal cyclic codes with three zeros, Appl. Algebra Engrg. Comm. Comput., 36 (2025), 743-767. doi: 10.1007/s00200-023-00636-0.
[36]	M. Xiong and N. Li, Optimal cyclic codes with generalized Niho-type zeros and weight distributions, IEEE Trans. Inf. Theory, 61 (2015), 4914-4922. doi: 10.1109/TIT.2015.2451657.
[37]	J. Yuan, C. Carlet and C. Ding, The weight distribution of a class of linear codes from perfect nonlinear functions, IEEE Trans. Inf. Theory, 52 (2006), 712-717. doi: 10.1109/TIT.2005.862125.