Perfect codes with big kernel dimensions

Avgustinovich S.V., Heden O., Solov'eva F.I.

Abstract:

Perfect codes of all admissible lengths $n>15$ with the rank $r<n$ and the kernel of dimension $k$ for each $k\in \{(n-1)/2,\ldots,U(n)\}$ are presented (here $U(n)$ is the dimension of maximal possible kernel of a full rank perfect code of length $n$). Full rank perfect codes of all admissible lengths $n>2^{10}-1$ with a kernel of dimension $k$ for each $k\in \{(n-1)/2,\ldots,U(n)\}$ are given. For length $31\leq n\leq 2^{10}-1$ the same result for each $k\in \{(n-1)/2,\ldots,U(n)-2\} $ is true.

A perfect binary code $C$ of length $n$ with code distance 3 (below a perfect code) is defined as a subset of the $n$-dimensional vector space $E^n$ over $GF(2)$ such that for a vector $y\in E^n$ there exists a unique codeword $x\in C$ with $d(x,y)\leq 1,$ where $d$ is the Hamming distance. Perfect binary codes with distance 3 exist iff the length of the codewords is equal to $n=2^m-1,m>1$. The rank $r=r(C)$ of a code $C$ is the dimension of the subspace $<C>$ spanned by $C.$ The kernel $Ker(C)$ of a code $C$ is the set of all its periods (all codewords $x\in C$ such that $x+C=C$). The dimension of the kernel is denoted by $k=k(C).$

First consider the short survey. Heden [2] constructed perfect codes of length 15 with kernels of dimension 1,2,3. Etzion and Vardy [3] found perfect codes of length $n\geq 15$ of all admissible ranks. Phelps and LeVan [4] established the existence of a nonlinear perfect code of length $n\geq 15$ with a kernel of dimension $k$ for each $k\in \{1,2,\ldots,n-m-2\}.$ Avgustinovich and Solov'eva [5] constructed full rank nonsystematic perfect codes of length $n>127$ with trivial automorphism group (that means with trivial kernel of size 2). The same result for systematic perfect codes of length $n>15$ was obtained by Malyugin [6]. Etzion and Vardy [7] proposed to describe all possible pairs of numbers $(r,k)$ which are attainable as the rank $r$ and kernel dimension $k$ of a perfect code of length $n.$ They proved [7] that for every $n\geq 2^m-1,m>3,$ the upper bound of the dimension of the kernel of length $n$ perfect codes is equal to $U(n)=n-m-\delta,$ where $\delta$ is the smallest integer, such that $2^{\delta}-\delta -1\geq m$ and showed that the bound is tight for each $n\geq 2^{10}-1.$ Phelps and Villanueva [8] established the upper and lower bound of pairs $(r,k)$ for a perfect code of length $n\geq 15$ and proved that all such pairs are attainable (with the exception of the upper bound of length 15th codes). They also constructed perfect codes of length $n$ for each $(r,k),$ where $k>n-2m, r<n.$ In [11] perfect codes of length $n>15$ for all possible pairs $(r,k),$ where $r<n$ are presented. In [10] the classification of perfect codes of ranks $n-m+1$ and $n-m+2$ is given. For $n=15$ full rank perfect codes with dimension kernel $1\leq k\leq 5$ are known, see [2,1,7]. For $r<15$ perfect codes of length 15 for all possible pairs $(r,k)$ are given in [9].


Perfect codes of length $n$ with kernel dimension $k\geq (n-1)/2$ and different ranks are investigated in the paper using well known iterative Vasil'ev construction [12]. Let us remind Vasil'ev construction [12]. Let $C^{\prime}$ be a perfect code of length $(n-1)/2=2^{m-1}-1, m\geq 2,$ and $\lambda$ be a function from $C^{\prime}$ to the set $\{0,1\}$. The set $ C = \{(u, u + v,\vert u\vert+\lambda (v)): u \in E^{(n-1)/2}, v \in C^{\prime}\} $ is the perfect code of length $n,$ where $\vert u\vert = u_1 + \cdots + u_{(n-1)/2}$ (mod 2) for $u = (u_1, \ldots,$ $u_{(n-1)/2}).$


Lemma. Assume there exists a perfect code $C^{\prime}$ of length $(n-1)/2$ with maximal kernel and the rank $r(C^{\prime})\leq n.$ Then there exist perfect codes of length $n$ with a kernel of dimension $k$ for each $k\in \{(n-1)/2,\ldots,U(n)\}$ and the ranks $r = (n-1)/2 + r(C^{\prime})$ and $r = (n+1)/2 + r(C^{\prime}).$


Taking into account the existence of perfect codes of length 15 with rank less than 15 and maximal kernel, a full rank perfect code of length $2^{10}-1$ with maximal kernel and full rank perfect code of length $15$ with kernel dimension 5 we have using the Lemma the following results respectively.


Theorem 1. There exist perfect codes of length $n>15$ with kernel dimension $k$ for each $k\in\{(n-1)/2,...,U(n)\}$ and the rank $r<n$.


Theorem 2. There exist full rank perfect codes of length $n>2^{10}-1$ with kernel dimension $k$ for each $k\in\{(n-1)/2,...,U(n)\}.$


Theorem 3. There exist full rank perfect codes of length $n,$ $31\leq n\leq 2^{10}-1,$ with kernel dimension $k$ for each $k\in\{(n-1)/2,...,U(n)-2\}.$


Thanks. We are grateful to Swedish Institute for supporting this research. The work of S.V. Avgustinovich was also supported by NWO-047-008-006. The work of F.I. Solov'eva was also supported by the Russian Foundation for Basic Research under the grant 00-01-00822.

Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Friday, 14-Sep-2001 10:27:45 NOVST