Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

Codes with the Same Weight Distributions as the Goethals Codes and the Delsarte-Goethals Codes

The Goethals code is a binary nonlinear code of length 2^m+1 which has codewords and minimum Hamming distance 8 for any odd . Recently, Hammons et. al. showed that codes with the same weight distribution can be obtained via the Gray map from a linear code over Z ₄of length 2^m and Lee distance 8. The Gray map of the dual of the corresponding Z ₄ code is a Delsarte-Goethals code. We construct codes over Z ₄ such that their Gray maps lead to codes with the same weight distribution as the Goethals codes and the Delsarte-Goethals codes.     

Classifying Subspaces of Hamming Spaces

A linear code in F ⁿ _q with dimension k and minimum distance at least d is called an [n, k, d] _q code. We here consider the problem of classifying all [n, k, d] _q codes given n, k, d, and q. In other words, given the Hamming space F ⁿ _q and a dimension k, we classify all k-dimensional subspaces of the Hamming space with minimum distance at least d. Our classification is an iterative procedure where equivalent codes are identified by mapping the code equivalence problem into the graph isomorphism problem, which is solved using the program nauty. For d = 3, the classification is explicitly carried out for binary codes of length n 14, ternary codes of length n 11, and quaternary codes of length n 10.     

An Enumeration of Binary Self-Dual Codes of Length 32

A binary self-dual code of length 2k is a (2k, k) binary linear code C with the property that every pair of codewords in C are orthogonal. Two self-dual codes, C ₁ and C ₂, are equivalent if and only if there is a permutation of the coordinates of C ₁ that takes C ₁ into C ₂. The automorphism group of a binary code C is the set of all permutations of the coordinates of C that takes C into itself.The main topic of this paper is the enumeration of inequivalent binary self-dual codes. We have developed algorithms that will take lists of inequivalent small codes and produce lists of larger codes where each inequivalent code occurs only a few times. We have defined a canonical form for codes that allowed us to eliminate the overenumeration. So we have lists of inequivalent binary self-dual codes of length up to 32. The enumeration of the length 32 codes is new. Our algorithm also finds the size of the automorphism group so that we can compute the number of distinct binary self-dual codes for a specific length. This number can also be found by counting and matches our total.     

On self-orthogonal group ring codes

We obtain structural results about group ring codes over F[G], where F is a finite field of characteristic p > 0 and the Sylow p-subgroup of the Abelian group G is cyclic. As a special case, we characterize cyclic codes over finite fields in the case the length of the code is divisible by the characteristic of the field. By the same approach we study cyclic codes of length m over the ring R = F _q [u], u ^r  = 0 with r  > 0, gcd(m, q) = 1. Finally, we give a construction of quasi-cyclic codes over finite fields.      

Construction of MDS self-dual codes over Galois rings

The purpose of this paper is to construct nontrivial MDS self-dual codes over Galois rings. We consider a building-up construction of self-dual codes over Galois rings as a GF(q)-analogue of (Kim and Lee, J Combin Theory ser A, 105:79–95). We give a necessary and sufficient condition on which the building-up construction holds. We construct MDS self-dual codes of lengths up to 8 over GR(3²,2), GR(3³,2) and GR(3⁴,2), and near-MDS self-dual codes of length 10 over these rings. In a similar manner, over GR(5²,2), GR(5³,2) and GR(7²,2), we construct MDS self-dual codes of lengths up to 10 and near-MDS self-dual codes of length 12. Furthermore, over GR(11²,2) we have MDS self-dual codes of lengths up to 12.      

Skew codes of prescribed distance or rank

In this paper we generalize the notion of cyclic code and construct codes as ideals in finite quotients of non-commutative polynomial rings, so called skew polynomial rings of automorphism type. We propose a method to construct block codes of prescribed rank and a method to construct block codes of prescribed distance. Since there is no unique factorization in skew polynomial rings, there are much more ideals and therefore much more codes than in the commutative case. In particular we obtain a [40, 23, 10]₄ code by imposing a distance and a [42,14,21]₈ code by imposing a rank, which both improve by one the minimum distance of the previously best known linear codes of equal length and dimension over those fields. There is a strong connection with linear difference operators and with linearized polynomials (or q-polynomials) reviewed in the first section.      

On Perfect Ternary Constant Weight Codes

We consider the space of ternary words of length n and fixed weight w with the usual Hamming distance. A sequence of perfect single error correcting codes in this space is constructed. We prove the nonexistence of such codes with other parameters than those of the sequence.     

Maximum distance separable poset codes

We derive the Singleton bound for poset codes and define the MDS poset codes as linear codes which attain the Singleton bound. In this paper, we study the basic properties of MDS poset codes. First, we introduce the concept of I-perfect codes and describe the MDS poset codes in terms of I-perfect codes. Next, we study the weight distribution of an MDS poset code and show that the weight distribution of an MDS poset code is completely determined. Finally, we prove the duality theorem which states that a linear code C is an MDS -code if and only if is an MDS -code, where is the dual code of C and is the dual poset of      

On maximal Spherical codes II

We consider spherical codes attaining the Levenshtein upper bounds on the cardinality of codes with prescribed maximal inner product. We prove that the even Levenshtein bounds can be attained only by codes which are tight spherical designs. For every fixed n ≥ 5, there exist only a finite number of codes attaining the odd bounds. We derive different expressions for the distance distribution of a maximal code. As a by-product, we obtain a result about its inner products. We describe the parameters of those codes meeting the third Levenshtein bound, which have a regular simplex as a derived code. Finally, we discuss a connection between the maximal codes attaining the third bound and strongly regular graphs. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 316–326, 1999     

On the reconstruction of linear codes

For a linear code over GF(q) we consider two kinds of “subcodes” called residuals and punctures. When does the collection of residuals or punctures determine the isomorphism class of the code? We call such a code residually or puncture reconstructible. We investigate these notions of reconstruction and show that, for instance, selfdual binary codes are puncture and residually reconstructible. A result akin to the edge reconstruction of graphs with sufficiently many edges shows that a code whose dimension is small in relation to its length is puncture reconstructible. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 285–291, 1998     

Artin–Schreier curves and weights of two-dimensional cyclic codes

Let be the finite field with q elements of characteristic p, be the extension of degree m>1 and f(x) be a polynomial over . The maximum number of affine -rational points that a curve of the form y^q−y=f(x) can have is q^m+1. We determine a necessary and sufficient condition for such a curve to achieve this maximum number. Then we study the weights of two-dimensional (2-D) cyclic codes. For this, we give a trace representation of the codes starting with the zeros of the dual 2-D cyclic code. This leads to a relation between the weights of codewords and a family of Artin–Schreier curves. We give a lower bound on the minimum distance for a large class of 2-D cyclic codes. Then we look at some special classes that are not covered by our main result and obtain similar minimum distance bounds.     

New Constructions for IPP Codes

Identifiable parent property (IPP) codes are introduced to provide protection against illegal producing of copyrighted digital material. In this paper we consider explicit construction methods for IPP codes by means of recursion techniques. The first method directly constructs IPP codes, whereas the second constructs perfect hash families that are then used to derive IPP codes. In fact, the first construction provides an infinite class of IPP codes having the best known asymptotic behavior. We also prove that this class has a traitor tracing algorithm with a runtime of O(M) in general, where M is the number of codewords.     

Projective Plane and Planar Quantum Codes

Cellulations of the projective plane RP ^2 define single qubit topological quantum error correcting codes since there is a unique essential cycle in H ₁ (RP ² ;Z ₂ ) . We construct three of the smallest such codes, show they are inequivalent, and identify one of them as Shor's original 9 qubit repetition code. We observe that Shor's code can be constructed in a planar domain and generalize to planar constructions of higher-genus codes for multiple qubits. June 21, 2000. Final version recieved: April 27, 2001.     

Antichain Codes

We show that almost all codes satisfy an antichain condition. This states that the minimum length of a two dimensional subcode of a code C increases if the subcode is constrained to contain a minimum weight codeword. In particular, almost no code satisfies the chain condition. In passing, we study the typical behaviour of codes with respect to generalized distances and show that almost all lie on a generalized Varshamov-Gilbert bound.     

A construction of mutually disjoint Steiner systems from isomorphic Golay codes

It is well known that the extended binary Golay [24,12,8] code yields 5-designs. In particular, the supports of all the weight 8 codewords in the code form a Steiner system S(5,8,24). In this paper, we give a construction of mutually disjoint Steiner systems S(5,8,24) by constructing isomorphic Golay codes. As a consequence, we show that there exists at least 22 mutually disjoint Steiner systems S(5,8,24). Finally, we prove that there exists at least 46 mutually disjoint 5-(48,12,8) designs from the extended binary quadratic residue [48,24,12] code.     

Failed disk recovery in double erasure RAID arrays

Reliability is a major concern in the design of large disk arrays. In this paper, we examine the effect of encountering more failures than that for which the RAID array was initially designed. Erasure codes are incorporated to enable system recovery from a specified number of disk erasures, and strive beyond that threshold to recover the system as frequently, and as thoroughly, as is possible. Erasure codes for tolerating two disk failures are examined. For these double erasure codes, we establish a correspondence between system operation and acyclicity of its graph model. For the most compact double erasure code, the full 2-code, this underlies an efficient algorithm for the computation of system operation probability (all disks operating or recoverable).When the system has failed, some disks are nonetheless recoverable. We extend the graph model to determine the probability that d disks have failed, a of which are recoverable by solving one linear equation, b of which are further recoverable by solving systems of linear equations, and d−a−b of which cannot be recovered. These statistics are efficiently calculated for the full 2-code by developing a three variable ordinary generating function whose coefficients give the specified values. Finally, examples are given to illustrate the probability that an individual disk can be recovered, even when the system is in a failed state.     

The Structure of 1-Generator Quasi-Twisted Codes and New Linear Codes

One of the most important problems of coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes have been proven to contain many such codes. In this paper, we consider quasi-twisted (QT) codes, which are generalizations of QC codes, and their structural properties and obtain new codes which improve minimum distances of best known linear codes over the finite fields GF(3) and GF(5). Moreover, we give a BCH-type bound on minimum distance for QT codes and give a sufficient condition for a QT code to be equivalent to a QC code.     

On the construction of prefix-free and fix-free codes with specified codeword compositions

We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost.     

A Gap in GRM Code Weight Distributions

The weight distribution of GRM (generalized Reed-Muller) codes is unknown in general. This article describes and applies some new techniques to the codes over F3. Specifically, we decompose GRM codewords into words from smaller codes and use this decomposition, along with a projective geometry technique, to relate weights occurring in one code with weights occurring in simpler codes. In doing so, we discover a new gap in the weight distribution of many codes. In particular, we show there is no word of weight 3^m–2 in GRM₃(4,m) for m>6, and for even-order codes over the ternary field, we show that under certain conditions, there is no word of weight d+, where d is the minimum distance and is the largest integer dividing all weights occurring in the code.