Surrogate-channel design of universal LDPC codes

A universal code is a code that may be used across a number of different channel types or conditions with little degradation relative to a good single-channel code. The explicit design of universal codes, which simultaneously seeks to solve a multitude of optimization problems, is a daunting task. This letter shows that a single channel may be used as a surrogate for an entire set of channels to produce good universal LDPC codes. This result suggests that sometimes a channel for which LDPC code design is simple may be used as a surrogate for a channel for which LDPC code design is complex. We explore here the universality of LDPC codes over the BEC, AWGN, and flat Rayleigh fading channels in terms of decoding threshold performance. Using excess mutual information as a performance metric, we present design results which support the contention that an LDPC code designed for a single channel can be universally good across the three channels.     

Finding All Small Error-Prone Substructures in LDPC Codes

It is proven in this work that it is NP-complete to exhaustively enumerate small error-prone substructures in arbitrary, finite-length low-density parity-check (LDPC) codes. Two error-prone patterns of interest include stopping sets for binary erasure channels (BECs) and trapping sets for general memoryless symmetric channels. Despite the provable hardness of the problem, this work provides an exhaustive enumeration algorithm that is computationally affordable when applied to codes of practical short lengths n ap 500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size les 13 and the trapping sets of size les11 can be exhaustively enumerated. The central theorem behind the proposed algorithm is a new provably tight upper bound on the error rates of iterative decoding over BECs. Based on a tree-pruning technique, this upper bound can be iteratively sharpened until its asymptotic order equals that of the error floor. This feature distinguishes the proposed algorithm from existing non-exhaustive ones that correspond to finding lower bounds of the error floor. The upper bound also provides a worst case performance guarantee that is crucial to optimizing LDPC codes when the target error rate is beyond the reach of Monte Carlo simulation. Numerical experiments on both randomly and algebraically constructed LDPC codes demonstrate the efficiency of the search algorithm and its significant value for finite-length code optimization.     

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.     

Finite-Dimensional Bounds on Zm and Binary LDPC Codes With Belief Propagation Decoders

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zopf_m and binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For Zopf _m LDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for Zopf_m LDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with nonequiprobably distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional noniterative bound, the latter of which is the best known bound that is tight for binary-symmetric channels (BSCs), and is a strict improvement over the existing bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for nonsymmetric channels, which coincides with the existing bound for symmetric channels     

On Universal Properties of Capacity-Approaching LDPC Code Ensembles

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.     

Upper Bounds on the Rate of LDPC Codes for a Class of Finite-State Markov Channels

In this correspondence, we consider the class of finite-state Markov channels (FSMCs) in which the channel behaves as a binary symmetric channel (BSC) in each state. Upper bounds on the rate of LDPC codes for reliable communication over this class of FSMCs are found. A simple upper bound for all noninverting FSMCs is first derived. Subsequently, tighter bounds are derived for the special case of Gilbert-Elliott (GE) channels. Tighter bounds are also derived over the class of FSMCs considered. The latter bounds hold almost-surely for any sequence of randomly constructed LDPC codes of given degree distributions. Since the bounds are derived for optimal maximum-likelihood decoding, they also hold for belief propagation decoding. Using the derivations of the bounds on the rate, some lower bounds on the density of parity check matrices for given performance over FSMCs are derived     

On the application of LDPC codes to arbitrary discrete-memoryless channels

We discuss three structures of modified low-density parity-check (LDPC) code ensembles designed for transmission over arbitrary discrete memoryless channels. The first structure is based on the well-known binary LDPC codes following constructions proposed by Gallager and McEliece, the second is based on LDPC codes of arbitrary (q-ary) alphabets employing modulo-q addition, as presented by Gallager, and the third is based on LDPC codes defined over the field GF(q). All structures are obtained by applying a quantization mapping on a coset LDPC ensemble. We present tools for the analysis of nonbinary codes and show that all configurations, under maximum-likelihood (ML) decoding, are capable of reliable communication at rates arbitrarily close to the capacity of any discrete memoryless channel. We discuss practical iterative decoding of our structures and present simulation results for the additive white Gaussian noise (AWGN) channel confirming the effectiveness of the 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.     

Approaching V-BLAST Capacity With Adaptive Modulation and LDPC Encoding

This paper presents a practical implementation of the vertical Bell Laboratories layered space-time (V-BLAST) type system, in which the multiple-input multiple-output (MIMO) open-loop capacity can be approached with conventional scalar coding, using adaptive modulation with appropriate channel codes, e.g., low-density parity-check (LDPC) codes and optimum successive detection (OSD). The density evolution (DE) technique is employed to determine the maximal achievable rate of an LDPC code for each transmit antenna for a given channel realization at a given SNR. Numerical results show that the average sum rate of the adaptively modulated LDPC-encoded system is quite close to the V-BLAST capacity with both rate and power adaptations. Considering the performing degradation caused by error propagation due to the imperfect feedback and relatively long decoding delay in the OSD, we use parallel interference cancellation (PIC) followed by minimum mean square error (MMSE) filtering in the bit error rate (BER) performance simulation. Simulation results show that a target BER of 10-5 can be achieved by the optimally designed LDPC codes. To simplify the code design, we replace the LDPC codes optimally designed for each channel realization with rate-compatible punctured LDPC codes, at the cost of a slight sum rate loss. If the fading process is nonergodic, the outage capacity corresponding to a given outage probability is used to measure the channel performance. As an example, we design the LDPC codes for an adaptively modulated 2 × 2 V-BLAST system to approach its outage capacity for a given outage probability.      

Reliable channel regions for good binary codes transmitted over parallel channels

We study the average error probability performance of binary linear code ensembles when each codeword is divided into J subcodewords with each being transmitted over one of J parallel channels. This model is widely accepted for a number of important practical channels and signaling schemes including block-fading channels, incremental redundancy retransmission schemes, and multicarrier communication techniques for frequency-selective channels. Our focus is on ensembles of good codes whose performance in a single channel model is characterized by a threshold behavior, e.g., turbo and low-density parity-check (LDPC) codes. For a given good code ensemble, we investigate reliable channel regions which ensure reliable communications over parallel channels under maximum-likelihood (ML) decoding. To construct reliable regions, we study a modifed 1961 Gallager bound for parallel channels. By allowing codeword bits to be randomly assigned to each component channel, the average parallel-channel Gallager bound is simplified to be a function of code weight enumerators and channel assignment rates. Special cases of this bound, average union-Bhattacharyya (UB), Shulman-Feder (SF), simplified-sphere (SS), and modified Shulman-Feder (MSF) parallel-channel bounds, allow for describing reliable channel regions using simple functions of channel and code spectrum parameters. Parameters describing the channel are the average parallel-channel Bhattacharyya noise parameter, the average channel mutual information, and parallel Gaussian channel signal-to-noise ratios (SNRs). Code parameters include the union-Bhattacharyya noise threshold and the weight spectrum distance to the random binary code ensemble. Reliable channel regions of repeat-accumulate (RA) codes for parallel binary erasure channels (BECs) and of turbo codes for parallel additive white Gaussian noise (AWGN) channels are numerically computed and compared with simulation results based on iterative decoding. In addition, an examp     

LDPC-coded cooperative relay systems: performance analysis and code design

We treat the problem of designing low-density parity-check (LDPC) codes to approach the capacity of relay channels. We consider an efficient analysis framework that decouples the factor graph (FG) of a B-block transmission into successive partial FGs, each of which denotes a two-block transmission. We develop design methods to find the optimum code ensemble for the partial FG. In particular, we formulate the relay operations and the destination operations as equivalent virtual MISO and MIMO systems, and employ a binary symmetric channel (BSC) model for the relay node output. For AWGN channels, we further develop a Gaussian approximation for the detector output at the destination node. Jointly treating the relay and the destination, we analyze the performance of the LDPC-coded relay system using the extrinsic mutual information transfer(EXIT) chart technique. Furthermore, differential evolution is employed to search for the optimum code ensemble. Our results show that the optimized codes always outperform the regular LDPC codes with a significant gain; in the AWGN case, when Protocol-II is employed and the relay is close to the source, the optimized code performs within 0.1dB to the capacity bound.     

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.      

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.     

Design of rate-compatible structured LDPC codes for hybrid ARQ applications

In this paper, families of rate-compatible protograph-based LDPC codes that are suitable for incrementalredundancy hybrid ARQ applications are constructed. A systematic technique to construct low-rate base codes from a higher rate code is presented. The base codes are designed to be robust against erasures while having a good performance on error channels. A progressive node puncturing algorithm is devised to construct a family of higher rate codes from the base code. The performance of this puncturing algorithm is compared to other puncturing schemes. Using the techniques in this paper, one can construct a rate-compatible family of codes with rates ranging from 0.1 to 0.9 that are within 1 dB from the channel capacity and have good error floors.     

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

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

Design of multi-input multi-output systems based on low-density Parity-check codes

We design serial concatenated multi-input multi-output systems based on low-density parity-check (LDPC) codes. We employ a receiver structure combining the demapper/detector and the decoder in an iterative fashion. We consider the a posteriori probability (APP) demapper, as well as a suboptimal demapper incorporating interference cancellation with linear filtering. Extrinsic information transfer (EXIT) chart analysis is applied to study the convergence behavior of the proposed schemes. We show that EXIT charts match very well with the simulated decoding trajectories, and they help explain the impact of different mappings and different demappers. It is observed that if the APP demapper transfer characteristics are almost flat, the LDPC codes optimized for binary-input channels are good enough to achieve performance close to the channel capacity. We also present a simple code-optimization method based on EXIT chart analysis, and we design a rate-1/2 LDPC code that achieves very low bit-error rates within 0.15 dB of the capacity of a two-input two-output Rayleigh fading channel with 4-pulse amplitude modulation. We next propose to use a space-time block code as an inner code of our serial concatenated coding scheme. By means of a simple example scheme, using an Alamouti inner code, we demonstrate that the design/optimization of the outer code (e.g., LDPC code) is greatly simplified.     

重量分布式约束的LDPC码性能研究

本文对"重量分布式约束的码集合内码性能"这一命题进行了初步研究,分别得到了码集合性能的上限和下限,本文给出了性能下限码的Fill-Shift构造方法,而且由LDPC码校验矩阵不变性可以对LDPC码的校验矩阵作必要的初等变换,这样可以在保持码性能不变的前提下降低编码复杂度和实现系统编码;此外,还可以利用该性质加强对重要信息符号的差错保护.     

Upper bounds on the rate of LDPC codes

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's (1963) bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes.     

Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes

Time-invariant hybrid (Hscr_TI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on Hscr_TI algorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB Hscr_TI algorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB Hscr_TI algorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB Hscr_TI algorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive     

Several properties of short LDPC codes

In this paper, we present several properties on minimum distance(d/sub min/) and girth(G/sub min/) in Tanner graphs for low-density parity-check (LDPC) codes with small left degrees. We show that the distance growth of (2, 4) LDPC codes is too slow to achieve the desired performance. We further give a tight upper bound on the maximum possible girth. The numerical results show that codes with large G/sub min/ could outperform the average performance of regular ensembles of the LDPC codes over binary symmetric channels. The same codes perform about 1.5 dB away from the sphere-packing bound on additive white Gaussian noise channels.