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     

Modeling End-to-End Wireless Lossy Channels: A Finite-State Markov Approach

In this paper, we present a model for wireless losses in packet transmission data networks. The model provides information about the wireless channel status that can be used in congestion control schemes. A Finite State Markov Channel (FSMC) approach is implemented to model the wireless slow fading for different modulation schemes. The arrival process statistics of the packet traces determine the channel state transition probabilities, where the statistics of both error-free and erroneous bursts are captured. Later, we establish SNR partitioning scheme that uses the transition probabilities as a basis for the state margins. The crossover probability associated with each state is calculated accordingly. We also propose an end-to-end approach to loss discrimination based on the channel state estimation at the receiver. Finally, we present a scheme for finding the channel optimal number of states as a function of the SNR. The presented FSMC approach does not restrict the state transitions to the adjacent states, nor does impose constant state duration as compared to some literature studies. We validate our model by experimental packet traces. Our simulation results show the feasibility of building a fading channel model for better wireless-loss awareness.     

On Information Rates of Time-Varying Fading Channels Modeled as Finite-State Markov Channels

We study information rates of time-varying flatfading channels (FFC) modeled as finite-state Markov channels (FSMC). FSMCs have two main applications for FFCs: modeling channel error bursts and decoding at the receiver. Our main finding in the first application is that receiver observation noise can more adversely affect higher-order FSMCs than lower-order FSMCs, resulting in lower capacities. This is despite the fact that the underlying higher-order FFC and its corresponding FSMC are more predictable. Numerical analysis shows that at low to medium SNR conditions (SNR ≲12 dB) and at medium to fast normalized fading rates (0.01 ≲fDT ≲0.10), FSMC information rates are non-increasing functions of memory order. We conclude that BERs obtained by low-order FSMC modeling can provide optimistic results. To explain the capacity behavior, we present a methodology that enables analytical comparison of FSMC capacities with different memory orders. We establish sufficient conditions that predict higher/lower capacity of a reduced-order FSMC, compared to its original high-order FSMC counterpart. Finally, we investigate the achievable information rates in FSMC-based receivers for FFCs. We observe that high-order FSMC modeling at the receiver side results in a negligible information rate increase for normalized fading rates fDT ≲0.01.     

On Designing Good LDPC Codes for Markov Channels

This paper presents a reduced-complexity approximate density evolution (DE) scheme for low-density parity-check (LDPC) codes in channels with memory in the form of a hidden Markov chain. This approximation is used to design degree sequences representing some of the best known LDPC code ensembles for the Gilbert-Elliott channel, and example optimizations are also given for other Markov channels. The problem of approximating the channel estimation is addressed by obtaining a specially constructed message-passing schedule in which the channel messages all approach their stable densities. It is shown that this new schedule is much easier to approximate than the standard schedule, but has the same ultimate performance in the limits of long block length and many decoding iterations. This result is extended to show that all message-passing schedules that satisfy mild conditions will have the same threshold under density evolution     

基于Markov信源和LDPC编码的信源信道联合译码算法

本文通过利用Markov信源的冗余信息,提出了一种基于系统LDPC码编码器的信源信道联合译码算法（JSCD）。仿真结果显示,当信源中存在更多的冗余信息时,该JSCD算法可相应取得更好的系统性能。     

Low-Floor Detection/Decoding of LDPC-Coded Partial Response Channels

The error-rate floor phenomenon associated with iterative LDPC decoders has delayed the use of LDPC codes in certain communication and storage systems. Error floors are known to generally be caused by so-called trapping sets which have the effect of confounding the decoder. In this paper, we introduce two techniques that lower the error-rate floors for LDPC-coded partial response (PR) channels which are applicable to magnetic and optical storage. The techniques involve, via external measures, ?pinning? one of the bits in each problematic trapping set and then letting the iterative decoder proceed to correct the rest of the bits. We also extend our earlier work on generalized-LDPC (G-LDPC) decoders for error-floor mitigation on the AWGN channel to partial response channels. Our simulations on PR1 and EPR4 channels demonstrate that the floor for the code chosen for this study, a 0.78(2048,1600) quasicyclic LDPC code, is lowered by orders of magnitude, beyond the reach of simulations. Because simulation in the floor region is so time-consuming, a method for accelerating such simulations is essential for research in this area. In this paper, we present an extension of Richardson?s importance sampling technique for estimating the level of error floors.     

FFT-Based BP Decoding of General LDPC Codes Over Abelian Groups

We introduce a wide class of low-density parity-check (LDPC) codes, large enough to include LDPC codes over finite fields, rings, or groups, as well as some nonlinear codes. A belief-propagation decoding procedure with the same complexity as for the decoding of LDPC codes over finite fields is also presented. Moreover, an encoding procedure is developed     

一种提高LDPC译码器吞吐率的译码算法

为了设计高效的LDPC译码器,结合准循环结构LDPC的校验矩阵H的规律性、乘性修正最小和译码算法不需要估计信道质量的特点和部分并行译码实现复杂度低的特点,介绍了一种新的译码算法——交迭的部分并行译码算法,这种译码算法相对于采用部分并行结构的BP译码算法,不但降低了硬件实现的复杂度,减少了存储资源的开销,而且提高了译码器的吞吐率。     

一种新的LDPC译码终止条件技术分析

为了在高速数据中继传输中保证高效率高功率的前提下达到很低的误码率,介绍了置信传播(Belief Propagation,BP)译码算法,仿真证明了基于欧式几何构造的(8 176,7 154)准循环(Quasi Cyclic,QC)低密度奇偶校验码(Low Density Parity Check,LDPC),简称QC-LDPC码是一种高速低误码率低复杂度的高效信道纠错编码,并通过仿真跟踪分析,提出了一种新的译码迭代终止条件,使译码仿真性能得到进一步优化。     

On Decoding Binary Perfect and Quasi-Perfect Codes over Markov Noise Channels

We study the decoding problem when a binary linear perfect or quasi-perfect code is transmitted over a binary channel with additive Markov noise. After examining the properties of the channel block transition distribution, we derive sufficient conditions under which strict maximum-likelihood decoding is equivalent to strict minimum Hamming distance decoding when the code is perfect. Additionally, we show a near equivalence relationship between strict maximum likelihood and strict minimum distance decoding for quasi-perfect codes for a range of channel parameters and the code's minimum distance. As a result, an improved (complete) minimum distance decoder is proposed and simulations illustrating its benefits are provided.     

Reduced-Complexity Decoding of LDPC Codes

Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.     

基于低密度校验码的OFDM编码调制译码算法

低密度校验码(LDPC)具有编码增益高、译码速度快、性能接近Shannon限的优点。LDPC码应用于OFDM，能有效地提高多径环境下OFDM的BER性能。本文首先简单介绍LDPC码及其概率域上的译码算法，在此基础上对译码算法作融合，阐述概率似然比的译码算法。为了把LDPC应用于OFDM系统上，提出了多电平调制下的LDPC译码的算法。仿真结果表明，在AWGN和Rayleigh信道下，此算法正确有效。     

空间耦合LDPC码的分层译码算法

针对长码长空间耦合低密度奇偶校验(SC-LDPC)码译码时延较长的问题,该文提出了分层滑动窗译码(LSWD)算法。该算法利用SC-LDPC子码码块的准循环特性和滑动窗内校验矩阵的层次结构,通过在滑动窗内对校验矩阵进行分层处理,优化层与层之间消息传递,从而加快窗内译码的收敛速度,减少了译码迭代次数。仿真和分析结果表明：在相同的信噪比(SNR)条件和相同的误码性能要求下,LSWD算法所需的迭代次数少于滑动窗译码(SWD)算法,特别在高信噪比下,LSWD算法的迭代次数约为SWD算法的一半,从而有效缩短全局译码时延;在相同译码迭代次数下,LSWD算法的译码性能优于SWD算法,而其计算复杂度增加不大。

     

一种低复杂度LDPC码提前结束迭代准则

采用直接观察校验子S中非零元素个数的方法来确定LDPC译码器迭代译码的收敛情况,提出了一种低复杂度的提前结束迭代准则.在不需要经过复杂的计算便可确定迭代译码的收敛情况,从而可以根据系统的实际需要实现性能和平均迭代次数的折衷.在CMMB标准下,对800×9 216个LDPC码字仿真表明该准则能在很小的性能损失的情况下很大程度地降低平均迭代次数.与现有的几种经典的提前结束迭代准则相比该准则具有性能良好、低复杂度和硬件消耗少的特点.     

一种低复杂度的LDPC码迭代译码算法

在LDPC码的译码算法中，和积算法性能最优但复杂性较高，最小和算法实现简单但性能与和积算法相差较多。针对这一性能与复杂度的矛盾，带有修正项的最小和算法成为研究的热点问题。文中基于一种性能与和积算法接近的修正最小和算法进行研究，对修正项的修正方式进行了简化，简化后的算法在性能上与和积算法仍非常接近，实现复杂度却比原修正最小和算法有明显的降低。     

非平稳信道下LDPC码低复杂度滑窗置信传播联合信道估计与译码算法

随着移动通信应用场景的持续增多,非平稳信道成为越来越常见的传输环境,而非平稳信道下的可靠传输依赖于准确的信道估计。基于信源编码中用于信源参数估计和信源相关性估计的滑窗置信传播(SWBP)算法,该文提出一种非平稳信道下LDPC码的联合信道估计与译码(JCED)算法;同时,分别基于交叉熵和离散傅里叶变换提出两种在每轮JCED迭代中自适应设置滑窗长度的快速算法。仿真结果表明,在无导频辅助的前提下,所提算法具有接近理想信道估计下置信传播译码的性能以及高效率、低复杂度、强鲁棒性和不导致错误平层等优点。     

非平稳信道下LDPC码低复杂度滑窗置信传播联合信道估计与译码算法

随着移动通信应用场景的持续增多,非平稳信道成为越来越常见的传输环境,而非平稳信道下的可靠传输依赖于准确的信道估计.基于信源编码中用于信源参数估计和信源相关性估计的滑窗置信传播(SWBP)算法,该文提出一种非平稳信道下LDPC码的联合信道估计与译码(JCED)算法;同时,分别基于交叉熵和离散傅里叶变换提出两种在每轮JCED迭代中自适应设置滑窗长度的快速算法.仿真结果表明,在无导频辅助的前提下,所提算法具有接近理想信道估计下置信传播译码的性能以及高效率、低复杂度、强鲁棒性和不导致错误平层等优点.     

LDPC卷积码的快速收敛译码

采用串行消息传递策略,文中提出了LDPC卷积码的一种改进的流水线式译码器.分析和仿真结果均表明改进的译码器在不增加单个处理器计算复杂度的前提下,仅通过改变消息传递方式就能够大大加速译码收敛速率,与原译码器相比大约可以节省一半的处理器.     

一种基于分层译码和Min-max的多进制LDPC码译码算法

该文在现有译码算法的基础上提出一种高效的非二进制低密度奇偶校验码(NB-LDPC)译码方法,充分利用了分层译码算法与Min-max算法的优点,不但译码复杂度低、需要的存储空间小,而且可将译码速度提高一倍。应用该算法,对一种定义在GF(25)上的(620,509)码进行了仿真。该码的仿真结果表明：在相同误码率下,该文译码算法所需最大迭代次数仅为Zhang的算法(2011)的45%。     

A Generalization of the Blahut–Arimoto Algorithm to Finite-State Channels

The classical Blahut-Arimoto algorithm (BAA) is a well-known algorithm that optimizes a discrete memoryless source (DMS) at the input of a discrete memoryless channel (DMC) in order to maximize the mutual information between channel input and output. This paper considers the problem of optimizing finite-state machine sources (FSMSs) at the input of finite-state machine channels (FSMCs) in order to maximize the mutual information rate between channel input and output. Our main result is an algorithm that efficiently solves this problem numerically; thus, we call the proposed procedure the generalized BAA. It includes as special cases not only the classical BAA but also an algorithm that solves the problem of finding the capacity-achieving input distribution for finite-state channels with no noise. While we present theorems that characterize the local behavior of the generalized BAA, there are still open questions concerning its global behavior; these open questions are addressed by some conjectures at the end of the paper. Apart from these algorithmic issues, our results lead to insights regarding the local conditions that the information-rate-maximizing FSMSs fulfill; these observations naturally generalize the well-known Kuhn-Tucker conditions that are fulfilled by capacity-achieving DMSs at the input of DMCs.