American Institute of Mathematical Sciences

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

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, 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.
Keywords: lower bound., $q$-ary codes, Perfect codes, components.
Mathematics Subject Classification: Primary: 94B2.
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-208. doi: 10.1109/TIT.1964.1053680.  Google Scholar

[2]

O. Heden, On the classification of perfect binary $1$-error correcting codes, preprint, TRITA-MAT-2002-01, KTH, Stockholm, 2002. Google Scholar

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

[5]

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

[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.  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-115. 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-228. 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-771. 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-731; Translated from Sib. Mat. Zh., 47 (2006), 873-887. 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), accepted; to be translated in Discrete Math. Appl., 21; arXiv:0912.5453 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-208. doi: 10.1109/TIT.1964.1053680.  Google Scholar

[2]

O. Heden, On the classification of perfect binary $1$-error correcting codes, preprint, TRITA-MAT-2002-01, KTH, Stockholm, 2002. Google Scholar

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

[5]

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

[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.  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-115. 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-228. 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-771. 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-731; Translated from Sib. Mat. Zh., 47 (2006), 873-887. 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), accepted; to be translated in Discrete Math. Appl., 21; arXiv:0912.5453 Google Scholar

[1]

Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165
[2]

Joaquim Borges, Josep Rifà, Victor A. Zinoviev. On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual. Advances in Mathematics of Communications, 2010, 4 (4) : 567-578. doi: 10.3934/amc.2010.4.567
[3]

Florent Foucaud, Tero Laihonen, Aline Parreau. An improved lower bound for $(1,\leq 2)$-identifying codes in the king grid. Advances in Mathematics of Communications, 2014, 8 (1) : 35-52. doi: 10.3934/amc.2014.8.35
[4]

Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[5]

Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223
[6]

Luciano Panek, Jerry Anderson Pinheiro, Marcelo Muniz Alves, Marcelo Firer. On perfect poset codes. Advances in Mathematics of Communications, 2020, 14 (3) : 477-489. doi: 10.3934/amc.2020061
[7]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[8]

Long Yu, Hongwei Liu. A class of $p$-ary cyclic codes and their weight enumerators. Advances in Mathematics of Communications, 2016, 10 (2) : 437-457. doi: 10.3934/amc.2016017
[9]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079
[10]

Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465
[11]

B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037
[12]

Lanqiang Li, Shixin Zhu, Li Liu. The weight distribution of a class of p-ary cyclic codes and their applications. Advances in Mathematics of Communications, 2019, 13 (1) : 137-156. doi: 10.3934/amc.2019008
[13]

Roland D. Barrolleta, Emilio Suárez-Canedo, Leo Storme, Peter Vandendriessche. On primitive constant dimension codes and a geometrical sunflower bound. Advances in Mathematics of Communications, 2017, 11 (4) : 757-765. doi: 10.3934/amc.2017055
[14]

Jesús Carrillo-Pacheco, Felipe Zaldivar. On codes over FFN$(1,q)$-projective varieties. Advances in Mathematics of Communications, 2016, 10 (2) : 209-220. doi: 10.3934/amc.2016001
[15]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[16]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295
[17]

Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425
[18]

J. De Beule, K. Metsch, L. Storme. Characterization results on weighted minihypers and on linear codes meeting the Griesmer bound. Advances in Mathematics of Communications, 2008, 2 (3) : 261-272. doi: 10.3934/amc.2008.2.261
[19]

Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175
[20]

Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences