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

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

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

Abstract
Related Papers

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

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

[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 and 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]	Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021058
[19]	Maura B. Paterson, Douglas R. Stinson. Splitting authentication codes with perfect secrecy: New results, constructions and connections with algebraic manipulation detection codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021054
[20]	Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Olof Heden Denis S. Krotov
on Google Scholar
Olof Heden Denis S. Krotov

[Back to Top]