The intractability of computing the minimum distance of a code

It is shown that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This result constitutes a proof of the conjecture of Berlekamp, McEliece, and van Tilborg (1978). Extensions and applications of this result to other problems in coding theory are discussed     

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 new lower bound for the minimum distance of a cyclic code

A new lower bound for the minimum distance of a linear code is derived. When applied to cyclic codes both the Bose-Chaudhuri-Hocquenghem (BCH) bound and the Hartmann-Tzeng (HT) bound are obtained as corollaries. Examples for which the new bound is superior to these two bounds, as well as to the Carlitz-Uchiyama bound, are given.     

Construction of linear codes with large minimum distance

A natural goal in coding theory is to find a linear [n, k;q]-code such that the minimum distance d is maximal. In this paper, we introduce an algorithm to construct linear [n, k;q]-codes with a prescribed minimum distance d by constructing an equivalent structure, the so-called minihyper, which is a system of points in the (k - 1)-dimensional projective geometry P/sub k-1/(q) over the finite field F/sub q/ with q elements. To construct such minihypers we first prescribe a group of automorphisms, transform the construction problem to a diophantine system of equations, and then apply a lattice-point-enumeration algorithm to solve this system of equations. Finally, we present a list of parameters of new codes that we constructed with the introduced method. For example, there is a new optimal [80, 4; 8]-code with minimum distance 68.     

Limit distribution of the minimum distance of random linear codes

The distribution of the ratio of minimum distance to code length of a random linear code approaches a step distribution as the code length becomes arbitrarily large at fixed code rate. The location of the step is at the smaller value ofpsatisfying1 + p log_{2}p + (1 - p) log_{2} (1 - p) = k/n.     

Performance of low-density parity-check codes with linear minimum distance

This correspondence studies the performance of the iterative decoding of low-density parity-check (LDPC) code ensembles that have linear typical minimum distance and stopping set size. We first obtain a lower bound on the achievable rates of these ensembles over memoryless binary-input output-symmetric channels. We improve this bound for the binary erasure channel. We also introduce a method to construct the codes meeting the lower bound for the binary erasure channel. Then, we give upper bounds on the rate of LDPC codes with linear minimum distance when their right degree distribution is fixed. We compare these bounds to the previously derived upper bounds on the rate when there is no restriction on the code ensemble.     

On the complexity of minimum distance decoding of long linear codes

We suggest a decoding algorithm of q-ary linear codes, which we call supercode decoding. It ensures the error probability that approaches the error probability of minimum-distance decoding as the length of the code grows. For n→∞ the algorithm has the maximum-likelihood performance. The asymptotic complexity of supercode decoding is exponentially smaller than the complexity of all other methods known. The algorithm develops the ideas of covering-set decoding and split syndrome decoding     

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     

Construction of some binary linear codes of minimum distance five

A method of constructing binary linear codes that have a minimum Hamming distance of five is presented. The author proposes a general formulation of the parity check matrix for the desired code and then derives necessary conditions for the code to have a minimum distance of five. Some new codes that satisfy the necessary conditions are described. Some efficient new codes are obtained. In particular, a (47,36,5) code is obtained that has six more information bits than the best previously known code with 11 check bits     

Maximalq-nary linear codes with large minimum distance (Corresp.)

This correspondence presents a complete solution to the problem of constructing maximalq-nary codes, for any word lengthnand minimum distancedin the regionqd geq (q - 1)n. Several interesting results regarding the interdependence of these codes are developed, which reveal the unique structure of the code spaces of the regionqd geq (q - 1)n. Some new maximal codes are obtained for the regionqd < (q - 1)n.     

Generalized minimum distance decoding

We introduce a new distance measure which permits likelihood information to be used in algebraic minimum distance decoding techniques. We give an efficient decoding algorithm, and develop exponential bounds on the probability of not decoding correctly. In one application, this technique yields the same probability of error as maximum likelihood decoding.     

On the minimum distance of cyclic codes

The main result is a new lower bound for the minimum distance of cyclic codes that includes earlier bounds (i.e., BCH bound, HT bound, Roos bound). This bound is related to a second method for bounding the minimum distance of a cyclic code, which we call shifting. This method can be even stronger than the first one. For all binary cyclic codes of length< 63(with two exceptions), we show that our methods yield the true minimum distance. The two exceptions at the end of our list are a code and its even-weight subcode. We treat several examples of cyclic codes of lengthgeq 63.     

Endcoding complexity versus minimum distance

A bound on the minimum distance of a binary error-correcting code is established given constraints on the computational time-space complexity of its encoder where the encoder is modeled as a branching program. The bound obtained asserts that if the encoder uses linear time and sublinear memory in the most general sense, then the minimum distance of the code cannot grow linearly with the block length when the rate is nonvanishing, that is, the minimum relative distance of the code tends to zero in such a setting. The setting is general enough to include nonserially concatenated turbo-like codes and various generalizations. Our argument is based on branching program techniques introduced by Ajtai. The case of constant-depth AND-OR circuit encoders with unbounded fanins are also considered.     

An asymptotic Hamming bound on the feedback decoding minimum distance of linear tree codes (Corresp.)

An asymptotic Hamming bound for tree codes is derived. This bound is not new, it has been obtained earlier by Pinsker. However, Markov chains were used by Pinsker in its proof whereas more direct methods are used here.     

Quantum codes of minimum distance two

It is reasonable to expect the theory of quantum codes to be simplified in the case of codes of minimum distance 2; thus it makes sense to examine such codes in the hopes that techniques that prove effective there will generalize. With this in mind, we present a number of results on codes of minimum distance 2. We first compute the linear programming bound on the dimension of such a code, then show that this bound can only be attained when the code either is of even length, or is of length 3 or 5. We next consider questions of uniqueness, showing that the optimal code of length 2 or 1 is unique (implying that the well-known one-qubit-in-five single-error correcting code is unique), and presenting nonadditive optimal codes of all greater even lengths. Finally, we compute the full automorphism group of the more important distance 2 codes, allowing us to determine the full automorphism group of any GF(4)-linear code     

On the minimum distance of composite-length BCH codes

In this letter, we derive a theorem which generalizes Theorem 3 in Chapter 9 of the book “The Theory of Error-Correcting Codes” by F.J. MacWilliams and N.J.A. Sloane (North-Holland, 1977). By this theorem, we are able to give several classes of BCH codes of composite length whose minimum distance does not exceed the BCH bound. Moreover, we show that this theorem can also be used to determine the true minimum distance of some other cyclic codes with composite-length     

On the minimum distance of ternary cyclic codes

There are many ways to find lower bounds for the minimum distance of a cyclic code, based on investigation of the defining set. Some new theorems are derived. These and earlier techniques are applied to find lower bounds for the minimum distance of ternary cyclic codes. Furthermore, the exact minimum distance of ternary cyclic codes of length less than 40 is computed numerically. A table is given containing all ternary cyclic codes of length less than 40 and having a minimum distance exceeding the BCH bound. It seems that almost all lower bounds are equal to the minimum distance. Especially shifting, which is also done by computer, seems to be very powerful. For length 40⩽n⩽50, only lower bounds are computed. In many cases (derived theoretically), however, these lower bounds are equal to the minimum distance     

More on the minimum distance of cyclic codes

It was recently shown that the so-called Jensen bound is generally weaker than the product method and the shifting method introduced by van Lint and Wilson (1986). It is shown that the minimum distance of the two cyclic codes of length 65 (for which it is known that the product method does not produce the desired result) can be proved using Jensen's method (1985) with some adaptations     

Bounds on the minimum distance of trellis codes

The performance of trellis codes is determined by their minimum Euclidean distance. Upper bounds on this minimum distance valid for phase-shift-keyed (PSK) signals that improve on previously derived bounds are derived. Although the bound is valid only for PSK signals, the bounding techniques developed here can be extended to other equal-energy configurations and hence could pave the way to obtaining more general results