The serial concatenation of rate-1 codes through uniform random interleavers

Until the analysis of repeat accumulate codes by Divsalar et al. (1998), few people would have guessed that simple rate-1 codes could play a crucial role in the construction of "good" binary codes. We construct "good" binary linear block codes at any rate r<1 by serially concatenating an arbitrary outer code of rate r with a large number of rate-1 inner codes through uniform random interleavers. We derive the average output weight enumerator (WE) for this ensemble in the limit as the number of inner codes goes to infinity. Using a probabilistic upper bound on the minimum distance, we prove that long codes from this ensemble will achieve the Gilbert-Varshamov (1952) bound with high probability. Numerical evaluation of the minimum distance shows that the asymptotic bound can be achieved with a small number of inner codes. In essence, this construction produces codes with good distance properties which are also compatible with iterative "turbo" style decoding. For selected codes, we also present bounds on the probability of maximum-likelihood decoding (MLD) error and simulation results for the probability of iterative decoding error.     

Construction of Quasi-Cyclic LDPC Codes for AWGN and Binary Erasure Channels: A Finite Field Approach

In the late 1950s and early 1960s, finite fields were successfully used to construct linear block codes, especially cyclic codes, with large minimum distances for hard-decision algebraic decoding, such as Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes. This paper shows that finite fields can also be successfully used to construct algebraic low-density parity-check (LDPC) codes for iterative soft-decision decoding. Methods of construction are presented. LDPC codes constructed by these methods are quasi-cyclic (QC) and they perform very well over the additive white Gaussian noise (AWGN), binary random, and burst erasure channels with iterative decoding in terms of bit-error probability, block-error probability, error-floor, and rate of decoding convergence, collectively. Particularly, they have low error floors. Since the codes are QC, they can be encoded using simple shift registers with linear complexity.     

Linear block codes for error detection (Corresp.)

The probability of undetected error of linear block codes for use on a binary symmetric channel is investigated. Upper hounds are derived. Several classes of linear block codes are proved to have good error-detecting capability.     

Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes

The performance of maximum-likelihood (ML) decoded binary linear block codes is addressed via the derivation of tightened upper bounds on their decoding error probability. The upper bounds on the block and bit error probabilities are valid for any memoryless, binary-input and output-symmetric communication channel, and their effectiveness is exemplified for various ensembles of turbo-like codes over the additive white Gaussian noise (AWGN) channel. An expurgation of the distance spectrum of binary linear block codes further tightens the resulting upper bounds     

On the Probability of Undetected Error for Linear Block Codes

The problem of computing the probability of undetected error is considered for linear block codes used for error detection. The recent literature is first reviewed and several results are extended. It is pointed out that an exact calculation can be based on either the weight distribution of a code or its dual. Using the dual code formulation, the probability of undetected error for the ensemble of all nonbinary linear block codes is derived as well as a theorem that shows why the probability of undetected error may not be a monotonic function of channel error rate for some poor codes. Several bounds on the undetected error probability are then presented. We conclude with detailed examples of binary and nonbinary codes for which exact results can be obtained. An efficient technique for measuring an unknown weight distribution is suggested and exact results are compared with experimental results.     

Exact Probabilistic Analysis of Memoryless Combiners

Exact analytical expressions for various probability distributions in a type of stream ciphers known as memoryless combiners are derived. They relate to arbitrary linear functions and subvectors of output bits as well as to arbitrary linear functions and subvectors of input bits when the output sequence is assumed to be given. Practical approximations to the exact expressions to be used in one-step and iterative fast correlation attacks and statistical distinguishers are proposed. More generally, the results also apply to arbitrary binary linear codes that are nonlinearly transformed by time-variant Boolean functions. For comparison, the corresponding probability distributions for linear block codes on a memoryless time-variant binary symmetric channel are also determined and some practical consequences pointed out.     

A lower bound on the undetected error probability and strictlyoptimal codes

Error detection is a simple technique used in various communication and memory systems to enhance reliability. We study the probability that a q-ary (linear or nonlinear) block code of length n and size M fails to detect an error. A lower bound on this undetected error probability is derived in terms of q, n, and M. The new bound improves upon other bounds mentioned in the literature, even those that hold only for linear codes. Block codes whose undetected error probability equals the new lower bound are investigated. We call these codes strictly optimal codes and give a combinatorial characterization of them. We also present necessary and sufficient conditions for their existence. In particular, we find all values of n and M for which strictly optimal binary codes exist, and determine the structure of all of them. For example, we construct strictly optimal binary-coded decimal codes of length four and five, and we show that these are the only possible lengths of such codes     

Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.     

A Study on Universal Codes With Finite Block Lengths

Based on random codes and typical set decoding, an alternative proof of Root and Varaiya's compound channel coding theorem for linear Gaussian channels is presented. The performance limit of codes with finite block length under a compound channel is studied through error bounds and simulation. Although the theorem promises uniform convergence of the probability of error as the block length approaches infinity, with short block lengths the performance can differ considerably for individual channels. Simulation results show that universal performance can be a practical goal as the block lengths become large.     

关于线性分组码的不可检错误概率

本文给出了检错好码的定义,证明了GF(2)上的(n,k)线性分组码为检错好码的充要条件是其对偶码也为检错好码。文中还得到了关于检错好码的一系列新的结果。对二元(n,k)线性分组码,我们给出了不可检错误概率新的下限。这些限只与n和k有关,而与码的重量结构无关。     

Optimum cycle redundancy-check codes with 16-bit redundancy

Optimal binary cyclic redundancy-check codes with 16 parity bits (CRC-16 codes) are presented and compared to those in existing standards for minimum-distance, undetected-error probability on binary symmetric channels (BSCs) and properness. The codes in several cases are seen to be superior at block lengths of practical interest when they are used on low-noise BSCs. The optimum minimum distance obtainable by some CRC-16 codes is determined for all block lengths. For several typical low-noise BSCs the minimum undetected error probability achievable with some CRC-16 codes is given for all block lengths     

Simple MAP decoding of first-order Reed-Muller and Hamming codes

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.     

Stopping set distribution of LDPC code ensembles

Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)<1, and in particular for almost all codes with smallest variable degree >2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/.     

Comparison of decoding algorithms of binary linear block codes inRayleigh fading channels with diversity reception

The word error probability of binary linear block codes is evaluated in Rayleigh fading channels with diversity reception for three decoding algorithms: error correction (EC), error/erasure correction (EEC), and maximum likelihood (ML) soft decoding algorithms. The performance advantage of EEC over EC in the required average SNR decreases as the number of diversity channels increases. The performance advantage of EEC over EC does not depend on the specific value of word error probability although the advantage of ML soft decoding over EC increases for lower word error probability     

Generalized IRA Erasure Correcting Codes for Hybrid Iterative/Maximum Likelihood Decoding

The design of low-density parity-check (LDPC) codes under hybrid iterative / maximum likelihood decoding is addressed for the binary erasure channel (BEC). Specifically, we focus on generalized irregular repeat-accumulate (GeIRA) codes, which offer both efficient encoding and design flexibility. We show that properly designed GeIRA codes tightly approach the performance of an ideal maximum distance separable (MDS) code, even for short block sizes. For example, our (2048,1024) code reaches a codeword error rate of 10^-5 at channel erasure probability isin= 0.450, where an ideal (2048,1024) MDS code would reach the same error rate at isin = 0.453.     

Coding theorems for the nonsynchronized channel

Capacity and error bounds are derived for a memoryless binary symmetric channel with the receiver having no a priori information as to the starting time of the code words. The channel capacity is the same as the capacity of the synchronized channel. For all rates below capacity, the minimum probability of error for the nonsynchronized channel decreases exponentially with the code-block length. For rates near channel capacity, the exponent in the upper bound on the probability of error for the nonsynchronized channel is the same as the corresponding exponent for the synchronized channel. For low rates, the largest exponent obtained for the nonsynchronized channel with conventional block coding is inferior to the exponent obtained for the synchronized channel. Stronger results are obtained for a new form of coding that allows for a Markov dependency between successive code words. Bounds on the minimum probability of error are obtained for unconstrained binary codes and for several classes of parity-check codes and are used to obtain asymptotic distance properties for various classes of binary codes. At certain rates there exist codes whose minimum distance, in the comma-free sense, is not only greater than one, but is proportional to the block length.     

Two topics on linear unequal error protection codes: Bounds on their length and cyclic code classes

It is possible for a linear block code to provide more protection for selected positions in the input message words than is guaranteed by the minimum distance of the code. Linear codes having this property are called linear unequal error protection (LUEP) codes. Bounds on the length of a LUEP code that ensures a given unequal error protection are derived. A majority decoding method for certain classes of cyclic binary UEP codes is treated. A list of short (i.e., of length less than 16) binary LUEP codes of optimal (i.e., minimal) length and a list of all cyclic binary UEP codes of length less than 40 are included.     

On general Gilbert bounds

We define a distance measure for block codes used over memoryless channels and show that it is related to upper and lower bounds on the low-rate error probability in the same way as Hamming distance is for binary block codes used over the binary symmetric channel. We then prove general Gilbert bounds for block codes using this distance measure. Some new relationships between coding theory and rate-distortion theory are presented.     

Undetected error probabilities of binary primitive BCH codes forboth error correction and detection

We investigate the undetected error probabilities for bounded-distance decoding of binary primitive BCH codes when they are used for both error correction and detection on a binary symmetric channel. We show that the undetected error probability of binary linear codes can be simplified and quantified if the weight distribution of the code is binomial-like. We obtain bounds on the undetected error probability of binary primitive BCH codes by applying the result to the code and show that the bounds are quantified by the deviation factor of the true weight distribution from the binomial-like weight distribution     

Probabilistic hard-decision table look-up decoding for binary block codes

A probabilistic hard-decision decoding algorithm based on the weight distribution of binary block codes and the random error distribution in the channel is briefly described. It reduces the number of look-up iterations performed in the conventional exhaustive search table look-up minimum distance decoder.