Some long cyclic linear binary codes are not so bad

We show that when an inner linear cyclic binary code which has an irreducible check polynomial is concatenated with an appropriately chosen maximal-distance-separable outer code, then the overall code is cyclic OverGF(2). Using this theorem, we construct a number of linear cyclic binary codes which are better than any previously known. In particular, by taking the inner code to be a quadratic residue code, we obtain linear cyclic binary codes of lengthN, rateR, and distanceD geq (1 - 2R)N/ sqrt{2 log N}, which compares favorably with the BCH distanceD sim (2 ln R^{-1})N/log N, although it still fails to achieve the linear growth of distance with block length which is possible with noncyclic linear concatenated codes. While this construction yields many codes, including several with block lengths greater than10^{10^5}, we have not been able to prove that there are arbitrarily long codes of this type without invoking the Riemann hypothesis or the revised Artin conjecture, as the existence of long codes of our type is equivalent to the existence of large primespfor which the index of 2 is(p - 1)/2.     

Some Remarks on BCH Bounds and Minimum Weights of Binary Primitive BCH Codes

It is shown that ifm neq 8, 12andm > 6, there are some binary primitive BCH codes (BCH codes in a narrow sense) of length2^{m} - 1whose minimum weight is greater than the BCH bound. This gives a negative answer to the question posed by Peterson [1] of whether or not the BCH bound is always the actual minimum weight of a binary primitive BCH code. It is also shown that for any evenm geq 6, there are some binary cyclic codes of length2^{m} - 1that have more information digits than the primitive BCH codes of length2^{m} - 1with the same minimum weight.     

An upper bound on the minimum distance of a convolutional code

An upper bound on the minimum distance of a linear convolutional code is given which reduces to the Plotkin bound for the block code case. It is shown that most linear convolutional codes have a minimum distance strictly less than their average distance. A table of the bound for several rates is given for binary codes as well as a comparison with the known optimum values for codes of block length2.     

A bound for arithmetic codes of composite length (Corresp.)

This correspondence presents an upper bound on the minimum distance of arithmetic codes of composite lengthn = n_1 n_2. The tightness of this bound gives a rather good working estimate of the minimum distance of a prospective code.     

A weight distribution bound for linear codes

A linear code of block length n possessing minimum weight d has one code word of weight zero, and no other code words of weight less thand. The weight distribution of the code is given by the set of allW(j), d leq j leq n, describing the number of code words having a weight of exactlyj. Exact weight distributions are known for only a handful of linear codes. This paper presents an explicit upper bound uponW(j)as a function ofn, d, andj. The bound has general applicability to all linear codes.     

Analysis of recurrent codes

A definition of a recurrent code is given in a framework which renders it amenable to mathematical analysis. Recurrent codes for both independent and burst errors are considered, and a necessary and sufficient condition for either type of error correction is established. For burst-error-correcting codes, the problem treated is (for a fixed burst length and redundancy) the minimization of the error-free distance ("guard space") required between bursts. A lower bound is obtained on the guard space, and in certain cases, codes which realize this bound are given. A general code which is close to the lower bound in many cases is also given. For independent errors, a code which will correct any error, provided that no consecutive "n" positions have more than "e" digits in error, is discussed. Fore = 1, a necessary and sufficient condition onnis derived; fore > 1, a lower bound onnis obtained, and for the case of redundancy1/2, an upper bound onnis also derived.     

Binary convolutional codes with application to magnetic recording

Calderbank, Heegard, and Ozarow [1] have suggested a method of designing codes for channels with intersymbol interference, such as the magnetic recording channel. These codes are designed to exploit intersymbol interference. The standard method is to minimize intersymbol interference by constraining the input to the channel using run-length limited sequences. Calderbank, Heegard, and Ozarow considered an idealized model of an intersymbol interference channel that leads to the problem of designing codes for a partial response channel with transfer function(1 - D^{N}) /2, where the channel inputs are constrained to bepm 1. This problem is considered here. Channel inputs are generated using a nontrivial coset of a binary convolutional code. The coset is chosen to limit the zero-run length of the output of the channel and so maintain clock synchronization. The minimum squared Euclidean distance between outputs corresponding to distinct inputs is bounded below by the free distance of a second convolutional code which we call the magnitude code. An interesting feature of the analysis is that magnitude codes that are catastrophic may perform better than those that are noncatastrophic.     

Further results on binary convolutional codes with an optimum distance profile (Corresp.)

Fixed binary convolutional codes are considered which are simultaneously optimal or near-optimal according to three criteria: namely, distance profiled, free distanced_{ infty}, and minimum number of weightd_{infty}paths. It is shown how the optimum distance profile criterion can be used to limit the search for codes with a large value ofd_{infty}. We present extensive lists of such robustly optimal codes containing rateR = l/2nonsystematic codes, several withd_{infty}superior to that of any previously known code of the same rate and memory; rateR = 2/3systematic codes; and rateR = 2/3nonsystematic codes. As a counterpart to quick-look-in (QLI) codes which are not "transparent," we introduce rateR = 1/2easy-look-in-transparent (ELIT) codes with a feedforward inverse(1 + D,D). In general, ELIT codes haved_{infty}superior to that of QLI codes.     

Some new constant weight codes (Corresp.)

Nonlinear cyclic codes are constructed which improve on published lower bounds for the numberA(n,d,w)of codewords in a binary code of lengthn, constant weightw, and minimum distanced.     

An upper bound onk/nfor affine-invariant codes with fixedd/n(Corresp.)

An upper bound on the transmission ratiok/nfor binary cyclic codes whose extended codes are invariant under the affine group of permutations, is presented. As a consequence, the transmission ratiok/nof any affine-invariant code with a fixedd(minimum weight)/nis shown to approach zero as the code length n increases. This is an extension of the Lin and Weldon result for primitive BCH codes.     

New family of single-error correcting codes

A construction is given that combines an(n, M_1, d_1)code with an(n, M_2, d_2 = [frac{1}{2}(d_1 + 1)])code to form a(2n, M_1 M_2, d_1)code. This is used to construct a new family of nongroup single-error correcting codes of all lengthsnfrom2^mto 3 ·2^{m-1} - 1, for everym geq 3. These codes have more codewords than any group code of the same length and minimum distance. A number of other nongroup codes are also obtained. Examples of the new codes are (16,2560,3) and (16,36,7) codes, both having more codewords than any comparable group code.     

An error-trapping decoder for nonbinary cyclic codes (Corresp.)

The error-trapping decoder is the simplest way of decoding cyclic codes satisfyingR < 1 / t, wheretis the maximum number of errors to be corrected andRis the code rate. These codes have low rates and/or correct only a few errors. Kasami has used the concept of covering polynomials to demonstrate modified error-trapping decoders for several binary cyclic codes not satisfyingR<1/t. In this paper Kasami's decoder is modified further for correcting multiple symbol errors on nonbinary cyclic codes satisfyingR < 2 / t. The Berlekamp decoder for these codes requires Galois field multiplication and division of two variables which are difficult to implement. Our decoder does not require these multiplications and divisions. Further, for all double-error-correcting codes, and triple-error-correcting codes with rateR < 2/3, an algorithm is presented for finding a minimum set of covering monomials.     

Bounds for codes over the unit circle

LetCbe a code of lengthnand rateRover the alphabetA(Q)={ exp (2pi ir/Q): r=O,1, cdots ,Q-1}, and letd(C)be the minimum Euclidean distance ofC. For largen, the lower and upper bounds are obtained in parametric form on the achievable pairs(R, delta), wheredelta = d^{2}(C)/nholds. To obtain these bounds, the arguments leading to the Gilbert bound and the Elias bound, respectively, are applied to the alphabetA(Q). ForQ rightarrow infty, they are shown to be expressible in terms of the modified Bessel function of the first kind. The Elias type bound is compared with the Kabatyanskii-Levenshtein (K-L) bound that holds for less restrictive alphabets. It turns out that our upper bound improves the K-L bound fordelta leq 0.93.     

A low-rate improvement on the Elias bound (Corresp.)

An upper bound on the minimum distance of binary blocks codes, which is superior to Elias' bound forR < 0.0509^+, is obtained. The new hound has the same derivative(-infty)atR = 0as Gilbert's lower bound. (Elias' bound has derivative-ln 2atR = 0).     

Concerning a bound on undetected error probability (Corresp.)

In the past, it has generally been assumed that the probability of undetected error for an(n,k)block code, used solely for error detection on a binary symmetric channel, is upperbounded by2^{-(n-k)}. In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.     

A lower bound forA(n,4,w)(Corresp.)

An explicit lower bound is given forA(n,4,w), the maximum number of codewords in a binary code of lengthn, minimum distance four, and constant weightw.     

A lower bound on the free distance of convolutional codes related to cyclic codes (Corresp.)

A lower bound is derived on the free distance of certain convolutional codes. This bound is based on the minimum weights of cyclic codes which are derived from the convolutionai code. The bound suggests a method for restricting the search for suitable codes. Some examples of codes are included.     

A new approach to error-correcting codes

A correspondence between linear(n,k,d)codes and algorithms for computing a systempsiofkbilinear forms is established under which the codelengthnis equal to the multiplicative complexity of the algorithm for computingpsi, and the code distancedis underbounded by the minimum number of multiplications required to compute any linear combination of thekforms inpsi. This hitherto unexplored approach to linear codes holds promise of a better understanding of the structure of existing codes as well as for methods of constructing new codes with prescribed rate and distance.     

Further results on the covering radius of codes

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) leq K(n, R)holds for sufficiently largen.     

On quasi-cyclic codes with rate l m (Corresp.)

An integer linear programming problem and an additional divisibility condition are described such that they have a common solution if and only if there is a quasi-cyclic code with rate1/m. A table of binary quasi-cyclic codes with dimensions seven and eight and rate1/mfor smallmis included. In particular, there are binary linear codes with (length, dimension, minimum distance)=(35, 7,16), (42, 7,19), (80, 8, 37), (96, 8, 46), and(112,8,54).