LDPC译码（精选八篇）
LDPC译码 篇1
在全球主要移动运营商的推动下，3GPP RAN通过了开展HSPA演进(HSPA+)研究项目的决定，试图进一步对HSDPA、HSUPA进行增强，为未来的3GPP系统提供平滑的演进路径。HSPA+系统是在原有3G系统中使用了新的调制方式和编码方式，以及全新的MIMO(2×2)配置。
LDPC码具有逼近Shannon限的良好性能,是继Turbo码之后编码领域的又一重大发现。LDPC码在许多场合下优于Turbo码，具有很大的灵活性以及较低的差错平底特性，特别是其译码的复杂度远远低于Turbo码，便于并行操作和硬件实现，因此非常适合在HSPA+系统中使用，从而改善整个系统的性能。
1 基本概念
1.1 HSPA+系统
HSPA+系统在关键技术上，它保留了HSPA的如下特征[1]：快速调度、混合自动重传+软合并(HARQ)、自适应调整和编码等技术以及所有信道及其特征。因此，它向下完全兼容HSPA技术，但为了支持更高的速率和更丰富的业务，HSPA+也引入了更多的新技术例如LDPC码、下行64QAM、上行16QAM、MIMO(2×2)技术，增加了容量，减小了时延，提高了系统使用效率。
1.2 LDPC码
LDPC码是一线性分组码，通常由它的校验矩阵来定义。采用LDPC长码可以达到Turbo码的性能，且具有更低的线性译码复杂度。码率为1/2，码长为107的二元LDPC码在AWGN信道下的误码率为106-时，其性能距Shannon限仅差0.0045dB，是目前已知距Shannon限最近的纠错码。
2 LDPC译码原理
2.1 译码算法
LDPC码的译码算法种类很多，可以分为两类[3]，一类硬判决译码算法，一类软判决译码算法。前者算法比较简单，计算复杂度远远低，并且具有并行结构，是一种便于实现的算法。后者就是BP译码[4]，也就是和积译码算法，它已经被证明是非常有效的，性能接近于最大似然译码。为了得到一定条件下的译码性能与复杂度的合理折衷，Marc P.C.Fossorie和Jinghu Chen等提出了几种简化的LLR BP算法[5]，仅通过加法运算来完成LDPC码的译码，大大降低了译码的实现复杂度。其中常用的是UMP BP-Based算法[6][7]，还有最小和算法。本文通过对UMP BP_based算法进行改进，这样既可以减少运算复杂度，容易硬件实现，并且使它的译码性能非常逼近BP算法。
2.2 UMP BP＿Based算法
UMP BP_Based算法的具体步骤是：
(1)初始化：对特定的信道预设信息比特的先验概率。
(2)计算出从校验节点传递给变量节点的软信息。
(3)计算出从变量节点传给校验节点的软信息。
(4)计算第i个比特Zi的后验概率。
(5)对Zi的后验概率L(Q k)进行硬判决，产生译码结果，将得到的译码结果序列左乘校验矩阵，获得各个校验式的校验结果Sk。
(6)重复2～5步骤，直到Sk=0或到达最大的迭代次数。
UMP BP_Based算法在对数域BP算法的基础上利用的特性基本上有的最小值决定。从而在传统BP算法的基础上简化L(rjik)，从而减少对数域BP算法的复杂度和存储量，并且可以减少算法定点化计算的复杂度。但是，简化后的L(rjik)计算和真实值有一定差距，所以我们提出改进UMP BP_Based算法，对UMP BP_Based算法进行一定的改进和修正。
2.3 改进UMP BP＿Based算法
值的确定：
由传统的对数域的BP算法求得L(rjik)的均值为E(L 1(rjik))，由UMP BP_Based算法求得L(rjik)的均值为E(L 2(rjik))，那么。
2.4 修正前后的UMP BP＿based算法性能比较
我们取1×105个随机数据进行测试，取值在0和1之间，是符合正态分布的随机数。取最小值及精确值计算。可以计算出修正前的UMP BP_based算法由于Y=X和实际的值相差比较大，不仅均方误差1NNi=∑1(yi-xi)2=0.0 186，而平均误差1NNi=∑1(yi-xi)=-0.123，由于存在较大的平均误差，在迭代过程中就会产生误差积累，从而导致性能下降。用正比例一次曲线拟合后的UMP BP_based算法估计值和精确值之间的均方误差为-0.017，均方误差为0.0038，比修正前算法的取最小值的方法有很大的性能改善。从二者对比可以发现，修正后的BP_based算法运算的复杂度和简化的BP算法几乎相近，但是当选择恰当的修正因子后，它的译码性能非常逼近BP算法的性能，而且可以减轻算法定点化计算的难度，所以修正UMP BP_based算法是一种比较优化的LDPC译码算法。
3 HSPA+系统及仿真结果
3.1 HSPA+系统分析
表1中第1～9类为HSDPA终端类型及参数，从表中可以看出HSPA+系统向上完全兼容HSDPA，同样也完全兼容HSUPA。
从表1详细列出了不同类别终端对应的峰值速率，以及影响峰值速率的各种因素。从表中我们可以总结对HSPA+系统影响终端峰值速率的主要因素有：调制方式、MIMO技术、支持最大的码字数。本文选用MIMO(2×2)配置技术，下行64QAM调制解调方式，上行16QAM调制解调方式。在TDD系统中以下行为例HSPA+系统结构基本框架图如图1所示。
3.2 LDPC译码算法仿真
在HSPA+系统中，使用64QAM调制解调，空时编码以及空时解码，在AWGN信道中，使用改进的UMP BP_Based LDPC译码算法进行译码仿真，仿真环境如图2所示。
利用图2的仿真环境，在码率为CR=1/2、码长为n=576，在AWGN信道参数E b/Nb一定的情况下，对比在BPSK,QPSK,16QAM,64QAM不同的调制方式下其译码的仿真图如图3、4所示。
从图3、图4通过对比使用UMP BP_Based LDPC译码算法分别在BPSK、QPSK、16QAM、64QAM调制方式下进行调制，可以看出，在误码率一定的情况下使用64QAM调制方式比QPSK调制方式信噪比提高将近2 dB。
4 结论
在HSPA+系统中，信源和信道要对编译码更高，虽然Turbo码已经可以满足对编译码的要求，但是由于Turbo码译码复杂度大，硬件资源占用多。当今很多TD芯片编译码方式是做成硬件的，LDPC码译码复杂度低，占用硬件资源少，更适合固化中芯片中。所以，如果在HSPA+系统中使用LDPC码将会极大提高系统的性能。
摘要：HSPA+系统中引入了LDPC码、上行16QAM、下行64QAM、MIMO等新技术,成为后3G的发展方向。本文在AWGN信道环境下,利用UMPBPBased译码算法,分别在BPSK、QPSK、16QAM调制方式下对LDPC译码算法进行仿真,仿真结果表明,LDPC码非常适合在HSPA+系统中,表现出其优越的性能。
关键词：HSPA+系统,UMP,BPBased,LDPC码,16QAM
参考文献
[1]Theodore S.Rappaport.无线通信原理及应用.北京电子工业出版社,2002.37-46
[2]郑侃,赵慧,王文博.3G长期演进技术与系统设计.电子工业出版社
[3]Mackay D.J.C,Hesketh C.P.Performance of Low Density Parity Check Codes as a Function of Actual and Assumed Noise Levels,Electr.Notes Theor.Comput.Sci,2002,74
[4]Fossorier M.Iterative Reliability-based Decoding of Low-Density Check Codes,IEEE J S A Comumun,2001,19(5):908-917
[5]Chen J,Forroier M.Near optimum universal belief propagation based decoding of LDPC codes,IEEE Trans on Commum,2002,50(3):406-414
LDPC译码 篇2
关键词低密度奇偶校验码；分层修正最小和译码算法；惰性调度
低密度奇偶校验（Low-density Parity-check）码[1] 是可以实际应用，性能接近Shannon极限的纠错编码，因而得到广泛关注，对于现在的无线通信有着至关重要的作用。在LDPC码译码时，由于校验节点与变量节点之间有大量的信息传送，因此降低LDPC码的译码复杂度与译码器的功率消耗，关键在于减少信息传送的运算量。
Gallager在提出LDPC码的同时给出了一种基于概率域的迭代译码算法，这就是目前被普遍采用的置信传播算法（Belief Propagation），又称为和积算法（Sum-Product Algorithm简称SPA）。借助于和积算法，LDPC码可获得最优的译码性能，但校验节点计算中的双曲余切函数 为算法的硬件带来了很大的困难。分层最小和译码算法用min（x）最小值函数代替了复杂的 函数，大大降低了译码算法的复杂度，而译码性能与和积算法非常接近。
一、分层最小和译码算法
分层译码的思想是将LDPC码的校验矩阵按水平方向分层，每一层可看作独立的码，各层的交集构成完整的码，
假设校验矩阵可分为M层，其中每一层的最大列重为1，译码时顺序处理每一层，所有M层参加完一次译码后完成一次迭代。记变量节点i的初始对数似然率（LLR）信息为 ；第n次迭代中，变量节点i传向第l层中检验节点j的LLR信息为 ；第l层的校验节点j传向变量节点i的LLR信息为 ；变量节点i的后验概率信息为 ；与校验节点j相连的变量节点集合记为N（j）。
分层置信传播译码时，首先进行初始化： =
随后对校验矩阵进行逐层译码，在每一层中变量节点i传向校验节点j的信息为：
=-
=-
校验节点j返回至变量节点i输出信息为:
= ×
其中 ， 表示与校验节点j相连的除去i节点外的变量节点的集合。同时更新变量节点的后验信息 = + 由于函数 的实现较为复杂，因此可将置信传播中 的简化为求最小值运算，得到最小和译码。同样，可将分层译码运用于最小和算法。此时校验节点的处理有所不同；
= ×
将和积算法简化为最小和运算后，将带来性能损失。因为最小和算法是高信噪比情况下对校验节点处理的简化，在一般情况下，其校验节点的输出信息都要大于最优的和积算法，因此，可以对最小和算法中校验节点输出的信息乘以乘性因子α（α<1）进行补偿；
在分层译码的最小和算法中引入乘性因子，得到分层修正最小和译码算法。
二、惰性调度在分层修正最小和译码算法的应用
在以上LDPC码译码算法中，经少量迭代次数，变量节点信息就可以稳定的传送，当变量节点信息的后验概率达到很高时（>98%）就可以使变量节点在接下来的迭代中处于睡眠状态，不再对传入和传出的信息进行更新，因此会减少很多的运算量，并且也不会影响到译码的结果。减少复杂度的分层修正最小和算法（R-L-MSA）如下：
当变量节点后验信息 超过设定值 ，将进行以下操作：
（1）变量节点后验概率信息 不会被更新，(6)式不会执行，无法影响到硬判决的结果。
（2）校验节点传向变量节点的信息 无法更新，（5）式跳过。
（3）变量节点传向校验节点的信息 无法更新，（3）式不能跳过，因为（4）式中的S的计算需要参量 。而当变量节点后验概率信息 能够稳定的传递时，不会影响到（3）式也不会直接跳到（7）式，这样简化了对校验信息的读取。
我们应设定合适的 值，如果设置的太低，则会出现“地板效应”。这时的处理方法是，译码器定时的唤醒睡眠节点来更新信息，这一定时可以设置为 次迭代。exe（）（ 小于其设定值 ，当前迭代次数到达 时）决定是否要唤醒变量节点，被唤醒后的节点，根据更新的信息来决定其工作状态。
三、LDPC码译码器的结构
基于改进算法，我们设计了译码器结构。
图1 译码器结构
Fig.1 Decoder architecture
比特信息单元（Get Bit Information unit）执行算法中的（3）式和（7）式；
串处理单元（Serial processing unit）执行（4）式；
信道信息单元（Get channel information unit）执行（5）和（6）式；
这样可以看出，我们增添译码器的部分为变量节点向量寄存器（variable node vector register ），其向量值与码长相等，用来监控变量节点是否处于睡眠状态。判断单元判定 值是否超过了设定值 ，并将结果反馈到变量节点向量寄存器。判定的结果又决定了惰性调度的控制器是否要执行检验节点与变量节点的信息传送。
当 值超过了设定值 时，检验信息将不会在其存储器中被读取；在信道信息单元没有任何运算，更新校验信息和变量节点后验信息不再需要，当然也就没有必要写入其相应的存储器中，此时变量节点处于睡眠状态。
四、仿真
我们对提出的算法进行了计算机仿真。仿真时取码长1024，码率R=1/2，采用BPSK调制和加性高斯白噪声信道，最大迭代次数为30.仿真结果如图2所示，在信噪比为0.8dB-1.3dB时减少分层的最小和译码算法（R-L-MSA，取 =10， =5）的误码率要优于和积算法（Sum-Product Algorithm），而最小和算法的译码性能则较差。
图2 MSA，SPA和R-L-MSA（ =10， =5）算法的性能比较
SNR
(dB)MSA
(K Ops)SPA
(K Ops)运算量减少百分比（%）R-L-MSA
(K Ops)运算量减少百分比（%）
17109786742465.446502899.33
3986478303718.797501331.51
5593144786323.923812144.21
73370240753-17.302296546.75
9131464265-55.97825259.30
图3 R-L-MSA（ =10， =5）与SMA、SPA相比减少的运算量百分比
Fig3、Operation of R-L-MSA（ =10， =5）reduction comparison with SMA、SPA
五、结论
为了进一步降低分层最小和译码算法的复杂度，在此篇论文中，我们提出了减少复杂度的分层最小和译码算法，当变量节点的后验信息概率较高时，变量节点处于睡眠状态，达到了目的。仿真结果表明我们改进的算法使变量节点运算量减少接近60%，减少了译码器的功率消耗，并保持了译码的良好性能。
参考文献
[1] R G Gallager. Low -Density -Parity –Check Codes.IER Transactions on Information Theory,1962:21-28.
[2] A Anastasopoulos.A Comparison between the sum –product and the min-sum iterative detection algorithms based on desity evolution[C]//.Global Telecommunications Conference(Volume2).San Antonio ,Tx,2001:25-29.
[3] F Zarkeshvari,A H Banihahemi.On imp lamentation of min-sum algorithm for decoding Low-desity parity-check (LDPC)codes[C]//.Global Telecommunications Conference (Volume 2).Taipei,2002:17-21.
[4] SL Howard,V C Gaudet,C Schlegel. Soft-BitDecoding of Regular Low-Density Parity-Check Codes.IEEE Transactions on Circuits and systemsⅡ,2005,P(99) .
[5] Hocevar D. A reduced complexity decoder architecture via layered decoding of LDPC codes [C]//IEEE Workshop on signal processing systems,sips:Design and Implementation .Austin,Texas,USA:IEEE,2004;107-112.
[6] Fossorier M,Mihaijevic’M,Imai H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation.IEEE Tranactions on communications,1999,47(5):673-680.
[7] Chen JH,Fossorier M Density evolution for two im2 proved BP2 based decoding algorithms of LDPC codes.IEEE Communications Letters,2002,6(5):208-210.
LDPC译码 篇3
LDPC码的译码算法可分为硬判决算法和软判决算法两种。两种算法各有优势和不足,硬判决易于实现,但性能较差;软判决性能较好,但复杂度高。文献[3]提出了混合比特反转(HBF)译码算法,核心思想是先进行BP译码,再进行BF译码,并且指出在译码复杂度不增加许多的情况下,HBF算法性能优于BP算法,此译码算法是先进行软判决,再进行硬判决,虽然性能有所提高,但是译码复杂度并没有降低,还有所升高。本文提出了一种混合迭代译码算法(Mixed Iteration Algorithm,MIA),核心思想是先进行硬判决,再进行软判决,这样在误码率性能没有下降的前提下,译码复杂度大大降低,并且减小了传播时延。
1 LDPC译码算法
1.1 硬判决算法
最初的硬判决算法是由Gallager提出的比特翻转算法(BF)[1],原理是传输序列的某一比特参与的校验方程错误越多,则认为此比特错误的概率越大,因此翻转该比特。BF算法在迭代过程中传递的是二进制硬信息,复杂度低,但性能较差。为了进一步提高BF算法的性能,Y.Kou等提出了一种加权比特翻转(WBF)算法[4],考虑利用信道输出的软信息,也就是比特判决的可靠度undefined越大,则其硬判决值的准确度就越高,因而获得了性能与复杂度之间的良好折中。WBF算法将一个校验关系的破坏归因于校验方程中绝对值最小的那一个符号。如果校验方程不成立,该方程中所有相关符号都可能出错,绝对值越小,符号出错的可能性越大,但绝对值较大的符号的可信度同样不应被忽略。基于以上分析,Feng Guo等提出了一种可靠性加权比特翻转(RRWBF)算法[5]。
1.2 软判决算法
在软判决译码算法方面,最初Gallager提出了置信传播算法(Belief Propagation Algorithm,BP),其中需要大量乘法和加法运算,Kschischang等将BP算法作了改进[6],通过对数将乘法运算变为加法运算,即对数域BP算法(LLR BP),在计算校验位节点信息时,该算法要用到双曲正切运算,实现复杂,为此,Fossorier研究了低复杂度的迭代译码算法[7,8],将校验位节点信息的计算简化为求符号运算和求最小值运算,提出了最小和算法(UMP BP-Based)。
2 MIA算法
RRWBF算法操作简单,易于硬件实现,但是性能较差,UMP BP-Based算法性能较好,但实现复杂度较高。MIA算法就是将两者结合,通过设定最大迭代次数iterRRWBF和iterMSA,提供的误码率性能接近UMP BP-Based算法,译码复杂度在RRWBF和UMP BP-Based算法之间,并且减小了传播时延。
假设二进制码字c=[c0,c1,…,cN-1],经过BPSK调制后得到序列x=[x0,x1,…,xN-1],其中xn=1-2cN,0≤n≤N-1,x进入均值为0,方差为σ2=N0/2的AWGN信道后得到信道输出序列y=[y0,y1,…,yN-1],其中yn=xn+vn,0≤n≤N-1,vn为加性高斯白噪声。根据接收序列y进行判决得到二进制硬判决序列z=[z0,z1,…,zN-1]。MIA算法的步骤如下:
1) 计算校正子s=[s0,s1,…,sM-1],即
undefined,m=0,1,…,M-1 (1)
如果s=0,停止迭代,输出硬判决序列z并显示译码成功,否则进入步骤2)。
2) 计算翻转函数En,即
undefined
undefined
3) 翻转最大的En所对应的比特zn。
4) 若s=0,则译码结束;若s≠0且未达到最大迭代次数,重复步骤1)～3),否则,执行后续步骤。
5) 初始化L(qij)=L(ci)=2yi/σ2。
6) 进行迭代处理,其中校验节点消息处理为
undefined
变量节点消息处理为
undefined
译码判决为
undefined
若L(Qi)>0,则undefined,否则undefined;若undefined或者达到最大迭代次数,则译码结束,否则从步骤6)继续迭代。
3 算法仿真及分析
为了验证混合译码算法的性能,采用BPSK调制、AWGN信道,选用Mackay的1A方法生成码长为200、码率1/2的LDPC码进行性能仿真。
3.1 算法性能比较
BF算法、RRWBF算法、UMP BP-Based算法和MIA算法在最大迭代次数为10时的误码率曲线如图1所示。
由图1可以看出,MIA算法误码率性能接近UMP BP-Based算法。
3.2 不同算法迭代次数比较
LDPC码的每种译码算法都要设定算法最大迭代次数,算法迭代次数会随着Eb/No的增大而减小,算法的复杂度一部分决定于算法的平均迭代次数,而MIA算法的平均迭代次数是由RRWBF算法和UMP BP-Based算法的平均迭代次数共同构成的。根据蒙特卡罗法可以计算固定Eb/No值时的算法平均迭代次数,本节设定算法的最大迭代次数为50,BF算法、RRWBF算法、UMP BP-Based算法和LLR BP算法4种不同算法的平均迭代次数曲线如图2所示。
由图2可以得出,当Eb/No=1 dB时,各算法的平均迭代次数如表1所示。
3.3 算法复杂度分析
码率1/2的LDPC码(n,p,2p),各种算法的每次迭代的运算量如表2所示[9]。
由表2可以计算,本文选用Mackay的1A方法生成的码为(200,3,6),每次迭代时RRWBF算法需217次加法,UMP BP-Based算法需850次加法,RRWBF算法运算量是UMP BP-Based算法的1/4。由分析可知,Eb/No=1 dB时,RRWBF算法误码率性能约为10-2,根据分析可知,RRWBF算法平均迭代次数为11,UMP BP-Based算法平均迭代次数为4。可以定义:平均算法复杂度为Iaverage,单次算法复杂度为I,平均迭代次数为N,则Eb/No=1 dB时,UMP BP-Based和MIA算法平均算法复杂度公式分别为
Iundefined=NUMP BP-Based×IUMP BP-Based (7)
Iundefined=NUMP BP-Based×IUMP BP-Based×1%+
NRRWBF×IRRWBF×99% (8)
由此可以计算,在Eb/No=1 dB时,MIA算法平均算法复杂度为2 431次加法,而UMP BP-Based平均算法复杂度为3 400次加法,MIA算法比UMP BP-Based算法运算复杂度降低了28.5%。
4 小结
本文提出的MIA算法先进行了硬判决,后进行了软判决译码,充分发挥了RRWBF算法实现复杂度低,UMP BP-Based算法性能好的优点,实现了在误码率性能没有下降的前提下,译码复杂度明显降低的效果,进而使得传播时延得到减小。根据MIA算法设计的LDPC解码器将会非常适用于质量很差、实时通信要求较高的信道,如临近空间雨衰信道、蜂窝网的城市环境的信道等。设备复杂度有所提高,但对于设备集成度越来越高的今天,这个因素的影响力将越来越小。
摘要：根据LDPC码RRWBF算法和UMP BP-Based算法,提出一种混合迭代译码算法。该算法充分利用硬判决算法具有复杂度低和软判决算法性能好的优点,实现了在误码率性能没有下降的前提下,译码复杂度明显降低的效果,进而使传播时延得到减小。仿真结果表明,经过精心设计的不同迭代次数的MIA算法与性能相当的UMP BP-Based算法相比,译码复杂度降低28.5%。
关键词：LDPC码,RRWBF算法,UMPBP-Based算法
参考文献
[1]GALLAGER R G.Low density parity check codes[M].[S.l.]:MITPress,1963.
[2]肖扬.Turbo与LDPC编解码及其应用[M].北京:人民邮电出版社,2010.
[3]周立媛,张立军,陈常嘉.低密度校验码的混合比特反转译码算法[J].北京交通大学学报,2005,29(2):1673-0291.
[4]KOU Y,LIN S,FOSSORIER M.Low density parity check codes based onfinite geometries:a rediscovery and new results[J].IEEE Trans.Infor-mation Theory,2001,47(7):2711-2736.
[5]GUO F,HANZO L.Reliability ratio based weighted bit-flipping decodingfor low-density parity-check codes[J].IEEE Trans.Electronic Letters,2004,40(21):1356-1358.
[6]KSCHISCHANG F R,FREY B J,LOELIGER H A.Factor graphs and thesum-product algorithm[J].IEEE Trans.Information Theory,2001,47(2):498-519.
[7]FOSSORIER M P C.Iterative reliability-based decoding of low-densityparity check codes[J].IEEE Journal of Selected Areas in Communica-tions,2001,19(5):908-917.
[8]FOSSORIER M R C,MIHALJEVIC M,IMAI H.Reduced complexity it-erative decoding of low-density parity check codes based on belief propa-gation[J].IEEE Trans.Communication,1999,47(5):673-680.
LDPC译码 篇4
LDPC码是一种具有稀疏校验矩阵的 (n, k) 线性分组码, 其具有逼近香农 (Shannon) 限的优良性质[1]。近年的研究表明, LDPC码是一类性能优异的好码, 它比Turbo码在技术上更具有优势, 更能适应未来通信系统高速数据传输和高性能的要求[2]。
LDPC码基于稀疏校验矩阵的特点使得它存在高效的译码算法, 能够克服分组码在码长较长时所面临的巨大译码计算量[3], 便于硬件实现。因此, 开展相关标准的技术开发和设计工作是十分重要和必要的, 相关技术的研究成为当前通信技术方面的一个研究的重点和热点。
1 CCSDS标准中的LDPC码
CCSDS标准实验规范由2部分组成: (1) 描述了一种码率为7/8的LDPC码, 该码的特点和性能适用于近地 (Near-earth) 应用; (2) 描述了一组多码率的LDPC码, 该码组的设计特点和性能适用于深空 (Deep-space) 应用[4]。这里采用深空通信中所采用的编译码方案。方案中定义了9种深空中适用的LDPC码, 信息位的长度分为1 024、4 096和16 384三种, 码率也分为1/2、2/3和4/5三种。1/2码率的LDPC码校验矩阵表示为:
式中, IM和0M分别表示M×M的单位矩阵和全零矩阵;Π1~Π8表示交织矩阵;交织矩阵Πk在第i行和第πk (i) 列i∈{0, ……M-1}非零, 其余元素为零。πk (i) 的定义如下:
M的取值不同可以获得不同码长的1/2码率的LDPC码。4/5码率的LDPC码校验矩阵可由矩阵H1/2经过简单扩展得到。
2 译码算法
2.1 归一化最小和算法
LDPC码常用的软判决译码算法是基于置信传播 (BP) 算法[5,6], 也称为和积译码算法, 但该算法校验节点计算中函数运算硬件实现复杂度很高, 不利于高速译码器的实现。归一化最小和 (NMS) 算法对和积译码算法校验节点消息更新过程进行了简化[7], 归一化最小和算法译码的步骤如下:
(1) 计算信道传递给变量节点的初始概率似然比信息L (Pi) , i=1, 2, …n;然后对每一个变量节点i, 设定变量节点传向校验节点初始信息表示为:
式中, yi为信道软比特信息;
(2) 计算第l次迭代时校验节点传向变量节点的消息:
(3) 计算第l次迭代时变量节点传向校验节点的消息:
(4) 硬判决译码, 对所有变量节点计算硬判决消息:
若L (l) (qi) >0, 则判决
(5) 若Hc^T=0或者到达最大迭代次数, 则结束运算, 输出判决结果, 否则重复步骤 (1) ~步骤 (4) 。
其中, α为归一化补偿因子;Rj为校验节点j相邻的变量节点集合;Ci为变量节点i相邻的校验节点集合;Rj/i为集合Rj中除变量节点i以外的所有元素;Ci/j为集合Ci中除变量节点j以外的所有元素。
2.2 信息量化
信息量化的主要目标是找到一个定点表示模型, 在性能衰减的可接受范围内用尽可能少的位宽表示数据[8]。降低数据占用的位宽, 能够减小译码器消耗的硬件资源、降低功耗的同时提高处理器的运行速度。
本文通过大量仿真验证, 确定在外信息和信道信息均为8 bits量化的情况下, 15次迭代的归一化最小和算法译码性能损失较小。因此本方案的译码器量化比特数选择为8 bits, 其中1 bit表示符号, 3 bits表示整数位, 5 bits表示小数位, 归一化补偿因子α为0.75, CCSDS (5120, 4096) LDPC码在量化前后的性能对比如图1所示。
2.3 译码器结构
归一化最小和译码算法实现结构有3种:串行结构、全并行结构和部分并行结构[9]。本文综合考虑译码器占用资源和运行速度之间的矛盾, 采用部分并行结构实现高速LDPC译码。
部分并行译码器的结构主要包含5个部分:输入缓存模块RAM_A集合、输出缓存模块_B、校验节点计算单元CFU集合、变量节点计算单元VFU集合和迭代信息存储阵列。部分并行译码器结构如图2所示。
输入缓存模块RAM_A集合用于存储信道初始软比特信息, 包含n个RAM存储块;校验节点计算单元CFU集合用于完成校验节点到变量节点的信息更新计算, 即完成式 (4) 的运算;变量节点计算模块VFU集合用于完成变量节点到校验节点的信息更新计算, 同时计算变量后验概率并进行硬判决译码输出, 即完成式 (5) 和式 (6) 的运算;存储阵列用于存储校验节点和变量节点信息, 由m×n个基本存储单元组成;输出缓存模块用于存储译码输出码字。
在传统的LDPC译码器译码工作过程中, CFU和VFU两者是交替工作的, 译码器在同一时刻只能进行一种运算, 硬件的利用率不足。为了提高译码效率, 文献[10]提出了一种2帧数据同时译码, 译码器中CFU和VFU计算单元交替处理2帧不同的信息的译码设计方法。两帧并行译码CFU和VFU更新时序图如图3所示。
译码器在一次译码迭代过程中同时读入2帧数据, 在同一时刻VFU和CFU分别处理不同的数据帧, 交替进行。由于CFU和VFU交替处理2帧不同的数据, 该方法下设计的译码器接近传统设计方法的2倍, 大大提高了译码效率[11]。
2.4 吞吐量分析
吞吐量是指译码器在单位时间内能够接收并完成译码的最大数据速率, 吞吐量计算为:
式中, n为LDPC码的码长;fc为译码器工作时钟频率;R为码率;N为译码器同时译码的帧数;b为LDPC码子矩阵的维数;Niter为译码器的迭代次数。
中码长n等于5 120;译码器工作时钟fc等于150 MHz;码率R等于4/5;译码器采用2帧同时译码, N=2;校验矩阵划分为12行, 44列的子矩阵, 每个子矩阵是维数为128的方阵;译码器的迭代次数Niter等于15次, 采用式 (8) 可以计算得到译码器的吞吐量为320 Mbps。
3 译码性能仿真结果分析
为了验证上述译码器性能, 对CCSDS中定义的 (5 120, 4 096) 译码器在AWGN信道下的译码器性能进行了仿真。调制方式采用BPSK调制, NMS算法中使用的归一化因子为α=0.75。不同迭代次数下 (5 120, 4 096) LDPC码的译码性能曲线如图4所示。
仿真中归一化最小和算法的迭代次数分别选取15次、20次、30次和50次。作为对比, 图4还给出了采用标准和积算法 (BP) 迭代50次的译码性能曲线, 从图4中可以看出, 采用归一化最小和算法迭代50次 (NMS) 与标准和积算法 (BP) 迭代50次相比较性能损失约为0.1 d B。在不同迭代次数的归一化最小和算法 (NMS) 中, 用15次迭代相对于50次迭代性能损失约为0.4 d B, 在可接受的范围之内, 因此在实现过程中选取的迭代次数为15次。
根据所提出的部分并行译码器结构, 在硬件可编程逻辑器件 (FPGA) 上实现了码率为4/5, 码长为5 120的LDPC码的译码算法。FPGA器件选用Xilinx公司的Virtex6系列芯片XC6VLX240T, 采用Verilog HDL硬件描述语言完成了各个模块的寄存器传输级 (RTL) 描述。利用Model Sim 7.2仿真工具进行了功能仿真验证。用Xilinx ISE 14.3综合工具进行了综合、布线, 译码器占用的查找表为56 695块, 占总查找表数的37%;占用的寄存器为53 922, 占总寄存器数的17%;占用的存储器为10 883, 占总查找表数的30%。
4 结束语
针对CCSDS标准中定义的码长为5 120、码率为4/5的LDPC码, 根据其校验矩阵的低密度准循环特性, 设计了基于部分并行结构的采用2帧交替译码的译码器。经过实际测试, 译码器可以在主频为150 Mhz的条件下稳定工作, 满足高速通信的性能要求。
摘要：简要介绍了准循环低密度奇偶校验 (LDPC) 码的重要性, 对CCSDS标准定义的LDPC码进行了深入研究。针对LDPC码的校验矩阵具有稀疏准循环特性, 对归一化最小和译码算法进行了研究, 给出了部分并行译码器的结构。通过数值仿真验证了译码算法在高斯白噪声条件下的译码性能。利用现场可编程逻辑器件 (FPGA) 对CCSDS标准中定义的 (5120, 4096) 码进行了实现。
关键词：CCSDS,低密度奇偶校验码,归一化最小和算法,译码器
参考文献
[1]李志勇, 李文铎.一种高速LDPC编译码器的设计与实现[J].无线电工程, 2009, 39 (7) :17-19.
[2]李刚, 黑勇, 仇玉林.IEEE 802.16e中LDPC译码器的实现[J].嵌入式系统应用, 2008, 24 (10) :18-19.
[3]LI Z W, CHEN L, ZENG L Q, et al.Efficient Encoding ofQuasi-Cyclic Low-Density Parity-Check Codes[J].IEEETransactions on Communications, 2006, 54 (1) :71-81.
[4]冉旭.CCSDS深空通信标准LDPC码编译码器设计[D].西安:西安理工大学, 2010:17-18.
[5]FOSSORIER M, MIHALJ EVIC M, LMAI H.ReducedComplexity Iterative Decoding of Low Density ParityCheck Codes Based on Belief Propagation[J].IEEETransactions on Communications, 1999, 47 (5) :673-680.
[6]魏瑞刚, 陈晖, 邱金蕙, 等.高速数据传输中的LDPC码译码算法研究[J].无线电工程, 2011, 41 (3) :20-22.
[7]谭林, 朱江, 杨军, 等.近地应用CCSDS标准LDPC码动态补偿译码算法研究[J].电子设计工程, 2011, 19 (18) :36-38.
[8]赵建功, 刘香玲.准循环LDPC码的部分并行译码算法[J].无线电工程, 2012, 42 (2) :55-57.
[9]乔华, 管武, 董明科, 等.LDPC码高速译码器的设计与实现[J].北京大学学报 (自然科学版) , 2008, 44 (3) :347-352.
[10]野晓东, 马林华, 王卫民, 等.基于整数运算的LDPC码最小和译码算法[J].通信学报, 2010, 31 (6) :106-111.
LDPC码译码器的设计与实现 篇5
LDPC码译码器的实现一直是研究LDPC码的一个重要方向。传统的短码长LDPC码译码器大多采用LLR BP译码算法进行实现,但是由于有指数和对数运算,相应的译码器资源消耗较高。本文改进了LLR BP译码算法的实现过程,对-ln tanh(|x|/2)函数采用分段拟合的方法,降低了资源消耗,并对码长为40、码率为0.5的规则LDPC码译码器进行仿真实现,给出了时序仿真图以及资源消耗结果。
1 LDPC码的译码算法
对于短码长的LDPC码,典型的译码算法有BP译码算法和LLR BP译码算法[7]。由于BP译码算法比较复杂,采用很多相乘运算,硬件实现的复杂度较高,所以本文采用LLR BP译码算法。LLR BP译码算法流程如下:
1) 初始化。将变量节点传向校验节点的信息初始化为
L(0)(qij)=2y/σ2 (1)
式中:y为接收到的信号;σ2为噪声方差。
2) 校验节点更新。在第l次迭代时,更新与校验节点j相邻的变量节点i∈R(j)传给校验节点的信息
undefined
式(2)可以写成
undefined
式中:Rj/i为除了变量节点i外所有与校验节点j相邻的变量节点的集合。
3) 变量节点更新。在第l次迭代时,更新与变量节点i相邻的校验节点j∈C(i)传给变量节点的信息
undefined
式中:Ci/j为除了校验节点j外所有与变量节点i相邻的校验节点的集合。
4) 译码判决。
undefined
则
undefined
5) 结束。增加迭代次数,把译码结果代入undefined进行校验,H为校验矩阵,undefined为码长长度。若校验方程成立或者达到最大迭代次数,则译码结束,否则继续迭代。
2 译码器结构设计
2.1 译码器总体结构
本文设计的LDPC码译码器总体结构如图1所示。
该译码器主要由变量节点处理模块、校验节点处理模块、交织模块以及码字校验模块组成。选择的码字是码长为40、码率为0.5的规则LDPC码。
2.2 译码器主要模块分析
2.2.1 变量节点处理模块
变量节点处理模块主要完成变量节点更新以及译码判决输出。接收的数据一方面来自初始信道似然信息,另一方面是校验节点传递给变量节点的迭代信息。本文中变量节点处理模块由40个变量节点处理单元构成。
由变量节点更新式(4)可知,每个变量节点更新输出是所有与之对应的校验节点传递来的迭代信息与初始信道似然信息的总和,再减去自身的内信息。另外,取所有信息之后的最高位作为译码判决输出。
变量节点更新运算基本是相同的,不同之处为度不同造成相加的个数不同。图2是度为4的变量节点处理单元的结构,其中din0是初始信道似然信息,din1～din4是校验节点传递给变量节点的迭代信息,dout1～dout4是变量节点更新输出,Check-Value为译码判决输出。
2.2.2 校验节点处理模块
校验节点处理模块的主要作用是更新校验节点到变量节点的迭代信息。本文设计的校验节点处理模块是由20个校验节点处理单元组成的。图3是度为6的校验节点处理单元的结构。
由更新式(3)可知,其主要过程分为两部分。第1部分计算符号,第2部分计算undefined。对于第1部分,对输入信息取最高位再进行异或即可完成符号部分的计算。对于第2部分,最重要的是实现-ln tanh(|x|/2)。由于计算-ln tanh(|x|/2)需要用到指数运算和对数运算,硬件实现的复杂度较高。本文采用一种用分段函数对-lntanh(|x|/2)进行拟合,然后对于分段函数进行6 bit均匀量化,写入MIF文件作为查找表的方法来简化硬件实现。
图4表示的是-ln tanh(|x|/2)与分段函数f(|x|)的对比图。由图4可见,拟合函数与-ln tanh(|x|/2)十分接近。
图5表示的是两种算法对于码长所选择的码字,在迭代次数为11时的误码率性能。由图5可见,这种用拟合函数代替-ln tanh(|x|/2)的方法与原LLR BP译码算法的误码性能相当。
3 译码器的仿真实现结果
本设计基于Quartus II 9.0进行仿真,使用Verilog语言[8],采用的芯片是Cyclone II系列的EP2C35F484C8。
3.1 译码器时序仿真
译码器的仿真实现包括数据的输入和接收。如图6所示为译码器译码的时序仿真结果。从图6中可以看出,收到的编码序列(result)在经过11次迭代译码后与译码输出结果(decode_out)一致,可证明仿真结果正确。
3.2 译码器资源使用概况
用Quartus II 9.0仿真得到的译码器的逻辑资源与存储资源利用情况如表1所示。
译码器的最大时钟频率是67.40 MHz,译码器一次迭代需要12个时钟周期,最大迭代次数为11,码长为40,所以11次迭代需要12×11+10=172个时钟周期,译码吞吐率可达到40×67.40/172=15.68Mbit/s,该译码吞吐率对于码长仅为40的译码器来说是很快的,并且由表1可知,译码器的资源仍有较大的余地。
4 小结
本文针对码长40、码率0.5的规则LDPC码,给出了译码算法流程以及FPGA实现方案,详细分析了译码器主要模块的设计,用分段函数拟合-ln tanh(|x|/2)的方法简化了硬件实现。仿真结果表明,译码器的吞吐率达到15.67 Mbit/s的同时,译码器的资源消耗适中,符合预期设计和实现的目标。
摘要：由于传统的LLR BP译码算法不易于FPGA实现,为了降低实现复杂度,采用一种改进的LLR BP译码实现方法,设计了一种码长为40、码率为0.5的规则LDPC码译码器,并完成了FPGA仿真实现。仿真和综合的结果表明,所设计的译码器吞吐量达到15.68 Mbit/s,且译码器的资源消耗适中。
关键词：LDPC码,LLR BP,译码器,FPGA
参考文献
[1]GALLAGER R G.Low density parity check codes[J].IRE Trans.In-formation Theory,1962,8(1):21-28.
[2]SIPSER M,SPIELMAN D A.Expander codes[J].IEEE Trans.Infor-mation Theory,1996,42(6):1710-1722.
[3]DAVEY M C,MACKAY D J C.Low density parity check codes over GF(q)[J].IEEE Communication Letters,1998,2(6):165-167.
[4]ETSI EN 302 307 v1.2.1,Digital video broadcasting(DVB)second gen-eration[S].2009.
[5]康亮,杨波,沈萌.符合CMMB标准的LDPC解码器设计[J].电视技术,2009,33(5):40-42.
[6]李刚,黑勇,刘志国,等.WiMAX中多码率LDPC解码器的设计与实现[J].电视技术,2008,32(2):59-61.
[7]贺鹤云.LDPC码基础与应用[M].北京:人民邮电出版社,2009.
一种改进的多元LDPC码译码算法 篇6
Gallager在1963年提出了二元LDPC码概念[1],Davey和Mac Kay于1998年引出了多元域上的LDPC码[2]。研究结果表明[3],在突发噪声信道中,多元LDPC码可以获得更好的性能,当采用中短码长时,多元LDPC码的性能,特别是抗突发误码能力要明显优于二元LDPC码[4]。但是,多元LDPC码的译码复杂度随着多元域阶数的增大而急剧增长[5],限制了其实际应用。多元LDPC码的推广应用需要寻求复杂度低的译码算法。
多元LDPC码译码算法主要可分为软判决译码算法和硬判决译码算法。软判决译码算法主要有BP、FFT-BP[6,7]和EMS[8]算法等,这些算法均是通过消息向量的迭代进行译码的,其普遍特点是复杂度高,但性能良好。硬判决译码算法由二元LDPC码的大数逻辑译码[9]和比特翻转译码[10]推广而来,这些算法译码复杂度低,但性能有损失。
1 混合译码
在软判决译码算法中,信道接收序列只被检测器用于一次性地提取软译码信息,如图1所示,其中X为发送序列,Y为接收序列,SISO为软输入软输出检测器,U为译码输出的结果。因为SISO检测器生成的概率或者似然比度量,能够包含接收序列中的绝大部分信息。在软译码判决算法中,只利用SISO检测器提取出的信息进行迭代译码。
软判决译码算法忽略了两部分可利用的信息。一是信号的接收序列本身包含的信息,在检测器中并不能一次提取完毕;二是迭代过程中判决结果也包含着变量节点可靠性和稳定性信息,这一部分信息在迭代中并没有得到利用。
对接收序列只利用一次的问题,在文献[11]中,提出了一种新的对接收序列的处理模式,如图2所示。该处理模式源于硬判决算法,检测器基于最大似然准则对接收序列进行硬判决得到估计序列,不产生任何软信息。估计序列在多元LDPC码的硬译码器中经由码约束关系和消息传递原理得到纠错,同时根据大数逻辑规则产生可靠度向量。译码器将纠错完的序列和可靠度向量反馈给检测器,检测器利用获得的反馈信息对软接收序列进行修正。修正将受到噪声污染而偏离原始发送信号的接收信号逐渐移动到正确的发送星座点上。这种处理模式对接收序列的利用并不仅仅是单次的信息提取,而且是基于判决结果的反馈式的多次修正和信息提取。
这种新的处理模式将软判决译码算法中的迭代过程引入到硬判决译码算法中,并利用译码获得的信息对译码初始状态进行调整,是一种混合式的译码算法。
对于软判决译码过程中迭代出的结果包含信息未充分利用问题,也可以从混合译码的角度来进行思考。在硬判决译码算法中,如大数逻辑译码算法中,常常通过对判决结果的统计分析,来对码字的可能值进行判断和调整。可以将这种做法迁移到软判决译码算法中,将迭代后的判决结果用于微调译码向量,使迭代结果朝更有利的方向发展。
2 改进思路及算法
2.1 改进思路
将硬判决译码算法中的统计反馈调整思想应用到FFT-BP译码算法中,可以实现码算法性能上的提升。在联合迭代检测译码算法中[12],2个最重要的译码策略是:
(1)利用校验和信息,采用大数逻辑进行统计。大数逻辑是指在校验和提供的变量节点的外部信息中,对应符号出现的次数越多,该变量节点实际为该符号的可能性就越大;
(2)利用变量节点的统计信息,对检测器接收端的信息序列进行调整。具体为使用统计获得的软信息,采用反馈的方式,对接收序列进行“去噪化”,使其慢慢移动到实际发送的星座点位置附近。
将这2个策略推广到FFT-BP译码算法中:
(1)统计迭代译码的判决结果和其校验和,获得变量节点对应的稳定度信息和可靠度信息。在判决结果稳定的节点中既有保持正确的,也有保持错误的,此时需要利用可靠度信息来加以区分;
(2)用获得的译码信息对迭代过程进行反馈调整。可以在保证稳定度和可靠度的前提下,对消息向量进行微调。调整可靠度高的变量节点的概率值,使其在下一次译码迭代时提供更多的正确信息。
在具体实现中,消息向量的调整幅度应与变量节点可靠度和稳定度有关。随着稳定度的逐渐增加,消息向量更确定的保持在正确或错误的状态。此时,引入可靠度对其正确性进行判断,可靠度高的节点,认为其已经稳定在正确的判决值下。
可靠度可采用非法校验值进行衡量[13]。若信道为加性高斯白噪声信道,编码码字为c=[c1c2…cN],接收端接收信息y=c+n,n为加性噪声,则对y作如式(1)运算。
记[H·n](modq)=·为非法校验。每一次迭代的非法校验值I由式(2)计算。
非法校验值为零的变量节点可靠程度较高,非法校验值不为零的变量节点可靠程度低。
变量节点的稳定度信息由统计得到。对每次迭代判决结果进行统计,变量节点在迭代中判决结果保持不变的迭代次数,即代表着此变量节点的稳定度。对每一次迭代后的判决结果进行统计,并计算判决结果的稳定度。使用式(3)统计稳定度k:
在得到变量节点的稳定度和可靠度信息后,对可靠程度高和已稳定的变量节点,可将其视作为已成功译码的变量节点,并进行倾向性的调整。思路是将此变量节点译码结果对应位置的概率值调整为最大值。在改进的译码算法中,调整消息向量Qmn的方式如式(4)和式(5)进行调整的公式为:
式中,μ为调整的步长,为此变量节点对应的判决符号值。
2.2 改进后的译码算法
改进后的FFT-BP译码算法过程为:
(1)初始化
设xl为发送符号,yl为接收端接收符号。计算各码元符号的q个初始后验概率,记为gna,其中a=0,1,…,q-1,即:
同时用式(1)计算发送序列每个位置的非法校验,用式(2)初始化非法校验值。对H(m,n)≠0的位置,译码消息向量初始化为:
(2)逐行更新Ramn
使用快速傅里叶变换更新Ramn。
(3)更新Qamn
归一化因子amn的选择使得
(4)判决码元符号
每次迭代后,计算码元符号的q个伪后验概率,选取最大的伪后验概率值所对应的a值作为该符号的判决输出:
如果,则迭代结束,译码器将作为码字输出,否则继续迭代。
(5)更新可靠度信息
对当前迭代判决出的结果,用式(2)重新计算此时的非法校验值信息。
(6)更新稳定度信息
对每一次迭代后的判决结果进行统计,用式(3)计算判决结果的稳定度。如果相邻两次判决结果一致,则对应位置的稳定度计数加一。
(7)更新消息向量
根据计算的非法校验值和统计的变量节点稳定度信息,对相应的消息向量进行调整。如果k(n)>c,且此位置的非法校验值为0,即,则依式(4)和式(5)更新消息向量。μ可根据实际情况进行大小的调整。μ可取为较接近1的值以确保在迭代初期,译码正确与否并不明朗时,对消息向量的调整并不会引入额外的错误。
2.3 复杂度分析
若为q进制的多元LDPC码,校验矩阵大小为M×N,行重为dc,列重为dv,则单次迭代增加的计算量为:
乘法:2MN;
加法:2MN-M-N。
对消息向量进行更新的步骤的计算量与当前迭代中统计出的需要改进的节点数有关,其可能的最大计算量为:
乘法:N dvq;
加法:N dv。
改进后的译码算法在单次迭代中增加了计算可靠度和统计稳定度的计算量,可能增加的最大乘法计算量为2MN+N dvq,最大加法计算量为2MN-N-M+N dv。虽然单次迭代的计算量有些许线性增加,但随着对消息向量传递的调整改进,译码所需的迭代次数会下降。
3 仿真分析
对提出的改进算法进行仿真验证,所用的仿真码型为Mackay随机构造法构造的码长700的16元规则LDPC码,其行重为6,列重为3,码率为3/7。仿真使用的调制方式为16QAM,信道为AWGN信道,译码的最大迭代次数为20,仿真停止条件为错误100 bit,μ值为调整步长,c为稳定度参数。本文仿真了多种μ值和c值下的性能情况,并进行了综合的比较,仿真结果如图3所示。
从图中可以看出,不同参数下的改进译码算法与原始译码算法相比均有一定的性能提升,性能提升的幅度在0.1~0.2 d B左右。
此外,仿真还统计了不同参数下译码算法的平均迭代次数,如表1所示。可以看出,不同参数下改进算法的平均迭代次数与原始译码算法相比,并没有显著变化,即在只增加了计算可靠度和统计稳定度的计算量的条件下,实现了性能的改进。
4 结束语
从混合译码思路出发,讨论了将硬判决译码思想应用到FFT-BP译码算法中的问题。从大数逻辑译码算法中的统计调整思想出发,将其应用到FFT-BP译码算法中,对FFT-BP译码算法进行了改进。在统计的稳定度信息和计算的可靠度信息的基础上,迭代中改进的译码算法对变量节点的消息向量进行倾向性的调整,使消息向量能够提供更多的正确信息。仿真结果表明,改进的FFT-BP译码算法可以获得更好的性能。
摘要：在多元LDPC码的软判决译码算法中,迭代过程中没有使用判决结果和校验和中隐藏的一些信息,在判决结果中隐藏着稳定性信息,校验和中隐藏着变量节点的可靠度信息。从混合译码算法思路出发,借鉴硬判决译码算法中统计校验和的做法和联合迭代检测译码算法中的反馈调整思想,对FFT-BP译码算法进行了改进。改进算法利用迭代过程中的可靠性和稳定度信息,对由变量节点向校验节点传递的消息向量进行调整以使其提供更多正确信息。仿真结果表明,改进的译码算法在没有增加复杂度的前提下,提升了FFT-BP译码算法的性能,在不同参数设置下,性能改进在0.2 d B左右。
LDPC译码 篇7
LDPC码[1]以其优良的译码性能和明显好于Turbo码的易实现性,逐渐成为了能够接近香农极限的综合性能最优的码,LDPC码的内在特性也使它能够随着处理技术的发展而获得更好的性能和更低的成本。LDPC码目前主要应用于通信和数据存储领域,下一代无线通信使用的几乎全部都是LDPC码标准,2009年美国NASA通过决议,建立了基于LDPC码的星群通信方案[2]等,因此要求使用LDPC码作为编译码手段的项目也会在未来几年或更长一段时间内蓬勃发展。
目前随着设备小型化、产品平台化步伐的加快,将数个功能的模块集成在一片FPGA上的要求越来越高。LDPC译码器若需要与前端的解调器集成在同一片FPGA上,就需要在开发LDPC译码器的过程中尽量节约硬件的存储资源,使得开发集成平台成为可能。因此节约资源的LDPC码译码器的研究迎合了目前和未来一段时间对高速LDPC译码设备产品集成度高的客观需要,具有良好的应用前景。
下面以CCSDS近地通信标准(8176,7154)LDPC码[3,4]为例,说明节约存储资源,同时保证较高速度的译码实现方案。
1传统译码方案的不足
传统的双向译码算法采用了CNU和VNU分别充当水平运算和垂直运算单元,但是正如在文献[5]中给出的经典LDPC双向译码算法那样,由于LDPC码的译码流程是串行进行的,也就是说需要先进行水平运算,然后用水平运算的结果进行垂直运算,因此对同一码字水平运算和垂直运算是不能够同时完成的,即CNU与VNU总是有50%的时间是空闲的。
另外,传统方法使用了大量的存储器[6],在不加入判决单元的情况下,每个列块有2个存储器参加水平运算,同时每个列块有4个存储器参加垂直运算,再加上一个外部信息存储单元,就已经达到了112个存储器。然而,工程实际的应用中,通常是将前端的解调器也和译码器在同一平台上实现的,这使本来就不丰富的LDPC资源就显得更加的紧张,在这种情况下想要实现高速数据通信的要求就更是难上加难。因此在设计高速译码平台的过程中需要强调存储和逻辑资源的节约,这样才便于开发集成设备。
下面重点阐述一种能够在提高CNU与VNU的利用率、节约存储资源和高速译码之间取得很好平衡的高效高速译码实现方法。
2最小和译码算法
LDPC码的译码算法主要分为软译码算法和硬译码算法,通常情况下采用软译码算法译码获得的编码增益比较高,虽然后来人们提出了很多针对BP算法、最小和算法、BF算法的改进算法,但是在大多数情况下,众多软译码算法中具备实现价值的译码方法之一仍是BP算法的改进算法之一——最小和算法[7,8]。传统最小和算法的水平运算公式为:
undefined。 (1)
垂直运算公式为:
undefined。 (2)
判决公式为:
undefined。 (3)
后来人们改进了最小和算法,提出了Normalized BP和Offset BP两种算法,这2种算法在本质上是等价的[9],都极大地改进了最小和算法的译码精度,使得最小和算法的编码增益更加接近传统的BP算法[10,11,12], Normalized BP算法与传统的最小和算法的区别主要表现在水平运算步骤上,水平运算步骤改为:
Lundefined⇐(1/λk)Lundefined。 (4)
前面乘性因子的数据选择通常为0.7～0.8。
Offset BP算法的水平运算过程为:
undefined。 (5)
式中,β称为偏移因子,式(5)将所有小于β的校验消息设为0,对变量节点消息的计算没有影响。
目前这2种算法中以Normalized BP算法应用较为广泛。这里采用了Normalized BP算法,Normalized BP的参数选择情况如图1所示。
在参数值为1.25时得到了最小和算法的最好修正结果,但是通常在实现过程中,为了利于硬件功能的实现,会将(1/λk)的值设为0.75,这样便于硬件乘法的实现。
3节约存储资源的实现方案
例如对CCSDS近地通信标准(8176,7154)LDPC码,按照文献[5]中给出的译码器实现方案,在水平运算流程和垂直运算流程中,水平运算过程中由于每个列块的行重为2,因此每个列块需要2个存储器来同时提供数据。而垂直运算过程中,由于每个列块的列重都是4,因此需要为每个列块开辟4个存储器。该码共有16个列块,因此可以看出仅仅是水平运算和垂直运算对该译码器的存储器资源消耗已经很大了,再加上外信息存储、译码结果判决,使得该系统的存储器资源愈发紧张。
注意到垂直运算过程中的存储器消耗的数目过大,每个列块都需要配置4个存储器,而且垂直运算过程中进行每一列的运算过程中所用的行信息并没有充分发挥它们的作用,很多有用信息没有被利用。
由图 2可见,左侧是列块1对应的一个用来存储水平信息的存储器,列块1共对应了4块这样的存储器,当列块1需要做垂直运算的时候,需要从水平信息存储器中读出对应行的信息,然而水平信息存储器中每个地址对应的信息,不止包含列块1的行信息,同时也包含了列块2、列块3直至列块N的同一行的信息。因此读取一次水平信息只用来做一个列块的垂直运算的方式,没有充分地利用信息,造成了很大的浪费。为了使得从“水平信息存储器”中每个地址读出的数据都能够被充分地利用,就需要在进行垂直运算时采用与水平运算运算相同的存储顺序。
下面举例说明上述垂直运算信息更新方案。如图 3所示,假设目前水平运算已经完成,开始进行垂直运算,水平运算的结果存储在R存储器内。垂直运算的过程不像上述那样以每一个列块的某一列为开始,而是统一以一个R存储器的地址为开始。假设这个开始的地址就是第1个地址,由图 3中可以看出,读出R存储器中第1个地址的数据可以进行列块C的第0和第6列的运算,同时可以进行列块D的第1列和第7列运算,由于每个存储器每个时钟只能分别读写一个地址,因此同一列块的垂直运算结果不能存入同一存储器,于是将该数据按照图 3中所示的路径存入列块中相应的2个存储器。
接下来R存储器的地址向下扫描,分别取出第2行、第3行等行的水平运算结果,这些水平运算的结果也按照上面所述的方法继续存入M存储器中。最终存储器M1,1和M2,1分别存储了列块C的一半的垂直运算结果。M1,2和M2,2分别存储了列块D的一半的垂直运算结果。
对以上的垂直运算过程需要做如下说明:
① 相邻的2个R存储器地址读出的数据写入M存储器过程中M存储器的寻址方式不一定恰好吻合;
② 在进行下一次迭代的水平运算前,同一列块中2个M存储器中的数据需要进行信息合并后使用。
首先介绍第一点。虽然单独看从存储器R中读取的任何一行数据,与它相关的列都是没有规律的,也就是说M存储器的寻址是随机的,但是如果从R存储器中读取数据的过程是按照存储地址的顺序,以一个初始位置开始,按照地址递增的顺序读取数据,那么需要写入2个M存储器的数据的写入地址都将是相邻的。如图 4所示,假设R存储器的开始读取位置就是第1个地址,第1个时钟周期从R存储器中的第1个地址读出第1行的水平运算结果,然后按照对应位置存入2个M存储器中,此时的地址是需要指定的,但是从第2个时钟周期开始,2个M存储器的写入地址开始依次后排。最终在读取完R存储器中对应第1行块的数据之后,重新定义R存储器的写入地址,然后在下一行块的计算中M存储器的地址依次后排。在这个过程中若采用部分并行的实现方案,依然有可能遇到取出的一组列没有恰好地对应到M存储器的一个地址的情况,在该情况下,可以采用数据的拼接加流水的方法解决问题。
第二点主要是为了使下一次迭代过程中水平运算能够完全利用本次垂直运算所提供的信息。
注意到在垂直运算结束后,垂直运算的结果被分别存储在同一列块对应的2个M存储器中,在下个迭代周期中,每个列块中同一行的水平运算同时需要2个M存储器的信息,也就是说需要2个M存储器相应位置求和后的信息,但是每行的2个需要进行水平运算的列位置不同,而且存储器一个周期只能进行一次读写。因此需要在进行下一次水平运算之前,先将同一列块对应的2个M存储器中的数值求和,求和后的结果是这2个M存储器中的数据完全一致,都变成原来2个存储器中数据的和。然后再进行水平运算,就不会有信息的丢失。
然而,求和是需要花费时间的。考虑到数值求和过程的逻辑过程简单,因此考虑增大存储器的定义宽度,这样求和的过程就不需要像水平运算和垂直运算那样消耗很长的时间,对于整个系统来说可以接受。
另外,在信息合并的过程中,也可以采用上述方法,提前开始下一个迭代周期的水平运算。即每个列块对应的2个M存储器都先以该列块的一组1的列起始位置为起点开始合并并向右做循环移位,合并半个列块宽度之后,开始以另一组1的列起始位置为起点开始合并,同时开始下一个迭代周期的水平运算,这样就可使得数据合并的周期缩短50%。
综上所述,该高效存储器使用方案大大节约了R存储器的使用数量,改善了传统算法中的每个列块都需要配备存储器的不足,整个系统只需要1个R存储器来存储水平运算的结果,而且垂直运算中的数据运算顺序与水平运算时的数据读取顺序一致,因此可以共用同一存储单元存储水平运算和垂直运算的初始位置。
4高效CNU利用方案
上述的译码方案虽然节省了存储资源,但是CNU和VNU的利用率还是各占50%,也就是还是处在算法串行执行的状态,先计算CNU,等CNU的运算完毕再计算VNU。这对于CNU的资源来说是很大的浪费。
利用上述高效存储器使用的译码方法,想要提前进行VNU的计算,必须使得VNU的计算不至于影响到还未完成的CNU运算。
从什么位置开始提前进行VNU的运算才是合适的呢?VNU的高效复用示意图如图5所示。
由图 5可以看出,如果在水平运算进行到位置1的时候(也就是刚开始进行水平运算的位置)就开始用上文所述的方法进行垂直运算,那么在行块A的水平运算结束后,每个列块对应的2个存储器M中的数据都已经被更改了,这样的数据不能够再用来指导行块B的水平运算,因此,在位置1开始进行垂直运算是行不通的。
若在位置2开始进行垂直运算,行块A已经完成了水平运算,而且运算结果已经存储到了R存储器的相应地址内,在行块B开始进行水平运算的同时,用上文所述的方法开始进行垂直运算,在每个列块所对应的2个M存储器中分别进行2组1的列信息更新。由于此时行块A已经完成了水平运算,因此垂直运算的数据更新,不会对行块A的水平运算产生影响。而对于行块B,由于每组1被垂直运算更新的位置,恰恰是刚参与完水平运算的位置,如图 6所示。
在第1个时钟周期,将行块B中的标注1的数据送入CNU,经过处理后存入R存储器,在若干个周期后,将行块B中标注2的数据送入CNU进行水平运算并将运算的结果送入R存储器中,与此同时,进行的是通过R中存储的标注1的数据进行垂直运算,更新存储器M中标注1的数据,以此类推。由于行块B是最后的一个行块,而且在一个列块中,一个 M存储器中的数据只对应一组1,因此水平运算只会从每组1初始的列位置把2个M存储器以循环右移的顺序遍历,而垂直运算对数据进行更新的地址紧随其后,因此从位置2开始提前进行的垂直运算不影响未完成的水平运算。但是垂直运算更新的顺序变为先更新行块B中的信息,后更新行块A中的信息。该算法可以使CNU的运算只进行一半就开始VNU的运算,因此利用率提高了50%。
仿真采用初始软信息6 bit量化,8路并行的方法,通过ISE中Xinlin公司V5-330芯片上的仿真可以看出该方法的资源消耗情况,由于该码校验矩阵列块数为16,因此初始化模块共需要16个72 bit位宽存储器,运算过程中为防止溢出,中间存储过程变为9 bit位宽,因此存储器M共需要32个,R存储器所需位宽为8×(32(符号位)+5(最小值位置)+16(最小值和次小值的绝对值))=424 bit,共需要6个,因此共需要的资源数据如表1所示。
5结束语
针对LDPC码实现过程中存储器消耗量大的问题,通过在垂直运算过程中充分利用取出的水平运算信息的方法,给出了一种能够大量节约存储资源的硬件实现方案,该方案能够使得译码器的存储资源降低50%。同时给出了基于该节约资源的实现方案的垂直运算加速方法,使得信息合并的时间缩短50%,并且不消耗任何多余的存储资源。
参考文献
[1]GALLAGER R G.Low-density Parity-check Codes[J].IRE Transactions on Information Theory,1962,IT-8(1):21-28.
[2]CHEN X,KANG J,LIN S,et al.Accelerating FPGA-basedEmulation of Quasi-Cyclic LDPC Codes with VectorProcessing[J].In Proc.Design,Automation and Test inEurope,2000,15(8):56-62.
[3]MOBINI N,BANIHASHEMI A,HEMATI S.A DifferentialBinary Message-Passing LDPC Decoder[C]∥Proc.Globecom,2007:1 561-1 565.
[4]131.1-O-2.Low Density Parity Check Codes for Use inNear-Earth And Deep Space Applications[S],2007.
[5]SMARANDACHE R,VONTOBEL P.Pseudo-codewordAnalysis of Tanner Graphs from Projective and EuclideanPlanes[J].IEEE Trans.Inf.Theory,2007,53(7):2 376-2 393.
[6]CHEN Xiaoheng,LIN Shu.Memory System Optimizationfor FPGABased Implementation of Quasi-Cyclic LDPCCodes Decoders[J].IEEE Transactions on Circuits andSystems—I:Regular Papers,2011,58(1):63-66.
[7]陈旭灿,刘冬培.改进的LDPC译码算法研究[J].电子科技大学学报,2010,39(2):68-75.
[8]李千玲,陈伟,樊丰.基于DVB-T2标准的LDPC码最小和译码算法的改进[J].电视技术,2011(7):120-126.
[9]张天瑜.MIMO-OFDM系统中LDPC码的改进型最小和译码算法研究[J].云南民族大学学报,2011(2):78-85.
[10]RICHARDSON T J,SHOKROLLAHI M A,URBAMKE RL.Design of Capacity-approaching Irregular Low-densityParity-check Codes[J].IEEE Trans.Inf.Therory,2001,47(2):619-637.
[11]BRINK S T.Design of Serially Concatenated Codes Basedon Iteratively Decoding Convergence[J].2nd InternationalSymposium on Turbo Codes and Related Topics,2000,27(9):319-322.
一种LDPC码改进型BP译码算法 篇8
衡量一种信道编码码字的性能以及应用前景的一个重要因素就是对应的译码算法, LDPC码的译码算法主要有置信传播算法 (BP) 以及在其基础上改进的各类算法。1958年, Gallager首先提出了置信传播算法 (BP) , 随后, Kschischang等人在此基础上进行了推广, 提出了和积算法 (SPA) [6], 此后, 学者们又相继提出了一些BP类的改进算法, 目的主要在于降低算法的复杂度, 在这之中, 应用最为广泛的主要有对数域置信传播算法 (LLR-BP) [7]以及最小和算法 (Min-Sum) [7,8], 但是前者复杂度较高, 不利于硬件实现, 而后者的性能往往较差[9]。
在已有BP类算法的基础之上, 提出了一种改进的LDPC码译码算法, 改进算法 (MBP) 通过引入乘性因子和加性因子两类参数, 使得最小和算法中校验节点传递给变量节点的消息更加精确, 可靠, 因此, 该算法能够在其性能和计算复杂度之间取得良好的折衷。仿真结果表明, 改进后的译码算法在低信噪比条件下的译码性能要优于传统算法, 并且能够降低LLR BP算法的复杂度, 从而兼顾译码性能与译码效率。
1 LDPC码
考虑一个二进制的规则LDPC码, 码长为N, 信息位的长度为K, 其校验矩阵为一个M×N的稀疏矩阵, 设为H, H=[hmn] (0≤m≤M-1, 0≤n≤N-1) , “稀疏”体现在校验矩阵中只有极少量的“1”, 其余位置由零元素组成。对于二进制的规则LDPC码, 其校验矩阵每行“1”的个数都相同, 设为q, 表示每个校验方程中所包含的码元数目相同, 这些码元都受到该校验方程的约束;并且, 校验矩阵每列所包含的“1”的个数也相同, 设为p, 表示每个码元都参与了p个校验方程, 即被p个检验方程约束。Gallager在提出LDPC码后, 就证明了当p≥3时, 这类码的汉明距离特性非常好。式 (1) 是一个6×9的LDPC码校验矩阵, 其中q=3, p=2。
LDPC码的校验矩阵通常利用因子图来表示, 图1表示了与图1所示校验矩阵对应的因子图, 其中x1→x9表示变量节点, z1→z6表示校验节点, 当且仅当某个变量节点参与了某个校验方程时, 它们之间才会有相连的边。
LDPC码的BP类译码算法核心思想就是在每一轮迭代中, 每一个校验节点都利用与其相连的变量节点传来的最新消息对其自身进行消息更新, 并将更新后的消息又再一次传递给与其相连的所有变量节点, 这些变量节点就能利用接收到的消息进行译码判决, 得到一个判决序列, 然后进入下一轮的迭代, 直到所有校验方程都满足, 或者达到最大的迭代次数, 译码失败。
2 BP类算法
2.1 LLR BP算法
在信息传输的过程中, 要发送的信息码字通过信道编码后得到带有校验码的二进制码字序列v= (v0, v2, …, vN-1) , 该序列通过BPSK调制, 按照映射rn=2vn-1, 得到一个对应序列r=[r0r1…rN-1], 然后该序列进入信道, 若信道为一个AWGN信道, 高斯白噪声均值为0, 方差为N0/2, 则通过信道后, 得到输出序列y=[y0y1…yN-1], 其中,
在接收端, 译码器返回的信息是每个变量节点的后验概率, 在LLR BP算法中, 这些概率由对数似然比表示, 在每一轮迭代中, 算法通过获得的信道的先验信息以及计算每个变量节点的最大后验概率逼近值来对该变量节点进行译码判决, LLR BP算法的流程如下:
(1) 根据信道的先验知识, 计算变量节点的初始概率似然比, 如式 (3) , 并将其作为每个变量节点的初始消息, 传送给相连的校验节点。
(2) 校验节点消息更新。设与校验节点j相连的变量节点的集合为R (j) , R (j) i表示R (j) 中除去变量节点i所剩下的变量节点集合, 那么, 在第k轮迭代过程中, 校验节点j通过式 (4) 更新其自身消息, 并把消息传递给与其相连的变量节点i。
式 (4) 中定义函数。
(3) 变量节点消息更新。设与变量节点i相连的校验节点的集合为C (i) , C (i) j表示C (j) 中除去变量节点j所剩下的变量节点集合, 在第k轮迭代过程中, 变量节点i通过式 (5) 更新其自身消息, 并把消息传递给与其相连的校验节点j。
(4) 判决译码。每个变量节点利用先验信息以及与其相连的所有校验节点传递过来的消息计进行译码判决。
如果L (k) (qi) >0, 那么将vi取0的概率大于取1的概率, 将其判为0;如果L (k) (qi) <0, 则将vi判为1。
(5) 若HVT=0或者达到预先设定好的最大迭代次数, 则迭代结束, 否则返回到步骤 (2) 继续迭代。
LLR BP在因子图没有环的情况下可等效为最大似然译码算法, 因此能够获得逼近香农限的译码性能, 此外, 其迭代过程是并行实现的, 从而能够有效地提高译码速度, 降低译码延时。不过, 该算法引入了tanh函数, 其计算比较复杂, 并且要占用较多硬件资源, 因此译码器电路非常复杂, 不利于硬件实现。
2.2 最小和算法
LLR BP算法中要用到tanh函数, 其计算复杂度较高, 且在实际应用中要通过查表才能实现, 因此, 需要占用大量的ROM资源, 所以设计出来的译码器电路相当复杂。最小和 (Min-Sum) 算法是LLR BP算法的一种简化算法, 其不需要进行查表计算, 大大降低了算法的复杂度。
最小和算法主要是对校验节点消息的更新公式进行化简, 而迭代过程中的其余步骤与LLR BP算法完全相同, 从而不需要再计算tanh函数, 化简后的计算式 (7) 。
式 (7) 中, signx表示x的符号。通过式 (7) 可以看出, 最小和算法只需进行符号乘积和计算最小值, 并且符号乘积还可以通过模2求和运算来计算, 因此, 该算法大大降低了复杂度, 计算简洁, 在实际工程中应用较为广泛, 不过, 由于引入了近似计算, 必定会带来译码性能上的损失。
3 改进算法 (MBP)
LLR BP译码算法和最小和译码算法的原理是相同的, 都是通过反复的迭代计算出变量节点和校验节点间传递的信息, 并根据得到的这些信息进行判决。本文提出一种改进型BP类译码算法, 结合了上述两种译码算法的思想, 引入参数, 使得校验节点的消息更新计算方法在复杂度以及译码性能间取得良好的折衷。
设LLR BP译码算法中校验节点消息的更新公式, 即式 (3) 为L1, 最小和算法中校验节点消息的更新公式, 即式 (7) 为L2, 显然, L1与L2的符号相同, 但是幅度不等, 根据tanhx函数的性质, 容易证明L1的幅度小于L2, 即|L1|<|L2|, 这也就是最小和算法性能下降的主要原因。因此, 可以引入参数对L2进行简单地处理, 使其逼近L1, 这样就能够在译码器硬件复杂度较低的基础上, 提高译码算法的性能。
MBP算法的校验节点消息更新公式通过引入乘性因子α和加性因子β, 实现对|L2|的减小, 设该算法的校验节点消息更新公式为L3, 则有:
若想获得更好的译码性能, α和β应该随着信道条件和迭代次数的变化而变化, 但是一般可以把其作为常数处理, 通过仿真获得, 其中0<α<1, β>0。显然, 通过对式 (8) 分析, 要想更好地逼近|L1|, α应该取得较大, 而β应该取较小值。
算法的基本思想是:当|L2|较大时, 先对其进行尺度上的缩减, 而后再引入一个偏移量使其进一步缩小, 更加逼近|L1|;当|L2|较小时, 则可认为其与|L1|相差并不大, 故只需进行尺度上的缩减。此外, 由于L1与L2的符号完全相同, 故L3的符号计算方法仍然运用最小和算法中校验节点更新公式L2的符号计算方法, 即
通过上述分析, 可以看出, LLR BP译码算法会用到大量的乘法器, 因此会占用大量的硬件资源, 并且引入了函数tanhx, 从而导致其硬件电路较为复杂, 算法的实现比较困难。最小和算法对硬件电路进行了简化, 只需进行符号乘积和计算最小值, 但它是以牺牲译码性能为代价的。而改进型算法MBP相比于最小和译码算法, 只是增加了少量的加法器和乘法器, 就可以使得校验节点消息的更新更加精确, 因此, 其可以使得译码性能和算法复杂度得到很好地兼顾。
4 仿真分析
为了验证改进算法的性能, 以Matlab软件作为平台进行实验仿真, 仿真选用的是IEEE802.16e标准中码长为2 304, 码率R=1/2的规则LDPC码, 调制方式为BPSK, 信道为高斯白噪声信道 (AWGN) 。实验采用蒙特卡洛法, 在不同信噪比情况下实验1 000次, 用于观察乘性因子α和加性因子β的取值对算法性能的影响, 以及LLR BP算法、最小和算法和笔者提出的改进型译码算法MBP的误码率性能比较。
4.1 α、β对算法性能的影响
图2表示了最大迭代次数为20时, α、β的取值对MBP算法性能的影响, 可以看出, 当信噪比较低时, α、β的取值对算法性能的影响很小, 可以忽略, 但随着信噪比的增加, 参数的取值会在很大程度上决定算法的性能, 当α取0.9, β取0.1时, MBP算法的性能可以达到最好, 系统的误码率达到最低, 这是因为α作为尺度缩减因子, 如果取值偏小的话, 会大大减小|L2|的值, 使之远远小于|L1|, 同样, 如果偏移量β取得较大, 也会出现同样的问题, 故在MBP算法中, 可把α、β看作常数, 其中α=0.9, β=0.1。
4.2 算法性能比较
LLRBP算法、最小和算法、MBP (α=0.9, β=0.1) 译码算法在最大迭代次数为20和30时的误码率性能曲线分别如图3和图4所示。
从图中可以看出, 最大迭代次数为20次和30次时, LLRBP算法以及MBP算法的性能均优于最小和算法, 当信噪比在1 d B以下时, 三种算法的性能相差不大, 而在信噪比达到1 d B以后, 最大迭代次数的选取将会影响到算法的性能, 随着最大迭代次数从20次增大到30次, 三种算法的性能都得到了一定的提高。最大迭代次数为20次时, MBP译码算法在信噪比较低的环境下, 性能优于LLR BP算法, 不过, 当信噪大于2.5 d B后, 两种算法的误码率已经相当接近, LLR BP算法性能略微超过了MBP算法;最大迭代次数为30次, 当信噪比小于2.3时, MBP译码算法在性能上优于LLR BP算法, 在BER=10-3时, MBP算法比LLR BP算法性能提高近0.3 d B, 但是随着信道条件的改善, LLR BP算法在每轮迭代中概率计算的准确性加强, 其在译码性能上的优势逐渐体现了出来, 当BER=10-5时, LLR BP算法比MBP算法性能提高大约0.1 d B。
5 结论
LDPC码是能够逼近香农限[10]的纠错码, 它良好的应用前景已经引起学术界以及IT业的高度重视。本文在LLR BP算法以及最小和算法的基础上, 进行了改进, 改进的算法通过引入乘性因子和加性因子改变校验节点的消息更新数据, 能够大大降低由于近似计算所带来的误差。此外, 该算法相比于最小和算法, 硬件上只是增加了少量的加法器和乘法器, 因此, 译码电路较为简单, 易于实现。仿真结果表明, 与最小和算法相比, 改进算法的译码性能能得到一定提高, 在低信噪比环境下甚至超过了LLR BP算法。因此, 该算法能够在保持良好的译码性能的同时降低算法的复杂度, 这使得LDPC码能够更好地应用在4G移动通信系统中。
参考文献
[1] Hans-Andrea Loeliger.An Introduction to Factor Graphs, IEEE Signal Processing Magazine, 2004; (1) :29—41
[2] Gallager R C.Low-density Parity-check Codes.Cambridge, MA:MIT Press, 1963
[3] 金美娟, 李川, 仰枫帆, 等.基于生成矩阵的LDPC/Turbo码的构造及内外迭代译码新技术.电讯技术, 2006; (6) :48—52
[4] 杨知行, 王昭城.下一代地面数字电视广播系统关键技术.电视技术, 2011;35 (8) :22—27
[5] 张鹏, 杨刚, 杨霏, 等, 基于改进LU分解的CMMB标准中LDPC编码器设计.电视技术, 2010;34 (4) :33—35
[6] Campello J, Modha D S.Extended bit-filling and LDPC code design.Proc IEEE Global Telecommunications Conference, 2001:985—989
[7] Fossorier M P, Mihal C, Jevic M, et al.Reduced complexity iterative decoding of low-density parity check codes based on belief propagation.IEEE Transactions on Communications, 1999;47 (5) :673—680
[8] Chen J, Fossorier M P C.Near optimum universal belief propagation based decoding of low density parity check codes.IEEE Transactions on Communications, 2002;50 (3) :406—414
[9] Pandya N, Honary B.Low-complexity decoding of LDPC codes.Electronics Letters, 2007;43 (18) :990—991