Correcting capabilities of binary irregular LDPC code under low-complexity iterative decoding algorithm

This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.     

On decoding of low-density parity-check codes over the binary erasure channel

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.     

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.     

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     

Performance Analysis for LDPC-Coded Modulation in MIMO Multiple-Access Systems

We consider a low-density parity-check (LDPC)-coded modulation scheme in multi-input multi-output (MIMO) multiple-access systems. The receiver can be regarded as a serially concatenated iterative detection and decoding scheme, where the LDPC decoders perform the role of outer decoder and the multiuser demapper does that of the inner decoder. In this paper, we investigate the performance of the scheme with simulation results and bounds. Union upper bounds are derived, which can be used as additional means to evaluate the performance of the MIMO multiple-access system.     

LDPC-based channel coding of correlated sources with iterative joint decoding

This letter considers low-density parity-check (LDPC) coding of correlated binary sources and a novel iterative joint channel decoding without communication of any side information. We demonstrate that depending on the extent of the source correlation, additional coding gains can be obtained. Two stages of iterative decoding are employed. During global iterations, updated estimates of the source correlation are obtained and passed on to the sum-product decoder that performs local iterations with a predefined stopping criterion and/or a maximum number of local decoding iterations. Simulation results indicate that very few global iterations (2-5) are sufficient to reap significant benefits from implicit knowledge of source correlation. Finally, we provide analytical performance bounds for our iterative joint decoder and comparisons with sample simulation results.     

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.     

Codes for iterative decoding from partial geometries

This paper develops codes suitable for iterative decoding using the sum-product algorithm. By considering a large class of combinatorial structures, known as partial geometries, we are able to define classes of low-density parity-check (LDPC) codes, which include several previously known families of codes as special cases. The existing range of algebraic LDPC codes is limited, so the new families of codes obtained by generalizing to partial geometries significantly increase the range of choice of available code lengths and rates. We derive bounds on minimum distance, rank, and girth for all the codes from partial geometries, and present constructions and performance results for the classes of partial geometries which have not previously been proposed for use with iterative decoding. We show that these new codes can achieve improved error-correction performance over randomly constructed LDPC codes and, in some cases, achieve this with a significant decrease in decoding complexity.     

瑞利衰落信道下基于LDPC码USTM的MIMO系统

研究了一种联合低密度校验(LDPC,Low-Density Parity-Check)码和酉空时调制(USTM,Unitary Space-Time Modulation)技术在不相关瑞利平坦衰落(Rayleigh flat fading)下的多输入多输出信道(MIMO,Multiple-Input Multiple-Output)系统的性能.在无信道状态信息下,采用可并行操作的和积译码算法(SPA,Sum-Product Algorithm)的LDPCC-USTM级联系统具有优异的性能,并分析了不同LDPC码集下对系统性能的影响.仿真结果表明LDPCC-USTM级联系统比与未级联的相比有近23dB的编码增益,与基于Turbo码的USTM[6]系统相比有5dB多的编码增益,且基于非规则的LDPC码的级联系统比基于规则码有近1dB的编码增益.     

LDPC block and convolutional codes based on circulant matrices

A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.     

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     

Joint iterative decoding of LDPC codes for channels with memory and erasure noise

This paper investigates the joint iterative decoding of low-density parity-check (LDPC) codes and channels with memory. Sequences of irregular LDPC codes are presented that achieve, under joint iterative decoding, the symmetric information rate of a class of channels with memory and erasure noise. This gives proof, for the first time, that joint iterative decoding can be information rate lossless with respect to maximum-likelihood decoding. These results build on previous capacity-achieving code constructions for the binary erasure channel. A two state intersymbol-interference channel with erasure noise, known as the dicode erasure channel, is used as a concrete example throughout the paper.     

Upper bounds on the rate of LDPC codes as a function of minimum distance

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.     

纠正随机错误与长突发删除的多进制乘积码研究

考虑多进制LDPC码的符号特性,以及对其残留错误和删除的分析,本文采用多进制LDPC码作为内码,相同Galois域下的高码率RS码作为外码来构造多进制乘积码;并提出了一种低复杂度的迭代译码方案,减少信息传输的各类错误。在译码时,只对前一次迭代中译码失败的码字执行译码,并对译码正确码字所对应的比特初始概率信息进行修正,增强下一次迭代多进制LDPC译码符号先验信息的准确性,减少内码译码后的判决错误,从而充分利用外码的纠错能力。仿真结果显示,多进制乘积码相较于二进制LDPC乘积码有较大的编码增益,并通过迭代进一步改善了性能,高效纠正了信道中的随机错误和突发删除。对于包含2%突发删除的高斯信道,在误比特率为10^-6时,迭代一次有0.4 dB左右的增益。     

一种新的终止LDPC迭代译码算法

在传统的卫星广播系统中,信道纠错通常采用BCH码级联LDPC码的方案以达到良好的误码率性能,例如DVB-S2系统。作为内码的LDPC码通常采用迭代译码,且迭代次数较高才能实现比较好的系统性能。借助BCH级联LDPC的结构,文中提出了将BCH检错嵌套进LDPC每一次迭代译码过程中的新的迭代译码结构。仿真结果表明,新算法以较低的BCH码检错运算复杂度换取了LDPC码迭代次数的明显下降,从而极大降低了迭代译码总体复杂度和译码时延,且整体纠错性能与原始LDPC译码后BCH纠错的算法相比基本保持不变。     

基于隐马尔科夫模型的多元LDPC联合译码

采用隐马尔科夫模型对信源估计,对基于多进制LDPC码的联合信源信道译码算法展开研究。该算法通过对传统的多进制LDPC译码算法的改进,在迭代过程中加入通过估计算法得到的信源冗余,校正了迭代软信息,提高译码性能。仿真结果表明,在AWGN信道中,改进算法相比传统译码算法性能优越。     

半双工中继信道下联合LDPC码设计

为了提高解码前传半双工中继通信系统的编码增益,提出了一种联合LDPC码编码结构及其度分布优化方法。该结构视信源和中继子码为联合LDPC码的一部分,目的端根据从信源和中继接收的消息进行联合译码,同时获得信源和中继的信息。为了分析联合LDPC码的渐进性能,推导了AWGN信道下联合LDPC码的高斯近似密度进化算法。结合译码收敛条件和度分布约束关系,提出联合LDPC码的度分布优化问题。仿真结果表明：联合LDPC码的渐进性能及误码性能优于BE-LDPC码和独立处理（SP）码。     

基于多元LDPC码的迭代符号定时恢复

针对极低/低信噪比深空通信中传统符号定时恢复难的问题,本文提出了一种联合符号定时恢复与多元LDPC迭代译码的方案。该方案将Mueller& Muller符号定时恢复算法与迭代译码方法相结合,对符号周期内的动态时延进行校正。根据译码反馈信息的不同,迭代译码方法可分为基于译码硬信息和译码软信息两种迭代方法。仿真结果表明,在高阶调制、低信噪比和动态时延下,基于两种迭代方法的符号定时恢复算法均取得了接近于理想情况的性能,且收敛速度快,适合于工程实现。其中,由于基于译码软信息迭代的符号定时恢复算法保留了更完整的概率信息,因而性能更优。      

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.