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

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

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     

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     

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.     

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.     

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     

New quasi-twisted degenerate ternary linear codes

Twenty six ternary linear quasi-twisted codes improving the best known lower bounds on minimum distance are constructed.     

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.     

Bounds for Binary Codes With Narrow Distance Distributions

New lower bounds are presented on the second moment of the distance distribution of binary codes, in terms of the first moment of the distribution. These bounds are used to obtain upper bounds on the size of codes whose maximum distance is close to their minimum distance. It is then demonstrated how such bounds can be applied to bound from below the smallest attainable ratio between the maximum distance and the minimum distance of codes. Finally, counterparts of the bounds are derived for the special case of constant-weight codes.     

New binary codes from a chain of cyclic codes

Starting with a chain of cyclic linear binary codes of length 127, linear binary codes of lengths 129-167, and dimensions 30-50 are constructed. Some of these codes have a minimum distance exceeding the lower bound given in Brouwer's table     

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.     

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.     

New binary one-generator quasi-cyclic codes

Sixteen new binary quasi-cyclic linear codes improving the best known lower bounds on minimum distance in Brouwer's tables are constructed. The parameters of these codes are [102, 26, 32], [102, 27, 30], [142, 35, 40], [142, 36, 38] [146, 36, 40], [170, 16, 72], [170, 20, 66], [170, 33, 52] [170, 36, 50], [178, 33, 56], [178, 34, 54], [182, 27, 64] [182, 36, 56], [186, 17, 76], [210, 23, 80], [254, 22, 102] Sixty cyclic and thirty quasi-cyclic codes, which attain the respective bounds in Brouwer's table and are not included in Chen's table are presented as well.     

Entropy/length profiles, bounds on the minimal covering ofbipartite graphs, and trellis complexity of nonlinear codes

The trellis representation of nonlinear codes is studied from a new perspective. We introduce the new concept of entropy/length profile (ELP). This profile can be considered as an extension of the dimension/length profile (DLP) to nonlinear codes. This elaboration of the DLP, the entropy/length profiles, appears to be suitable to the analysis of nonlinear codes. Additionally and independently, we use well-known information-theoretic measures to derive novel bounds on the minimal covering of a bipartite graph by complete subgraphs. We use these bounds in conjunction with the ELP notion to derive both lower and upper bounds on the state complexity and branch complexity profiles of (nonlinear) block codes represented by any trellis diagram. We lay down no restrictions on the trellis structure, and we do not confine the scope of our results to proper or one-to-one trellises only. The basic lower bound on the state complexity profile implies that the state complexity at any given level cannot be smaller than the mutual information between the past and the future portions of the code at this level under a uniform distribution of the codewords. We also devise a different probabilistic model to prove that the minimum achievable state complexity over all possible trellises is not larger than the maximum value of the above mutual information over all possible probability distributions of the codewords. This approach is pursued further to derive similar bounds on the branch complexity profile. To the best of our knowledge, the proposed upper bounds are the only upper bounds that address nonlinear codes. The novel lower bounds are tighter than the existing bounds. The new quantities and bounds reduce to well-known results when applied to linear codes     

Soft decision decoding of Reed-Solomon codes

This paper presents a maximum-likelihood decoding (MLD) and a suboptimum decoding algorithm for Reed-Solomon (RS) codes. The proposed algorithms are based on the algebraic structure of the binary images of RS codes. Theoretical bounds on the performance are derived and shown to be consistent with simulation results. The proposed suboptimum algorithm achieves near-MLD performance with significantly lower decoding complexity. It is also shown that the proposed suboptimum, algorithm has better performance compared with generalized minimum distance decoding, while the proposed MLD algorithm has significantly lower decoding complexity than the well-known Vardy-Be'ery (1991) MLD algorithm.     

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.     

Packing radius, covering radius, and dual distance

Tietaivainen (1991) derived an upper bound on the covering radius of codes as a function of the dual distance. This was generalized to the minimum distance, and to Q-polynomial association schemes by Levenshtein and Fazekas. Both proofs use a linear programming approach. In particular, Levenshtein and Fazekas (1990) use linear programming bounds for codes and designs. In this article, proofs relying solely on the orthogonality relations of Krawtchouk (1929), Lloyd, and, more generally, Krawtchouk-adjacent orthogonal polynomials are derived. As a by-product upper bounds on the minimum distance of formally self-dual binary codes are derived     

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     

Combined coding and modulation: theory and applications

The theoretical aspects of the encoding process are investigated, resulting in a precise definition of linear codes together with theorems that clarify how they can be obtained. A particular subset of linear codes, called superlinear codes, for which the performance analysis is highly simplified is identified. The most relevant performance measures for the analysis of this class of codes are discussed. The minimum Euclidean distance and the event and bit error probabilities are found analytically using the uniform error property (when applicable) or variations on it. This yields accurate upper and lower bounds to the error rate at the price of reasonable computational complexity. The theory is then applied to the search for `good' codes and to their performance evaluation. The cases of 16- and 32-PSK codes, which are good candidates for use in digital satellite transmission, are considered. Several new results in terms of error event and bit error probabilities are presented, showing considerable gains in terms of SNR with respect to the uncoded case