The non-existence of some perfect codes over non-prime power alphabets

Let denote the number of times the prime number p appears in the prime factorization of the integer q. The following result is proved: If there is a perfect 1-error correcting code of length n over an alphabet with q symbols then, for every prime number .This condition is stronger than both the packing condition and the necessary condition given by the Lloyd theorem, as it for example excludes the existence of a perfect code with the parameters (n,q,e)=(19,6,1).     

On perfect binary codes

Some results on perfect codes obtained during the last 6 years are discussed. The main methods to construct perfect codes such as the method of -components and the concatenation approach and their implementations to solve some important problems are analyzed. The solution of the ranks and kernels problem, the lower and upper bounds of the automorphism group order of a perfect code, spectral properties, diameter perfect codes, isometries of perfect codes and codes close to them by close-packed properties are considered.     

On perfect Lee codes

In this paper we survey recent results on the Golomb-Welch conjecture and its generalizations and variations. We also show that there are no perfect 2-error correcting Lee codes of block length 5 and 6 over Z. This provides additional support for the Golomb Welch conjecture as it settles the two smallest cases open so far.     

On the embedding of constant-weight codes into perfect codes

We show that each q-ary constant-weight code of weight 3, minimum distance 4, and length m embeds in a q-ary 1-perfect code of length n = (q ^m ? 1)/(q ? 1).     

On kernels of perfect codes

It is shown that there exists a perfect one-error-correcting binary code with a kernel which is not contained in any Hamming code.     

On the non-existence of linear codes attaining the Griesmer bound

A lower bound on the size of a set K in PG(3, q) satisfying for any plane of PG(3, q), q4 is given. It induces the non-existence of linear [n,4,n + 1 – q ²]-codes over GF(q) attaining the Griesmer bound for .     

On extremely transitive extended perfect codes

We prove that, for every n = 2 ^k with k ≥ 4, there exist nonequivalent extremely transitive extended perfect codes. A transitive extended perfect code we call extremely transitive if the perfect code obtained from this code by puncturing any coordinate position is not transitive. The classification is given for all extended perfect codes of length 16.     

On diameter perfect constant-weight ternary codes

From cosets of binary Hamming codes we construct diameter perfect constant-weight ternary codes with weight n-1 (where n is the code length) and distances 3 and 5. The class of distance 5 codes has parameters unknown before.     

On nonsystematic perfect codes over finite fields

The nonsystematic perfect q-ary codes over finite field F _q of length n = (q ^m − 1)/(q − 1) are constructed in the case when m ≥ 4 and q ≥ 2 and also when m = 3 and q is not prime. For q ≠ 3, 5, these codes can be constructed by switching seven disjoint components of the Hamming code H _q ⁿ ; and, for q = 3, 5, eight disjoint components.     

On perfect deletion‐correcting codes

In this article, we present constructions for perfect deletion‐correcting codes. The first construction uses perfect deletion‐correcting codes without repetition of letters to construct other perfect deletion‐correcting codes. This is a generalization of the construction shown in 1 . In the third section, we investigate several constructions of perfect deletion‐correcting codes using designs. In the last section, we investigate perfect deletion‐correcting codes containing few codewords. © 2003 Wiley Periodicals, Inc.     

On full-rank perfect codes over finite fields

We propose a construction of full-rank q-ary 1-perfect codes. This is a generalization of the construction of full-rank binary 1-perfect codes by Etzion and Vardy (1994). The properties of the i-components of q-ary Hamming codes are investigated, and the construction of full-rank q-ary 1-perfect codes is based on these properties. The switching construction of 1-perfect codes is generalized to the q-ary case. We propose a generalization of the notion of an i-component of a 1-perfect code and introduce the concept of an (i, σ)-component of a q-ary 1-perfect code. We also present a generalization of the Lindström–Schönheim construction of q-ary 1-perfect codes and provide a lower bound for the number of pairwise distinct q-ary 1-perfect codes of length n.     

On rank and kernel of some mixed perfect codes

Mixed perfect 1-error correcting codes and the associated dual codes over the group Z(n,l),

     

On the non-existence of certain M.D.S. codes and projective planes

Mathematische Zeitschrift -     

On the construction of perfect deletion-correcting codes using design theory

We consider a way to construct perfect codes capable of correcting 2 or more deletions using design-theory. As a starting point we use an (ordered) block design to construct a perfect deletion correcting code. Using this code we are able to construct more perfect deletion correcting codes over smaller or larger alphabets by removing or adding symbols in a smart way.In this way we are able to find all perfect 2-deletion correcting codes of length 4, and all perfect 3-deletion correcting codes of length 5 with different coordinates. The perfect 3-deletion correcting codes of length 5 with repeated symbols can be constructed for almost all possible alphabet sizesv, except forv=13, 14, 15, and 16, and forv7, 8 (mod 10),v17. For these values ofv we are neither able to prove the existence, nor the non-existence of perfect 3-deletion correcting codes of length 5 over an alphabet of sizev.     

On the classification of perfect codes: side class structures

The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) C describes the linear relations between the coset representatives of the kernel of C. Two perfect codes C and C′ are linearly equivalent if there exists a non-singular matrix A such that AC = C′ where C and C′ are matrices with the code words of C and C′ as columns. Hessler proved that the perfect codes C and C′ are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa; any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes.     

On weight distributions of perfect colorings and completely regular codes

A vertex coloring of a graph is called “perfect” if for any two colors a and b, the number of the color-b neighbors of a color-a vertex x does not depend on the choice of x, that is, depends only on a and b (the corresponding partition of the vertex set is known as “equitable”). A set of vertices is called “completely regular” if the coloring according to the distance from this set is perfect. By the “weight distribution” of some coloring with respect to some set we mean the information about the number of vertices of every color at every distance from the set. We study the weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular, with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions. Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very simple formula for the weight enumerator of an arbitrary perfect coloring.     

Cyclotomic graphs and perfect codes

We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of $\mathbb{Z}[{\zeta }_m]/A$, with connection sets $\{\pm ({\zeta }_m^i+A):0\le i\le m?1\}$ and $\{\pm ({\zeta }_m^i+A):0\le i\le ?(m)?1\}$, respectively, where ${\zeta }_m$ ($m\ge 2$) is an mth primitive root of unity, A a nonzero ideal of $\mathbb{Z}[{\zeta }_m]$, and ? Euler's totient function. We call them the mth cyclotomic graph and the second kind mth cyclotomic graph, and denote them by $G_m(A)$ and $G_m^{?}(A)$, respectively. We give a necessary and sufficient condition for $D/A$ to be a perfect t-code in $G_m^{?}(A)$ and a necessary condition for $D/A$ to be such a code in $G_m(A)$, where $t\ge 1$ is an integer and D an ideal of $\mathbb{Z}[{\zeta }_m]$ containing A. In the case when $m=3,4$, $G_m((\alpha ))$ is known as an Eisenstein–Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for $(\beta )/(\alpha )$ to be a perfect t-code in $G_m((\alpha ))$, where $0\ne \alpha ,\beta \in \mathbb{Z}[{\zeta }_m]$ with β dividing α. In the literature such conditions are known to be sufficient when $m=4$ and $m=3$ under an additional condition. We give a classification of all first kind Frobenius circulants of valency 2p and prove that they are all pth cyclotomic graphs, where p is an odd prime. Such graphs belong to a large family of Cayley graphs that are efficient for routing and gossiping.     

On the classification of perfect codes: Extended side class structures

The two 1-error correcting perfect binary codes, C and C^′ are said to be equivalent if there exists a permutation π of the set of the n coordinate positions and a word such that . Hessler defined C and C^′ to be linearly equivalent if there exists a non-singular linear map φ such that C^′=φ(C). Two perfect codes C and C^′ of length n will be defined to be extended equivalent if there exists a non-singular linear map φ and a word such that