|
This article is cited in 3 scientific papers (total in 3 papers)
Discrete mathematics and mathematical cybernetics
Systematic and nonsystematic perfect codes of infinite length over finite fields
S. A. Malyugin Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Abstract:
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.
Received July 19, 2019, published November 28, 2019
Citation:
S. A. Malyugin, “Systematic and nonsystematic perfect codes of infinite length over finite fields”, Sib. Èlektron. Mat. Izv., 16 (2019), 1732–1751
Linking options:
https://www.mathnet.ru/eng/semr1163 https://www.mathnet.ru/eng/semr/v16/p1732
|
Statistics & downloads: |
Abstract page: | 242 | Full-text PDF : | 111 | References: | 16 |
|