A note on the Newton radius

The Newton radius of a code is the largest weight of a uniquely correctable error. We establish a lower bound for the Newton radius in terms of the rate. In particular we show that in any family of linear codes of rate below one half, the Newton radius increases linearly with the codeword length.     

On the Covering Radius of Ternary Extremal Self-Dual Codes

In this paper, we investigate the covering radius of ternary extremal self-dual codes. The covering radii of all ternary extremal self-dual codes of lengths up to 20 were previously known. The complete coset weight distributions of the two inequivalent extremal self-dual codes of length 24 are determined. As a consequence, it is shown that every extremal ternary self-dual code of length up to 24 has covering radius which meets the Delsarte bound. The first example of a ternary extremal self-dual code with covering radius which does not meet the Delsarte bound is also found. It is worth mentioning that the found code is of length 32.     

On the Weak Order Ideal Associated to Linear Codes

In this work we study a weak order ideal associated with the coset leaders of a non-binary linear code. This set allows the incrementally computation of the coset leaders and the definitions of the set of leader codewords. This set of codewords has some nice properties related to the monotonicity of the weight compatible order on the generalized support of a vector in \(\mathbb {F}_q^n\) which allows to describe a test set, a trial set and the set of zero neighbours of a linear code in terms of the leader codewords.     

Signcryption with Non-interactive Non-repudiation

In this paper various methods for computing the support weight enumerators of binary, linear, even, isodual codes are described. It is shown that there exist relationships between support weight enumerators and coset weight distributions of a code that can be used to compute partial information about one set of these code invariants from the other. The support weight enumerators and complete coset weight distributions of several even, isodual codes of length up to 22 are computed as well. It is observed that there exist inequivalent codes with the same support weight enumerators, inequivalent codes with the same complete coset weight distribution and inequivalent codes with the same support eight enumerators and complete coset weight distribution.Communicated by:T. HellesethAMS Classification: 11T71, 68P30Parts of the results in this paper were presented at the 2001 International Symposium on Information Theory, Washington, and at the 2002 International Symposium on Information Theory, Lauzanne.     

Weight distribution moments of random linear/coset codes

A simple method is proposed for the calculation of moments of the weight function of a random linear code. Applying this method we compute the exact expression for the third-order covariance of the weight function. The results are also extended to random coset codes.     

The weight distribution of the coset leaders for some classes of codes with related parity-check matrices

We construct an infinite sequence of codes with related parity-check matrices. We show how to reduce the calculations of the weight distribution of the coset leaders for all these codes, to the calculation of finitely many numbers F_lj. This method is applied in determining the weight distribution of the coset leaders for several classes of codes.     

On a class of binary linear completely transitive codes with arbitrary covering radius

An infinite class of new binary linear completely transitive (and so, completely regular) codes is given. The covering radius of these codes is growing with the length of the code. In particular, for any integer ρ≥2, there exist two codes in the constructed class with d=3, covering radius ρ and lengths and , respectively. The corresponding distance-transitive graphs, which can be defined as coset graphs of these completely transitive codes are described.     

New Quaternary Linear Codes with Covering Radius 2

A new quaternary linear code of length 19, codimension 5, and covering radius 2 is found in a computer search using tabu search, a local search heuristic. Starting from this code, which has some useful partitioning properties, different lengthening constructions are applied to get an infinite family of new, record-breaking quaternary codes of covering radius 2 and odd codimension. An algebraic construction of covering codes over alphabets of even characteristic is also given.     

On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes

We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by generalizing a method due to S. Litsyn and A. Tietäväinen lt:newu and combining it with a new upper bound on the asymptotic information rate of non-binary codes. The upper bound on the information rate is an application of a shortening method of a code and is an analogue of the Shannon-Gallager-Berlekamp straight line bound on error probability. These results improve on the best presently known asymptotic upper bounds on minimum distance and covering radius of non-binary codes in certain intervals.     

Ternary Covering Codes Derived from BCH Codes

It is shown how ternary BCH codes can be lengthened to get linear codes with covering radius 2. The family obtained has the ternary Golay code as its first code, contains codes with record-breaking parameters, and has a good asymptotic behavior. The ternary Golay code is further used to obtain short proofs for the best known upper bounds for the football pool problem for 11 and 12 matches.     

张量积码的多重覆盖半径

码的多重覆盖半径是最近对码的通常覆盖半径的一个推广．本文研究了由两个二元线性码构成的张量积码的多重覆盖半径．并得到了该张量积码的多重覆盖半径的界．     

Burst distribution of a linear code

In this note, the distribution of bursts is obtained, as defined by Chien and Teng, for a linear code and its coset.     

Linear Programming Bounds for Codes via a Covering Argument

We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, therefore, is large. This implies the original code to be small. We also point out that this bound is a natural isoperimetric constant of the Hamming cube, related to its Faber–Krahn minima. While our approach belongs to the general framework of Delsarte’s linear programming method, its main technical ingredient is Fourier duality for the Hamming cube. In particular, we do not deal directly with Delsarte’s linear program or orthogonal polynomial theory. This research was partially supported by ISF grant 039-7682.     

Covering radii are not matroid invariants

We show by example that the covering radius of a binary linear code is not generally determined by the Tutte polynomial of the matroid. This answers Problem 361 (P.J. Cameron (Ed.), Research problems, Discrete Math. 231 (2001) 469-478).     

Codes with given distances

One of the main results says that ifC is a binary linear code of length 4t and of dimension greater than 2t, thenC contains a word of weight 2t and this bound is best possible. Several results of similar flavor are established both for linear and non-linear codes. For the proof a lemma introducing the binormal forms of binary matrices is needed. The results are applied to determine the coset chromatic number of Hadamard graphs, to solve a problem of Galvin and to give a short proof of a theorem of Gleason on self-dual doubly-even codes.     

Four classes of linear codes from cyclotomic cosets

This paper presents four classes of linear codes from coset representatives of subgroups and cyclotomic coset families of certain finite field, and determines their weight enumerators. These linear codes may have applications in consumer electronics, communications and secret sharing schemes.     

Jacobi Polynomials, Type II Codes, and Designs

Jacobi polynomials were introduced by Ozeki in analogy with Jacobi forms of lattices. They are useful to compute coset weight enumerators, and weight enumerators of children. We determine them in most interesting cases in length at most 32, and in some cases in length 72. We use them to construct group divisible designs, packing designs, covering designs, and (t,r)-designs in the sense of Calderbank-Delsarte. A major tool is invariant theory of finite groups, in particular simultaneous invariants in the sense of Schur, polarization, and bivariate Molien series. A combinatorial interpretation of the Aronhold polarization operator is given. New rank parameters for spaces of coset weight distributions and Jacobi polynomials are introduced and studied here.     

New uniqueness proofs for the (5, 8, 24), (5, 6, 12) and related Steiner systems

New elementary proofs of the uniqueness of certain Steiner systems using coding theory are presented. In the process some of the codes involved are shown to be unique.The uniqueness proof for the (5, 8, 24) Steiner system is due to John Conway. The blocks of the system are used to generate a length 24 binary code. Any two such codes are then shown to be equivalent up to a permutation of the coordinates. This code turns out to be the extended Golay code.In the uniqueness proof for the (4, 7, 23) system, the blocks generate a length 23 code which is extended to a length 24 code. The minimum weight vectors of this larger code hold a (5, 8, 24) Steiner system. This result together with the previous one completes the proof. At this point it is also possible to conclude that the codes involved are unique and hence equivalent to the binary perfect Golay code and its extension.Continuing with the uniqueness result for the (3, 6, 22) Steiner system, the blocks generate a length 22 code which is extended to the same length 24 code by the addition of two coordinates and one additional vector. This extension ultimately requires the computation of the coset weight distribution of the length 22 code, a result heretofore unknown. The complete coset weight distribution for a specific (22, 11, 6) self-dual code is computed using the CAMAC computer system.The (5, 6, 12) and (4, 5, 11) Steiner systems are treated differently. It is shown that each system is completely determined by the choice of six blocks which may be assumed to lie in any such design. These six blocks in fact form a basis for length 12 (and 11) ternary codes corresponding to the two systems and may be generated by an algorithm independent of the designs. This algorithm is presented and the minimum weight vectors of the resulting codes, the perfect ternary Golay code and its extension, are calculated by the CAMAC system.     

The extended coset leader weight enumerator of a twisted cubic code

Designs, Codes and Cryptography - The extended coset leader weight enumerator of the generalized Reed–Solomon $$[q+1,q-3,5]_q$$ code is computed. In this computation methods in finite...     

Covering radius and dual distance

Recently a number of bounds have been obtained for the covering radius of a code with given length and cardinality. In this paper we show that—perhaps surprisingly—the covering radius of a code depends heavily on its dual distance. We consider an arbitrary finite Abelian group alphabet though in the applications the alphabet is very often the field F ₂.