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     

Distance properties of expander codes

The minimum distance of some families of expander codes is studied, as well as some related families of codes defined on bipartite graphs. The weight spectrum and the minimum distance of a random ensemble of such codes are computed and it is shown that it sometimes meets the Gilbert-Varshamov (GV) bound. A lower bound on the minimum distances of constructive families of expander codes is derived. The relative minimum distance of the expander code is shown to exceed the product bound, i.e., the quantity /spl delta//sub 0//spl delta//sub 1/ where /spl delta//sub 0/ and /spl delta//sub 1/ are the minimum relative distances of the constituent codes. As a consequence of this, a polynomially constructible family of expander codes is obtained whose relative distance exceeds the Zyablov bound on the distance of serial concatenations.     

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.     

Strengthened lower bound on definite decoding minimum distance for periodic convolutional codes (Corresp.)

A new lower bound on definite decoding minimum distance for the class of systematic binary periodic convolutional codes is presented. The bound is everywhere stronger than Wagner's bound and has the same form as the bound obtained by Massey for the class of systematic binary fixed convolutional codes. The bound is also shown to apply to a specific subclass of simply implemented periodic codes for which Wagner's bound also holds.     

一种具有最小距离下界的正则LDPC码的构造

主要提出一种新的计算规则LDPC(low-density parity-check)码的最小距离下界的方法。该方法是基于LDPC码的每个变量节点的独立树进行构造LDPC码。与随机构造的LDPC码和用PEG方法构造的方法比较,这个新的构造方法得到了更大的围长和最小距离下界。在AWGN信道中,在码长N=1 008和N=1 512时进行Matlab仿真,仿真结果表明随着信噪比的增加此方法构造的LDPC码有优异的误码率性能。     

Doubly-Generalized LDPC Codes: Stability Bound Over the BEC

The iterative decoding threshold of low-density parity-check (LDPC) codes over the binary erasure channel (BEC) fulfills an upper bound depending only on the variable and check nodes with minimum distance $2$. This bound is a consequence of the stability condition, and is here referred to as stability bound. In this paper, a stability bound over the BEC is developed for doubly-generalized LDPC codes, where variable and check nodes can be generic linear block codes, assuming maximum a posteriori erasure correction at each node. It is proved that also in this generalized context the bound depends only on the variable and check component codes with minimum distance $2$. A condition is also developed, namely, the derivative matching condition, under which the bound is achieved with equality. The stability bound leads to consider single parity-check codes used as variable nodes as an appealing option to overcome common problems created by generalized check nodes.      

DC-free error-correcting codes based on convolutional codes

A new construction of direct current (DC)-free error-correcting codes based on convolutional codes is proposed. The new code is constructed by selecting a proper subcode from a convolutional code composed of two different component codes. The encoder employs a Viterbi algorithm as the codeword selector so that the selected code sequences satisfy the DC constraint. A lower bound on the free distance of such codes is proposed, and a procedure for obtaining this bound is presented. A sufficient condition for these codes to have a bounded running digital sum (RDS) is proposed. Under the assumption of a simplified codeword selection algorithm, we present an upper bound on the maximum absolute value of the RDS and derive the sum variance for a given code. A new construction of standard DC-free codes, i.e., DC-free codes without error-correcting capability, is also proposed. These codes have the property that the decoder can be implemented by simple symbol-by-symbol hard decisions. Finally, under the new construction, we propose several codes that are suitable for the systems that require small sum variance and good error-correction capability     

On the stopping distance of finite geometry LDPC codes

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.     

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.     

A New Bound for the Minimum Distance of a Cyclic Code From Its Defining Set

A new lower bound for the distance of cyclic codes is proposed. This bound depends on the defining set of the code, like several other bounds. The proposed bound improves upon the Bose-Chaudhuri-Hocquehghen (BCH) bound and, for some codes, improves upon the Hartmann-Tzeng bound and the Roos bound as well     

Sequential decoding of systematic and nonsystematic convolutional codes with arbitrary decoder bias

This paper presents several results involving Fano's sequential decoding algorithm for convolutional codes. An upper bound to theath moment of decoder computation is obtained for arbitrary decoder biasBanda leq 1. An upper bound on error probability with sequential decoding is derived for both systematic and nonsystematic convolutional codes. This error bound involves the exact value of the decoder biasB. It is shown that there is a trade-off between sequential decoder computation and error probability as the biasBis varied. It is also shown that for many values ofB, sequential decoding of systematic convolutional codes gives an exponentially larger error probability than sequential decoding of nonsystematic convolutional codes when both codes are designed with exponentially equal optimum decoder error probabilities.     

Commutative group codes for the Gaussian channel

A class of codes for the Gaussian channel is analyzed. The code class is a subclass of the group codes for the Gaussian channel described by Slepian. Using the vector model for the Gaussian channel, the code vectors are obtained by transformations of an initial vector. The class of codes in which the transformations form a commutative group is called the class of commutative group codes. The performance of the codes is evaluated using the union bound on the error probability as a performance measure. The union bound is shown to be closely related to the moments of the scalar product between the code vectors. Commutative group codes are described. It is shown that linear algebraic codes may be represented as commutative group codes. The code class is also shown to include simplex and biorthogonal codes in all dimensions.     

New results on self-orthogonal unequal error protection codes

A lower bound on the length of binary self-orthogonal unequal error protection (UEP) codes is derived, and two design procedures for constructing optimal self-orthogonal UEP codes are proposed. With this lower bound, known self-orthogonal UEP codes can be evaluated. It is pointed out that, for given values of minimum distance and code rate, the self-orthogonal codes must be relatively long, so optimal self-orthogonal codes are not optimal in general. But self-orthogonal codes can be implemented simply, and they have error-correcting capabilities beyond those guaranteed by their minimum distance. These properties can be viewed as a partial compensation for using self-orthogonal codes     

Information-theoretic bounds for authentication codes and block designs

Authentication codes with secrecy and with splitting are investigated. An information-theoretic lower bound for the probability of successful deception for a spoofing attack of order r is obtained. The condition necessary on authentication codes to achieve the lower bound is determined as a single simple requirement. Based on the simplicity of the result a construction, by use of so-called partially balanced t-designs, for authentication codes that can achieve the lower bound is suggested.This research was partially supported by a K. C. Wong Fellowship.     

Upper bound on the minimum distance of turbo codes

An upper bound on the minimum distance of turbo codes is derived, which depends only on the interleaver length and the component scramblers employed. The derivation of this bound considers exclusively turbo encoder input words of weight 2. The bound does not only hold for a particular interleaver but for all possible interleavers including the best. It is shown that in contrast to general linear binary codes the minimum distance of turbo codes cannot grow stronger than the square root of the block length. This implies that turbo codes are asymptotically bad. A rigorous proof for the bound is provided, which is based on a geometric approach     

Better Binary List Decodable Codes Via Multilevel Concatenation

A polynomial time construction of binary codes with the currently best known tradeoff between rate and error-correction radius is given. Specifically, linear codes over fixed alphabets are constructed that can be list decoded in polynomial time up to the so-called Blokh–Zyablov bound. The work builds upon earlier work by the authors where codes list decodable up to the Zyablov bound (the standard product bound on distance of concatenated codes) were constructed. The new codes are constructed via a (known) generalization of code concatenation called multilevel code concatenation. A probabilistic argument, which is also derandomized via conditional expectations, is used to show the existence of inner codes with a certain nested list decodability property that is appropriate for use in multilevel concatenated codes. A “level-by-level” decoding algorithm, which crucially uses the list recovery algorithm for the outer folded Reed–Solomon codes, enables list decoding up to the designed distance bound, aka the Blokh–Zyablov bound, for multilevel concatenated codes.      

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     

Linear-time encodable/decodable codes with near-optimal rate

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1-r-/spl epsiv/)/2 of errors over an alphabet of constant size depending only on /spl epsiv/, for every 00. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures; our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the Zyablov bound, and also the more general Blokh-Zyablov bound (by resorting to multilevel concatenation). Our work also yields linear-time encodable/decodable codes which match Forney's error exponent for concatenated codes for communication over the binary symmetric channel. The encoding/decoding complexity was quadratic in Forney's result, and Forney's bound has remained the best constructive error exponent for almost 40 years now. In summary, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear-time encoding and decoding algorithms.     

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.     

Systematic construction of self-orthogonal diffuse codes

A systematic procedure for constructing binary self-orthogonal diffuse codes is presented. These codes correct both random and burst errors. A lower bound on actual constraint length for this class of codes is found. The given construction procedure generally yields codes that approach the lower bound for large burst error correction and are, therefore, asymptotically optimal.