针对极化码置信度传播算法的低复杂度早期停止准则

张小军 李 娜 董雁飞 崔建明 郭 华

①(山东科技大学电子信息工程学院 青岛 266590)

②(高效能服务器和存储技术国家重点实验室 济南 250101)

1 引言

2019年9月，芬兰奥卢大学6G旗舰研究计划组发布了全球首个6G白皮书，该白皮书认为6G的大多数性能指标相比5G将提升10～100倍。其中通信时延可低至0.1 ms，将是5G的1/10，并且具有超高可靠性[1]。这些需求对移动通信中的信道编解码的延迟特性和译码性能提出了更高的要求。极化码是第1种被证明在二进制离散无记忆信道下能够达到信道容量的纠错码[2]，具有较高的可靠度和实用价值，已经成为5G控制信道的编码方案，并有望成为6G通信中主要的信道编码方案。在极化码的译码算法方面，串行抵消(Successive Cancellation, SC)算法[3,4]和串行抵消列表(Successive Cancellation List, SCL)[5]作为极化码的低复杂度译码方案，具有较高的可靠性，但在译码时均需遍历译码二叉树的每个节点，导致译码延迟较高。与SC, SCL算法不同，置信度传播算法(Belief Propagation, BP)是一种并行迭代的译码算法，可获得较低的译码延迟。然而，大量的迭代次数仍造成BP较高的计算复杂度。由于大部分BP译码器在到达最大迭代次数之前已经收敛于原始码字，因此需要引入迭代早期迭代停止准则提前判断。为了减少迭代冗余，Yuan等人[6]提出了G矩阵(G-matrix)和最小对数似然比 (minimum Log Likelihood Ratio, minLLR)两个准则。其中，G-Matrix包含 N log N次二进制操作，而minLLR需要进行大量的比较运算。Yan等人[7]提出一种基于局部固定比特的早期停止准则，将固定位作为提前停止的准则。为降低资源消耗，文献[8]提出一种有效节省资源消耗的提前迭代终止准则，与基于阈值的算法相比，该准则可降低资源消耗且不会造成译码性能损失。Ren等人[9]提出了LLR辅助(LLR-Magnitude Aided, LMA)和循环冗余校验辅助(CRC Aided, CA)两种早期停止准则，当信噪比为4 dB、最大迭代次数为30时，LMA和CA分别能减少72.6%和84.5%的迭代次数。此外，Simsek等人[10]提出一种基于最坏信息位(Worst of Information Bits, WIB)的早期停止准则，它只需检测一部分LLR的符号位，可使译码复杂度有所降低，但译码性能低于G-Matrix。Simsek等人[11]通过去除冗余加法器阵列对WIB进行了优化。另外，Albayrak等人[12]提出了一种基于Luby变换的提前停止准则，通过观察译码器中LLR信息的符号位变化，确定译码输出是否收敛到原始序列。文献[13]于2017年提出了一种检测冻结位误码率(Frozen Bit Error Rates, FBER)的早期停止准则，该准则只检测在最可靠的冻结子信道中传输的冻结位。受到早期停止准则的启发，Giard等人[14]提出了基于极化码BP译码算法的盲检测法。上述准则都取决于或与对应的对数似然比(Log Likelihood Ratio,LLR)。

2 基本理论

2.1 极化码

2.2 BP译码算法

图1 (8, 4)极化码的因子图

3 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

图2 T d, T u和 T x的大小关系

图3 中符号变化和中错误位数

3.2 比较空间的构造

图4 (8, 4)极化码的Tanner图

4 性能分析

采用二进制相移键控(Binary Phase Shift Keying, BPSK)调制，在二进制加性高斯白噪声(Binary-Input Additive White Gaussian Noise,BI-AWGN)信道下，对(1024, 512)极化码进行BP算法仿真，其中 α=0.9375，最大迭代次数设置为40次。

算法1 (N, K) X-tolerance BP译码器

4.1 译码性能分析

如图5所示，当Q=128, X=2时，所提出的准则在误帧率和误码率上与40次固定迭代(fixed 40),WIB和FBER译码性能相似。如果Q降低到64，则需将X至少增加到3，以弥补性能损失。每当X增加1时，它将至少导致平均迭代次数上升一次。同样可观察到Q值越大，译码性能越好。然而，较高的Q值增加了计算复杂度。因此，可通过仿真选择合适的(X,Q)来权衡硬件复杂度和平均迭代次数。

4.2 对迭代次数的分析

4.3 硬件结构

图5 不同迭代终止准则的极化码译码性能比较

图6 不同迭代终止准则的平均迭代次数比较

图8中给出了(8, 4)极化码的BP译码流程。虚线部分表示处理单元的阶段和停止准则之间的数据依赖关系。采用X-tolerance时，在第t次迭代的第3个时钟中，译码器输出,i ∈[N]，然后确定。接下来，和被发送到相等检测器。第5个时钟，计算X比较器的结果。如果满足X-tolerance，译码器将计算,i ∈[N]，终止译码，否则继续下一次迭代。对于大多数具有实际长度 (n ≤10000)的极化码，相等检测器和X比较器的关键路径延迟总是小于PE[7]。因此，X-tolerance不会增加整个译码器的关键路径延迟。此外，G-Matrix, WIB和FBER只能在得到后开始早期停止准则的判决，由于译码器和早期停止准则并行运行，在得到早期停止准则的结果前，译码无法终止，这会导致额外的延迟和复杂度。如图8所示，在第t次迭代的第6个时钟中译码器计算输出,i ∈[N]，之后的第7个时钟其他准则才会开始判断是否终止译码，相对于X-tolerance会多出部分时钟译码延迟。当 n>2时，X-tolerance不会导致额外的延迟，因为X-tolerance的检测在获得之前已完成。

4.4 计算复杂度和资源消耗分析

图7 X-tolerance的硬件结构

图8 采用X-tolerance的BP译码流程

表1 早期停止准则的计算复杂度比较

表2 不同早期停止准则的综合结果

5 结束语

为了降低极化码置信度传播算法的译码延迟，减少迭代次数，本文提出一种基于码字估值的早期迭代停止准则。通过构造比较空间，只需检测码字估值中的部分位置，进一步降低计算复杂度，且不会引入额外的延迟。仿真表明，当最大迭代次数为40，信噪比为3.5 dB时，与G-Matrix相比，X-tolerance平均迭代次数上升了29.98%，与WIB,FBER相比，X-tolerance平均迭代次数分别降低39.44%和27.67%。综合结果表明，与G-Matrix,WIB和FBER相比，X-tolerance可节省90%以上的ALM资源。