基于校验和更新的低复杂度LDPC码硬判决译码算法

吴伊蒙,石志东,邓斌

(上海大学通信与信息工程学院,上海200444)

基于校验和更新的低复杂度LDPC码硬判决译码算法

吴伊蒙,石志东,邓斌

(上海大学通信与信息工程学院,上海200444)

为使低密度奇偶校验(low-density parity-check,LDPC)码的硬判决译码算法具有更低的计算复杂度和更高的译码性能,提出了一种新的校验和计算算法,具有较低的计算量,可应用于现有的所有硬判决译码算法.结合该算法对一种计算量近似于比特翻转(bit fl ipping, BF)算法的多阈值比特翻转(multi-threshold BF,MTBF)算法进行了进一步改进,获得了更低的译码复杂度和更好的译码性能,在迭代5次时获得了0.15 dB的性能增益.

低密度奇偶校验码;硬判决译码;低复杂度;校验和更新;多阈值比特翻转

低密度奇偶校验(low-density parity-check,LDPC)码最早由Gallager[1]于1962年提出,历经数年发展,其译码算法主要已发展为硬判决译码和软判决译码两大类.设计良好的软判决算法具有非常优异的译码性能,但译码复杂度也随之上升.硬判决算法虽然译码性能较差,但其具有远低于软判决算法的译码复杂度,非常适用于一些资源配置都很有限的网络环境(如WSN,Ad hoc网络等),该优势是软判决算法所不可比拟的.因此,为了进一步发挥硬判决算法的优势,现有的硬判决算法大多致力于译码性能的提升和译码复杂度的降低,使硬判决算法具有更广阔的应用空间.

最早的硬判决算法是由Gallager提出的比特翻转(bit fl ipping,BF)算法[1].该算法仅依靠校验信息计算作为判决条件,可在单次迭代中翻转多个比特,计算量非常低,但是性能也较差. Kou等[2]提出的加权BF(weight BF,W BF)算法,在判决条件计算中引入了比特的幅值信息,而且在单次迭代中只翻转一个比特,使得比特翻转更加可靠.之后的改进型WBF(modified WBF,MWBF)[3]以及改进的MWBF(improved MWBF,IMWBF)[4]等算法又在WBF算法的基础上做了进一步改进,将BF算法的性能进行了进一步的提升.但是由于判决条件的计算引入了新的计算量,而且其单次迭代只翻转一个比特,使得该类算法的计算量不可避免地增加.为了降低其计算复杂度,各种多比特翻转算法被提出,如梯度下降BF(gradient descent BF, GDBF)算法[5]、自适应加权多比特翻转(adaptive weight multi-BF,AWMBF)算法[6].这些算法通过在单次迭代中翻转多个比特减少计算复杂度,但是译码性能也不可避免地受到影响,多要以计算更为复杂的判决条件来补偿,从而取得更好的译码性能.而文献[7]提出的多阈值比特翻转(multi-threshold BF,MTBF)算法,通过设置多个阈值可在单次迭代中翻转多个比特,具有近似于标准BF算法的译码复杂度和更快的收敛速度,但是较之AWMBF算法及一些混合类算法[8-9],其译码性能仍有些微差距.

为了获取译码复杂度更低、性能更好的硬判决算法,本工作提出了一种新的校验和更新算法,对校验和计算进行了简化,使硬判决译码算法具有更低的计算复杂度,并结合所提出算法对MTBF算法进行了改进,在降低其计算复杂度的同时还获得了译码性能的提升.

1 校验和更新算法

首先,令规则二进制LDPC码的校验矩阵为H,它是一个M×N的稀疏矩阵,每列含有γ个“1”,每行含有ρ个“1”,比特n参与的校验方程的集合为M(n)={m:hmn=1}.c=[c1, c2,···,cN-1]为编码后的码字,x=[x1,x2,···,xN-1]为二进制相移键控(binary phase shift keying,BPSK)调制后的码字,经加性高斯白噪声(additive white Gaussian noise,AWGN)信道传输后的接收信息为r=[r0,r1,···,rN-1],其中rn=xn+vn,vn为高斯随机变量,均值为0,方差为σ2=N0/2.对r进行硬判决后得到z=[z0,z1,···,zN-1],校验和s=

由于在硬判决算法的每次迭代中都需对校验和s=zHT进行计算,而该过程需采用一个1×N矩阵与一个N×M矩阵的乘积,因此经过多次迭代后将耗费非常大的计算量,尤其在码长较长时其计算量将更大.由于硬判决译码的校验和计算均采用模二加法运算,所以码字的每次翻转都会引起其对应的γ个校验方程的改变.基于此,本工作提出了一种新的校验和更新算法,只在译码运算中进行一次校验和计算,其后的每次迭代只需在码字翻转时直接翻转其对应的γ个校验和,而不再进行s=zHT运算.如图1所示,对于列重为2的校验矩阵H,当比特z0翻转时,z0所参与的两个校验方程s0,s1的计算结果也发生改变,由0变为1,或由1变为0,因此只需在每次比特翻转后翻转其对应的γ个校验和即可,而无需对所有的校验方程进行计算.校验和更新的计算过程可总结如下.

图1 校验和更新原理Fig.1 Principle of check-sums updating

步骤3计算翻转条件(本步骤可代入各种硬判决算法),翻转相应比特zn,同时更新zn所对应的γ个校验和,将其由0翻转为1或由1翻转为0(对sm取非,即sm=!sm,m∈M(n)).

步骤4重复步骤2和步骤3,直到满足所有的校验和或达到最大迭代次数.

对于上述算法,本工作选用了文献[7]中的MTBF算法进行验证,校验矩阵采用码长为1 023、列重和行重均为32的欧氏几何矩阵,其仿真图形如图2所示,其中BER(bit error ratio)为误码率,ITE(iteration)为迭代次数.MTBF算法采用的是普通的校验和算法进行计算,而New-MTBF算法是本工作提出的校验和更新算法.由图中可以看出,MTBF算法在采用两种校验和计算方法时的译码性能完全一致,说明本工作提出的更新算法可以替代普通的校验和计算算法,且不会对译码算法的性能产生影响.

图2 MTBF和New-MTBF算法的译码性能比较F ig.2 Performance comparisons decoded by MTBF and New-MTBF algorithms

在本算法中,每次译码只需进行一次校验和计算,其后的每次迭代也只需进行32x (γ=32)次逻辑运算即可完成校验和计算,其中x为每次迭代时翻转的比特数目,且随着信噪比(signal to noise ratio,SNR)的增大,每次迭代所翻转的比特数目会逐渐减少,计算量也会随之变小.尤其对于一些单次迭代只翻转1个或少数几个比特的译码算法,可以有效降低其计算复杂度,而且码长越长、迭代次数越多、单次迭代中翻转的比特数目越少,相应的减少的计算量也越多.此外,本算法在校验和计算中不必调用整个校验矩阵,可减少对存储的访问,在硬件实现中具有更低的解码时延.本校验和更新算法最大的优势在于其具有很强的适用性,可以适用于各种硬判决算法.

2 改进的MTBF算法

文献[7]中提出的MTBF算法与大数逻辑算法[10]较为类似.由于接收信息rn的幅值为浮点小数,大数逻辑算法在译码的初始化阶段将浮点小数化为整数进行运算,从而减少了译码迭代中的运算量.MTBF算法采用类似的方法,根据其幅值的大小设定多个阈值,在译码运算中不再进行浮点小数计算,单次译码迭代中可翻转多个比特,有效减少了译码的迭代次数,并且译码性能也超过了常见的WBF[2]和IMWBF[4]等算法的性能,使得MTBF算法以较低的译码复杂度获取了较高的译码性能.但是由于MTBF算法只简单依靠校验和信息以及码字的幅值信息进行码字的翻转,使得码字翻转的可靠度较之译码复杂度较高的AWMBF[6]等算法相对较低,因而本工作对MTBF算法做出了一些改进,增加了一些新的判决信息来提升比特翻转的可靠度,提高译码性能,同时引入了第1节中提出的校验和更新算法,以降低译码复杂度.

首先,对于接收信息rn=xn+vn,其中xn为BPSK调制后的码字,其值为“+1”或“-1”, vn为高斯随机变量,此时|rn|越大则该比特就越可靠.由于该变化由vn引起,那么若vn引起|rn|发生正的变化(|rn|>1),则rn就越可靠;若发生负的变化(|rn|<1),则rn就越不可靠.因此,本工作采用了噪声信号的不可靠度en=1-|rn|来衡量硬判决算法中的比特不可靠度,若en越小,则该比特越可靠.较之于MTBF算法,本工作在改进算法中对阈值组数不再严格控制为⌊γ/2」组,而是由参数α决定,使得阈值选择更加灵活;而当en<0时,阈值则统一被设定为Tn=2×⌊γ/2」-2.同时,为了增加比特翻转的准确性,本工作在每个符合翻转条件的比特zn及其所对应的校验和都翻转后,会计算此时zn不满足的校验方程翻转前所不满足的校验方程数目,如果g>f,说明该nn次翻转不成功,将zn及其对应的校验和重新翻转回去,反之则翻转成功,继续译码.改进后的MTBF(improved MTBF,IMTBF)算法步骤如下.

步骤1计算比特的不可靠度en=1-|rn|,n=0,1,···,N-1,使用预定参数α (α>0)将其分为多个群组.如果en>0,对于(k-1)α<|en|≤kα(k为大于0的正整数),阈值被设置为Tn=2×⌊γ/2」-k;如果en≤0,则Tn=2×⌊γ/2」-2.对于m=0,1,···,M-1,计算校验和

步骤4重复步骤2和步骤3,直到满足所有的校验和或达到最大迭代次数.

3 仿真结果及性能分析

本工作采用MATLAB对上述算法进行仿真,校验矩阵采用欧式几何法构造,大小为1 023×781,码长为1 023,校验矩阵的列重和行重均为32,其仿真图形如图3～5所示.

图3为IMTBF算法在不同的信噪比下BER随参数α的变化曲线.可以看出,本工作提出的IMTBF算法在信噪比较高时受α的影响较大,但在不同的信噪比下BER随α的变化较为一致,因而本工作选取α=0.05.

图3(1 023,781)EG-LDPC码在IMTBF算法下采用不同的α值时的译码性能Fig.3(1 023,781)EG-LDPC codes’performance comparisons decoded by IMTBF algorithmwith diff erent values ofα

图4 为BF,MTBF和IMTBF算法在不同信噪比下迭代5次时的性能仿真比较,其中, MTBF算法选取的α值为0.10.可以看出,改进后的算法较之改进前在迭代次数为5时有明显的性能提升,在BER为10-5时获得了约0.15 dB的性能增益,而BF算法在迭代5次时,其译码性能却与MTBF和IMTBF算法有较大差距,说明改进后的译码算法也有较快的收敛速度,能够以较少的迭代次数换取较高的译码性能.

图4 (1 023,781)EG-LDPC码采用BF,MTBF和IMTBF算法在不同信噪比下的性能比较Fig.4(1 023,781)EG-LDPC codes’performance comparisons decoded by BF,MTBF and IMTBF algorithms with diff erent SNR

此外,从IMTBF与MTBF算法的描述中分析可知,二者的译码复杂度大致相似,主要差别在于二者的步骤3中gn及校验和的计算.在IMTBF算法中由于每翻转一个码字zn都要计算其不满足的校验方程的数目需采用一个1×1 023矩阵乘以一个1 023×1矩阵.若IMTBF算法在单次迭代中需翻转x个码字,则IMTBF算法需多计算一个1×1023矩阵乘以1 023×x矩阵,该过程需进行1 022x次加法和1 023x次乘法.此外,IMTBF算法在迭代中无需计算校验和,只需32x次逻辑操作即可.而MTBF算法中校验和的计算则需一个1×1 023矩阵乘以一个1 023×1 023矩阵,同理需要约106次加法和106次乘法.由于x必定小于1 023(2≤SNR≤3时,x通常小于300,SNR≥4时,x通常小于90或更小),所以IMTBF算法的译码复杂度理论上低于MTBF算法.而且IMTBF算法的译码复杂度与x有关,那么随着信噪比的增大,翻转比特的数目会逐渐减少,此时IMTBF算法的计算量也会随之减少.本工作对两种算法的加法和乘法复杂度进行了仿真计算,如图5所示.仿真结果表明,IMTBF算法的加法和乘法计算量均低于MTBF算法,且随着信噪比的增大,两种算法的计算量均逐渐减少,但IMTBF算法的计算量始终低于MTBF算法.

图5 MTBF和IMTBF算法在不同信噪比下的计算量比较Fig.5 Computations comparisons of MTBF and IMTBF algorithmswith diff erent SNR

4 结束语

本工作提出了一种新的校验和更新算法,可以有效减少校验和计算过程中的计算量,且不会对算法的译码性能造成影响,能够降低译码过程中的译码时延,因而可适用于现有的各种硬判决译码算法及一些软判决译码算法.此外,本工作结合所提出算法对MTBF算法进行了改进,采用了噪声信号的不可靠度作为硬判决算法中比特不可靠度的衡量,使阈值选择更加灵活,并引入了新的判决信息来增加比特翻转的可靠度.仿真结果表明,改进后的IMTBF算法具有更低的译码复杂度和更好的译码性能,在BER为10-5时,迭代5次后获得了0.15 dB的性能增益.

[1]G ALLAGER R G.Low-density parity-check codes[J].Information Theory,1962,8(1):21-28.

[2]K OU Y,L IN S,F OSSORIER M.Low-density parity-check codes based on finite geometries:a rediscovery and new results[J].Information Theory,2001,47(7):2711-2736.

[3]Z HANG J,F OSSORIER MP C.Amodified weighted bit-fl ipping decoding of low-density paritycheck codes[J].Communications Letters,2004,8(3):165-167.

[4]J IANG M,Z HAO C,S HI Z,et al.An improvement on themodified weighted bit fl ipping decoding algorithmfor LDPC codes[J].Communications Letters,2005,9(9):814-816.

[5]W ADAYAMAT,N AKAMURAK,Y AGITAM,et al.G radient descent bit fl ipping algorithms for decoding LDPC codes[J].Communications,2010,58(6):1610-1614.

[6]C HEN T C.Adaptive-weightedmu ltibit-fl ipping decoding of low density parity-check codesbased on ordered statistics[J].IET Communications,2013,7(14):1517-1521.

[7]L IU Y H,N IU X L,Z HANG ML.Multi-threshold bit fl ipping algorithmfor decoding structured LDPC codes[J].Communications Letters,2015,19(2):127-130.

[8]T ORSHIZI E O,S HARIFI H,S EYRAFI M.Anew hybrid decoding algorithmfor LDPC codes based on the improved variab lemultiweighted bit-fl ipping and BP algorithms[C]//2013 21st Iranian Conference on Electrical Engineering.2013:1-6.

[9]T ORSHIZI E O,S HARIFI h,D ANESHGAR A,et al.Anew hybrid decoding algorithmbased on multi-dimensional searching for regu lar LDPC codes in finite geometries[C]//2014 22nd Iranian Conference on Electrical Engineering.2014:1471-1476.

[10]L IN S,C OSTELLO D J.Error control coding:fundamentals and applications[J].Prentice-Hall Computer Applications in E lectrical Engineering Series,1983,25(1):4-12.

H ard-decision decod ing algorithmwith low complexity based on check-sumupdating for LDPC codes

WU Yimeng,SHIZhidong,DENG Bin
(School of Communication and In formation Engineering,Shanghai University,Shanghai 200444,China)

To reduce computational complexity of hard-decision decoding algorithms of low-density parity-check(LDPC)codes and improve decoding performance,a check-sums algorithmis proposed.It requires less computation,and is applicable to all existing harddecision algorithms.The algorithmis applied to a multi-threshold bit fl ipping(MTBF) algorithmwhose computation complexity is similar to the bit fl ipping(BF)algorithm,and further improvement ismade.The resu lts show that the proposed algorithmcan achieve a 0.15 dB performance gain after 5 iterationswith lower computational complexity and better decoding performance.

low-density parity-check(LDPC)codes;hard-decision decoding;low complexity;check-sums updating;multi-threshold bit fl ipping(MTBF)

TN 919.3+2

A

1007-2861(2017)04-0510-07

DO I:10.12066/j.issn.1007-2861.1674

2015-09-28

国家自然科学基金资助项目(11474195);上海市自然科学基金资助项目(13ZR 1440800)

石志东(1964—),男,研究员,博士生导师,博士,研究方向为光纤通信和传感器网络等.

E-mail:zdshi@shu.edu.cn