Combinatorial analysis of the minimum distance of turbo codes

In this paper, new upper bounds on the maximum attainable minimum Hamming distance of turbo codes with arbitrary-including the best-interleavers are established using a combinatorial approach. These upper bounds depend on the interleaver length, the code rate, and the scramblers employed in the encoder. Examples of the new bounds for particular turbo codes are given and discussed. The new bounds are tighter than all existing ones and prove that the minimum Hamming distance of turbo codes cannot asymptotically grow at a rate more than the third root of the codeword length     

On Randomized Linear Network Codes and Their Error Correction Capabilities

Randomized linear network code for single source multicast was introduced and analyzed in Ho et al. (IEEE Transactions on Information Theory, October 2006) where the main results are upper bounds for the failure probability of the code. In this paper, these bounds are improved and tightness of the new bounds is studied by analyzing the limiting behavior of the failure probability as the field size goes to infinity. In the linear random coding setting for single source multicast, the minimum distance of the code defined in Zhang, (IEEE Transactions on Information Theory, January 2008) is a random variable taking nonnegative integer values that satisfy the inequality in the Singleton bound recently established in Yeung and Cai (Communications in Information and Systems, 2006) for network error correction codes. We derive a bound on the probability mass function of the minimum distance of the random linear network code based on our improved upper bounds for the failure probability. Codes having the highest possible minimum distance in the Singleton bound are called maximum distance separable (MDS). The bound on the field size required for the existence of MDS codes reported in Zhang, (IEEE Transactions on Information Theory, January 2008) and Matsumoto (arXiv:cs.IT/0610121, Oct. 2006) suggests that such codes exist only when field size is large. Define the degradation of a code as the difference between the highest possible minimum distance in the Singleton bound and the actual minimum distance of the code. The bound for the probability mass function of the minimum distance leads to a bound on the field size required for the existence of network error correction codes with a given maximum degradation. The result shows that allowing minor degradation reduces the field size required dramatically.     

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     

On the computation of the performance probabilities for block codeswith a bounded-distance decoding rule

When a block code is used on a discrete memoryless channel with an incomplete decoding rule that is based on a generalized distance, the probability of decoding failure, the probability of erroneous decoding, and the expected number of symbol decoding errors can be expressed in terms of the generalized weight enumerator polynomials of the code. For the symmetric erasure channel, numerically stable methods to compute these probabilities or expectations are proposed for binary codes whose distance distributions are known, and for linear maximum distance separable (MDS) codes. The method for linear MDS codes saves the computation of the weight distribution and yields upper bounds for the probability of erroneous decoding and for the symbol error rate by the cumulative binomial distribution. Numerical examples include a triple-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) code of length 63 and a Reed-Solomon code of length 1023 and minimum distance 31     

Composition bounds for channel block codes

The performance of Channel block codes for a general channel is studied by examining the relationship between the rate of a code, the joint composition of pairs of codewords, and the probability of decoding error. At fixed rate, lower bounds and upper bounds, both on minimum Bhattacharyya distance between codewords and on minimum equivocation distance between codewords, are derived. These bounds resemble, respectively, the Gilbert and the Elias bounds on the minimum Hamming distance between codewords. For a certain large class of channels, a lower bound on probability of decoding error for low-rate channel codes is derived as a consequence of the upper bound on Bhattacharyya distance. This bound is always asymptotically tight at zero rate. Further, for some channels, it is asymptotically tighter than the straight line bound at low rates. Also studied is the relationship between the bounds on codeword composition for arbitrary alphabets and the expurgated bound for arbitrary channels having zero error capacity equal to zero. In particular, it is shown that the expurgated reliability-rate function for blocks of letters is achieved by a product distribution whenever it is achieved by a block probability distribution with strictly positive components.     

Bounds on distance distributions in codes of known size

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis, we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg, and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.     

Free distance bounds for convolutional codes

The best asymptotic bounds presently known on free distance for convolutional codes are presented from a unified point of view. Upper and lower bounds for both time-varying and fixed codes are obtained. A comparison is made between bounds for nonsystematic and systematic codes which shows that more free distance is available with nonsystematic codes. This result is important when selecting codes for use with sequential or maximum-likelihood (Viterbi) decoding since the probability of decoding error is closely related to the free distance of the code. An ancillary result, used in proving the lower bound on free distance for time-varying nonsystematic codes, furnishes a generalization of two earlier bounds on the definite decoding minimum distance of convolutional codes.     

Upper bounds on the rate of LDPC codes as a function of minimum distance

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.     

Binomial moments of the distance distribution: bounds andapplications

We study a combinatorial invariant of codes which counts the number of ordered pairs of codewords in all subcodes of restricted support in a code. This invariant can be expressed as a linear form of the components of the distance distribution of the code with binomial numbers as coefficients. For this reason we call it a binomial moment of the distance distribution. Binomial moments appear in the proof of the MacWilliams (1963) identities and in many other problems of combinatorial coding theory. We introduce a linear programming problem for bounding these linear forms from below. It turns out that some known codes (1-error-correcting perfect codes, Golay codes, Nordstrom-Robinson code, etc.) yield optimal solutions of this problem, i.e., have minimal possible binomial moments of the distance distribution. We derive several general feasible solutions of this problem, which give lower bounds on the binomial moments of codes with given parameters, and derive the corresponding asymptotic bounds. Applications of these bounds include new lower bounds on the probability of undetected error for binary codes used over the binary-symmetric channel with crossover probability p and optimality of many codes for error detection. Asymptotic analysis of the bounds enables us to extend the range of code rates in which the upper bound on the undetected error exponent is tight     

Minimum distance bounds for cyclic codes and Deligne's theorem

At the present time, there are very good methods to obtain bounds for the minimum distance of BCH codes and their duals. On the other hand, there are few other bounds suitable for general cyclic codes. Therefore, research Problem 9.9 of MacWilliams and Sloane (1977), The Theory of Error-Correcting Codes, asks if the bound of Deligne (1974) for exponential sums in several variables or the bound of Lang and Weil (1954), can be used to obtain bounds on the minimum distance of codes. This question is answered in the affirmative by showing how Deligne's theorem can be made to yield a lower bound on the minimum distance of certain classes of cyclic codes. In the process, an infinite family of binary cyclic codes is presented for which the bound on minimum distance so derived is as tight as possible. In addition, an infinite family of polynomials of degree 3 in 2 variables over a field of characteristic 2, for which Deligne's bound is tight, is exhibited. Finally, a bound is presented for the minimum distance of the duals of the binary subfield subcodes of generalized Reed-Muller codes as well as for the corresponding cyclic codes. It is noted that these codes contain examples of the best binary cyclic codes     

序列的线性复杂度在循环码最小距离下界研究中的应用

本文首先介绍了有限域中傅氏变换及序列线性复杂度的概念,然后简述了循环码最小距离的几个下界,最后用序列的线性复杂度分析了循环码的最小距离,得到了关于最小距离下界的几个新定理。     

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.     

Krawtchouk polynomials and universal bounds for codes and designsin Hamming spaces

Universal bounds for the cardinality of codes in the Hamming space F_rⁿ with a given minimum distance d and/or dual distance d' are stated. A self-contained proof of optimality of these bounds in the framework of the linear programming method is given. The necessary and sufficient conditions for attainability of the bounds are found. The parameters of codes satisfying these conditions are presented in a table. A new upper bound for the minimum distance of self-dual codes and a new lower bound for the crosscorrelation of half-linear codes are obtained     

THE APPLICATION OF LINEAR COMPLEXITY OF SEQUENCES TO LOWER BOUNDS ON THE MINIMUM DISTANCE OF CYCLIC CODES

Firstly,the Fourier transforms in finite fields and the concept of linear complexityof sequences are described.Then several known lower bounds on the minimum distance of cycliccodes are outlined.Finally,the minimum distance of cyclic codes is analyzed via linear complexityof sequences,and new theorems about the lower bounds are obtained.     

Minimum-distance bounds for binary linear codes

This paper presents a table of upper and lower bounds ond_{max} (n,k), the maximum minimum distance over all binary, linear(n,k)error-correcting codes. The table is obtained by combining the best of the existing bounds ond_{max} (n,k)with the minimum distances of known codes and a variety of code-construction techniques.     

二元等距码的Q-变换分布及其应用

研究了二元等距码、等重等距码及其距离分布的Q-变换。通过使用Q-变换分布的性质,研究了二元等距码和等重等距码的最大码字数并得到2个新的上界,这些上界在某些情况下优于已知的结果。     

Six new binary quasi-cyclic codes

Six new quasi-cyclic codes are presented, which improve the lower bounds on the minimum distance for a binary code. A local exhaustive search is used to find these codes and many other quasi-cyclic codes which attain the lower bounds.<>     

Woven codes with outer warp: variations, design, and distanceproperties

We consider convolutional and block encoding schemes which are variations of woven codes with outer warp. We propose methods to evaluate the distance characteristics of the considered codes on the basis of the active distances of the component codes. With this analytical bounding technique, we derived lower bounds on the minimum (or free) distance of woven convolutional codes, woven block codes, serially concatenated codes, and woven turbo codes. Next, we show that the lower bound on the minimum distance can be improved if we use designed interleaving with unique permutation functions in each row of the warp of the woven encoder. Finally, with the help of simulations, we get upper bounds on the minimum distance for some particular codes and then investigate their performance in the Gaussian channel. Throughout this paper, we compare all considered encoding schemes by means of examples, which illustrate their distance properties     

A note on nonlinear Xing codes

Nonlinear Xing codes are considered. It is shown that Xing codes of length p-1 (where p is a prime) are subcodes of cosets of Reed-Solomon codes whose minimum distance equals Xing's lower bound on the minimum distance. This provides a straightforward proof for the lower bound on the minimum distance of the codes. The alphabet size of Xing codes is restricted not to be larger than the characteristic of the relevant finite field F/sub r/. It is shown that codes with the same length and the same lower bounds on the size and minimum distance as Xing codes exist for any alphabet size not exceeding the size r of the relevant finite field, thus extending Xing's results.     

Binary codes with improved minimum weights (Corresp.)

A recent table of Helgert and Stinaff gives bounds ford_{max}(n,k), the maximum minimum distance over all binary linear(n,k)error-correcting codes,1 leq k leq n leq 127. Twelve new codes are constructed which improve lower bounds in the table. Two methods are employed: the algebraic puncturing technique of Solomon and Stiffler and generation by combinatorial incidence matrices.