一种低迭代次数的极化码置信传播译码算法*

王华华，石 丹，赵昊明

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

根据香农有噪信道编码定理，存在可靠传输的最大信息速率即信道容量，采用合适的信道编码方法可以达到信道容量[1]。2009年，Arikan教授[2]提出了一种极化码编码方法，并且证明极化码能达到二进制离散无记忆信道的信道容量。其中的置信传播(Belief Propagation，BP)译码算法，基本原理来源于因子图与和积算法[3]。与SC(Successive Concellation)算法[4-5]相比，利用软信息判决方法的BP译码算法[6]拥有更低的译码时延和更大的吞吐量。该算法本质的并行译码性质非常适合使用现场可编程门阵列(Field Programmable Gate Array,FPGA)实现并行译码，但原始BP译码算法的复杂度较高。为了减少了BP译码算法的计算复杂度，工程中常利用等误差的线性近似函数来代替算法中的双曲函数[7]。这种使用线性近似的方法同样也能用在SC算法中，并且仅需乘法和加法操作，非常易于硬件实现。为了解决BP译码算法误帧率(Frame Error Rate,FER)相对较大的问题，有学者提出了基于BP的比特翻转译码算法[8]，采用预先构造关键集合的方式，对不能通过CRC校验的码块利用CS集合进行比特翻转，从而获得更大的FER增益。在原始BP译码的基础上引入信息纠正的策略同样也能带来可观的FER增益[9]。一种基于G矩阵的早期终止方式[10]，在每一次迭代完成后，都将判决码字比特和信息码字比特进行判决，判决结果两者一致就终止译码，从而减少BP译码的迭代次数和处理单元(Processing Element，PE)计算次数。近年来，有学者将深度学习引入到BP译码中，通过使用交叉熵损失函数与提出的交叉熵多损失函数对深度神经网络译码器进行训练,生成深度神经网络译码器也能达到降低复杂度和时延，提高译码性能的效果。

本文提出一种低迭代次数极化码BP译码算法，该算法能进一步减少BP译码过程的迭代次数，减少PE运算次数，从而降低极化码译码器的译码时延和功耗。

1 极化码

极化码是迄今为止唯一被严格证明能达到信道容量的信道编码方式[2]，通过信道联合和信道分裂两个步骤实现信道极化。当码长N趋于无穷时，一部分信道趋于完全可靠，其对称信道容量趋近于1；另一部分信道趋于完全噪声，其对称信道容量趋近于0。选k个最可靠的信道用于信息比特，另外N-k个信道固定为“0”，从而构成码率为k/N的(N,k)极化码。

1.1 极化码编码

Arikan基于二进制输入离散无记忆信道(Binary-discrete Memoryless Channel，B-DMC)提出了极化码的编码方案，其步骤如下：

Step1 估计极化信道可靠性。使用巴氏参数Z(W)来衡量信道的可靠性，W为删除概率ε=0.5的二进制删除信道(Binary Erasure Channel，BEC)。利用公式计算各个子信道的巴氏参数：

(1)

(2)

式中：GN为生成矩阵，可利用公式(3)得到。

GN=BNF⊗n。

(3)

1.2 极化码BP译码

图1 置信传播译码算法处理单元

PE的运算公式采用最小和近似简化[8](见式(4))，其中最小和近似系数α=0.937 5。

(4)

(5)

(6)

2 低迭代次数极化码置信传播译码算法

图2 CSFG与SC中的树状结构等价图

本文提出一种低迭代次数极化码BP译码算法，该算法能加快CSFG早期停止BP译码算法中子信道收敛，从而进一步降低译码器迭代次数。算法步骤如下：

Step1 根据Ac得到所有R1节点[4]索引关键集合(Critical Set，CS)，CS也是易错比特集合。

Step2 在每次硬判决信息利用公式(4)向右运算的过程中，尝试着对顺序子信道进行冻结。利用公式(7)求得子信道的码字序列估计值：

(7)

再利用公式(8)得到子信道信源序列估计值：

(8)

当子信道的码字序列估计值中的比特满足

(9)

(10)

已冻结的子信道在之后的迭代过程中将不再进行运算，相关PE也不再参与运算。但是在CSFG译码的过程中，会遇到含有信息比特的子信道由于对数似然比信息收敛较慢，经过了多次迭代仍然不能将其冻结的情况，这使得迭代次数增加，从而导致译码时延和译码功耗的增加。

Step3 对未能冻结的单个子信道i(i∈CS)进行flipcnt(i)自加计数，flipcnt(i)表示子信道i的迭代次数，当多次迭代后若flipcnt(i)>flipmax就利用公式(10)对未冻结的子信道进行比特翻转：

(11)

式中：flipmax表示仿真中达到最少迭代次数时需要设置的最大比特翻转迭代次数，可由公式(12)得到：

(12)

式中：flip∈{1,2,…,tmax}表示子信道翻转时所需的迭代次数，当子信道迭代次数达到flip时，进行比特翻转。公式(12)表示在不同码长N和不同信噪比RSN情况下，遍历所有flip使得平均迭代次数最少的flip，其中tercnt表示一次译码所需的迭代次数(译码错误时，当次tercnt为tmax)，Simcnt为仿真次数，设置为105次。可将仿真中得到的flipmax存入一张以N和RSN为索引的最大比特翻转迭代次数表中，在译码过程中，直接通过查表得到flipmax。

低迭代次数极化码BP译码算法伪代码如下：

Step1 根据Ac得到所有R1节点易错比特集合CS，当执行后转Step 2。

Step4 ifi+2n-j>frozcnt(j)，if第k个信道满足公式(9)子信道冻结条件时，转Step 5，else转Step 6 endif endif。/*跳过第k个子信道前面已经冻结的信道，并判断第k个子信道是否冻结*/

Step6 ifj=n，t++ endif；ift>tmax，结束译码，elsifj=n且子信道索引i∈CS时转Step 7，else转Step 8 endif。/*R向右是否运算到最后一级，迭代次数t=t+1，当t>tmax结束译码，否则不结束译码，判断不能冻结的子信道索引i是否在易错比特集合CS中*/

Step8 iffrozcnt(j+1)<2·frozcnt(j)，frozcnt(j+1)=2·frozcnt(j)；k=0。当执行后转Step 3 endif。/*下一级已冻结信道的最大位置索引frozcnt(j+1)至少是frozcnt(j)的两倍。k清零后进入下一状态尝试对子信道冻结*/

图3为本文提出译码算法的部分译码流程，图3(a)～(b)中j状态包含8个信道，这8个信道是原信道的子信道。尝试着对j状态的两个子信道进行冻结，发现k=2子信道不满足冻结条件；对k=1子信道冻结后进入j+1状态，尝试对未冻结的j+1状态中k=1子信道进行冻结。从图3(c)中发现，其不满足子信道冻结条件，且该子信道中信息比特索引i∈CS，则flipcnt(i)自加1，重新开始下一次迭代运算；当多次迭代后flipcnt(i)>flipmax，则对其进行比特翻转。从图3(d)中发现，经过多次迭代，j状态中k=2子信道满足冻结条件，至此j状态的所有子信道冻结完毕，则对整个j状态进行冻结并得到j状态信源序列估计值译码结果。

图3 低迭代次数极化码BP译码算法部分译码流程图

3 仿真与分析

图4 最大比特翻转迭代次数图

图5为极化码译码性能仿真图，仿真中所有算法迭代公式均采用α=0.937 5的最小和近似系数进行近似运算。本文所提出的低迭代次数极化码BP译码算法在不同信噪比情况下采用图4中最佳flipmax，在信噪比较低时(小于2 dB)其FER性能与G矩阵早期停止译码相似，但仍然存在微小的信噪比增益(0.03～0.06 dB)；在信噪比较大时(大于2 dB)其FER性能与CSFG接近，但FER略高于后者(0.01～0.03 dB)；在3 dB情况下，FER比G矩阵早期停止译码低约0.11 dB。图中基于BP的译码算法与基于SC的译码算法在性能上存在差距，但FER性能没有恶化。

图5 极化码译码性能

图6为(1 024,512)极化码平均迭代次数仿真图，其中本文所提出的低迭代次数极化码BP译码算法采用图4中不同信噪比所对应最佳的flipmax。仿真结果表明，本文所提出的算法比G矩阵早期停止译码和基于连通子因子图的早期停止BP译码平均迭代次数都少，这意味着更快的译码速率和更低的译码时延，在信噪比为3 dB时比tmax=40的传统BP译码减少了约53%，比G矩阵早期停止译码减少了约27%，比基于连通子因子图的早期停止BP译码减少了约14%。

图6 (1 024,512)极化码平均迭代次数

图7为(1 024,512)的极化码处理单元归一化平均计算次数。仿真结果表明，随着信噪比的增加和迭代次数的减少，后3种算法的PE归一化平均计算次数也相应地减少，其中低迭代次数极化码BP译码算法的PE归一化平均计算次数最低。在信噪比为3 dB时，其处理单元归一化平均计算次数比tmax=40的传统BP译码减少了约68%，比G矩阵早期停止译码减少了约50%，比基于CSFG的早期停止译码算法减少约10%。由此可以看出，本文提出的算法在低功耗译码方面也表现出了不错的性能。

图7 处理单元归一化平均计算次数

4 结 论

本文提出了一种低迭代次数极化码译码算法，能有效减少译码时延，降低处理单元功率消耗，从而降低译码器功率消耗。所提的并行译码算法可运用在对功耗要求较高的大规模机器类型通信，以及对时延要求较高的超可靠低延迟通信等5G场景下的极化码译码中。