Shadow bounds for self-dual codes

Conway and Sloane (1990) have previously given an upper bound on the minimum distance of a singly-even self-dual binary code, using the concept of the shadow of a self-dual code. We improve their bound, finding that the minimum distance of a self-dual binary code of length n is at most 4[n/24]+4, except when n mod 24=22, when the bound is 4[n/24]+6. We also show that a code of length a multiple of 24 meeting the bound cannot be singly-even. The same technique gives similar results for additive codes over GF(4) (relevant to quantum coding theory)     

Linear programming bounds for doubly-even self-dual codes

Using a variant of the linear programming method we derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives d/n⩽0.166315···+o(1), thus improving on the Mallows-Odlyzko-Sloane bound of 1/6. To establish this, we prove that in any doubly even-self-dual code the distance distribution is asymptotically upper-bounded by the corresponding normalized binomial distribution in a certain interval     

Averaging bounds for lattices and linear codes

General random coding theorems for lattices are derived from the Minkowski-Hlawka theorem and their close relation to standard averaging arguments for linear codes over finite fields is pointed out. A new version of the Minkowski-Hlawka theorem itself is obtained as the limit, for p→∞, of a simple lemma for linear codes over GF(p) used with p-level amplitude modulation. The relation between the combinatorial packing of solid bodies and the information-theoretic “soft packing” with arbitrarily small, but positive, overlap is illuminated. The “soft-packing” results are new. When specialized to the additive white Gaussian noise channel, they reduce to (a version of) the de Buda-Poltyrev result that spherically shaped lattice codes and a decoder that is unaware of the shaping can achieve the rate 1/2 log₂ (P/N)     

Improved asymptotic bounds for error-correcting codes

The author has previously developed a new upper bound on nonsystematic binary error-correcting codes, using a sphere-packing approach and combinatorial analysis. A significant refinement is now added; together with a detailed study of the asymptotic behavior of the upper bound, this enables one to show that any large code must {em correct} almost all sequences with a larger number of errors than the code was designed for. This excess is expressed numerically as a fraction of the designed error-correcting capability of the code. The fraction is a function of the ratio of the sequence length and the designed error-correcting capability. A possible application might be in the use of a larger code giving almost certain error correction rather than a smaller one with certain correction capability.     

New performance bounds for turbo codes

We derive a new upper bound on the word- and bit-error probabilities of turbo codes with maximum-likelihood decoding by using the Gallager bound. Since the derivation of the bound for a given interleaver is intractable, we assume uniform interleaving as in the derivation of the standard union bound for turbo codes. The result is a generalization of the transfer function bound and remains useful for a wider range of signal-to-noise ratios, particularly for some range below the channel cutoff rate. The new bound is also applicable to other linear codes     

New lower bounds for covering codes

Some new lower bounds on |C| for a binary linear [n, k]R code C with n+1=t(R +1)-r(0⩽r<R+1, t>2 odd) or with n+1=t(R+1)-1(t>2 even) are obtained. These bounds improve the sphere covering bound considerably and give several new values and lower bounds for the function t[n, k], the smallest covering radius of any [n, k] code     

New extremal self-dual codes of length 62 and related extremalself-dual codes

New extremal self-dual codes of length 62 are constructed with weight enumerators of three different types. Two of these types were not represented by any known code up till now. All these codes possess an automorphism of order 15. Some of them are used to construct extremal self-dual codes of length 60 by the method of subtracting. By additional subtracting, an extremal self-dual [58, 29, 10] code was obtained having a weight enumerator which does not correspond to any code known so far     

New lower bounds for asymmetric and unidirectional codes

New lower bounds on the sizes of asymmetric codes and unidirectional codes are presented. Various methods are used, three of them of special interest. The first is a partitioning method that is a modification of a method used to construct constant weight codes. The second is a combining codes method that is used to obtain a new code from a few others. The third method is shortening by weights that is applied on symmetric codes or on codes generated by the combining codes method. Tables for the sizes of codes of length n⩽23 are presented     

New lower bounds for constant weight codes

Some new lower bounds are given for A(n,4,w ), the maximum number of codewords in a binary code of length n , minimum distance 4, and constant weight w. In a number of cases the results significantly improve on the best bounds previously known     

New extremal self-dual codes of lengths 42 and 44

All extremal binary self-dual codes of lengths 42 and 44 which have an automorphism of order 5 with eight independent cycles are obtained up to equivalence. There are 109 inequivalent [42, 21, 8] codes with such an automorphism. All [44, 22, 8] codes that are obtained have 29 different weight enumerators     

卡氏积码的MDR码和自对偶码

定义了Z_(r_1),Z_(r_2)…,Z_(r_s)上线性码C_1,C_2,…,C_s的卡氏积码.利用子模同构定理,研究了在Z_(r_1)×Z_(r_2)×…×Z_(r_s)上卡氏积码C_1×C_2×…×C_s的秩与在Z_(r_1),Z_(r_2),…,Z_(r_s)码C_1,C_2,…,C_s的秩的关系,借助这一关系,得到了MDR码的卡氏积仍为MDR码和自对偶码的卡氏积码也为自对偶码.     

Cubic self-dual binary codes

We study binary self-dual codes with a fixed point free automorphism of order three. All binary codes of that type can be obtained by a cubic construction that generalizes Turyn's. We regard such "cubic" codes of length 3/spl lscr/ as codes of length /spl lscr/ over the ring F/sub 2//spl times/F/sub 4/. Classical notions of Type II codes, shadow codes, and weight enumerators are adapted to that ring. Two infinite families of cubic codes are introduced. New extremal binary codes in lengths /spl les/ 66 are constructed by a randomized algorithm. Necessary conditions for the existence of a cubic [72,36,16] Type II code are derived.     

New trellis codes based on lattices and cosets

A new technique is proposed for constructing trellis codes. which provides an alternative to Ungerboeck's method of "set partitioning." The new codes use a signal constellation consisting of points from ann-dimensional latticeLambda, with an equal number of points from each coset of a sublatticeLambda '. One part of the input stream drives a generalized convolutional code whose outputs are cosets ofLambda ', while the other part selects points from these cosets. Several of the new codes are better than those previously known.     

New minimum distance bounds for certain binary linear codes

Let an [n, k, d]-code denote a binary linear code of length n, dimension k, and minimum distance at least d. Define d(n, k) as the maximum value of d for which there exists a binary linear [n, k, d]-code. T. Verhoeff (1989) has provided an updated table of bounds on d(n, k) for 1⩽k⩽n⩽127. The authors improve on some of the upper bounds given in that table by proving the nonexistence of codes with certain parameters     

Augmented product codes and lattices: Reed-Muller codes and Barnes-Wall lattices

This paper concerns the construction of the so-called augmented product codes and augmented product lattices. These are obtained by augmenting product codes or product lattices from certain classes thus obtaining higher dimensional codes or lattices from the same class, respectively. Certain properties of the augmented product construction are derived, and specific construction examples are given. In particular, it is shown that the Reed-Muller codes, the Golay code, the Barnes-Wall lattices, as well as the Leech lattice all have various augmented product constructions.     

Gleason's theorem on self-dual codes

The weight enumerator of a code is the polynomial begin{equation} W(x,y)= sum_{r=0}^n A_r x^{n-r} y^r, end{equation} wherendenotes the block length andA_r, denotes the number of codewords of weightr. LetCbe a self-dual code overGF(q)in which every weight is divisible byc. Then Gleason's theorem states that 1) ifq= 2 andc= 2, the weight enumerator ofCis a sum of products of the polynomialsx^2 + y^2andx^2y^2 (x^2 - y^2 )^2ifq= 2 andc= 4, the weight enumerator is a sum of products ofx^8 + 14x^4 y^4 + y^8andx^4 y^4 (x^4 - y^4)^4; and 3) ifq= 3 andc= 3, the weight enumerator is a sum of products ofx^4 + 8xy^3andy^3(x^3 - y^3)^3. In this paper we give several proofs of Gleason's theorem.     

Weight enumerators of self-dual codes

Some construction techniques for self-dual codes are investigated, and the authors construct a singly-even self-dual [48,24,10]-code with a weight enumerator that was not known to be attainable. It is shown that there exists a singly-even self-dual code C' of length n =48 and minimum weight d=10 whose weight enumerator is prescribed in the work of J.H. Conway et al. (see ibid., vol.36, no.5, p.1319-33, 1990). Two self-dual codes of length n are called neighbors, provided their intersection is a code of dimension (n/2)-1. The code C' is a neighbor of the extended quadratic residue code of length 48     

Good self-dual quasi-cyclic codes exist

We show that there are long binary quasi-cyclic self-dual (either Type I or Type II) codes satisfying the Gilbert-Varshamov bound.     

New lower bounds and constructions for binary codes correcting asymmetric errors

In this correspondence, we study binary asymmetric error-correcting codes. A general construction for binary asymmetric error-correcting codes is presented. We show that some previously known lower bounds for binary asymmetric error-correcting codes can be obtained from this general construction. Furthermore, some new lower bounds for binary asymmetric error-correcting codes are obtained from this general construction. These new lower bounds improve the existing ones.     

New bounds and constructions for authentication/secrecy codes with splitting

We investigate authentication codes with splitting, using the mathematical model introduced by Simmons. Besides an overview of the existing bounds, we obtain some new bounds for the probability of deception of the transmitter/ receiver in case of an impersonation or substitution game. We also prove some new bounds for a spoofing attack of order L. Further, we give several new constructions for authentication/secrecy codes with splitting, derived from finite incidence structures such as partial geometries and affine resolvable designs. In some of these codes the bounds are attained with equality.