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.