On the structure of non-full-rank perfect $q$-ary codes

Olof Heden; Denis S. Krotov

doi:10.3934/amc.2011.5.149

Article Contents

2011, Volume 5, Issue 2: 149-156. Doi: 10.3934/amc.2011.5.149

This issue Previous Article Editorial Next Article A geometric proof of the upper bound on the size of partial spreads in $H(4n+1,$q²$)$

On the structure of non-full-rank perfect $q$-ary codes

Olof Heden^1, and
Denis S. Krotov^2,

1.
Department of Mathematics, KTH, S-100 44 Stockholm
2.
Sobolev Institute of Mathematics, Mechanics and Mathematics Department, Novosibirsk State University, Novosibirsk

Received: February 28, 2010

Revised: July 31, 2010

Published: April 2011

Abstract Related Papers Cited by

Abstract

The Krotov combining construction of perfect $1$-error-correcting binary codes from 2000 and a theorem of Heden saying that every non-full-rank perfect $1$-error-correcting binary code can be constructed by this combining construction is generalized to the $q$-ary case. Simply speaking, every non-full-rank perfect code $C$ is the union of a well-defined family of $\bar\mu$-components K_$\bar\mu$, where $\bar\mu$ belongs to an “outer” perfect code C^*, and these components are at distance three from each other. Components from distinct codes can thus freely be combined to obtain new perfect codes. The Phelps general product construction of perfect binary code from 1984 is generalized to obtain $\bar\mu$-components, and new lower bounds on the number of perfect $1$-error-correcting $q$-ary codes are presented.

Keywords:

Mathematics Subject Classification: Primary: 94B25.

Citation:

Related Papers

Cited by

References

[1]	S. W. Golomb and E. C. Posner, Rook domains, Latin squares, and error-distributing codes, IEEE Trans. Inf. Theory, 10 (1964), 196-208.doi: 10.1109/TIT.1964.1053680.
[2]	O. Heden, On the classification of perfect binary $1$-error correcting codes, preprint, TRITA-MAT-2002-01, KTH, Stockholm, 2002.
[3]	D. S. Krotov, Combining construction of perfect binary codes, Probl. Inf. Transm., 36 (2000), 349-353; Translated from Probl. Peredachi Inf., 36 (2000), 74-79.
[4]	D. S. Krotov, V. N. Potapov and P. V. Sokolova, On reconstructing reducible $n$-ary quasigroups and switching subquasigroups, Quasigroups Relat. Syst., 16 (2008), 55-67.
[5]	C. F. Laywine and G. L. Mullen, "Discrete Mathematics Using Latin Squares,'' Wiley, New York, 1998.
[6]	A. V. Los', Construction of perfect $q$-ary codes by switchings of simple components, Probl. Inf. Transm., 42 (2006), 30-37; Translated from Probl. Peredachi Inf., 42 (2006), 34-42.doi: 10.1134/S0032946006010030.
[7]	M. Mollard, A generalized parity function and its use in the construction of perfect codes, SIAM J. Algebraic Discrete Methods, 7 (1986), 113-115.doi: 10.1137/0607013.
[8]	K. T. Phelps, A general product construction for error correcting codes, SIAM J. Algebraic Discrete Methods, 5 (1984), 224-228.doi: 10.1137/0605023.
[9]	K. T. Phelps, A product construction for perfect codes over arbitrary alphabets, IEEE Trans. Inf. Theory, 30 (1984), 769-771.doi: 10.1109/TIT.1984.1056963.
[10]	V. N. Potapov and D. S. Krotov, Asymptotics for the number of $n$-quasigroups of order $4$, Sib. Math. J., 47 (2006), 720-731; Translated from Sib. Mat. Zh., 47 (2006), 873-887.doi: 10.1007/s11202-006-0083-9.
[11]	V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order (in Russian), Diskretnaya Matematika, 23 (2011), accepted; to be translated in Discrete Math. Appl., 21; arXiv:0912.5453