极化码BP译码算法中量化问题的研究*

任 洁，韩 娟，冯雪林，刘 林

0 引 言

移动通信业务的变革使得数据通信流量呈指数增长，迫切需要新的移动通信技术满足用户的需求[1]。第五代移动通信（5G）作为下一代移动通信技术的重要发展方向[2-3]，面向mMTC（海量机器类通信）、eMBB（增强移动宽带）、uRLLC（超可靠低时延通信）三种业务场景，不仅用于人与人通信，还实现人与物和物与物之间的互联互通。与4G移动通信相比，5G为实现系统的低时延、高容量，对信道编码方案提出了更高要求[4]。4G采用Turbo码编码方案，但其存在较高的编码时延且算法复杂度高。为此，E.Arikan提出了极化码（Polar Codes）。这是唯一理论上证明可达到香农极限且编译码过程简单的高性能信道编码方案[5]。在码长无限长时，Polar码可以达到二元对称信道容量限，性能良好，但在码长有限长时，与RS码、LDPC码等相比，性能相对较差。

目前，改善极化码在有限长时性能的译码方案主要是置信度传播（Belief Propagation，BP）译码算法[6]。BP译码算法的核心思想是利用极化码的构造因子图，实现并行译码的迭代算法，具有良好的性能。它的主要缺点是算法复杂度较高，且硬件实现比较复杂。为了降低译码算法的复杂度及利于硬件实现，Leroux等提出了最小和近似方法[7]，核心思想是通过ln cosh x ≈|x|-ln2来简化BP译码算法中的迭代更新公式。然而，对比BP译码算法，最小和译码算法在性能方面有较大退化，难以满足高速数据传输编码性能要求。

在上述研究基础上，结合5G对信道编码的要求，提出了极化码BP译码的量化问题。该算法简化最小和译码算法中的迭代更新公式，选择|x|-ln 2和ln cosh(x)误差较大的|x|≤2.5的区间进行量化，从而便于提高译码算法的性能。同时，考虑查表法可以大大降低计算复杂度、硬件的实现难度以及提升算法的译码速率，通过引入大小为8比特的量化表来实现译码过程。仿真结果表明，在8比特均匀量化时，其译码性能几乎与置信度传播译码算法相同。

1 Polar码及其译码算法

Polar码可表示为(N,K,A,uAc)的GN陪集码。其中N=2n（n是正整数）表示码长；K代表维数，也是信息集合A（ A ⊂ { 1 , 2,… ,N }）的大小，由信道极化选取信息集合A；uAc（uAc∈XN-K）代表固定比特。

1.1 极化码的BP译码算法

BP译码算法自身的并行性使得其更加易于硬件实现[8]。BP译码算法按照极化码构造因子图表示[9]。一个(N,K )极化码通过一个n（其中n=log2N）阶段的因子图进行迭代译码，因子图包含N(n+1)个节点，用整数对(i, j)表示每个节点，其中i代表阶层，j表示行。第一阶层的节点(1, j)与信源矢量u相关，n+1阶层的节点(n+1, j)与接收到的信息相关。每个阶段有N/2个处理单元。译码器中，1≤i≤n，1≤j≤N。在每个处理单元中，i和j的取值是1≤i≤n，1≤j≤N/2。图1表示n=3时极化码的因子图，分为3个阶段，每个阶段有4个处理单元，图2表示了每个处理单元的信息传递过程[10]。

图1 n=3时极化码的构造因子图

图2 BP算法中处理单元的信息传递

从图2可以看出，每个处理单元共分为4个节点， 分 别 为 VN(i, j)、VN(i, j+N/2)、VN(i+1,2j-1)、VN(i+1,2j)。

节点之间存在以下逻辑关系：

开始解码时，根据第j位是否为信息比特，初始化因子图最左边一层节点上的消息R1,j：

根据信道输出的每个节点的对数似然比（LLR），初始化因子图最右边一层节点上的消息Ln+1,j为：

中间的其他节点初始化为0。迭代译码过程中，从左向右计算更新置信度消息Ri,j，并向右传播至最右边，再从右往左计算更新置信度消息Li,j，并向左传播至最左边，相邻节点间的置信度传播消息通过处理单元运算模块计算。传播一个往返为一次迭代过程。每一个处理单元运算模块按照式（5）～式（8）计算L和R消息[11]：

或：

1.2 极化码的最小和译码算法

其中，x1、x2表示信道的对数似然比信息。从式（10）、式（11）可知，最小和译码算法和BP译码算法的不同在于g(x1,x2)的定义有差别。

因此，组织必须根据自身管理特点和组织发展需要，对软件供应商进行详细的考察论证，选择一套适合企业实际的软件系统。

图3 cosh x的近似函数

图4 ln cosh x的近似函数

2 BP译码算法的量化方案

通过对BP译码算法进行量化，可以提高BP译码算法的译码性能，降低译码算法的计算复杂度。文献[12-13]提出的量化方案，其算法由于涉及到加减法、比较、查表运算，从而在一定程度上降低了算法的计算复杂度，提高了算法性能。笔者主要基于这种思想对最小和译码算法中误差较大的区间范围进行合理量化，从而减少误差，提高译码性能。下面将详细介绍BP译码算法的量化方案。

BP译码算法中，令ln cosh x≈|x|-ln 2得出了最小和译码算法，但在区间|x|≤2.5时，ln cosh x与|x|-ln 2的误差较大。尤其当|x|=0时，ln cosh x与|x|-ln 2的差值达到了ln 2，具体如图5所示。

图5 ln cosh x的分段近似

由图5可以看出，在|x|＞2.5时，ln cosh x与|x|≤2.5几乎相同，误差极小；而在|x|≤2.5时，ln cosh x与|x|-ln 2的误差越来越大，进而极大地降低了译码算法的性能。为此，笔者提出在(-2.5,2.5)区间内按照8比特量化，即整体分为两段：

具体如图6所示。

图6 ln cosh x 比特量化后的对比结果

将式（10）中的双曲函数ln cosh x用式（13）代替，则式（10）转化为：

通过分析，如果仅对函数ln cosh x进行量化，采用不同的量化方法对译码性能影响不大。相比于非均匀量化，采用均匀量化更利于硬件实现，所以文中对函数ln cosh x使用8比特量化，其中量化表如表1所示。

表1 y=ln cosh x在量化区间的量化表

在区间(-2.5,2.5)进行量化后的函数曲线，如图7所示。

图7 量化后的函数曲线

硬件实现中，当更新函数中变量落在(-2.5,2.5)区间时，可以通过查询表1来实现。量化后的BP译码算法的迭代公式和节点之间的迭代更新信息规则均和BP译码算法相同，不同在于迭代更新公式的计算方法。具体得，更新公式由式（13）决定。

量化后的BP译码算法的详细步骤如下。

（1）初始化：根据式（3）和式（4）计算左信息R1,j和右信息Ln+1,j，并设定迭代次数T；

（2）当迭代更新次数小于T时，在每轮迭代中，首先从因子图中的第1阶段到第n阶段的每个处理单元中根据式（7）、式（8）更新每个阶段中各个处理单元的节点的右信息Ri,j；然后，从第n阶段到第1阶段，利用式（5）、式（6）更新每个阶段中各个处理单元的节点的左信息L[14]。

（3）当达到迭代次数T时进行比特判决，判决的依据是最后一次迭代更新的左信息Li,j值的大小。对于译码码字u^j(1≤j≤N)的判定规则如下：

①当j∈Ac时，u^j=0；

② 当j∈A时， 若L1,j＞0， 则u^j=0； 若L1,j≤ 0，u^j=1。

3 算法性能分析

3.1 算法的计算复杂度分析

笔者提出的译码算法对ln cosh x进行量化，进而改变更新函数定义的算法公式。量化后的BP译码算法相比于BP译码算法，极大降低了更新公式的复杂度。而相比于最小和译码算法，它的算法复杂度有微弱增加，但性能有较大提升。从3种算法的更新式式（10）、式（11）、式（13）的定义中可以看出，在BP译码算法中，g(x1,x2)的计算需要2次对数运算、2次双余弦函数的计算法、2次乘法运算和3次加法运算。由于运算公式是指数形式，造成运算时延较大，硬件实现相对艰难。最小和译码算法由于g(x1, x2)的计算公式较为简单，仅需要2次符号运算、2次取绝对值和1次比较得出最小值。而量化后的BP译码算法最多需要2次比较运算、2次加法运算、2次绝对值运算、2次符号运算和2次查表运算，虽然相比于最小和译码算法多了查表运算，但整体的计算复杂度较低，运算时延较小，硬件实现上更加简单。

3.2 算法的仿真分析

为了验证算法的译码性能，分别对量化后的BP译码算法、最小和译码算法和BP译码算法进行仿真实验。实验中均采取二进制输入的高斯白噪声信道，采取BPSK调制方式，码长N分别设为256和512，码率为0.5，总迭代次数设为60次，帧数为50 000帧。

在不同信噪比（Eb/N0）下，量化后的BP译码算法、最小和译码算法及BP译码算法在节点更新函数中（如式（13）所示），调用分段函数g(x1,x2)在各段所占的比例，结果如表2所示，不同情景如式（14）所示。

表2 三种译码算法调用g(x1,x2)各段占比

图8比较了码长为256时，量化后的BP译码算法、最小和译码算法和BP译码算法的误码率性能。可以看出，量化后的BP译码算法与BP译码算法的译码性能几乎相同。与最小和译码算法对比，当Eb/N0小于2.5 dB时，在相同的误码率情况下，量化后的BP译码算法性能比最小和译码算法的性能要好，在0.25 dB左右。当信噪比大于2.5 dB时，二者性能差距逐渐减少，但量化后的BP译码算法性能仍优越于最小和译码算法。

图8 N=256极化码3种译码算法的性能

图9 比较了码长为512时，量化后的BP译码算法、最小和译码算法和BP译码算法的误码率性能。如图9所示，量化后的BP译码算法与BP译码算法的译码性能几乎相同。与最小和译码算法相较，当Eb/N0小于3 dB时，在相同误码率下，量化后的BP译码算法性能比最小和译码算法要好，在0.4 dB左右。而当信噪比大于3.5 dB时，二者的性能差距逐渐减少，但量化后的BP译码算法性能仍优越于最小和译码算法。

图9 N=512极化码的3种译码算法的性能

如表2所示，低信噪比下，量化后的BP译码算法调用情景1、情景2、情景3这3种情况所占的比例较高。而从图8可知，低信噪比时量化后的BP译码算法的性能明显优于最小和译码算法。随着信噪比的提高，量化后的BP译码算法调用情景4的比例增加。从图8可以看出，笔者提出的量化后的BP译码算法与最小和译码算法相比性能趋于变小，但仍具有显著优势。结合表2和图8、图9可以看出，量化后的BP译码算法相较于最小和译码算法，其性能提升明显，几乎达到与BP译码算法相同的性能。

4 结 语

提出了一种量化后的BP译码算法，在最小和译码算法的基础上，在[-2.5,2.5]区间内，利用8比特的区间量化代替迭代更新公式中的ln cosh x，以均衡最小和译码算法的性能损失。仿真结果表明，量化后的BP译码算法相比于最小和译码算法略增加了计算复杂度，但算法性能提高显著，同BP译码算法的性能几乎相同，同时算法的计算复杂度又明显低于BP译码算法，更利于硬件实现。

[1] Zhou Y,Liu H,Pan Z,et al.Spectral and Energy Efficient Two-Stage Cooperative Multicast for LTE-A and Beyond[J].IEEE Wireless Magazine,2014(04):34-41.

[2] Liu L,Zhou Y, Tian L,et al.Load Aware Joint CoMP Clustering and Inter-cell Resource Scheduling in Heterogeneous Ultra Dense Cellular Networks[J].IEEE Trans. Vehicular Technology,Early Access,2017,99(11):1-14.

[3] Garcia V,Zhou Y,Shi J L.Coordinated Multipoint Transmission in Dense Cellular Networks with User-Centric Adaptive Clustering[J].IEEE Trans. Wireless Comm.,2014,13(08):4297-4308.

[4] 杜昊阳,王呈贵,栾亚婷.基于LDPC码的多信道停等HARQ系统设计与分析[J].通信技术,2015,48(08):886-892.DU Hao-yang,WANG Chen-gui,LUAN Ya-ting.Design and Analysis of Multi-Channel Stop-And-Wait HARQ based on LDPC Codes[J].Communi-cations Technology,2015,48(08):886-892.

[5] Arikan E.Channel Polarization:A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memory less Channels[J].IEEE Transactions on Information Theory,2009,55(07):3051-3073.

[6] Zhang Y,Liu A,Pan X,et al.A Modified Belief Propagation Polar Decoder[J].IEEE Communications Letters,2014,18(07):1091-1094.

[7] Leroux C,Raymond A J,Sarkis G,et al.Hardware Implementation of Successive-Cancellation Decoders for Polar Codes[J].Journal of Signal Processing Systems,2012,69(03):305-315.

[8] Niu K,Chen K.Stack Decoding of Polar Codes[J].Electronics Letters,2012,48(12):695-697.

[9] Hussami N,Korada S B,Urbanke R.Performance of Polar Codes for Channel and Source Coding[C].IEEE International Symposium on Information Theory,2009:1488-1492.

[10] 吴道龙.极化码构造与译码算法研究[D].西安:西安电子科技大学,2016.WU Dao-long.Polarization Code Construction and Decoding Algorithm[D].Xi’an:Xidian University,2016.

[11] 洪银芳,李晖,王新梅.改进的Polar码的最小和译码算法[J].北京邮电大学学报,2016,39(06):22-26.HONG Yin-fang,LI Hui,WANG Xin-mei.Min-sum Decoding Algorithm of Improved Polar Codes[J].Journal of Beijing University of Posts and Telecommunicatio ns,2016,39(06):22-26.

[12] 樊婷婷,杨维,许昌龙.Polar码SC译码算法的量化问题[J].北京邮电大学学报,2015(04):95-100.FAN Ting-ting,YANG Wei,XU Chang-long.Quantization Problems of Polar Code SC Decoding Algorithm[J].Journal of Beijing University of Posts and Telecommunicatio ns,2015(04):95-100.

[13] 童胜,王鹏,王单等.LDPC码量化和积译码的高效实现[J].西安电子科技大学学报:自然科学版,2004,31(05):709-713.TONG Sheng,WANG Peng,WANG Dan,et al.Efficient Implementation of Quantization and Product Decoding of LDPC Codes[J].Journal of Xidian University(Natural Science Edition),2004,31(05):709-713.

[14] Fayyaz U U,Barry J R.A Low-complexity Soft-output Decoder for Polar Codes[C].Global Communications Conference IEEE,2014:2692-2697.