一种改进的Polar码的BP译码算法

洪银芳,李 晖,王新梅

(西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071)

一种改进的Polar码的BP译码算法

洪银芳,李 晖,王新梅

(西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071)

为了减少置信度传播译码算法的计算复杂度,提出了一种改进的置信度传播译码算法.该算法在节点更新时,利用等误差的线性近似函数来代替算法中的双曲函数,相比于原始的置信度传播译码算法,改进的算法仅仅需要乘法和加法运算,因此大大降低了算法的计算复杂度,更易于硬件实现.仿真结果表明,在低信噪比时,改进的置信度传播译码算法的性能与原始BP译码算法的性能几乎相同,在高信噪比时,改进的置信度传播译码算法的性能比原始置信度传播译码算法的性能略差,在码长为256,误码率是10-6时,改进的置信度传播译码算法的误码率性能比原始的置信度传播译码算法退化了0.1 dB.

信道极化码;置信度传播算法;等误差;线性近似;计算复杂度

文献[1]提出的信道极化(Polar)码是惟一被证明能够达到容量限的码且在串行抵消(Successive Cancellation,SC)译码下的复杂度较低.Polar码在不同通信信道下的设计和应用研究已经取得了一定的成绩,如在对称二进制离散无记忆信道、非对称二进制信道、多址接入信道、高斯信道、瑞利信道以及混合信道中都进行了拓展研究.

Polar码在长码长时性能良好,但在中短码长时,性能却要比低密度奇偶校验码(Low Density Parity Check,LDPC)和Turbo码要差.为了改善Polar码在有限码长时的性能,学者们提出了许多有效的译码算法[2-9].文献[4]将码的因子图表示引入Polar码中,利用置信度传播(Belief Propagation,BP)算法来译Polar码[5].文献[6]给出了Polar码的BP译码算法的具体实现方法.文献[7]提出了一种改进的Polar码的BP译码器,相比于SC译码算法,BP译码算法能达到较好的性能且能并行计算而利于硬件实现.文献[8]提出了一种改进的SC译码算法,利用线性近似函数来代替退化转化函数,降低了计算复杂度,但是其性能要比原始的SC译码算法差.文献[9-10]将线性近似方法应用到LDPC码的BP译码算法中,降低了BP译码算法的计算复杂度.

Polar码在对数域上的BP译码算法可看成和积算法,其操作需要双曲函数的计算,计算复杂度较高.为了降低BP译码算法的复杂度,笔者提出了一种改进的Polar码的BP译码算法.在节点更新时,改进的BP算法利用等误差的线性近似函数来代替算法中的双曲函数,即用乘法和加法运算代替了BP算法中的对数、指数和除法运算,大大降低了算法的计算复杂度,易于硬件实现.仿真结果表明,在低信噪比(Signal-to-Noise Ratio,SNR)时,改进的BP译码算法的性能与原始BP译码算法的性能相同;在高信噪比时,改进的BP译码算法的性能比原始BP译码算法的性能略差;同时,改进的BP译码算法的性能比SC算法和已知的相似简化算法[8]的性能要好.

1　Polar码及其BP译码算法

Polar码可以看成是一个GN陪集码,可以表示为其中N是码长,可以表示成N=2n,n是正整数,K是维数,也可看成是信息集合A的大小,A⊂{1,2,…,N},信息集合A的选取是由信道极化所决定的.表示固定比特,

图1　n=3时Polar码的因子图表示

Polar码的BP译码算法基于文献[4]提出的码的因子图表示.一个(N,K)Polar码由一个n阶段的因子图来迭代译码,因子图包括N(n+1)个节点,每个节点由整数对(i,j)表示,每个阶段包括N/2个处理单元(Processing Elements,PE).节点(i,j)的第1个元素表示阶层,第2个元素表示行,第1阶层的节点与信源矢量u有关,第n+1阶层的节点与接收到的信道信息有关.在整个译码器中,i和j的取值范围为1≤i≤n,1≤j≤N,在每个PE中,1≤i≤n,1≤j≤N/2.图1描述了n=3时Polar码的因子图表示,在图中共有3个阶段,每个阶段包括4个PE,每个PE的信息传递过程见图2所示.在译码器的每个PE中,节点(i,j)与两种类型的信息相关:从右到左的信息Li,j和从左到右的信息Ri,j.Li,j和Ri,j都是在相邻的节点间传递和迭代更新的,信息更新过程与文献[6]相同,信息首先从最右边的节点传到最左边的节点,然后从最左边的节点传到最右边的节点,这个过程就是BP译码算法中的一轮迭代.在迭代中,传递的信息都是对数似然比形式的,迭代公式为

图2　BP译码算法中PE的信息传递过程

其中,1≤i≤n,1≤j≤N/2,且

初始信息R1,j(1≤j≤N)定义为

来自于信道的信息Ln+1,j(1≤j≤N)为

2　改进的Polar码的BP译码算法

2.1等误差线性逼近原理

等误差线性逼近是指每个逼近的直线段与曲线之间的误差相等[11],其原理如图3所示.

图3　非圆曲线的等误差线性逼近原理

已知曲线方程y=f(x),直线逼近曲线的误差设为δ,令A(xa,ya)为曲线的起点,首先以A点为圆心,δ为半径作圆,然后作圆与曲线的公切线PT,切点分别为P(xp,yp),T(xt,yt),然后作一条过A点与PT平行的直线AB,点B(xb,yb)为曲线与直线AB的交点,则点B即为分段直线的一个端点.然后以B点为起点,重复前面作误差圆的过程,可以得到所有逼近直线段的端点,将相邻两点用直线相连即可得到逼近曲线的所有分段直线.

2.2基于等误差的线性近似函数

采用上述的基于等误差线性逼近原理对双曲正切函数y=tanh x进行等误差直线逼近.当x≥7时,逼近直线取为y=0.999 998,当x≤-7时,逼近直线取为y=-0.999 998.当选取误差为δ=0.02,得出双曲正切函数y=tanh x的等误差线性逼近的所有节点坐标为:(-7.0,-0.999 998),(-3.68,-0.998 7), (-1.82,-0.948 8),(-1.24,-0.845 5),(-0.66,-0.5784),(0,0),(0.66,0.5784),(1.24,0.8455), (1.82,0.9488),(3.68,0.9987),(7.0,0.999998).根据两点间直线公式求得所有相邻两点间的直线方程,由于在点(0,0)两边的两段直线的斜率都是0.876 4,因此可将其合为一段直线.双曲正切函数y=tanh x的分段线性近似方程y1(x)=ax+b为

根据反函数的性质,可以得到函数y=arctanh x的所有分段线性近似方程y2(x)=cx+d为

将算法中的双曲函数分别用分段的线性近似函数代替,则式(2)可以转化为

其中,a,b,c,d是线性近似函数的系数.

2.3改进的Polar码的BP译码算法

在改进的Polar码的BP译码算法中,在节点更新规则中所传递的信息的更新公式为

其中,1≤i≤n,1≤j≤N/2,h(x1,x2)由式(7)定义.

基于等误差的改进的Polar码的BP译码算法步骤如下:

(1)初始化:计算式(4)中的Ln+1,j的值作为初始信道信息,其中1≤j≤N;

(2)在每轮迭代中,根据Polar码的BP译码算法的迭代规则,利用式(8)更新每个阶段的每个PE的节点信息;

(3)当达到设定的迭代次数T时,进行判决:如果j∈Ac或者j∈A&L1,j＞0,则判j=0;否则,判j=1.

3　复杂度分析和计算机仿真

3.1复杂度分析

SC译码算法的时间复杂度是O(N log N)[1],其中N是Polar码的码长.文献[5]给出的Polar码的BP译码算法的时间复杂度也是O(N log N),其性能要优于SC译码算法.相比于SC译码算法,BP译码算法能并行计算,因此更利于硬件实现.

改进的Polar码的BP译码算法只是对原始BP译码算法中的双曲函数进行替代,并没有改变节点之间循环交换信息的规则以及算法的迭代次数,因此,改进的BP译码算法和原始的BP译码算法的时间复杂度是一样的,它们的运算复杂度的不同主要是由于节点更新时的计算规律不同而造成的.在原始的BP译码算法中,双曲函数的计算中包含了指数、对数及除法等运算,运算复杂度是指数的,因此造成的时延会比较大,硬件实现上比较困难;而改进的BP译码算法中的线性近似函数仅仅需要乘法和加法运算,运算复杂度是线性的,时延较小,硬件实现上相对比较简单.表1给出了双曲函数和线性近似函数的核心运算的运算复杂度.

表1　双曲函数和线性近似函数的运算复杂度

表2总结了各种算法的校验节点更新的核心运算的运算复杂度.原始的BP译码算法的节点更新公式中,式(2)的计算需要计算2次tanh x,1次arctanh x,4次乘法;而改进的BP译码算法的节点更新公式中,式(7)的计算仅仅需要3次乘法和3次加法运算.

表2　各算法校验节点更新的运算复杂度

综合表1和表2可以很容易得出,相比于原始的BP译码算法,改进的BP译码算法大大降低了的校验节点更新的核心运算的运算复杂度,更利于硬件实现.文献[8]的节点更新的运算复杂度要比改进的BP译码算法的运算复杂度略高.

3.2计算机仿真

为了验证算法性能,分别对改进的BP译码算法、原始的BP译码算法、原始SC译码算法和文献[8]中的译码算法进行了对比仿真实验.仿真中采用的信道都是二进制输入的加性高斯白噪声(Additive White Gaussian Noise,AWGN)信道,调制方式是基带二进制相移键控(Binary Phase Shift Keying,BPSK)调制,为检验Polar码的性能,分别选取了几种不同码长、不同码率的Polar码进行了仿真实验.Polar码的信息集合A是利用Tal-Vardys方法来选取的[12].

图4和图5的参数设置为:码长N为256,码率R为0.5,迭代次数T设置为60次.图4比较了改进的BP译码算法、原始的BP译码算法、原始SC译码算法和文献[8]中的译码算法的误码率(Bit Error Rate, BER)性能.从图4中可以看出,相比于BP译码算法,当信噪比小于4.5 dB时,改进的BP译码算法与原始的译码算法的BER性能几乎相同;当信噪比大于4.5 d B时,改进的BP译码算法比原始的译码算法的BER性能略差,当误码率达到10-6时,改进的BP译码算法比原始BP译码算法的性能差0.1 d B左右.相比于基于SC译码算法,改进的BP译码算法的BER性能要比原始SC译码算法和文献[8]的译码算法的BER性能好,当误码率为10-4时,改进的BP译码算法比原始SC译码算法的BER性能要好0.5 dB,比文献[8]中的译码算法的BER性能要好1.1 d B.

图4　(256,128)时Polar码多种算法的BER性能比较

图5　(256,128)时Polar码多种算法的FER性能比较

图5比较了各算法的误帧率(Frame Error Rate,FER)性能.从图5中可以看出,相比于BP译码算法,当信噪比小于3 dB时,改进的BP译码算法与原始的译码算法的FER性能差不多;当信噪比大于3 dB时,改进的BP译码算法比原始的译码算法的FER性能略差;当误码率达到10-5时,改进的BP译码算法比原始BP译码算法的性能差0.2 d B左右.相比于基于的SC译码算法,改进的BP译码算法的FER性能要比SC译码算法和文献[8]的译码算法的FER性能好;当误码率为10-3时,改进的BP译码算法比原始SC译码算法的FER性能好0.4 dB;比文献[8]中的译码算法的FER性能好1.0 dB.由图4和图5中可知,在同等条件下,基于BP译码算法的性能要比基于SC算法的性能好,因此在下面的图6和图7中,主要只比较了基于BP译码算法的BER性能.

图6　R=0.5,T=60时不同码长Polar码的BER性能比较

图7　N=1 024时Polar码的BER性能比较

图6比较了Polar码在不同码长时改进的BP译码算法、原始的BP译码算法和SC算法的BER性能.

其中码率R为0.5,迭代次数T为60次.从图6中可以看出,当码长N=1 024时,相比于原始的BP译码算法,当信噪比小于3.5 dB时,改进的BP译码算法与原始的BP译码算法的性能几乎相同;当信噪比大于3.5 d B时,改进的BP译码算法比原始的BP译码算法的性能略差;当误码率达到10-6时,改进的BP译码算法比原始的BP译码算法的性能要差0.15 dB左右;码长相同时的BP算法的性能要优于SC算法的.当Polar码的码长选取为256时,算法的性能最差;码长为2 048时算法的性能最好;即码长越长,算法的性能越好.

图7比较了码率和迭代次数不同时,码长N=1 024的Polar码的改进的BP译码算法的BER性能.首先考察码率对BER性能的影响,固定码长N=1 024,迭代次数T为60次,选取的码率分别为0.375、0.5和0.75.从图7中可知,当R=0.375时,改进的BP译码算法的性能最好;当R=0.75时,算法的性能最差;当误码率达到10-4时,码率为0.375时的性能比码率为0.5时的性能好0.4 dB左右;码率为0.5时的性能比码率为0.75时的性能好1.2 dB左右.其次考察迭代次数T对BER性能的影响,固定码长N=1 024,码率R=0.5,选取了3组不同的迭代次数分别为60次、40次、30次.从图7中可以看出,当信噪比小于3.0 d B时,迭代次数大的性能略好,且信噪比越低,其性能的差异越明显;当信噪比大于3.0 d B时,算法所选取的3种不同的迭代次数对BER性能几乎没有影响.由Polar的BP译码过程可知,当改变码率时,并没有改变算法中需要运算的节点的数目,因此,改变码率对算法的复杂度并没有影响.迭代次数越大,其运算的节点的数目越多,因此算法的复杂度越高.

4　结束语

笔者提出了一种改进的Polar码的BP译码算法,在节点更新时,改进的BP译码算法利用等误差的线性近似函数来代替算法中的双曲函数,即用乘法和加法运算代替了原始BP译码算法中的对数、指数和除法运算,大大降低了算法的计算复杂度,易于硬件实现.仿真结果表明,在低信噪比时,改进的BP译码算法的性能与原始BP译码算法的性能相同;在高信噪比时,改进的BP译码算法的性能比原始BP译码算法的性能略差;当码长为256,误码率为10-6时,改进的BP译码算法的误码率性能比原始的BP译码算法退化了0.1 d B;同时,改进的BP译码算法的性能要比SC算法和已知的相似简化算法[8]的性能要好.

[1]ARIKAN E.Channel Polarization:a Method for Constructing Capacity Achieving Codes for Symmetric Binary-input Memoryless Channels[J].IEEE Transactions on Information Theory,2009,55(7):3051-3073.

[2]TRIFONOV P.Efficient Design and Decoding of Polar Codes[J].IEEE Transactions on Communications,2012,60 (11):3221-3227.

[3]CHEN K,NIU K,LIN J R.Improving Successive Cancellation Decoding of Polar Codes[J].IEEE Transactions on Communications,2013,61(8):3100-3107.

[4]Jr FORNEY G D.Codes on Graphs:Normal Realizations[J].IEEE Transactions on Information Theory,2001,47(2): 520-548.

[5]ARIKAN E.A Performance Comparison of Polar Codes and Reed-Muller Codes[J].IEEE Communications Letters, 2008,12(6):447-449.

[6]PAMUK A.An FPGA Implementation Architecture for Decoding of Polar Codes[C]//Proceedings of 8th International Symposium on Wireless Communications Systems.Piscataway:IEEE,2011:437-441.

[7]ZHANG Y,LIU A,PAN X,et al.A Modified Belief Propagation Polar Decoder[J].IEEE Communications Letters, 2014,18(7):1091-1094.

[8]XING C,WANG B,ZHAO S M.A Reduced-complexity Successive-cancellation Decoding Algorithm for Polar Codes [C]//The 6th International Congress on Image and Signal Processing.Piscataway:IEEE,2013:1221-1225.

[9]YUAN B,PARHI K K.Architectures for Polar BP Decoders Using Folding[C]//Proceedings of the IEEE International Symposium on Circuits and Systems.Piscataway:IEEE,2014:205-208.

[10]PAPAHARALABOS S,SWEENEY P,EVANS B G,et al.Modified Sum-product Algorithms for Decoding Lowdensity Parity-check Codes[J].IET Communications,2007,1(3):294-300.

[11]侯军奎.LDPC码译码算法的研究和简化[D].西安:西安电子科技大学,2014.

[12]TAL I,VARDY A.How to Construct Polar Code[J].IEEE Transactions on Information Theory,2013,59(10):6562 -6582.

(编辑:王 瑞)

Improved BP decoding algorithm for Polar codes

HONG Yinfang,LI Hui,WANG Xinmei
(State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

In the decoding algorithm for Polar codes,the belief propagation(BP)decoding algorithm in the loglikelihood ratio domain incurs high computation complexity due to the computation of the hyperbolic functions Motivated by this observation we propose an improved BP decoding algorithm.In the node update rules,our method replaces the hyperbolic functions with the linear approximation functions based on the principle of equal error.Compared with the original BP decoding algorithm,the modified BP decoding algorithm is only implemented by addition and multiplication operations,which greatly reduces computation complexity,and simplifies hardware implementation.Simulation results show that the performance of the modified BP decoding algorithm is almost the same as that of the original BP decoding algorithm in the low Signal to Noise Ratio(SNR)region,and in the high SNR region the performance of our method is slightly worse.Compared with the original BP decoding algorithm, the bit error rate(BER)performance of the modified BP decoding algorithm has about 0.1 dB degradation when the length of Polar codes is 256 and the BER is 10-6.

Polar codes;belief propagation(BP)algorithm;equal error;linear approximation; computation complexity

TN911

A

1001-2400(2016)04-0039-06

10.3969/j.issn.1001-2400.2016.04.008

2015-04-09 网络出版时间：2015-10-21

国家973计划资助项目(2010CB328300,2012CB316100);国家自然科学基金资助项目(61201138,61372072)

洪银芳(1984-),女,西安电子科技大学博士研究生,E-mail:yfhong@stu.xidian.edu.cn.

网络出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.016.html