Parity-Check Density Versus Performance of Binary Linear Block Codes: New Bounds and Applications

The moderate complexity of low-density parity-check (LDPC) codes under iterative decoding is attributed to the sparseness of their parity-check matrices. It is therefore of interest to consider how sparse parity-check matrices of binary linear block codes can be a function of the gap between their achievable rates and the channel capacity. This issue was addressed by Sason and Urbanke, and it is revisited in this paper. The remarkable performance of LDPC codes under practical and suboptimal decoding algorithms motivates the assessment of the inherent loss in performance which is attributed to the structure of the code or ensemble under maximum-likelihood (ML) decoding, and the additional loss which is imposed by the suboptimality of the decoder. These issues are addressed by obtaining upper bounds on the achievable rates of binary linear block codes, and lower bounds on the asymptotic density of their parity-check matrices as a function of the gap between their achievable rates and the channel capacity; these bounds are valid under ML decoding, and hence, they are valid for any suboptimal decoding algorithm. The new bounds improve on previously reported results by Burshtein and by Sason and Urbanke, and they hold for the case where the transmission takes place over an arbitrary memoryless binary-input output-symmetric (MBIOS) channel. The significance of these information-theoretic bounds is in assessing the tradeoff between the asymptotic performance of LDPC codes and their decoding complexity (per iteration) under message-passing decoding. They are also helpful in studying the potential achievable rates of ensembles of LDPC codes under optimal decoding; by comparing these thresholds with those calculated by the density evolution technique, one obtains a measure for the asymptotic suboptimality of iterative decoding algorithms     

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.     

Decoding and Design of LDPC Codes for High-Order Modulations

A concatenated code model is proposed for high-order low-density parity-check (LDPC) coded modulations. A corresponding concatenated-code belief propagation (CCBP) decoding algorithm is derived for our proposed concatenated code. Moreover, the design of LDPC codes under the CCBP decoding is developed using extrinsic information transfer (EXIT) charts. Compared with other algorithms, the CCBP method provides an excellent parallel decoding process, and the EXIT-based design method offers highly accurate LDPC code ensembles. Simulation results show that the performance of the proposed CCBP algorithm is superior to that of the conventional belief propagation decoding within a wide range of modulation orders, and the EXIT-based method can design capacity-approaching LDPC codes for high-order modulations.     

On Achievable Rates and Complexity of LDPC Codes Over Parallel Channels: Bounds and Applications

A variety of communication scenarios can be modeled by a set of parallel channels. Upper bounds on the achievable rates under maximum-likelihood (ML) decoding, and lower bounds on the decoding complexity per iteration of ensembles of low-density parity-check (LDPC) codes are presented. The communication of these codes is assumed to take place over statistically independent parallel channels where the component channels are memoryless, binary-input, and output-symmetric. The bounds are applied to ensembles of punctured LDPC codes where the puncturing patterns are either random or possess some structure. Our discussion is concluded by a diagram showing interconnections between the new theorems and some previously reported results     

Capacity Achieving LDPC Codes Through Puncturing

The performance of punctured low-definition parity-check (LDPC) codes under maximum-likelihood (ML) decoding is studied in this correspondence via deriving and analyzing their average weight distributions (AWDs) and the corresponding asymptotic growth rate of the AWDs. In particular, it is proved that capacity-achieving codes of any rate and for any memoryless binary-input output-symmetric (MBIOS) channel under ML decoding can be constructed by puncturing some original LDPC code with small enough rate. Moreover, it is shown that the gap to capacity of all the punctured codes can be the same as the original code with a small enough rate. Conditions under which puncturing results in no rate loss with asymptotically high probability are also given in the process. These results show high potential for puncturing to be used in designing capacity-achieving codes, and in rate-compatible coding under any MBIOS channel.      

Capacity-achieving codes for finite-state channels with maximum-likelihood decoding

Codes on sparse graphs have been shown to achieve remarkable performance in point-to-point channels with low decoding complexity. Most of the results in this area are based on experimental evidence and/or approximate analysis. The question of whether codes on sparse graphs can achieve the capacity of noisy channels with iterative decoding is still open, and has only been conclusively and positively answered for the binary erasure channel. On the other hand, codes on sparse graphs have been proven to achieve the capacity of memoryless, binary-input, output-symmetric channels with finite graphical complexity per information bit when maximum likelihood (ML) decoding is performed. In this paper, we consider transmission over finite-state channels (FSCs). We derive upper bounds on the average error probability of code ensembles with ML decoding. Based on these bounds we show that codes on sparse graphs can achieve the symmetric information rate (SIR) of FSCs, which is the maximum achievable rate with independently and uniformly distributed input sequences. In order to achieve rates beyond the SIR, we consider a simple quantization scheme that when applied to ensembles of codes on sparse graphs induces a Markov distribution on the transmitted sequence. By deriving average error probability bounds for these quantized code ensembles, we prove that they can achieve the information rates corresponding to the induced Markov distribution, and thus approach the FSC capacity.     

LDPC编译码算法分析

低密度奇偶校验(LDPC)码是一种线性分组码,其纠错能力可以接近香农极限。针对LDPC码的编译码问题,分析了校验矩阵的构造方法。给出了LDPC码的编码算法以及算法的实现结构。分析了基于软判决的置信传播(BP)译码算法,并给出了可以进一步降低计算复杂度的简化译码方法。通过仿真对比了不同的译码算法在高斯信道下的译码性能。     

Performance Bounds for Nonbinary Linear Block Codes Over Memoryless Symmetric Channels

The performance of nonbinary linear block codes is studied in this paper via the derivation of new upper bounds on the block error probability under maximum-likelihood (ML) decoding. The transmission of these codes is assumed to take place over a memoryless and symmetric channel. The new bounds, which are based on the Gallager bounds and their variations, are applied to the Gallager ensembles of nonbinary and regular low-density parity-check (LDPC) codes. These upper bounds are also compared with sphere-packing lower bounds. This study indicates that the new upper bounds are useful for the performance evaluation of coded communication systems which incorporate nonbinary coding techniques.      

Coding for Parallel Channels: Gallager Bounds and Applications to Turbo-Like Codes

The transmission of coded communication systems is widely modeled to take place over a set of parallel channels. This model is used for transmission over block-fading channels, rate-compatible puncturing of turbo-like codes, multicarrier signaling, multilevel coding, etc. New upper bounds on the maximum-likelihood (ML) decoding error probability are derived in the parallel-channel setting. We focus on the generalization of the Gallager-type bounds and discuss the connections between some versions of these bounds. The tightness of these bounds for parallel channels is exemplified for structured ensembles of turbo codes, repeat-accumulate (RA) codes, and some of their recent variations (e.g., punctured accumulate-repeat-accumulate codes). The bounds on the decoding error probability of an ML decoder are compared to computer simulations of iterative decoding. The new bounds show a remarkable improvement over the union bound and some other previously reported bounds for independent parallel channels. This improvement is exemplified for relatively short block lengths, and it is pronounced when the block length is increased. In the asymptotic case, where we let the block length tend to infinity, inner bounds on the attainable channel regions of modern coding techniques under ML decoding are obtained, based solely on the asymptotic growth rates of the average distance spectra of these code ensembles.     

一种新的LDPC译码算法

由于LDPC码的优良性能,因此在信息可靠传输中有良好的应用前景。本文提出了一种将BP算法和基于列表的SIHO(软输入硬输出)算法相结合的译码算法,通过与BP、MLD算法的误码率性能和译码复杂度比较,本算法复杂度比MLD有明显降低,而在性能上优于BP算法并接近MLD译码算法。     

Asymptotic enumeration methods for analyzing LDPC codes

We show how asymptotic estimates of powers of polynomials with nonnegative coefficients can be used in the analysis of low-density parity-check (LDPC) codes. In particular, we show how these estimates can be used to derive the asymptotic distance spectrum of both regular and irregular LDPC code ensembles. We then consider the binary erasure channel (BEC). Using these estimates we derive lower bounds on the error exponent, under iterative decoding, of LDPC codes used over the BEC. Both regular and irregular code structures are considered. These bounds are compared to the corresponding bounds when optimal (maximum-likelihood (ML)) decoding is applied.     

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.     

Performance analysis on LDPC-Coded systems over quasi-static (MIMO) fading channels

In this paper, we derive closed form upper bounds on the error probability of low-density parity-check (LDPC) coded modulation schemes operating on quasi-static fading channels. The bounds are obtained from the so-called Fano- Gallager?s tight bounding techniques, and can be readily calculated when the distance spectrum of the code is available. In deriving the bounds for multiple-input multiple-output (MIMO) systems, we assume the LDPC code is concatenated with the orthogonal space-time block code as an inner code. We obtain an equivalent single-input single-output (SISO) channel model for this concatenated coded-modulation system. The upper bounds derived here indicate good matches with simulation results of a complete transceiver system over Rayleigh and Rician MIMO fading channels in which the iterative detection and decoding algorithm is employed at the receiver.     

On improved bounds on the decoding error probability of block codesover interleaved fading channels, with applications to turbo-like codes

We derive here improved upper bounds on the decoding error probability of block codes which are transmitted over fully interleaved Rician fading channels, coherently detected and maximum-likelihood (ML) decoded. We assume that the fading coefficients during each symbol are statistically independent (due to a perfect channel interleaver), and that perfect estimates of these fading coefficients are provided to the receiver. The improved upper bounds on the block and bit error probabilities are derived for fully interleaved fading channels with various orders of space diversity, and are found by generalizing some previously introduced upper bounds for the binary-input additive white Gaussian nose (AWGN) channel. The advantage of these bounds over the ubiquitous union bound is demonstrated for some ensembles of turbo codes and low-density parity-check (LDPC) codes, and it is especially pronounced in a portion of the rate region exceeding the cutoff rate. Our generalization of the Duman and Salehi bound (Duman and Salehi 1998, Duman 1998) which is based on certain variations of Gallager's (1965) bounding technique, is demonstrated to be the tightest reported upper bound. We therefore apply it to calculate numerically upper bounds on the thresholds of some ensembles of turbo-like codes, referring to the optimal ML decoding. For certain ensembles of uniformly interleaved turbo codes, the upper bounds derived here also indicate good match with computer simulation results of efficient iterative decoding algorithms     

Complexity versus performance of capacity-achieving irregular repeat-accumulate codes on the binary erasure channel

We derive upper and lower bounds on the encoding and decoding complexity of two capacity-achieving ensembles of irregular repeat-accumulate (IRA1 and IRA2) codes on the binary erasure channel (BEC). These bounds are expressed in terms of the gap between the channel capacity and the rate of a typical code from this ensemble for which reliable communications is achievable under message-passing iterative (MPI) decoding. The complexity of the ensemble of IRA1 codes grows like the negative logarithm of the gap to capacity. On the other hand, the complexity of the ensemble of IRA2 codes with any choice of the degree distribution grows at least like the inverse square root of the gap to capacity, and at most like the inverse of the gap to capacity.     

Constrained Information Combining: Theory and Applications for LDPC Coded Systems

This paper tightens previous information combining bounds on the performance of iterative decoding of binary low-density parity-check (LDPC) codes over binary-input symmetric-output channels by tracking the probability of erroneous bit in conjunction with mutual information. Evaluation of the new bounds as well as of other known bounds on different LDPC ensembles demonstrates sensitivity of the finite dimensional iterative bounds to lambda₂, the fraction of edges connected to degree 2 variable nodes     

Bounds on the Number of Iterations for Turbo-Like Ensembles Over the Binary Erasure Channel

This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check (LDPC) codes and variations of repeat–accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-$2$ variable nodes, the target bit erasure probability, and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-$2$ variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).      

LDPC码译码器的设计与实现

由于传统的LLR BP译码算法不易于FPGA实现,为了降低实现复杂度,采用一种改进的LLR BP译码实现方法,设计了一种码长为40、码率为0.5的规则LDPC码译码器,并完成了FPGA仿真实现.仿真和综合的结果表明,所设计的译码器吞吐量达到15.68 Mbit/s,且译码器的资源消耗适中.     

A high‐performance belief propagation decoding algorithm for codes with short cycles

The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.     

Matched information rate codes for Partial response channels

In this paper, we design capacity-approaching codes for partial response channels. The codes are constructed as concatenations of inner trellis codes and outer low-density parity- check (LDPC) codes. Unlike previous constructions of trellis codes for partial response channels, we disregard any algebraic properties (e.g., the minimum distance or the run-length limit) in our design of the trellis code. Our design is purely probabilistic in that we construct the inner trellis code to mimic the transition probabilities of a Markov process that achieves a high (capacity-approaching) information rate. Hence, we name it a matched information rate (MIR) design. We provide a set of five design rules for constructions of capacity-approaching MIR inner trellis codes. We optimize the outer LDPC code using density evolution tools specially modified to fit the superchannel consisting of the inner MIR trellis code concatenated with the partial response channel. Using this strategy, we design degree sequences of irregular LDPC codes whose noise tolerance thresholds are only fractions of a decibel away from the capacity. Examples of code constructions are shown for channels both with and without spectral nulls.