On maximum length convolutional codes under a trellis complexity constraint

We look at convolutional codes with maximum possible code length for prescribed redundancy, conditioned on constraints on the free distance and on the bit-oriented trellis state complexity. Rate (n−1)/n codes have been studied to some extent in the literature, but more general rates have not been studied much. In this work we consider convolutional codes of rate (n−r)/n, r⩾1. Explicit construction techniques for free distance d_free=3 and 4 codes are described. For codes with r=2, an efficient exhaustive search algorithm is outlined. For the more general case with r⩾2, a heuristic approach is suggested. Several new codes were found for r=1 and in particular for r=2 and 3. Compared to previously known codes of similar free distance and complexity constraints, the new codes have either strictly higher rate, or the same rate but smaller low distance multiplicities.     

Higher Weights of Anticodes and the Generalized Griesmer Bound

We show that the minimum r-weight d_r of an anticode can be expressed in terms of the maximum r-weight of the corresponding code. As examples, we consider anticodes from homogeneous hypersurfaces (quadrics and Hermitian varieties). In a number of cases, all differences (except for one) of the weight hierarchy of such an anticode meet an analog of the generalized Griesmer bound.     

A symmetric Roos bound for linear codes

The van Lint-Wilson AB-method yields a short proof of the Roos bound for the minimum distance of a cyclic code. We use the AB-method to obtain a different bound for the weights of a linear code. In contrast to the Roos bound, the role of the codes A and B in our bound is symmetric. We use the bound to prove the actual minimum distance for a class of dual BCH codes of length q²−1 over Fq. We give cyclic codes [63,38,16] and [65,40,16] over F₈ that are better than the known [63,38,15] and [65,40,15] codes.     

Improving bounds on the minimum Euclidean distance for block codes by inner distance measure optimization

The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size |C|. For q=8, we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean.The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with q=8 that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters n and |C|. This is true for many multilevel codes.     

A Lower Bound on the Greedy Weights of Product Codes

A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r - 1)-subcode. The r-th greedy weight e _r is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes.     

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

Sphere of influence graphs in general metric spaces

Let χ = {X₁…, X_n} be a set of points in a metric space (n ≥ 2). Let r_i, denote the minimum distance between X_i and the other points in χ. The sphere of influence at X_i is the open ball with center X_iand radius r_i. The sphere of influence graph has vertex set χ with an edge joining a pair of distinct vertices provided the corresponding spheres of influence intersect. This proximity graph was introduced by Toussaint to model computer vision and pattern recognition problems in the Euclidean plane. We discuss the abstract properties of sphere of influence graphs in general metric spaces with emphasis on normed linear spaces. Our work generalizes and simplifies some theorems in the literature on sphere of influence graphs and lays the groundwork for future work.     

On the minimum average distance of binary constant weight codes

Let β(n,M,w) denote the minimum average Hamming distance of a binary constant weight code with length n, size M and weight w. In this paper, we study the problem of determining β(n,M,w). Using the methods from coding theory and linear programming, we derive several lower bounds on the average Hamming distance of a binary constant weight code. These lower bounds enable us to determine the exact value for β(n,M,w) in several cases.     

On repeated-root multivariable codes over a finite chain ring

In this work we consider repeated-root multivariable codes over a finite chain ring. We show conditions for these codes to be principally generated. We consider a suitable set of generators of the code and compute its minimum distance. As an application we study the relevant example of the generalized Kerdock code in its r-dimensional cyclic version.      

The codes and the lattices of Hadamard matrices

It has been observed by Assmus and Key as a result of the complete classification of Hadamard matrices of order 24, that the extremality of the binary code of a Hadamard matrix H of order 24 is equivalent to the extremality of the ternary code of H^T. In this note, we present two proofs of this fact, neither of which depends on the classification. One is a consequence of a more general result on the minimum weight of the dual of the code of a Hadamard matrix. The other relates the lattices obtained from the binary code and the ternary code. Both proofs are presented in greater generality to include higher orders. In particular, the latter method is also used to show the equivalence of (i) the extremality of the ternary code, (ii) the extremality of the Z₄-code, and (iii) the extremality of a lattice obtained from a Hadamard matrix of order 48.     

Algebraic decoding of negacyclic codes over {\mathbb Z_4}

In this article we investigate Berlekamp’s negacyclic codes and discover that these codes, when considered over the integers modulo 4, do not suffer any of the restrictions on the minimum distance observed in Berlekamp’s original papers: our codes have minimum Lee distance at least 2t + 1, where the generator polynomial of the code has roots α, α ³, . . . , α ^2t-1 for a primitive 2nth root α of unity in a Galois extension of ${\mathbb {Z}_4}$ ; no restriction on t is imposed. We present an algebraic decoding algorithm for this class of codes that corrects any error pattern of Lee weight ≤ t. Our treatment uses Gröbner bases, the decoding complexity is quadratic in t.     

Codes over Zm

In this paper we study cyclic codes inZ _m. i.e., ideals inZ _mG, G a finite abelian group, and we give a classification of such codes.We also study the minimum Hamming distance and the generalized Hamming weight of BCH codes overZ _m.     

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.     

Optimal packings of K4's into a Kn

In this paper we determine the maximum cardinality of a packing of K₄'s into K_n, that is, construct optimal constant weight codes with weight 4 and minimum distance 6.     

The weight distribution of irreducible cyclic codes with block lengths n1((q1−1)N)

We study the weight distribution of irreducible cyclic (n, k) codeswith block lengths n = n₁((q¹ ? 1)/N), where N|q ? 1, gcd(n₁,N) = 1, and gcd(l,N) = 1. We present the weight enumerator polynomial, A(z), when k = n₁l, k = (n₁ ? 1)l, and k = 2l. We also show how to find A(z) in general by studying the generator matrix of an (n₁, m) linear code, $\text{V}{}^1{}_{\mathrm{d}}$ over GF(q^d) where d = gcd (ord_n1(q), l). Specifically we study A(z) when $\text{V}{}^1{}_{\mathrm{d}}$ is a maximum distance separable code, a maximal shiftregister code, and a semiprimitive code. We tabulate some numbers A_μ which completely determine the weight distributionof any irreducible cyclic (n₁(2¹ ? 1), k) code over GF(2) for all n₁ ? 17.     

Exact Bounds on the Sizes of Covering Codes

A code c is a covering code of X with radius r if every element of X is within Hamming distance r from at least one codeword from c. The minimum size of such a c is denoted by c _r(X). Answering a question of Hämäläinen et al. [10], we show further connections between Turán theory and constant weight covering codes. Our main tool is the theory of supersaturated hypergraphs. In particular, for n > n ₀(r) we give the exact minimum number of Hamming balls of radius r required to cover a Hamming ball of radius r + 2 in {0, 1}ⁿ. We prove that c _r(B _n(0, r + 2)) = _{1 i r + 1} ( ^{(n + i – 1) / (r + 1) 2}) + n / (r + 1) and that the centers of the covering balls B(x, r) can be obtained by taking all pairs in the parts of an (r + 1)-partition of the n-set and by taking the singletons in one of the parts.     

Codes of Small Defect

The parameters of a linear code C over GF(q) are given by [n,k,d], where n denotes the length, k the dimension and d the minimum distance of C. The code C is called MDS, or maximum distance separable, if the minimum distance d meets the Singleton bound, i.e. d = n-k+1 Unfortunately, the parameters of an MDS code are severely limited by the size of the field. Thus we look for codes which have minimum distance close to the Singleton bound. Of particular interest is the class of almost MDS codes, i.e. codes for which d=n-k. We will present a condition on the minimum distance of a code to guarantee that the orthogonal code is an almost MDS code. This extends a result of Dodunekov and Landgev Dodunekov. Evaluation of the MacWilliams identities leads to a closed formula for the weight distribution which turns out to be completely determined for almost MDS codes up to one parameter. As a consequence we obtain surprising combinatorial relations in such codes. This leads, among other things, to an answer to a question of Assmus and Mattson 5 on the existence of self-dual [2d,d,d]-codes which have no code words of weight d+1. Actually there are more codes than Assmus and Mattson expected, but the examples which we know are related to the expected ones.     

Diameter-girth sufficient conditions for optimal extraconnectivity in graphs

For a connected graph G, the rth extraconnectivity κ_r(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1 vertices. The standard connectivity and superconnectivity correspond to κ₀(G) and κ₁(G), respectively. The minimum r-tree degree of G, denoted by ξ_r(G), is the minimum cardinality of N(T) taken over all trees T⊆G of order |V(T)|=r+1, N(T) being the set of vertices not in T that are neighbors of some vertex of T. When r=1, any such considered tree is just an edge of G. Then, ξ₁(G) is equal to the so-called minimum edge-degree of G, defined as ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, where d(u) stands for the degree of vertex u. A graph G is said to be optimally r-extraconnected, for short κ_r-optimal, if κ_r(G)?ξ_r(G). In this paper, we present some sufficient conditions that guarantee κ_r(G)?ξ_r(G) for r?2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1.     

Weighted Reed–Muller codes revisited

We consider weighted Reed–Muller codes over point ensemble S ₁ × · · · × S _m where S _i needs not be of the same size as S _j . For m = 2 we determine optimal weights and analyze in detail what is the impact of the ratio |S ₁|/|S ₂| on the minimum distance. In conclusion the weighted Reed–Muller code construction is much better than its reputation. For a class of affine variety codes that contains the weighted Reed–Muller codes we then present two list decoding algorithms. With a small modification one of these algorithms is able to correct up to 31 errors of the [49,11,28] Joyner code.     

On linear codes whose weights and length have a common divisor

In this paper we prove that a set of points (in a projective space over a finite field of q elements), which is incident with 0 mod r points of every hyperplane, has at least (r−1)q+(p−1)r points, where 1<r<q=ph, p prime. An immediate corollary of this theorem is that a linear code whose weights and length have a common divisor r<q and whose dual minimum distance is at least 3, has length at least (r−1)q+(p−1)r. The theorem, which is sharp in some cases, is a strong generalisation of an earlier result on the non-existence of maximal arcs in projective planes; the proof involves polynomials over finite fields, and is a streamlined and more transparent version of the earlier one.