Geodesic
Systematic and nonsystematic perfect codes of infinite length over finite fields
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1732-1751

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $F_q$ be a finite field of $q$ elements ($q=p^k$, $p$ is a prime number). An infinite-dimensional $q$-ary vector space $F_q^{{\mathbb N}_0}$ consists of all sequences $u = (u_1,u_2,\ldots)$, where $u_i \in F_q$ and all $u_i$ are $0$ except some finite set of indices $i$ $\in$ $\mathbb N$. A subset $C$ $\subset$ $F_q^{{\mathbb N}_0}$ is called a perfect $q$-ary code with distance $3$ if all balls of radius $1$ (in the Hamming metric) with centers in $C$ are pairwise disjoint and their union covers the space. Define the infinite perfect $q$-ary Hamming code $H_q^\infty$ as the infinite union of the sequence of finite $q$-ary codes ${\widetilde H}_q^n$ where for all $n = (q^m-1)/(q-1)$, ${\widetilde H}_q^n$ is a subcode of ${\widetilde H}_q^{qn+1}$. We prove that all linear perfect $q$-ary codes of infinite length are affine equivalent. A perfect $q$-ary code $C \subset F_q^{{\mathbb N}_0}$ is called systematic if $\mathbb N$ could be split into two subsets $N_1$, $N_2$ such that $C$ is a graphic of some function $f:F_q^{N_{1,0}}\to F_q^{N_{2,0}}$. Otherwise, $C$ is called nonsystematic. Further general properties of systematic codes are proved. We also prove a version of Shapiro–Slotnik theorem for codes of infinite length. Then, we construct nonsystematic codes of infinite length using the switchings of $s < q - 1$ disjoint components. We say that a perfect code $C$ has the complete system of triples if for any three indices $i_1$, $i_2$, $i_3$ the set $C-C$ contains the vector with support $\{i_1,i_2,i_3\}$. We construct perfect codes of infinite length having the complete system of triples (in particular, such codes are nonsystematic). These codes can be obtained from the Hamming code $H_q^\infty$ by switching some family of disjoint components ${\mathcal B} = \{R_1^{u_1},R_2^{u_2},\ldots\}$. Unlike the codes of finite length, the family $\mathcal B$ must obey the rigid condition of sparsity. It is shown particularly that if the family of components $\mathcal B$ does not satisfy the condition of sparsity then it can generate a perfect code having non-complete system of triples.
Keywords: perfect $q$-ary code, code of infinite length, component, systematic code, nonsystematic code, complete system of triples, condition of sparsity. 
S. A. Malyugin. Systematic and nonsystematic perfect codes of infinite length over finite fields. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1732-1751. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a78/
@article{SEMR_2019_16_a78,
     author = {S. A. Malyugin},
     title = {Systematic and nonsystematic perfect codes of infinite length over finite fields},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1732--1751},
     year = {2019},
     volume = {16},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a78/}
}
TY  - JOUR
AU  - S. A. Malyugin
TI  - Systematic and nonsystematic perfect codes of infinite length over finite fields
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 1732
EP  - 1751
VL  - 16
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a78/
LA  - ru
ID  - SEMR_2019_16_a78
ER  - 
%0 Journal Article
%A S. A. Malyugin
%T Systematic and nonsystematic perfect codes of infinite length over finite fields
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 1732-1751
%V 16
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a78/
%G ru
%F SEMR_2019_16_a78

[1] Avgustinovich S. V., Solov'eva F. I., “On the nonsystematic perfect binary codes”, Problems Inform. Transmission, 32:3 (1996), 258–261 | MR | Zbl

[2] Krotov D. S., Potapov V. N., “Propelinear 1-perfect codes from quadratic functions”, IEEE Trans. Inform Theory, 60:4 (2014), 2065–2068 | DOI | MR | Zbl

[3] Krotov D. S., Sotnikova E. V., “Embedding in q-ary 1-Perfect Codes and Partitions”, Discrete Mathematics, 338:11 (2015), 1856–1859 | DOI | MR | Zbl

[4] Los' A. V., “Construction of perfect q-ary codes by sequential switchings of $\widetilde\alpha$-components”, Problems Inform. Transmission, 40:1 (2004), 37–43 | DOI | MR | Zbl

[5] Malyugin S. A., “On enumeration of the perfect binary codes of length 15”, Discrete Applied Mathematics, 135:1–3 (2004), 161–181 | DOI | MR

[6] Malyugin S. A., “On nonsystematic perfect codes over finite fields”, J. Appl. Indust. Math., 4:2 (2010), 218–230 | DOI | MR

[7] Malyugin S. A., “Perfect binary codes of infinite length”, J. Appl. Indust. Math., 8:4 (2017), 552–556 | DOI | MR

[8] Malyugin S. A., “Perfect binary codes of infinite length with complete system of triples”, Sib. Elektron. Mat. Izv., 14 (2017), 877–888 (in Russian) | MR | Zbl

[9] Phelps K. T., Levan M. J., “Nonsystematic perfect codes”, SIAM J. Discrete Math., 12:1 (1999), 27–34 | DOI | MR | Zbl

[10] Potapov V. N., “Infinite-Dimensional Quasigroups of finite orders”, Math. Notes, 93:3 (2013), 479–486 | DOI | MR | Zbl

[11] Romanov A. M., “On nonsystematic perfect codes of length 15”, Diskretn. Anal. Issled. Oper. Ser 1, 4:4 (1997), 75–78 (in Russian) | MR | Zbl

[12] Romanov A. M., “On partitions of q-ary Hamming codes into disjoint components”, Diskretn. Anal. Issled. Oper. Ser 1, 11:3 (2004), 80–87 (in Russian) | MR | Zbl

[13] Shapiro O. S., Slotnik D. L., “On the mathematical theory of error correcting codes”, IBM J. Res. and Devel., 3:1 (1959), 25–34 | DOI | MR | Zbl

[14] Solov'eva F. I., Introduction to coding theory, Novosibirsk State University, Novosibirsk, 2006 (in Russian)

[15] Shönheim J., “On linear and nonlinear single-error-correcting $q$-ary perfect codes”, Inform. and Control, 12:1 (1968), 23–26 | DOI | MR

[16] Vasil'ev Yu. L., “On Nongroup Close-Packed Codes”, Problems of Cybernetics, 8 (1962), 337–339 | MR | Zbl

[17] Vasil'eva A. Yu., “Local spectra of perfect binary codes”, Diskretn. Anal. Issled. Oper. Ser 1, 6:1 (1999), 3–11 (in Russian) | MR | Zbl