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.

[2]

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

[3]

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

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

[5]

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

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

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

[8]

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

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

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

[11]

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

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.

[2]

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

[3]

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

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

[5]

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

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

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

[8]

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

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

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

[11]

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

[1]

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

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

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

[4]

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

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

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

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

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018

[16]

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

[17]

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

[18]

P. Charters. Finding an asymptotically bad family of $q$-th power residue codes. Advances in Mathematics of Communications, 2009, 3 (1) : 53-58. doi: 10.3934/amc.2009.3.53

[19]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF($q$). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007

[20]

Alonso Sepúlveda, Guilherme Tizziotti. Weierstrass semigroup and codes over the curve $y^q + y = x^{q^r + 1}$. Advances in Mathematics of Communications, 2014, 8 (1) : 67-72. doi: 10.3934/amc.2014.8.67

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (0)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]