On maximum distance separable and completely regular codes
DOI:
https://doi.org/10.55630/mem.2026.55.350-356Keywords:
maximum distance separable codes, completely regular codesAbstract
We investigate when a maximum distance separable (MDS) code over Fq is also completely regular (CR). For lengths n = q + 1 and n = q + 2 we provide a complete classification of the MDS codes that are CR or at least uniformly packed in the wide sense (UPWS). For the more restricted case n <= q with q <= 5 we obtain a full classification (up to equivalence) of all nontrivial MDS codes: there are none for q = 2; only the ternary Hamming code for q = 3; four nontrivial families for q = 4; and exactly six linear MDS codes for q = 5 (three of which are CR and one admits a self-dual version). Additionally, we close two gaps left open in a previous classification of self-dual CR codes with covering radius ρ <= 3: we precisely determine over which finite fields the MDS self-dual completely regular codes with parameters [2, 1, 2]_q and [4, 2, 3]_q exist.
References
S. BALL. On sets of vectors of a finite vector space in which every subset of basis size is a basis. J. Eur. Math. Soc., 14:733–748, 2012.
L. A. BASSALYGO, G. V. ZAITSEV, and V. A. ZINOVIEV. Uniformly packed codes. Problems Inform. Transmiss., 10(1):9–14, 1974.
L. A. BASSALYGO and V. A. ZINOVIEV. A note on uniformly packed codes. Problems Inform. Transmiss., 13(3):22–25, 1977.
M. C. BHANDARI and C. DURAIRAJAN. On the covering radius of simplex codes. Journal of Discrete Mathematical Sciences and Cryptography, 6:59–69, 2003.
J. BORGES, J. RIFÀ, and V. A. ZINOVIEV. On completely regular codes. Problems Inform. Transmiss., 55(1):1–45, 2019.
J. BORGES and V. A. ZINOVIEV. On self-dual completely regular codes with covering radius ρ <= 3. Finite Fields and their Applications, 105:102617, 2025.
P. DELSARTE. An Algebraic Approach to the Association Schemes in Coding Theory. Technical report 10, Philips Res. Rep. Suppl., 1973.
M. F. EZERMAN, M. GRASSL, and P. SOLÉ. The weights in MDS codes. IEEE Trans. Inform. Theory, IT-57:392–396, 2011.
J. M. GOETHALS and H. C. A. VAN TILBORG. Uniformly packed codes. Philips Res., 30:9–36, 1975.
J. H. GRIESMER. A bound for error-correcting codes. IBM J. Res. Develop., 4:532–542, 1960.
W. C. HUFFMAN and V. PLESS. Fundamentals of error-correcting codes. Cambridge Univ. Press, New York, 2003.
RUDOLF LIDL and HARALD NIEDERREITER. Finite fields, number 20. Cambridge university press, 1997.
B. SEGRE. Curve razionali normali ek-archi negli spazi finiti. Ann. Mat. Pur. Appl., 39(1):357–379, 1955.
N. V. SEMAKOV, V. A. ZINOVIEV, and G. V. ZAITZEV. Uniformly packed codes. Problems Inform. Transmiss., 7:38–50, 1971.
M. SHI and P. SOLÉ, editors. Completely Regular Codes in Distance Regular Graphs. CRC Press, Boca Raton FL, 2025.
R. C. SINGLETON. Maximum distance q-ary codes. IEEE Trans. Inform. Theory, IT-10:116–118, 1964.
P. SOLÉ. Completely regular codes and completely transitive codes. Discrete Maths., 81:193–201, 1990.
G. SOLOMON and J. J. STIFFLER. Algebraically punctured cyclic codes. Inform. and Control, 8:170–179, 1965.
A. TIETÄVÄINEN. On the nonexistence of perfect codes over finite fields. SIAM J. Appl. Math., 24(1):88–96, 1973.
V. A. ZINOVIEV and V. K. LEONTIEV. On non-existence of perfect codes over Galois fields. Probl. Upravlen. Teor. Inform., 2(2):123–132, 1973. English translation in Probl. Control Inf. Theory, vol. 2, no. 2, pp. 16–24, 1973.
