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.     

Enumerating and decoding perfect linear Lee codes

Using group theory approach, we determine all numbers q for which there exists a linear 1-error correcting perfect Lee code of block length n over Z _q , and then we enumerate those codes. At the same time this approach allows us to design a linear time decoding algorithm.      

Bounds in the Lee metric and optimal codes

In this paper we investigate known Singleton-like bounds in the Lee metric and characterize their extremal codes, which turn out to be very few. We then focus on Plotkin-like bounds in the Lee metric and present a new bound that extends and refines a previously known, and out-performs it in the case of non-free codes. We then compute the density of extremal codes with regard to the new bound. Finally we fill a gap in the characterization of Lee-equidistant codes.     

Class of generalized Goppa codes perfect in weighted Hamming metric

A weighted Hamming metric is considered. A class of binary linear codes consistent with the weighted Hamming metric is discussed. A class of binary generalized Goppa codes perfect in the weighted Hamming metric is offered.     

A necessary condition for the existence of perfect codes in Lie metric

A theorem of Lloyd is extended to the Lie metric case.     

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.     

A generalization of Lee codes

Motivated by a problem in computer architecture we introduce a notion of the perfect distance-dominating set (PDDS) in a graph. PDDSs constitute a generalization of perfect Lee codes, diameter perfect codes, as well as other codes and dominating sets. In this paper we initiate a systematic study of PDDSs. PDDSs related to the application will be constructed and the non-existence of some PDDSs will be shown. In addition, an extension of the long-standing Golomb–Welch conjecture, in terms of PDDS, will be stated. We note that all constructed PDDSs are lattice-like which is a very important feature from the practical point of view as in this case decoding algorithms tend to be much simpler.     

Weighted Hamming metric structures

It is known that the binary generalized Goppa codes are perfect codes for the weighted Hamming metrics. In this paper, we present the existence of a weighted Hamming metric that admits a binary Hamming code (resp. an extended binary Hamming code) to be perfect code. For a special weighted Hamming metric, we also give some structures of a 2-perfect code, show how to construct a 2-perfect linear code and obtain the weight distribution of a 2-perfect code from the partial information of the code.     

Nearly perfect codes in distance-regular graphs

The idea of a nearly perfect code in a vector space over a binary field is generalized to the class of distance-regular graphs. A necessary condition for the existence of a nearly perfect code in a distance-regular graph is obtained, and it is shown that this condition implies the analogous result in the classical binary case.     

Intersections of q-ary perfect codes

The intersections of q-ary perfect codes are under study. We prove that there exist two q-ary perfect codes C ₁ and C ₂ of length N = qn + 1 such that |C ₁ ? C ₂| = k · |P _i |/p for each k ∈ {0,..., p · K ? 2, p · K}, where q = p ^r , p is prime, r ≥ 1, $n = \tfrac{{q^{m - 1} - 1}}{{q - 1}}$ , m ≥ 2, |P _i | = p ^nr(q?2)+n , and K = p ^{n(2r?1)?r(m?1)}. We show also that there exist two q-ary perfect codes of length N which are intersected by p ^nr(q?3)+n codewords.     

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.     

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 non-existence of perfect and nearly perfect codes

The main result of the paper is the proof of the non-existence of a class of completely regular codes in certain distance-regular graphs. Corollaries of this result establish the non-existence of perfect and nearly perfect codes in the infinite families of distance-regular graphs J(2b + 1, b) and J(2b+2,b).     

New upper bounds on Lee codes

The paper considers exact values of and upper bounds on the maximal cardinality of a q-ary Lee code of length n with a minimum distance ?d. Special attention is paid to small parameters. Some new results are presented and tables with the presently known best upper bounds are given for q∈{5,6,7} and n?7.