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.      

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 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 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.     

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 non-antipodal binary completely regular codes

Binary non-antipodal completely regular codes are characterized. Using a result on nonexistence of nontrivial binary perfect codes, it is concluded that there are no unknown nontrivial non-antipodal completely regular binary codes with minimum distance d?3. The only such codes are halves and punctured halves of known binary perfect codes. Thus, new such codes with covering radius ρ=6 and 7 are obtained. In particular, a half of the binary Golay [23,12,7]-code is a new binary completely regular code with minimum distance d=8 and covering radius ρ=7. The punctured half of the Golay code is a new completely regular code with minimum distance d=7 and covering radius ρ=6. The new code with d=8 disproves the known conjecture of Neumaier, that the extended binary Golay [24,12,8]-code is the only binary completely regular code with d?8. Halves of binary perfect codes with Hamming parameters also provide an infinite family of binary completely regular codes with d=4 and ρ=3. Puncturing of these codes also provide an infinite family of binary completely regular codes with d=3 and ρ=2. Both these families of codes are well known, since they are uniformly packed in the narrow sense, or extended such codes. Some of these completely regular codes are new completely transitive codes.     

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

     

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).     

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.     

A remark on full rank perfect codes

Any full rank perfect 1-error correcting binary code of length n=2^k-1 and with a kernel of dimension n-log(n+1)-m, where m is sufficiently large, may be used to construct a full rank perfect 1-error correcting binary code of length 2^m-1 and with a kernel of dimension n-log(n+1)-k. Especially we may construct full rank perfect 1-error correcting binary codes of length n=2^m-1 and with a kernel of dimension n-log(n+1)-4 for m=6,7,…,10.This result extends known results on the possibilities for the size of a kernel of a full rank perfect code.     

On the Hamming distances of repeated-root constacyclic codes of length 4ps

Let $p$ be an odd prime, $s$, $m$ be positive integers, $\gamma ,\lambda$ be nonzero elements of the finite field ${\mathbb{F}}_{p^m}$ such that ${\gamma }^{p^s}=\lambda$. In this paper, we show that, for any positive integer $\eta$, the Hamming distances of all repeated-root $\lambda$-constacyclic codes of length $\eta p^s$ can be determined by those of certain simple-root $\gamma$-constacyclic codes of length $\eta$. Using this result, Hamming distances of all constacyclic codes of length $4p^s$ are obtained. As an application, we identify all MDS $\lambda$-constacyclic codes of length $4p^s$.     

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 symbol-pair distances of repeated-root constacyclic codes of length 2ps

Let $p$ be an odd prime, and $\lambda$ be a nonzero element of the finite field ${\mathbb{F}}_{p^m}$. The $\lambda$-constacyclic codes of length $2p^s$ over ${\mathbb{F}}_{p^m}$ are classified as the ideals of quotient ring $\frac{{\mathbb{F}}_{p^m}\left[x\right]}{〈x^{2p^s}?\lambda 〉}$ in terms of their generator polynomials. Based on these generator polynomials, the symbol-pair distances of all such $\lambda$-constacyclic codes of length $2p^s$ are obtained in this paper. As an application, all MDS symbol-pair constacyclic codes of length $2p^s$ over ${\mathbb{F}}_{p^m}$ are established, which produce many new MDS symbol-pair codes with good parameters.     

Maximal partial packings of $${Z_2^n}$$ with perfect codes

A maximal partial Hamming packing of is a family of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in . The number of translates of Hamming codes in is the packing number, and a partial Hamming packing is strictly partial if the family does not constitute a partition of . A simple and useful condition describing when two translates of Hamming codes are disjoint or not disjoint is proved. This condition depends on the dual codes of the corresponding Hamming codes. Partly, by using this condition, it is shown that the packing number p, for any maximal strictly partial Hamming packing of , n = 2 ^m −1, satisfies . It is also proved that for any n equal to 2 ^m −1, , there exist maximal strictly partial Hamming packings of with packing numbers n−10,n−9,n−8,...,n−1. This implies that the upper bound is tight for any n = 2 ^m −1, . All packing numbers for maximal strictly partial Hamming packings of , n = 7 and 15, are found by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5,6,7,...,13 and 14.      

Some combinatorial constructions for optimal perfect deletion-correcting codes

There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(k − t, k, v)-codes and T(k − t, k, v)-codes respectively. The cardinality of a T(k − t, k, v)-code is determined by its parameters, while T*(k − t, k, v)-codes do not necessarily have a fixed size. Let N(k − t, k, v) denote the maximum number of codewords in any T*(k − t, k, v)-code. A T*(k − t, k, v)-code with N(k − t, k, v) codewords is said to be optimal. In this paper, some combinatorial constructions for optimal T*(2, k, v)-codes are developed. Using these constructions, we are able to determine the values of N(2, 4, v) for all positive integers v. The values of N(2, 5, v) are also determined for almost all positive integers v, except for v = 13, 15, 19, 27 and 34.