Volume 23, No 3, 2016, P. 107-123

UDC 519.8
A. M. Romanov
On full-rank perfect codes over finite fields

Abstract:
We propose a construction of full-rank $q$-ary 1-perfect codes over finite fields. This is a generalization of the construction of full-rank binary 1-perfect codes by Etzion and Vardy (1994). The properties of the $i$-components of $q$-ary Hamming codes are investigated and the construction of full-rank $q$-ary 1-perfect codes is based on these properties. The switching construction of 1-perfect codes is generalized for the $q$-ary case. We propose a generalization of the notion of $i$-component of a 1-perfect code and introduce the concept of an ($i, \sigma$)-component of $q$-ary 1-perfect codes. We also present a generalization of the Lindström–Schönheim construction of $q$-ary 1-perfect codes and provide a lower bound for the number of pairwise distinct $q$-ary 1-perfect codes of length $n$.
Bibliogr. 16.

Keywords: Hamming code, nonlinear perfect code, full-rank code, $i$-component.

DOI: 10.17377/daio.2016.23.522

Alexander M. Romanov ¹
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: rom@math.nsc.ru

Received 29 December 2015
Revised 17 March 2016

References

[1] Yu. L. Vasil’ev, On nongroup close-packed codes, in A. A. Lyapunov, ed., Problemy kibernetiki (Problems of Cybernetics), Vol. 8, pp. 375–378, Fizmatgiz, Moscow, 1962.

[2] A. M. Romanov, On construction of nonlinear perfect binary codes by inversion of symbols, Diskretn. Anal. Issled. Oper., Ser. 1, 4, No. 1, 46–52, 1997.

[3] A. M. Romanov, On partitions of $q$-ary Hamming codes into disjoint components, Diskretn. Anal. Issled. Oper., Ser. 1, 11, No. 3, 80–87, 2004.

[4] A. M. Romanov, A survey of methods for constructing nonlinear perfect binary codes, Diskretn. Anal. Issled. Oper., Ser. 1, 13, No. 4, 60–88, 2006. Translated in J. Appl. Ind. Math., 2, No. 2, 252–269, 2008.

[5] A. M. Romanov, On admissible families of components of Hamming codes, Diskretn. Anal. Issled. Oper., 19, No. 2, 84–91, 2012. Translated in J. Appl. Ind. Math., 6, No. 3, 355–359, 2012.

[6] S. V. Avgustinovich and D. S. Krotov, Embedding in a perfect code, J. Comb. Des., 17, No. 5, 419–423, 2009.

[7] T. Etzion and A. Vardy, Perfect binary codes: Constructions, properties, and enumeration, IEEE Trans. Inf. Theory., 40, No. 3, 754–763, 1994.

[8] T. Etzion, Nonequivalent q-ary perfect codes, SIAM J. Discrete Math., 9, No. 3, 413–423, 1996.

[9] O. Heden and D. S. Krotov, On the structure of non-full-rank perfect $q$-ary codes, Adv. Math. Comb., 5, No. 2, 149–156, 2011.

[10] B. Lindström, On group and nongroup perfect codes in q symbols, Math. Scand., 25, 149–158, 1969.

[11] A. V. Los’, Construction of perfect $q$-ary codes, in Proc. 9th Int. Workshop Algebraic Comb. Coding Theory, Kranevo, Bulgaria, June 19–25, 2004, pp. 272–276, Inst. Math. Inform., Sofia, 2004.

[12] P. R. J. Östergård, O. Pottonen, and K. T. Phelps, The perfect binary one-error-correcting codes of length 15: Part II - Properties, IEEE Trans. Inform. Theory, 56, No. 6, 2571–2582, 2010.

[13] K. T. Phelps and M. Villanueva, Ranks of $q$-ary 1-perfect codes, Des. Codes Cryptogr., 27, No. 1вЂ-2, 139–144, 2002.

[14] K. T. Phelps, J. Rifà, andM. Villanueva, Kernels and $p$-kernels of $pr$-ary 1-perfect codes, Des. Codes Cryptogr., 37, No. 2, 243–261, 2005.

[15] A. M. Romanov, Hamiltonicity of minimum distance graphs of 1-perfect codes, Electron. J. Comb., 19, No. 1, P65, 1–6, 2012.

[16] J. Schönheim, On linear and nonlinear single-error-correcting $q$-nary perfect codes, Inform. Control, 12, 23–26, 1968.