Systematic and nonsystematic perfect codes of infinite length over finite fields

S. A. Malyugin

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1732-1751.

Résumé

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.

Détail

Keywords: perfect $q$-ary code, code of infinite length, component, systematic code, nonsystematic code, complete system of triples, condition of sparsity.

Bibliographie

[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