EXIT-chart properties of the highest-rate LDPC code with desired convergence behavior

We consider uniparametric LDPC decoding schemes, i.e., the class of decoding algorithms for which an extrinsic information transfer (EXIT) chart analysis of the decoder is exact. We treat the general case of code design for a desired convergence behavior and provide necessary conditions and sufficient conditions that the EXIT chart of the maximum rate low-density parity-check code must satisfy. Our results generalize some of the existing results for the binary erasure channel: our results apply to all uniparametric decoding schemes and they apply to any desired convergence behavior.     

Design of serially concatenated systems depending on the block length

Based on extrinsic information transfer (EXIT) charts, the convergence behavior of iterative decoding is studied for a number of serially concatenated systems, such as a serially concatenated code, coded data transmission over an intersymbol interference channel, bit-interleaved coded modulation, or trellis-coded modulation. Efficient optimization algorithms based on simplified EXIT chart construction are devised to find irregular codes improving the convergence of iterative decoding. One optimization criterion is to find concatenated systems exhibiting thresholds of successful decoding convergence, which are close to information-theoretic limits. However, these thresholds are approached only for very long block lengths. To overcome this problem, the decoding convergence after a fixed, finite number of iterations is optimized, which yields systems performing very well for short block lengths, too. As an example, optimal system configurations for communication over an additive white Gaussian noise channel are presented.     

Replica horizontal-shuffled iterative decoding of low-density parity-check codes

For practical considerations, it is essential to accelerate the convergence speed of the decoding algorithm used in an iterative decoding system. In this paper, replica versions of horizontal-shuffled decoding algorithms for low-density parity-check (LDPC) codes are proposed to improve the convergence speed of the original versions. The extrinsic information transfer (EXIT) chart technique is extended to the proposed algorithms to predict their convergence behavior. Both EXIT chart analysis and numerical results show that replica plain horizontal-shuffled (RPHS) decoding converges much faster than both plain horizontal-shuffled (PHS) decoding and the standard belief-propagation (BP) decoding. Furthermore, it is also revealed that replica group horizontal-shuffled (RGHS) decoding can increase the parallelism of RPHS decoding as well as preserve its high convergence speed if an equivalence condition is satisfied, and is thus suitable for hardware implementation.     

Extrinsic information transfer functions: model and erasure channel properties

Extrinsic information transfer (EXIT) charts are a tool for predicting the convergence behavior of iterative processors for a variety of communication problems. A model is introduced that applies to decoding problems, including the iterative decoding of parallel concatenated (turbo) codes, serially concatenated codes, low-density parity-check (LDPC) codes, and repeat-accumulate (RA) codes. EXIT functions are defined using the model, and several properties of such functions are proved for erasure channels. One property expresses the area under an EXIT function in terms of a conditional entropy. A useful consequence of this result is that the design of capacity-approaching codes reduces to a curve-fitting problem for all the aforementioned codes. A second property relates the EXIT function of a code to its Helleseth-Klove-Levenshtein information functions, and thereby to the support weights of its subcodes. The relation is via a refinement of information functions called split information functions, and via a refinement of support weights called split support weights. Split information functions are used to prove a third property that relates the EXIT function of a linear code to the EXIT function of its dual.     

Memory-Efficient and High-Throughput Decoding of Quasi-Cyclic LDPC Codes

We propose turbo-sum-product (TSP) and shuffled-sum-product (SSP) decoding algorithms for quasi-cyclic low-density parity-check codes, which not only achieve faster convergence and better error performance than the sum-product algorithm, but also require less memory in partly parallel decoder architectures. Compared with the turbo decoding algorithm, our TSP algorithm saves the same amount of memory and may achieve a higher decoding throughput. The convergence behaviors of our TSP and SSP algorithms are also compared with those of the SP, turbo, and shuffled algorithms by their extrinsic information transfer (EXIT) charts.     

EXIT chart analysis of BICM-ID with imperfect channel state information

We analyze the convergence of iteratively decoded bit-interleaved coded modulation with imperfect channel state information using the extrinsic information transfer (EXIT) chart. A canonical analysis model is adopted, where the power correlation coefficient between the fading and its estimate becomes the key parameter affecting the extrinsic transfer characteristics of the demapper and hence the convergence of iterative decoding. We further illustrate that decoding convergence can be triggered by tradeoff between the quality of channel estimation and code rate.     

非高斯脉冲噪声下Turbo均衡性能分析的改进EXIT图方法

该文提出了一种改进的外信息转移图(EXIT图)方法,可用于分析加性非高斯对称稳定分布噪声多径信道条件下Turbo均衡性能,为实际的Turbo均衡系统设计提供预估性能参数。该方法对传统的EXIT图分析做出的改进在于给出了非高斯对称稳定分布条件下一种实用的外信息的概率密度分布的近似估计。将EXIT图与系统误码率分析相结合,可对互信息变化的迭代轨迹、迭代次数和每次迭代能达到的误码率做出预测估计。对截断Turbo均衡方法的仿真结果表明,利用该方法预测的系统性能与实际的仿真结果基本一致,证实了该方法的有效性。     

Code characteristic matching for iterative decoding of serially concatenated codes

The design of serially concatenated codes has yet been dominated by optimizing asymptotic slopes of error probability curves. We propose mutual information transfer characteristics for soft in/soft out decoders to design serially concatenated codes based on the convergence behavior of iterative decoding. The exchange of extrinsic information is visualized as a decoding trajectory in the Extrinsic Information Transfer Chart (exit chart). By finding matching pairs of inner and outer decoder transfer characteristics we are able to construct serially concatenated codes whose iterative decoder converges towards low bit error rate at signal- to- noise ratios close to the theoretical limits.     

On the limiting performance of turbo-Hadamard codes

In this letter, we employ the extrinsic information transfer (EXIT) chart technique to assess the limiting performance of turbo-Hadamard codes and identify the optimized design parameters for such codes. It is shown that for a sufficiently long code length and a sufficiently large number of iterations, a carefully designed low rate turbo-Hadamard code can potentially achieve successful decoding at E/sub b//N/sub 0//spl ap/-1.3 dB, which is about 0.29 dB from the ultimate Shannon limit.     

Optimization of scaling soft information in iterative decoding via density evolution methods

Density evolution has recently been used to analyze iterative decoding and explain many characteristics of iterative decoding including convergence of performance and preferred structures for the constituent codes. The scaling of extrinsic information (messages) has been heuristically used to enhance the performance in the iterative decoding literature, particularly based on the min-sum message passing algorithm. In this paper, it is demonstrated that density evolution can be used to obtain the optimal scaling factor and also estimate the maximum achievable scaling gain. For low density parity check (LDPC (codes and serially) concatenated convolutional codes (SCCC) with two-state constituent codes, the analytic density evolution technique is used, while the signal-to-noise ratio (SNR) evolution technique and the EXIT chart technique is used for SCCC with more than 2 state constituent codes. Simulation results show that the scaling gain predicted by density evolution or SNR evolution matches well with the scaling gain observed by simulation.     

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.     

A simple convergence comparison of Gallager codes under two message-passing schedules

The convergence rate of iterative decoding of Gallager codes on the additive white Gaussian noise (AWGN) channel using the sum-product algorithm (SPA) under the flooding schedule (FS) is compared with that under the turbo-decoding schedule (TDS). Analyses using extrinsic information transfer (EXIT) charts show that TDS exhibits a much faster convergence behavior than FS.     

Nonsystematic turbo codes

In this paper, we introduce the concept of nonsystematic turbo codes and compare them with classical systematic turbo codes. Nonsystematic turbo codes can achieve lower error floors than systematic turbo codes because of their superior effective free distance properties. Moreover, they can achieve comparable performance in the waterfall region if the nonsystematic constituent encoder has a low-weight feedforward inverse. A uniform interleaver analysis is used to show that rate R=1/3 turbo codes using nonsystematic constituent encoders have larger effective free distances than when systematic constituent encoders are used. Also, mutual information-based transfer characteristics and extrinsic information transfer charts are used to show that rate R=1/3 turbo codes with nonsystematic constituent encoders having low-weight feedforward inverses achieve convergence thresholds comparable to those achieved with systematic constituent encoders. Catastrophic encoders, which do not possess a feedforward inverse, are shown to be capable of achieving low convergence thresholds by doping the code with a small fraction of systematic bits. Finally, we give tables of good nonsystematic turbo codes and present simulation results comparing the performance of systematic and nonsystematic turbo codes.     

Convergence rates comparison of sum-product decoding of RA codes under different message-passing schedules

In iterative decoding of turbo-like codes, serial schedule generally provides a much faster convergence rate compared with parallel schedule. With the aid of extrinsic information transfer (EXIT) charts, sum-product decoding of repeat accumulate (RA) codes under both message passing schedules is investigated as an example for verifying the above statement.     

Generalized Low-Density Parity-Check Codes Based on Hadamard Constraints

In this paper, we consider the design and analysis of generalized low-density parity-check (GLDPC) codes in AWGN channels. The GLDPC codes are specified by a bipartite Tanner graph, as with standard LDPC codes, but with the single parity-check constraints replaced by general coding constraints. In particular, we consider imposing Hadamard code constraints at the check nodes for a low-rate approach, termed LDPC-Hadamard codes. We introduce a low-complexity message-passing based iterative soft-input soft-output (SISO) decoding algorithm, which employs the a posteriori probability (APP) fast Hadamard transform (FHT) for decoding the Hadamard check codes at each decoding iteration. The achievable capacity with the GLDPC codes is then discussed. A modified LDPC-Hadamard code graph is also proposed. We then optimize the LDPC-Hadamard code ensemble using a low-complexity optimization method based on approximating the density evolution by a one-dimensional dynamic system represented by an extrinsic mutual information transfer (EXIT) chart. Simulation results show that the optimized LDPC-Hadamard codes offer better performance in the low-rate region than low-rate turbo-Hadamard codes, but also enjoy a fast convergence rate. A rate-0.003 LDPC-Hadamard code with large block length can achieve a bit-error-rate (BER) performance of 10^-5 at -1.44 dB, which is only 0.15 dB away from the ultimate Shannon limit (-1.592 dB) and 0.24 dB better than the best performing low-rate turbo-Hadamard codes     

On MSE Exit Chart Analysis and Real Time DSP Implementation for Iterative (Turbo) Detection

We investigate the use of the mean square error (MSE) transfer characteristics to examine the convergence behaviour of the iterative (turbo) multiuser detector for coded code-division multiple-access (CDMA) systems. Both MSE and mutual information (MI) based extrinsic information transfer (MSE-EXIT and MI-EXIT) chart techniques reveal the same asymptotic and convergence behaviours. An improved low complexity version of the soft interference cancellation MMSE (SIC-MMSE) detection scheme is also proposed for CDMA systems utilizing BPSK modulation. Herein, under fixed-point data representation and computation constraint a real time DSP implementation (using TMS320C6416) is suggested. EXIT charts reveal that fixed-point implementation is feasible at possibly no performance degradation. Based on the measured number of cycles of different constituent sub-functions of the proposed receiver, a data transmission rate of up to 186 Kb/s can be reached for a 5-users load and a processing gain of 7 in an AWGN channel.     

Simple and Accurate Design of Low-Density Parity-Check Codes for Multi-Input Multi-Output Systems

In this paper we design an irregular low-density parity-check (LDPC) code for multiple-input multiple-output (MIMO) systems, using a simple extrinsic information transfer (EXIT) chart method. The MIMO systems considered are the optimal maximum a posteriori probability (MAP) detector and the suboptimal minimum mean square error soft-interference cancellation (MMSE-SIC) detector. The MIMO detector and the LDPC decoder exchange soft information and form a turbo iterative receiver. The EXIT charts are used to obtain the edge degree distribution of the irregular LDPC code which is optimized for the MIMO detector. It is shown that the performance of the designed LDPC code is better than that of conventional LDPC code which was optimized for either the Additive White Gaussian Noise (AWGN) channel or the MIMO channel without an explicit consideration of the given detector structure.     

EXIT charts for turbo trellis-coded modulation

In this letter, we extend the previously proposed extrinsic information transfer charts (EXIT) method to the analysis of the convergence of turbo codes to turbo trellis-coded modulation (TTCM) schemes. The effectiveness of the proposed method is demonstrated through examples. The proposed method provides a convenient way to systematically compare between schemes and thus can be used as a tool in the design of TTCM.     

Threshold of LDPC-coded BICM for Rayleigh fading

We analyze the threshold and convergence of LDPC coded bit interleaved coded modulation over Rayleigh fading channels. We compute the system threshold using the discretized density evolution and the extrinsic information transfer (EXIT) chart, and verify its effectiveness by simulation. Simulated detector output pdf is used to compute the variable node EXIT curve. It is shown that the convergence SNR observed from the transfer curves matches the density evolution threshold perfectly, and the EXIT chart actually provides a more computational efficient approach to estimate the threshold. An irregular code design example using the EXIT chart is given.     

Soft-Output BEAST Decoding With Application to Product Codes

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximate a posteriori probabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.