Spectral-Null Codes and Null Spaces of Hadamard Submatrices

Codes of length 2 ^m over {1, -1} are defined as null spaces of certain submatrices of Hadamard matrices. It is shown that the codewords of all have an rth order spectral null at zero frequency. Establishing the connection between and the parity-check matrix of Reed-Muller codes, the minimum distance of is obtained along with upper bounds on the redundancy of . An efficient algorithm is presented for encoding unconstrained binary sequences into .     

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.     

Bounds for binary multiple covering codes

We study codes that are multiple coverings of the Hamming space and discuss lower and upper bounds onK(n, r, ), the minimum cardinality of a binary code of lengthn such that the Hamming spheres of radiusr centered at the codewords cover at least times. We also study the similar problem of multiple coverings containing repeated words. A table of bounds forn16,r4, 4 is given.     

Perfect codes in direct products of cycles—a complete characterization

Let be a direct product of cycles. It is known that for any r1, and any n2, each connected component of G contains a so-called canonical r-perfect code provided that each ℓ_i is a multiple of rⁿ+(r+1)ⁿ. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist.     

Small weight codewords in the codes arising from Desarguesian projective planes

We study codewords of small weight in the codes arising from Desarguesian projective planes. We first of all improve the results of K. Chouinard on codewords of small weight in the codes arising from PG(2, p), p prime. Chouinard characterized all the codewords up to weight 2p in these codes. Using a particular basis for this code, described by Moorhouse, we characterize all the codewords of weight up to 2p + (p−1)/2 if p ≥ 11. We then study the codes arising from . In particular, for q ₀ = p prime, p ≥ 7, we prove that the codes have no codewords with weight in the interval [q + 2, 2q − 1]. Finally, for the codes of PG(2, q), q = p ^h , p prime, h ≥ 4, we present a discrete spectrum for the weights of codewords with weights in the interval [q + 2, 2q − 1]. In particular, we exclude all weights in the interval [3q/2, 2q − 1]. Geertrui Van de Voorde research is supported by the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen) Joost Winne was supported by the Fund for Scientific Research - Flanders (Belgium).     

The Classification of Some Perfect Codes

Perfect 1-error correcting codes C in Z ₂ ⁿ , where n=2 ^m–1, are considered. Let ; denote the linear span of the words of C and let the rank of C be the dimension of the vector space . It is shown that if the rank of C is n–m+2 then C is equivalent to a code given by a construction of Phelps. These codes are, in case of rank n–m+2, described by a Hamming code H and a set of MDS-codes D _h , h H, over an alphabet with four symbols. The case of rank n–m+1 is much simpler: Any such code is a Vasil'ev code.     

The Automorphism Groups of BCH Codes and of Some Affine-Invariant Codes Over Extension Fields

Affine-invariant codes are extended cyclic codes of length p ^m invariant under the affine-group acting on . This class of codes includes codes of great interest such as extended narrow-sense BCH codes. In recent papers, we classified the automorphism groups of affine-invariant codes berg, bech1. We derive here new results, especially when the alphabet field is an extension field, by expanding our previous tools. In particular we complete our results on BCH codes, giving the automorphism groups of extended narrow-sense BCH codes defined over any extension field.     

Subcodes of the Projective Generalized Reed-Muller Codes Spanned by Minimum-Weight Vectors

We use methods of Mortimer [19] to examine the subcodes spanned by minimum-weight vectors of the projective generalized Reed-Muller codes and their duals. These methods provide a proof, alternative to a dimension argument, that neither the projective generalized Reed-Muller code of order r and of length over the finite field F _q of prime-power order q, nor its dual, is spanned by its minimum-weight vectors for 0<r<m–1 unless q is prime. The methods of proof are the projective analogue of those developed in [17], and show that the codes spanned by the minimum-weight vectors are spanned over F _q by monomial functions in the m variables. We examine the same question for the subfield subcodes and their duals, and make a conjecture for the generators of the dual of the binary subfield subcode when the order r of the code is 1.     

Existence of Perfect 4-Deletion-Correcting Codes with Length Six

By a T ^*(2, k, v)-code we mean a perfect4-deletion-correcting code of length 6 over an alphabet of size v, which is capable of correcting anycombination of up to 4 deletions and/or insertions of letters that occur in transmission of codewords. Thethird author (DCC Vol. 23, No. 1) presented a combinatorial construction for such codes and prove thata T ^*(2, 6, v)-code exists for all positive integers v 3 (mod 5), with 12 possible exceptions of v. In this paper, the notion of a directedgroup divisible quasidesign is introduced and used to show that a T ^*(2, 6,v)-code exists for all positive integers v 3 (mod 5), except possiblyfor v {173, 178, 203, 208}. The 12 missing cases for T ^*(2,6, v)-codes with v 3 (mod 5) are also provided, thereby the existenceproblem for T ^*(2, 6, v)-codes is almost complete.     

Two New Infinite Families of 3-Designs from Kerdock Codes over Z4

In this paper we show that the support of the codewords of each type in the Kerdock code of length 2^m over Z₄ form 3-designs for any odd integer . In particular, twonew infinite families of 3-designs are obtained in this constructionfor any odd integer . In particular, twonew infinite families of 3-designs are obtained in this constructionfor any odd integer , whose parameters are ,and .     

The Invariants of the Clifford Groups

The automorphism group of the Barnes-Wall lattice L _m in dimension 2 ^m (m ; 3) is a subgroup of index 2 in a certain Clifford group of structure 2 ₊ ^1+2m . O ⁺(2m,2). This group and its complex analogue of structure .Sp(2m, 2) have arisen in recent years in connection with the construction of orthogonal spreads, Kerdock sets, packings in Grassmannian spaces, quantum codes, Siegel modular forms and spherical designs. In this paper we give a simpler proof of Runge@apos;s 1996 result that the space of invariants for of degree 2k is spanned by the complete weight enumerators of the codes , where C ranges over all binary self-dual codes of length 2k; these are a basis if m k - 1. We also give new constructions for L _m and : let M be the -lattice with Gram matrix . Then L _m is the rational part of M ^m, and = Aut(M^m). Also, if C is a binary self-dual code not generated by vectors of weight 2, then is precisely the automorphism group of the complete weight enumerator of . There are analogues of all these results for the complex group , with doubly-even self-dual code instead of self-dual code.     

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.     

Designs in Additive Codes over GF(4)

In this paper we discuss the security of digital signature schemes based on error-correcting codes. Several attacks to the Xinmei scheme are surveyed, and some reasons given to explain why the Xinmei scheme failed, such as the linearity of the signature and the redundancy of public keys. Another weakness is found in the Alabbadi-Wicker scheme, which results in a universal forgery attack against it. This attack shows that the Alabbadi-Wicker scheme fails to implement the necessary property of a digital signature scheme: it is infeasible to find a false signature algorithm D from the public verification algorithm E such that E(D ( )) = for all messages . Further analysis shows that this new weakness also applies to the Xinmei scheme.     

Extremal Self-Dual Codes over \mathbb{F} 2 × \mathbb{F} 2

In this paper, it is shown that extremal (Hermitian) self-dual codes over ₂ × ₂ exist only for lengths 1, 2, 3, 4, 5, 8 and 10. All extremal self-dual codes over ₂ × ₂ are found. In particular, it is shown that there is a unique extremal self-dual code up to equivalence for lengths 8 and 10. Optimal self-dual codes are also investigated. A classification is given for binary [12, 7, 4] codes with dual distance 4, binary [13, 7, 4] codes with dual distance 4 and binary [13, 8, 4] codes with dual distance 4.     

Stickelberger Codes

Let p be an odd prime and be a primitive p th root of unity over . The Galois group G of over is a cyclic group of order p-1. The integral group ring [G] contains the Stickelberger ideal S _p which annihilates the ideal class group of K. In this paper we investigate the parameters of cyclic codes S _p (q) obtained as reductions of S _p modulo primes q which we call Stickelberger codes. In particular, we show that the dimension of S _p (p) is related to the index of irregularity of p, i.e., the number of Bernoulli numbers B _2k , , which are divisible by p. We then develop methods to compute the generator polynomial of S _p (p). This gives rise to anew algorithm for the computation of the index of irregularity of a prime. As an application we show that 20,001,301 is regular. This significantly improves a previous record of 8,388,019 on the largest explicitly known regular prime.     

On Codes Identifying Sets of Vertices in Hamming Spaces

A code is called (t, 2)-identifying if for all the words x, y(x y) and the sets (B _t (x) B _t (y)) C and are nonempty and different. Constructions of such codes and a lower bound on the cardinality of these codes are given. The lower bound is shown to be sharp in some cases. We also discuss a more general notion of -identifying codes and introduce weakly identifying codes.     

Minimum Distance Bounds for s-Regular Codes

A code C F ⁿ is s-regular provided, forevery vertex x F ⁿ, if x is atdistance at most s from C then thenumber of codewords y C at distance ifrom x depends only on i and the distancefrom x to C. If denotesthe covering radius of C and C is -regular,then C is said to be completely regular. SupposeC is a code with minimum distance d,strength t as an orthogonal array, and dual degrees ^*. We prove that d 2t + 1 whenC is completely regular (with the exception of binaryrepetition codes). The same bound holds when C is(t + 1)-regular. For unrestricted codes, we show thatd s ^* + t unless C is a binary repetitioncode.     

Combinatorial S >n-Modules as Codes

Certain -modules related to the kernels ofincidence maps between types in the poset defined by the natural productorder on the set of n-tuples with entries from {1, ,m} are studied as linear codes (whencoefficients are extended to an arbitrary field K). Theirdimensions and minimal weights are computed. The Specht modules areextremal among these submodules. The minimum weight codewords of theSpecht module are shown to be scalar multiples of polytabloids. Ageneralization of t-design arising from the natural permutationS _n-modules labelled by partitions with mparts is introduced. A connection with Reed-Muller codes is noted and acharacteristic free formulation is presented.     

Unit-distance graphs,graphs on the integer lattice and a Ramsey type result

Summary Let (R ², 1) denote the graph withR ² as the vertex set and two vertices adjacent if and only if their Euclidean distance is 1. The problem of determining the chromatic number(R ², 1) is still open; however,(R ², 1) is known to be between 4 and 7. By a theorem of de Bruijn and Erdös, it is enough to consider only finite subgraphs of (R ², 1). By a recent theorem of Chilakamarri, it is enough to consider certain graphs on the integer lattice. More precisely, forr > 0, let (Z ²,r, ) denote a graph with vertex setZ ² and two vertices adjacent if and only if their Euclidean distance is in the closed interval [r – ,r + ]. A simple graph is faithfully -recurring inZ ² if there exists a real numberd > 0 such that, for arbitrarily larger, G is isomorphic to a subgraph of (Z ²,r, ) in which every pair of vertices are at least distancedr apart. Chilakamarri has shown that, ifG is a finite simple graph, thenG is isomorphic to a subgraph of (R ², 1) if and only ifG is faithfully -recurring inZ ². In this paper we prove that(Z ²,r, ) 5 for integersr 1. We also prove a Ramsey type result which states that for any integerr > 1, and any coloring ofZ ² either there exists a monochromatic pair of vertices with their distance in the closed interval [r – ,r + ] or there exists a set of three vertices closest to each other with three distinct colors.