LDPC码的一种高效加权比特翻转译码算法

针对低密度奇偶校验(LDPC)码中加权比特翻转(WBF)译码算法在迭代过程中绝大多数情况都是进行单比特翻转,导致译码效率低并且可能会发生比特翻转"死循环"的现象,提出一种更为高效的加权比特翻转(EWBF)算法.该算法对翻转阈值进行了改进,使得每次迭代能够翻转多个比特,提高译码效率,并且能够避免译码过程出现的翻转"死循环"现象.仿真结果表明,所提译码算法与WBF算法、改进的WBF(MWBF)算法和IMWBF(Improved MWBF)算法相比,平均迭代次数分别降低51.6%~56.2%、49.6%~54.2%和48.1%~51.3%;而在译码性能方面,算法性能接近甚至优于IMWBF算法,当最大迭代次数设定为30次时,相比于IMWBF算法,在误码率为10-4时可获得0.92 dB的增益.     

系统RA码的基于WBF策略的改进BP译码算法

 针对重复累积(RA)码译码算法(BP算法和最小和算法)复杂度高或纠错性能下降的问题,将加权位翻转WBF的思想用于改进BP算法,提出了基于WBF策略的改进BP译码算法. 在每次迭代译码中若未能译出合法码字,则按一定规则进行位翻转操作,以期获得合法码字. 仿真结果表明,本算法能有效降低系统RA码的运算复杂度,且能保持优异的译码性能.     

Hybrid Iterative Decoding for Low-Density Parity-Check Codes Based on Finite Geometries

In this letter, a two-stage hybrid iterative decoding algorithm which combines two iterative decoding algorithms is proposed to reduce the computational complexity of finite geometry low-density parity-check (FG-LDPC) codes. We introduce a fast weighted bit-flipping (WBF) decoding algorithm for the first stage decoding. If the first stage decoding fails, the decoding is continued by the powerful belief propagation (BP) algorithm. The proposed hybrid decoding algorithm greatly reduces the computational complexity while maintains the same performance compared to that of using the BP algorithm only.     

基于平均幅度的LDPC码加权比特翻转译码算法

针对LDPC码的加权比特翻转(WBF)和改进型加权比特翻转(MWBF)算法,该文提出一种改进型算法。该方法以信息节点的平均幅度作为校验方程的可靠度信息,可以提高比特翻转效率。仿真结果表明,在AWGN信道下,误比特率为10-5时,相比于WBF和MWBF算法,该文提出的算法可分别获得约1.65 dB和1.36 dB的增益。同时,平均迭代次数分别降低18.20%~39.91%和17.54%~34.78%。     

LDPC码加权比特翻转译码算法研究

近年来,基于置信传播(BP),最小和(MS)和归一化最小和(NMS)算法,已经提出3种相对应的LDPC码加权比特翻转(WBF)译码算法。但这3种WBF算法所代表的物理意义和内在的紧密联系问题目前仍未有所研究。该文依据一种全新的理解方式,对3种WBF算法进行理论推导,并阐述3种算法内在的紧密联系,最后通过仿真验证所得结论的合理性和正确性。这对于设计新的改进型WBF算法具有一定的指导意义。     

An efficient decoding algorithm for block turbo codes

An efficient soft-input soft-output iterative decoding algorithm for block turbo codes (BTCs) is proposed. The proposed algorithm utilizes Kaneko's (1994) decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decisions using reliability calculations. Three different schemes for reliability calculations incorporating different levels of approximation are suggested. The algorithm proposed here presents a major advantage over existing decoding algorithms for BTCs by providing ample flexibility in terms of performance-complexity tradeoff. This makes the algorithm well suited for wireless multimedia applications. The algorithm can be used for optimal as well as suboptimal decoding. The suboptimal versions of the algorithm can be developed by changing a single parameter (the number of error patterns to be generated). For any performance, the computational complexity of the proposed algorithm is less than the computational complexity of similar existing algorithms. Simulation results for the decoding algorithm for different two-dimensional BTCs over an additive white Gaussian noise channel are shown. A performance comparison of the proposed algorithm with similar existing algorithms is also presented     

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

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

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.     

MAP algorithms for decoding linear block codes based onsectionalized trellis diagrams

The maximum a posterioriprobability (MAP) algorithm is a trellis-based MAP decoding algorithm. It is the heart of turbo (or iterative) decoding that achieves an error performance near the Shannon limit. Unfortunately, the implementation of this algorithm requires large computation and storage. Furthermore, its forward and backward recursions result in a long decoding delay. For practical applications, this decoding algorithm must be simplifled and its decoding complexity and delay must be reduced. In this paper, the MAP algorithm and its variation's, such as log-MAP and max-log-MAP algorithms, are first applied to sectionalized trellises for linear block codes and carried out as two-stage decodings. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be reduced. Computation-wise optimum sectionalizations of a trellis for MAP algorithms are investigated. Also presented in this paper are bidirectional and parallel MAP decodings     

消息复用下的空间耦合LDPC码窗译码优化算法

空间耦合低密度奇偶校验（Spatially Coupled Low Density Parity Check,SC-LDPC）码由于其奇偶校验矩阵呈现对角带非零项的特点,采用窗译码可获得较低的时延及复杂度。针对SC-LDPC码窗译码性能损失、译码复杂度依然较高的问题,提出了消息复用（Message Reuse for Window Decoding,MR-WD）算法和动态多目标符号输出（Dynamic Multi-target-symbol Output for Window Decoding,DMO-WD）算法。消息复用算法以外部对数似然比值作为边信息传入窗口,与传统窗译码相比,译码性能得到了提升,译码复杂度降低。动态多目标符号输出算法在连续若干个窗口均满足奇偶校验方程判定为零时,增加目标符号的输出数量,反之减少目标符号的输出数量。该算法在误码率损失可忽略不计的情况下降低译码复杂度最大达20%,且在动态多目标符号窗译码中使用消息复用更新边信息时,相比于传统窗译码性能提升约0.2 dB,复杂度下降约35%。     

New concatenated soft decoding of Reed-Solomon codes with lower complexities

To improve error-correcting performance, an iterative concatenated soft decoding algorithm for Reed-Solomon (RS) codes is presented in this article. This algorithm brings both complexity as well as advantages in performance over presently popular sott decoding algorithms. The proposed algorithm consists of two powerful soft decoding techniques, adaptive belief propagation (ABP) and box and match algorithm (BMA), which are serially concatenated by the accumulated log-likelihood ratio (ALLR).Simulation results show that, compared with ABP and ABP-BMA algorithms, the proposed algorithm can bring more decoding gains and a better tradeoffbetween the decoding performance and complexity.     

IRA码最小和译码算法的改进算法

研究了重复累积(IRA)码的简化译码算法.IRA码的BP译码算法具有较高的复杂度,为了降低复杂度,首先提出将最小和算法应用于IRA码.然而,最小和算法使译码性能降低约1.2 dB.为了在复杂度和译码复杂度之间取得较好的折衷,提出了对IRA码的最小和算法的改进算法:归一化算法和偏移算法.仿真结果表明,IRA码归一化算法和偏移算法在复杂度略有增加的情况下,性能得到明显改善.     

A new sequential decoding algorithm based on branch metric

A new sequential decoding algorithm with an adjustable threshold and a new method of moving through the decoding tree is proposed. Instead of the path metric of the conventional sequential decoding algorithms, the proposed algorithm uses a branch metric based on maximum-likelihood criterion. Two new parameters, the jumping-back distance and going-back distance, are also introduced. The performance of the algorithm for long constraint length convolutional codes is compared to those of the other sequential decoding algorithms and the Viterbi algorithm. The results show that the proposed algorithm is a good candidate for decoding of convolutional codes due to its fast decoding capability and good bit error rate (BER) performance. This work was supported in part by the Research Foundation at Karadeniz Technical University under Grant 2004.112.004.01 and 2005.112.009.2.     

On the complexity of decoding lattices using the Korkin-Zolotarevreduced basis

Upper and lower bounds are derived for the decoding complexity of a general lattice L. The bounds are in terms of the dimension n and the coding gain γ of L, and are obtained based on a decoding algorithm which is an improved version of Kannan's (1983) method. The latter is currently the fastest known method for the decoding of a general lattice. For the decoding of a point x, the proposed algorithm recursively searches inside an, n-dimensional rectangular parallelepiped (cube), centered at x, with its edges along the Gram-Schmidt vectors of a proper basis of L. We call algorithms of this type recursive cube search (RCS) algorithms. It is shown that Kannan's algorithm also belongs to this category. The complexity of RCS algorithms is measured in terms of the number of lattice points that need to be examined before a decision is made. To tighten the upper bound on the complexity, we select a lattice basis which is reduced in the sense of Korkin-Zolotarev (1873). It is shown that for any selected basis, the decoding complexity (using RCS algorithms) of any sequence of lattices with possible application in communications (γ⩾1) grows at least exponentially with n and γ. It is observed that the densest lattices, and almost all of the lattices used in communications, e.g., Barnes-Wall lattices and the Leech lattice, have equal successive minima (ESM). For the decoding complexity of ESM lattices, a tighter upper bound and a stronger lower bound result are derived     

Turbo码的一种高效改进型MAP译码算法

该文给出了一种改进型最大后验概率(MAP)译码算法用于实现并行级联卷积码(Turbo码)的最优译码。与基于对数域的Log-MAP算法相比较,该文给出的算法不引入对数域,但能够完全消除标准MAP算法在迭代过程中必须进行的大量指数和对数运算。计算机仿真结果表明,这种具有最优纠错性能的改进型MAP算法能够显著减少运行时间,其译码效率甚至优于牺牲了较多纠错性能的最快速的对数域MAP译码算法(Max-Log-MAP)。     

基于PD-CNN的Polar码译码算法

针对传统Polar码译码算法在相关噪声信道下性能严重下降的问题,提出了一种基于前置预判-卷积神经网络（Prior Decision-Convolutional Neural Networks,PD-CNN）的译码算法。通过前置预判深度优化CNN,使其准确地估计信道噪声并使残余噪声尽可能遵循高斯分布,再根据残余噪声分布统计更新出可靠的似然比信息。分析了不同译码算法对不同码率Polar码在不同噪声相关强度下的译码性能,并与本文所提出的译码算法进行对比。仿真结果表明:在相关噪声信道下,当误码率为10-5时,本文所提出的译码算法与标准置信度传播算法相比可获得约2.5 Bd的增益。此外,在高信噪比时,与置信度传播-卷积神经网络算法相比,本文提出的译码算法具有相同的性能,但复杂度更低,译码延迟最大可减少42%。      

DVB-S中RS译码的快速算法

本文介绍了DVB-S中RS码的编码及常用的译码算法,然后又介绍了几种有限域中快速傅里叶变换(FFT)算法。提出了一种快速频域译码算法,该算法用速度较快的Good-ThomasFFT和素数域中的半快速算法来优化频域译码算法,使DVB-S中(204,188)RS码的译码速度提高了近10倍。     

基于变量节点更新的交替方向乘子法 LDPC惩罚译码算法

基于交替方向乘子法(ADMM)的改进惩罚函数LDPC译码算法能够提升译码性能,但其所需优化参数过多且性能提升有限。针对该问题,将该算法与其它带有惩罚函数的译码算法比较后发现,两者的不同之处仅在于译码算法中变量节点的更新规则不同。因此,该文通过构造一种新的变量节点的更新方法去减少优化参数数目并提升译码性能。实验仿真表明,相较于原有算法,该文所提算法有效减少了所需优化的参数数目,此外,所提算法的平均迭代次数更少且能实现约0.1 dB的性能提升。     

On maximum-likelihood detection and the search for the closest lattice point

Maximum-likelihood (ML) decoding algorithms for Gaussian multiple-input multiple-output (MIMO) linear channels are considered. Linearity over the field of real numbers facilitates the design of ML decoders using number-theoretic tools for searching the closest lattice point. These decoders are collectively referred to as sphere decoders in the literature. In this paper, a fresh look at this class of decoding algorithms is taken. In particular, two novel algorithms are developed. The first algorithm is inspired by the Pohst enumeration strategy and is shown to offer a significant reduction in complexity compared to the Viterbo-Boutros sphere decoder. The connection between the proposed algorithm and the stack sequential decoding algorithm is then established. This connection is utilized to construct the second algorithm which can also be viewed as an application of the Schnorr-Euchner strategy to ML decoding. Aided with a detailed study of preprocessing algorithms, a variant of the second algorithm is developed and shown to offer significant reductions in the computational complexity compared to all previously proposed sphere decoders with a near-ML detection performance. This claim is supported by intuitive arguments and simulation results in many relevant scenarios.     

基于Kaczmarz迭代的大规模MIMO系统低复杂度软输出信号检测

大规模MIMO系统上行链路中,最小均方误差（MMSE）算法能获得接近最优的线性检测性能,但是涉及复杂度较高的矩阵求逆运算.本文基于Kaczmarz迭代提出一种低复杂度软输出信号检测算法,在算法实现中避免了矩阵求逆运算,将实现复杂度由O（K³）降为O（K²）.同时,引入了最优松弛参数进一步加快算法收敛,最后给出了两种用于信道译码的LLR的近似计算方法.仿真结果表明：所提出的Kaczmarz迭代软输出信号检测算法经过两到三次简单的迭代即可较快地收敛,并达到接近MMSE检测算法的误码率性能的水平,其性能与复杂度均优于基于矩阵近似求逆的一类检测算法.