3×3核矩阵极化码的BP译码算法

邱开虎,黄志亮,张莜燕,周水红

(浙江师范大学 物理与电子信息工程学院,浙江 金华 321004)

0 引言

极化码最早是由Arikan教授[1]提出,是第一个具有多项式级数的编译码复杂度并且可以通过理论证明可达香农极限的编码方案。由于极化码具有低复杂度的编译码方案和较好的纠错性能,在2016年3GPP会议中被选为5G控制信道eMBB场景编码方案。Arikan[1]提出了串行消去(Successive Cancellation,SC)译码算法。Tal等人[2]提出了串行消去列表 (Successive Cancellation List,SCL)译码算法。Chen等人[3]提出采用堆栈的SC译码算法。SCL译码算法与采用堆栈的SC译码算法均为基于SC译码改进的译码算法。串行译码算法由于应用了极化码特有的链式概率模型,可以从理论上被证明可达香农极限,但是存在时延较高、吞吐率较低的缺陷,这些缺陷限制了极化码在5G高速通信时代的应用,学者们针对SC译码算法在有限码长下译码性能较差的问题提出了许多有效的方法[4-7]。Gallager[8]提出置信度传播(Belief Propagation,BP)译码算法。Arikan[9]使用BP译码算法进行极化码译码。与串行译码算法相比,BP译码算法性能与串行译码性能相当,译码时延大幅度降低。

基于2×2核的极化码BP译码算法通过级联的方式推广至基于3×3核矩阵极化码。基于2×2核的极化码BP译码算法信息更新公式,给出了3×3核内部最小计算单元的信息更新公式。基于最小单元信息更新公式给出了3×3核极化码的BP译码算法流程。基于3×3核矩阵下的极化码,相较于2×2核构造的极化码,码长更具丰富性,相较于串行译码算法中的SC译码算法,在35码长下,BP译码算法在1～4 dB的信噪比下,译码性能更具优势,在信噪比大于4 dB的情况下,BP译码算法性能稍弱于SC译码算法,由于BP译码算法具有并行译码结构,相较于SC译码算法,BP译码时延降低了约50%。

1 相关工作

1.1 符号说明

(1)

2×2核的极化码生成矩阵为：

(2)

(3)

1.2 极化码的构造

1.3 极化码的BP译码算法

BP译码算法是一种广泛使用的消息传递译码算法,主要应用场景有低密度奇偶校验码[8](Low Density Parity Check Code,LDPC)以及极化码,LDPC使用BP译码算法进行译码是基于奇偶校验矩阵进行消息更新的,极化码的BP译码算法消息更新是基于因子图[18]实现的。在2×2核矩阵构造的极化码中,因子图一共由n=lbN个阶段及N×(n+1)个节点组成,图1为一个(8,4)极化码的BP译码因子图[19]。图2中Li,j表示因子图中向左传递信息,Ri,j表示因子图中向右传播信息,0≤i≤n(n=lb(N))表示节点所在的列序号,0≤j≤N-1表示节点所在的行序号。

图1 码长为8的的极化码因子图Fig.1 Polar code factor graph with code length of 8

图2 BP译码算法中最小计算单元Fig.2 Minimum computing unit in BP decoding algorithm

Li,j与Ri,j在因子图相邻节点之间进行信息传递以及迭代更新,其中每次迭代更新遵循如下：

(4)

式中：L和R分别表示左右信息的值。

(5)

式中：s,t∈R,为了降低运算复杂度该函数一般使用基于最小和(Min-Sum)来近似。近似函数如下：

g(s,t)≈α×sign(s)×sign(t)×min(|s|,|t|),

(6)

式中：α一般取值为0.937 5。

在进行译码前,左信息与右信息对数似然比初始化如下：

(7)

(8)

(9)

2 基于3×3大核的极化码BP译码算法

在2×2核极化码BP译码算法[9]的基础上,本文提出了3×3核极化码BP译码算法。相较于传统的SC译码算法[12],二者译码性能相当,但BP译码算法在译码时延上更具优势。本节主要介绍基于3×3核的最小计算单元、BP译码算法、左右信息更新公式、译码算法流程等核心内容。

2.1 基于3×3核的最小计算单元

图3 基于3×3核极化码BP译码算法的最小计算单元Fig.3 Minimum computing unit of BP decoding algorithm based on 3×3 kernel polar code

2.2 3×3核极化码BP译码算法左右信息更新公式

BP译码算法是在变量节点与校验节点之间传递外信息,经过多次迭代后,达到算法收敛。BP译码算法是一种典型的后验概率译码算法,经过充分迭代之后逼近最大后验概率(Maximum a Posteriori,MAP)估计译码性能。

BP译码算法相较于串行译码算法最大的一个特点是可以并行译码,由此可以加快译码速度。在BP译码算法中,主要是通过因子图中的节点来实现左右信息的传递以及更新,图4为N=9时的3×3核BP译码因子图。

图4 码长为 9 的极化码因子图Fig.4 Polar code factor graph with code length of 9

基于消息传递算法,图4中信息更新遵循如下准则：先迭代更新节点中的左信息,再迭代更新节点中的右信息。

3×3核极化码最小计算单元中,左信息更新公式如下：

(10)

右信息更新如下：

(11)

2.3 基于核极化码BP译码算法流程

3×3核矩阵构造的极化码BP译码算法流程如算法1所示。

算法1 极化码BP译码算法输入：LLR(yj),0≤j

3 仿真结果与分析

将提出的3×3核BP译码算法与文献[12]提出的SC译码算法从纠错能力方面进行比对,从而验证高维BP译码算法的有效性。本文的仿真环境参数如表1所示。

表1 仿真参数

为了评估本文所提出的高维BP译码算法的性能,通过仿真码长为35、码率为0.5的极化码的FER以及实际计算不同码长下所需的计算单元,即为译码时延,并复现了文献[12]的SC译码算法结果作为对比,如图5所示。

图5 35码长下BP译码算法与SC译码算法性能比较 Fig.5 Performance comparison of BP decoding algorithm and SC decoding algorithm under 35

与串行消去译码算法相比,BP译码算法具有时延低、吞吐量大、易于实现软信息交互等优势。本文通过译码算法所需计算单元数量来等效替代译码算法的时延。考虑计算资源充足情况下的具体结果如表2所示。

表2 SC译码算法与 BP 译码算法时延对比

由图5与表2可以看出,BP译码算法在低信噪比的情况下,FER性能明显优于SC译码算法;在高信噪比的情况下,虽然BP译码算法略差于SC译码算法方法,但是BP译码算法的时延要好于SC译码算法。综上,高维BP译码算法在低信噪比、通信条件较差时,将会是优于SC译码算法的选择,若通信场景对于时延有着较高的要求,亦可考虑BP译码算法。

4 结论

本文主要将已有的BP译码算法推广至3×3大核BP译码算法,并且在35码长下将其与使用较多的SC译码算法性能上做了比较,结果显示在低信噪比的环境下,3×3大核BP译码算法FER性能优于高维SC译码算法性能。同时,3×3大核BP译码算法在译码时延上相较于SC译码算法更具优势,在相同的硬件环境下,对通信时延有着更高要求的应用场景,可以考虑使用大核BP译码算法替代SC译码算法。接下来研究的重点是提升高维BP译码算法的纠错能力以及在其他码长下BP译码的纠错能力。