基于随机置换展开与停止集的LT码联合编译码算法

针对短码长LT码(码长在103以下)的随机编码方式,需要较高的编码冗余才能保证一定的译码性能的问题。设计了一种基于限制Tanner图连接边随机关系的随机置换展开编码算法,可以实现在较小编码冗余开销下提高短码长LT码的可译码概率。在此基础上,针对短码长LT码的传统BP译码算法效率不高的问题,充分利用BP算法译码失败的停止集剩余信息,设计了采用上述编码算法的短码长LT码的停止集高斯译码算法,可以获得接近最大似然译码的性能。仿真结果表明,所提出的编译码联合算法有效降低了短码长LT码满足10 4译码失败概率时所需的编码冗余开销。     

LDPC码加权比特翻转译码算法的低复杂度提前停止准则

近年来,针对LDPC码置信传播(BP)译码算法的提前停止准则的研究已经有了很多,但设计适合加权比特翻转(WBF)译码算法的提前停止准则却研究甚少。依据对WBF算法的全新理解方式,该文提出一种实现简单、适用性强的WBF算法提前停止准则,它能在译码的初始阶段检测绝大多数不可纠错的帧。仿真结果表明,基于提前停止准则的WBF算法在性能损失可以忽略的条件下,极大地降低迭代次数,在实现复杂度和性能之间达到了很好的折中。     

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates     

New stopping criteria for iterative decoding of LDPC codes in H‐ARQ systems

Under severely unreliable channel, decoding of error‐correcting codes frequently fails, which requires a lot of computational complexity, especially, in the iterative decoding algorithm. In hybrid automatic repeat request systems, most of computation power is wasted on failed decoding if a codeword is retransmitted many times. Therefore, early stopping of iterative decoding needs to be adopted. In this paper, we propose a new stopping algorithm of iterative belief propagation decoding for low‐density parity‐check codes, which is effective on both high and low signal‐to‐noise ratio ranges and scalable to variable code rate and length. The proposed stopping algorithm combines several good stopping criteria. Each criterion is extremely simple and will not be a burden to the overall system. With the proposed stopping algorithm, it is shown via numerical analysis that the decoding complexity of hybrid automatic repeat request system with adaptive modulation and coding scheme can be fairly reduced. Copyright © 2012 John Wiley & Sons, Ltd.     

一种适用于Turbo译码的新型迭代停止算法

针对Turbo码迭代译码延时大的问题,本文提出了一种加速译码的新型迭代停止方法,该方法利用了两个分量译码器输出的对数似然比LLR(Logarithm Likelihood Ratio)的统计特性,简称为LCB(LLR Characters Based)算法.同现存的经典停止准则相比,在相同的比特误码率性能下,新方法有效的降低了译码平均迭代次数,加速了Turbo码译码,可应用于流媒体信号传输系统.     

有限平面LDPC码的停止集

有限平面LDPC码是一类重要的有结构的LDPC码,在利用和积算法(SPA)等迭代译码方法进行译码时表现出卓越的纠错性能。众所周知,次优的迭代译码不是最大似然译码,因而如何对迭代译码的性能进行理论分析一直是LDPC码的核心问题之一。近几年来,Tanner图上的停止集(stopping set)和停止距离(stopping distance)由于其在迭代译码性能分析中的重要作用而引起人们的重视。该文通过分析有限平面LDPC码的停止集和停止距离,从理论上证明了有限平面LDPC码的最小停止集一定是最小重量码字的支撑,从而对有限平面LDPC码在迭代译码下的良好性能给出了理论解释。     

基于联合判决消息传递机制的LDPC码译码算法研究

采用消息传递算法(Message passing algorithm)对LDPC码进行译码时,变量消息的振荡会引起错误的发生.本文以(600.300)非规则LDPC码仿真实验为例分析了不同译码效果下判决消息均值的分布特点,并结合环的特点,分析了译码产生错误判决的原因.研究了"纠删"型消息传递机制和联合判决迭代停止准则,针对判决消息出现振荡情况,提出以"纠删"方式处理变量消息的更新,并结合变量节点判决消息均值分布趋势与伴随式结果确定迭代终止条件.在此基础上,提出一种新的LDPC码译码算法.仿真分析表明,新的译码算法能够在减少迭代次数和降低译码复杂度的同时,有效提高译码的纠错性能.     

基于平均概率和停止准则的多元LDPC码加权符号翻转译码算法

为了提高多元低密度奇偶校验(LDPC, low density parity-check)码符号翻转译码算法的性能并降低译码的复杂度,提出了基于平均概率和停止准则的多元LDPC码加权符号翻转译码(APSCWSF, average probability and stopping crite-rion weighted symbol flipping)算法。该算法将校验节点邻接符号节点的平均概率信息作为权重,使翻转函数更加有效,提高符号的翻转效率,进而改善译码性能。并且通过设置迭代停止准则进一步加快算法的收敛速度。仿真结果显示,在加性高斯白噪声信道下,误符号率为10?5时,相比WSF算法、NSCWSF算法(Osc=10)和NSCWSF算法(Osc=6),APSCWSF算法(Osc=10)分别获得约0.68 dB、0.83 dB和0.96 dB的增益。同时,APSCWSF算法(Osc=6)的平均迭代次数也分别降低78.60% ~79.32%、74.89% ~ 75.95% 和67.20% ~70.80%。     

改善LT码性能的预译码集优化方法研究

喷泉码是第一种与码率无关的编码方式.LT码是在删除信道下性能优异的稀疏随机线性喷泉码.与传统编码相比,大大降低了编译码的复杂度.通过分析影响LT码性能的预译码集,提出了优化LT码预译码集的方法.主要在编码端改变初始预译码集大小以及修改度为2的生成矩阵,在译码端利用编码冗余情况来破解译码停止集,同时消除短环.大量的数据仿真结果表明本文方法对译码性能有明显的改善.     

Iterative reliability-based decoding of low-density parity checkcodes

In this paper, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between belief propagation decoding which remains suboptimum, and maximum likelihood decoding which is too complex to be implemented for the codes considered. Trade-offs between decoding complexity and error performance are also investigated. In particular, a stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is proposed for this combined decoding approach. Simulation results for several Gallager (1963, 1968) LDPC codes and different set cyclic codes of hundreds of information bits are given and elaborated     

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes

We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via LovÁsz's Local Lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.      

一种应用于LTE系统的Viterbi译码算法

LTE(long term evolution,长期演进)系统中采用了咬尾卷积码和Turbo码来实现前向纠错,Viterbi译码是卷积码的一种杰出的译码算法,它是一种最大似然译码方法。本文基于LTE系统中的咬尾卷积码,详细分析了几种较成熟的Viterbi译码算法,并综合现有算法,提出了一种改进算法,减小了译码计算的复杂度。仿真结果表明,改进算法在降低译码计算复杂度的同时还降低了译码误比特率,因此非常适合LTE系统的译码要求。     

基于停止集的喷泉编码有限长性能估计

喷泉编码是一类基于删除信道、面向数据分组的前向纠错编码技术。该文分析了停止集的尺度分布对固定码率喷泉编码解码性能的影响,提出了一种估算低误码条件下喷泉编码有限长性能的方法以及一种低复杂度的停止集尺度分布搜索算法。比较结果表明,该文给出的喷泉码解码性能上下界与实际仿真结果非常接近。     

Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-size turbo stopping set which is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garello et al. in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.     

一种简化的LDPC码BP译码算法的研究

低密度奇偶校验码(LDPC码)是一种逼近香农限的线性分组码,译码的复杂度较低;在LDPC码译码算法中性能较好的是置信传播译码(BP)算法,他能够在迭代译码过程中确定码字是否已译出,但是复杂度高,运算量大。采用一种改进的BP译码算法,在迭代译码过程中对校验节点的更新信息进行曲线拟合,以减小译码运算量,有利于硬件的并行实现,减少译码延时。仿真结果表明,改进的BP算法译码性能和原来的BP算法接近,而且复杂度较低。     

基于改进罚函数的LDPC码分层调度ADMM惩罚译码

通过增加伪码字的代价,基于交替方向乘子法（Alternating Direction Method of Multipliers,ADMM）的惩罚译码方法可以改善低密度奇偶校验（Low-Density Parity-Check,LDPC）码低信噪比区域的译码性能,同时具有低的译码复杂度.而减少ADMM惩罚译码的欧几里德投影次数、选择合适的消息调度策略和设计有效的罚函数是提高ADMM惩罚译码速度的三种重要方法.为了进一步提高ADMM惩罚译码速度,通过利用Wei等人提出的方法来减少欧几里德投影的次数,本文设计了基于I-l₁-PF罚函数的水平分层调度与垂直分层调度策略的两种LDPC码ADMM惩罚译码方法.仿真实验表明,与现有ADMM惩罚译码方法相比较,所设计的译码方法不仅具有较好的译码性能,而且能够显著降低LDPC码译码的平均迭代次数和平均译码时间.     

Low-Latency Factorization Architecture for Algebraic Soft-Decision Decoding of Reed–Solomon Codes

Bivariate polynomial factorization is an important stage of algebraic soft-decision decoding of Reed-Solomon (RS) codes and contributes to a significant portion of the overall decoding latency. With the exhaustive search-based root computation method, factorization latency is dominated by the root computation step, especially for RS codes defined over very large finite fields. The root-order prediction method proposed by Zhang and Parhi only improves average latency, but does not have any effect on the worst-case latency of the factorization procedure. Thus, neither approach is well-suited for delay-sensitive applications. In this paper, a novel architecture based on direct root computation is proposed to greatly reduce the factorization latency. Direct root computation is feasible because in most practical applications of algebraic soft-decision decoding of RS codes, enough decoding gain can be achieved with a relatively low interpolation cost, which results in a bivariate polynomial with low Y-degree. Compared with existing works, not only does the new architecture have a significantly smaller worst-case decoding latency, but it is also more area efficient since the corresponding hardware for routing polynomial coefficients is eliminated.     

Stopping Set Analysis of Iterative Row-Column Decoding of Product Codes

In this paper, we introduce stopping sets for iterative row-column decoding of product codes using optimal constituent decoders. When transmitting over the binary erasure channel (BEC), iterative row-column decoding of product codes using optimal constituent decoders will either be successful, or stop in the unique maximum-size stopping set that is contained in the (initial) set of erased positions. Let C_p denote the product code of two binary linear codes C_c and C_r of minimum distances dc and d_r and second generalized Hamming weights d₂(C_c) and d₂(C_r), respectively. We show that the size s_min of the smallest noncode- word stopping set is at least mm(d_rd₂(C_c),d_cd₂(C_r)) > d_rd_c, where the inequality follows from the Griesmer bound. If there are no codewords in C_p with support set S, where S is a stopping set, then S is said to be a noncodeword stopping set. An immediate consequence is that the erasure probability after iterative row-column decoding using optimal constituent decoders of (finite-length) product codes on the BEC, approaches the erasure probability after maximum-likelihood decoding as the channel erasure probability decreases. We also give an explicit formula for the number of noncodeword stopping sets of size s_min, which depends only on the first nonzero coefficient of the constituent (row and column) first and second support weight enumerators, for the case when d₂(C_r) < 2d_r and d₂(C_c) < 2d_c. Finally, as an example, we apply the derived results to the product of two (extended) Hamming codes and two Golay codes.     

基于DTMB标准的最小和积译码改进算法

基于最小和积(MSA)的译码算法,是对数似然比BP(LLR-BP)算法的近似,通过在译码算法中的变量处理阶段添加IIR滤波,同时结合迭代终止准则,实现了一种修改的归一化最小和积算法.该算法仿真建立在DTMB标准中的LDPC码元基础上,仿真结果表明,该算法与常规的归一化译码算法相比,在性能无损失甚至于有所改善的情况下大幅减少了迭代次数,具有很好的使用价值.     

On the stopping distance of finite geometry LDPC codes

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.