May  2011, 5(2): 149-156. doi: 10.3934/amc.2011.5.149

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

1. 

Department of Mathematics, KTH, S-100 44 Stockholm, Sweden

2. 

Sobolev Institute of Mathematics, Mechanics and Mathematics Department, Novosibirsk State University, Novosibirsk, Russian Federation

Received  March 2010 Revised  August 2010 Published  May 2011

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.
Citation: Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149
References:
[1]

S. W. Golomb and E. C. Posner, Rook domains, Latin squares, and error-distributing codes,, IEEE Trans. Inf. Theory, 10 (1964), 196.  doi: 10.1109/TIT.1964.1053680.  Google Scholar

[2]

O. Heden, On the classification of perfect binary $1$-error correcting codes,, preprint, (2002), 2002.   Google Scholar

[3]

D. S. Krotov, Combining construction of perfect binary codes,, Probl. Inf. Transm., 36 (2000), 349.   Google Scholar

[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.   Google Scholar

[5]

C. F. Laywine and G. L. Mullen, "Discrete Mathematics Using Latin Squares,'', Wiley, (1998).   Google Scholar

[6]

A. V. Los', Construction of perfect $q$-ary codes by switchings of simple components,, Probl. Inf. Transm., 42 (2006), 30.  doi: 10.1134/S0032946006010030.  Google Scholar

[7]

M. Mollard, A generalized parity function and its use in the construction of perfect codes,, SIAM J. Algebraic Discrete Methods, 7 (1986), 113.  doi: 10.1137/0607013.  Google Scholar

[8]

K. T. Phelps, A general product construction for error correcting codes,, SIAM J. Algebraic Discrete Methods, 5 (1984), 224.  doi: 10.1137/0605023.  Google Scholar

[9]

K. T. Phelps, A product construction for perfect codes over arbitrary alphabets,, IEEE Trans. Inf. Theory, 30 (1984), 769.  doi: 10.1109/TIT.1984.1056963.  Google Scholar

[10]

V. N. Potapov and D. S. Krotov, Asymptotics for the number of $n$-quasigroups of order $4$,, Sib. Math. J., 47 (2006), 720.  doi: 10.1007/s11202-006-0083-9.  Google Scholar

[11]

V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order (in Russian),, Diskretnaya Matematika, 23 (2011).   Google Scholar

show all references

References:
[1]

S. W. Golomb and E. C. Posner, Rook domains, Latin squares, and error-distributing codes,, IEEE Trans. Inf. Theory, 10 (1964), 196.  doi: 10.1109/TIT.1964.1053680.  Google Scholar

[2]

O. Heden, On the classification of perfect binary $1$-error correcting codes,, preprint, (2002), 2002.   Google Scholar

[3]

D. S. Krotov, Combining construction of perfect binary codes,, Probl. Inf. Transm., 36 (2000), 349.   Google Scholar

[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.   Google Scholar

[5]

C. F. Laywine and G. L. Mullen, "Discrete Mathematics Using Latin Squares,'', Wiley, (1998).   Google Scholar

[6]

A. V. Los', Construction of perfect $q$-ary codes by switchings of simple components,, Probl. Inf. Transm., 42 (2006), 30.  doi: 10.1134/S0032946006010030.  Google Scholar

[7]

M. Mollard, A generalized parity function and its use in the construction of perfect codes,, SIAM J. Algebraic Discrete Methods, 7 (1986), 113.  doi: 10.1137/0607013.  Google Scholar

[8]

K. T. Phelps, A general product construction for error correcting codes,, SIAM J. Algebraic Discrete Methods, 5 (1984), 224.  doi: 10.1137/0605023.  Google Scholar

[9]

K. T. Phelps, A product construction for perfect codes over arbitrary alphabets,, IEEE Trans. Inf. Theory, 30 (1984), 769.  doi: 10.1109/TIT.1984.1056963.  Google Scholar

[10]

V. N. Potapov and D. S. Krotov, Asymptotics for the number of $n$-quasigroups of order $4$,, Sib. Math. J., 47 (2006), 720.  doi: 10.1007/s11202-006-0083-9.  Google Scholar

[11]

V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order (in Russian),, Diskretnaya Matematika, 23 (2011).   Google Scholar

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[2]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269

[3]

Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (38)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]