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]

IEEE Trans. Inf. Theory, 10 (1964), 196-208. doi: 10.1109/TIT.1964.1053680.  Google Scholar

[2]

preprint, TRITA-MAT-2002-01, KTH, Stockholm, 2002. Google Scholar

[3]

Probl. Inf. Transm., 36 (2000), 349-353; Translated from Probl. Peredachi Inf., 36 (2000), 74-79.  Google Scholar

[4]

Quasigroups Relat. Syst., 16 (2008), 55-67.  Google Scholar

[5]

Wiley, New York, 1998.  Google Scholar

[6]

Probl. Inf. Transm., 42 (2006), 30-37; Translated from Probl. Peredachi Inf., 42 (2006), 34-42. doi: 10.1134/S0032946006010030.  Google Scholar

[7]

SIAM J. Algebraic Discrete Methods, 7 (1986), 113-115. doi: 10.1137/0607013.  Google Scholar

[8]

SIAM J. Algebraic Discrete Methods, 5 (1984), 224-228. doi: 10.1137/0605023.  Google Scholar

[9]

IEEE Trans. Inf. Theory, 30 (1984), 769-771. doi: 10.1109/TIT.1984.1056963.  Google Scholar

[10]

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]

Diskretnaya Matematika, 23 (2011), accepted; to be translated in Discrete Math. Appl., 21; arXiv:0912.5453 Google Scholar

show all references

References:
[1]

IEEE Trans. Inf. Theory, 10 (1964), 196-208. doi: 10.1109/TIT.1964.1053680.  Google Scholar

[2]

preprint, TRITA-MAT-2002-01, KTH, Stockholm, 2002. Google Scholar

[3]

Probl. Inf. Transm., 36 (2000), 349-353; Translated from Probl. Peredachi Inf., 36 (2000), 74-79.  Google Scholar

[4]

Quasigroups Relat. Syst., 16 (2008), 55-67.  Google Scholar

[5]

Wiley, New York, 1998.  Google Scholar

[6]

Probl. Inf. Transm., 42 (2006), 30-37; Translated from Probl. Peredachi Inf., 42 (2006), 34-42. doi: 10.1134/S0032946006010030.  Google Scholar

[7]

SIAM J. Algebraic Discrete Methods, 7 (1986), 113-115. doi: 10.1137/0607013.  Google Scholar

[8]

SIAM J. Algebraic Discrete Methods, 5 (1984), 224-228. doi: 10.1137/0605023.  Google Scholar

[9]

IEEE Trans. Inf. Theory, 30 (1984), 769-771. doi: 10.1109/TIT.1984.1056963.  Google Scholar

[10]

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]

Diskretnaya Matematika, 23 (2011), accepted; to be translated in Discrete Math. Appl., 21; arXiv:0912.5453 Google Scholar

[1]

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

[2]

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

[3]

Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072

[4]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

[5]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007

[6]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[7]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[8]

Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003

[9]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002

[10]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[11]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135

[12]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077

[13]

Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078

[14]

Gioconda Moscariello, Antonia Passarelli di Napoli, Carlo Sbordone. Planar ACL-homeomorphisms : Critical points of their components. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1391-1397. doi: 10.3934/cpaa.2010.9.1391

[15]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075

[16]

Christian Meyer, Stephan Walther. Optimal control of perfect plasticity part I: Stress tracking. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021022

[17]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161

[18]

János Kollár. Relative mmp without $ \mathbb{Q} $-factoriality. Electronic Research Archive, , () : -. doi: 10.3934/era.2021033

[19]

Mengyao Chen, Qi Li, Shuangjie Peng. Bound states for fractional Schrödinger-Poisson system with critical exponent. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021038

[20]

Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]