极化码自适应信道译码算法

2022-09-27叶茂林谭晓青许丽卿吕善翔

深圳大学学报（理工版） 2022年5期

叶茂林，谭晓青，许丽卿，吕善翔

暨南大学信息科学技术学院/ 网络空间安全学院，广东广州510632

在二进制无记忆对称信道中，使用极化码的串行抵消（successive cancellation，SC）译码可令信道容量理论上达到香农极限［1］，因此极化码成为目前5G的编码标准之一，且在未来的多种无线通信应用场景下有巨大潜力［2-3］.然而，在编码长度有限情况下，SC 译码的性能低于低密度奇偶校验（low density parity check，LDPC）码［4］，需研究更可靠译码方法.

ARIKAN［5］提出置信传播（belief propagation，BP）译码方法，利用置换因子图方式进行译码，迭代计算多次后，该方法性能高于SC 译码方法.TAL 等［6］提出连续抵消列表法译码，通过在译码时保留多条路径提高了算法的可靠性.NIU 等［7］基于串行抵消列表（successive cancellation list，SCL）提出循环冗余校验辅助（cyclic redundancy check-aided SCL，CA-SCL）译码算法，利用循环冗余校验（cyclic redundancy check，CRC）检查SCL算法产生的译码分支，准确率比BP译码方法高［8］，但SCL算法复杂度高且译码复杂度不会随信道条件变化而变化，每次译码都会计算大量分支的值，显著的增加了译码过程的时间步数［9］，但在信道条件较好的时候，SC 算法有较好的性能，不必额外开分支使用SCL算法.在效率优化方面，SARKIS 等［10］根据冻结位数量和分布特点将译码树分割出4 种特殊节点类型，提出快速串行抵消（Fast-SC）译码算法.ANIF等［11］将Fast-SC中的特殊节点进行了更详细的分类，并给出了确定特殊节点方法，进一步降低了译码时延.CAVATASSI 等［12］将Fast-SC 译码算法拓展到多核情况，增加了Fast-SC 译码的灵活度.然而，Fast-SC 译码搜索特殊节点返回中间码字的迭代过程均与SC 译码相同，存在可靠性能偏低的问题.为兼顾极化码译码时间效率和准确率上的性能，LI等［13］提出自适应SCL（adaptive-SCL）算法，通过动态选取保留路径数目，提高了译码效率，其实质为SC 联合SCL 算法译码.本研究基于联合译码的思想，提出preFast-SCL 译码方法，进一步提高译码效率.该方法首先使用Fast-SC 译码算法，快速得到一组译码结果，对得到的译码结果进行校验，通过校验则作为结果输出，不通过校验则继续迭代使用SCL译码算法保证译码算法的可靠性.仿真结果表明，新算法的正确率与SCL算法基本相同，在中高信噪比条件下可有效降低译码复杂度.

1 极化码译码算法

为便于描述极化码常见和本研究提出的译码方法，表1给出了部分参数说明.

表1 参数说明Table 1 Parameters description

1.1 SC译码算法

极化码的SC 译码使用对数似然比（logarithm likelihood ratio，LLR）进行译码运算.对于长度N=2n(n∈N*)的极化码，设u=(u1，u2，…，uN)为发送信号.SC 译码算法先使用接收到的信号序列的对数似然比计算u1对应的估计值，随后利用估计，再用估计，以此类推并最终得到估计的发送信号其中，为信道序号1 到i的译码结果.信道序号值为i的节点的估计值为

SC 译码算法结构如图1.其中，信道i接收到的信号ri转换为LLR值的转换公式为

这里，σ为噪声方差.图1 中虚线和实现箭头分别为式（5）和式（6）的f操作和g操作；每个节点代表1个LLR 值，最右侧节点的LLR 值与接收端信道的LLR值相等，既，其余节点的LLR值可通过递归公式计算得到，再使用式（1）估计对应节点的值，则最左侧节点组成的序列即译码结果.

图1 SC译码算法结构Fig.1 Structure of SC decoding algorithm.

每个计算基本单元如图2所示.基本单元运算可分为两部分：

图2 SC译码基本单元Fig.2 Basic unit of SC decoding.

1）f操作.从右往左计算左上节点的LLR 值，并使用式（1）估计该节点的比特值为u1.

其中，L1和L2为图2中右边2个节点的LLR值.

2）g操作.采用式（6）计算左下节点的LLR值，再使用式（1）估计该节点的比特值.

为减少仿真计算的复杂度，将式（2）简化［14］为

图3 SC译码算法的伪代码Fig.3 Pseudocode of SC decoding algorithm.

1.2 SCL译码算法

SCL译码在SC译码的基础上保留了L条具有最小路径度量（path metric，PM）值的路径，增加了译码的可靠性.对于长度为N=2n(n∈N*)的极化码，SCL 译码中第l条(l=1，2，…，L)路径上的第i位(i=1，2，…，N)的路径度量为

PM 值越小，路径越可靠.每个节点译码最多保留L条路径，拓展路径条数超过L后将保留L条具有最小PM 值的路径，其余路径将被剪枝删除.因此，迭代完成后会得到L条分支，再按照PM 值从小到大排序，取第1条分支作为结果并输出.

CA-SCL 是信道传输中差错检验的常见技术，通过加入冗余校验位，可更充分利用SCL的译码路径.CA-SCL译码算法将译码路径按PM值从小到大排序，再依次进行校验，并取第1个通过路径作为译码结果输出，若都不通过则译码失败.CA-SCL算法的准确性比SCL算法有明显提高［7］.

2 自适应信道译码算法

传统的SCL译码虽然准确性高，但缺乏对信道条件的判断和利用，且在时间复杂度上仍有较大优化空间.本研究通过优化Fast-SC 算法和探究保留路径L对SCL 算法的影响，选择适当的保留路径数，译码时通过1次预快速译码检测信道情况，提高极化码译码效率.

2.1 Fast-SC译码算法及优化

Fast-SC 算法将译码树分成若干种特殊节点，然后根据节点的长度，迭代计算出相应层数的对数似然比值.图4 展示了4 种特殊节点的结构，使用该结构时其准确性与SC 译码算法基本相同［15］.特殊节点包含但不限于以下4种结构：

图4 SC快速译码特殊节点Fig.4 Special nodes of Fast-SC decoding.

1）码率0（rate 0，R0），所有信源比特全是冻结比特，所有比特译码为0，即β=（0，0，…，0）.

2）重复（repetition，Rep）码，除最后一位外其他位全为冻结位.记，若S≥0，则β=(0，0，…，0)；否则，β=(1，1，…，1).

3）单偶校验（single parity check，SPC）码，除了u1是冻结比特，其余都是信息比特.硬判决为

当SPC 译码结果β=(β1，β2，…，βN)的异或和为1，即时，使用比特翻转思想［16］，取进行βp=βp⊕1 操作，得到的β为译码结果.

4）码率1（rate 1，R1），所有的信源比特都为信息比特，直接使用式（8）进行硬判决.

这4种节点都可由LLR序列(y1，y2，…，yN)直接估计极化码码字序列β=(β1，β2，…，βN)，无需使用SC 译码迭代至叶节点.但是，R0节点的译码没有使用接收序列，在优化后的Fast-SC 译码算法中，需先辨认特殊节点是否为R0 节点，若是，则返回全0比特；否则，计算下一层LLR时再使用对应的译码规则.

表2 对比了当N=1 024 时，SC、Fast-SC 和优化Fast-SC译码算法中f函数执行次数和对应的误帧率（frame error rate，FER）.由表1 可见，优化Fast-SC译码比Fast-SC算法在效率上约有7%的提升.

表2 不同译码算法f函数执行效率和误帧率（N=1 024）Table 2 Comparison of f function execution efficiency of different algorithms (N=1 024)

2.2 选择CA-SCL译码算法合适的分支数

若CA-SCL 算法保留的路径数L太大，会产生很大时延，但若L太小，则可选择的译码器很少，且算法误帧率高、可靠性低.图5 给出了CA-SCL算法中保留路径数对误帧率的影响.其中，图注中括号内数值分别为码长和信息值；信噪比（signal to noise ratio，SNR）分别为1.5、2.0、2.5 dB.由图5可见，随着L的增大，算法译码的准确性上升，特别是在L=[2，16]时，FER 下降最快.当L≥8时，FER 的变化趋于平缓.因此，本研究取L=8作为保留路径数.

图5 CA-SCL译码算法保留路径数与误帧率的关系Fig.5 The relationship between reservation path and frame error rate of CA-SCL decoding algorithm.

2.3 preFast-SCL译码算法

自适应信道的preFast-SCL 译码算法流程和主要模块如图6.

图6 preFast-SCL译码流程图Fig.6 Flow chart of preFast-SCL.

得到对数似然比序列后，配合信息位集合A和使用的特殊节点类型node_type 进行Fast-SC 译码中，得到译码序列，并对该结果进行CRC 校验.若通过校验，则作为最终结果输出；否则，使用CA-SCL 译码器进行译码，提高译码结果可靠性.当信道条件较好时候，Fast-SC 有较高通过率，可大幅提升译码效率.当Fast-SC译码结果出现差错，校验不通过时，仍有CA-SCL 译码器兜底，有效提升了译码结果的可靠性.preFast-SCL译码算法的伪代码见图7.其中，进行CRC 校验，存储了所有L条路径的译码结果；为第l条路径的译码结果.

图7 preFast-SCL译码算法伪代码Fig.7 PreFast-SCL decoding algorithm pseudo code.

下面将讨论的最大和平均时间复杂度，以及空间复杂度的推导.

1）preFast-SCL最大复杂度是O(LNlbN)

Fast-SC 算法的时间复杂度为O(NlbN)；CASCL译码时间复杂度为O(NlbN)；CRC校验时间复杂度O(m).其中，L为CA-SCL算法的保留路径数；m为CRC校验位长度.最差的情况是执行快速译码后，检验失败，而在执行CA-SCL 译码算法时候，检测到最后一条路径才结束进行输出，此时有最大时间复杂度为

2）平均时间复杂度是O(1 +Pe(γ)L)NlbN

Pe(γ)是SC 算法在信噪比Eb/N0=γ时的误帧率.其中，Eb为平均比特符号能量；N0为噪声功率频谱.算法总会执行1次Fast-SC译码算法，但仅在不通过CRC 校验情况下才执行CA-SCL 算法，因此，平均时间复杂度为

其中，Pe(γ)为极化码误帧率满足Pe≤O(2-Nβ)，β为极化率［17］，即码长越长，preFast-SCL的译码时间复杂度比起SCL算法，下降得明显.

3）preFast-SCL算法的空间复杂度为O(LN)

Fast-SC译码算法与SC算法的空间复杂度相同，只需O(N)空间，而CA-SCL 算法使用懒复制（lazy copy）策略［6］，只需O(LN)空间.preFast-SCL 空间复杂度为

3 系统仿真分析

3.1 参数设置

为探究preFast-SCL 算法译码性能，本研究在加性高斯噪声信道下进行仿真，仿真参数设置如下：CA-SCL、adaptive-SCL［13］和preFast-SCL算法使用的CRC 生成多项式均为g(x)=x16+x15+x2+1，采用二进制相移键控（binary phase shift keying，BPSK）调制方式，极化码构造采用改进高斯估计法［18］，码率为0.5，BP译码最大迭代数为50次.

3.2 仿真结果与分析

图8对比了preFast-SCL、adaptive-SCL［13］和CASCL译码算法在N分别为512和1 024，信息位分别为256 和512 时的性能.其中，图注中括号内容表示信息比特序列长度和码长，如(512，1 024)表示信息比特序列长度为512，码长为1 024.

图8 信道适应译码算法与CA-SCL性能对比（a）可靠性；（b）耗时Fig.8 Performance comparison between channel adaptive decoding algorithm and CA-SCL for(a)reliability and(b)time consuming.

由图8（a）可见，信道适应算法preFast-SCL 和adaptive-SCL 都不会造成FER 性能损失，可靠性与CA-SCL算法基本相等.由图8（b）可得，在Eb/N0=0～1.5 dB 时，preFast-SCL 和adative-SCL 算法的复杂度比CA-SCL 算法更高，但在Eb/N0＞1.5 dB 时，preFast-SCL和adative-SCL算法的时间复杂度比CASCL算法都有大幅降.其中，preFast-SCL算法的时间性能优于adaptive-SCL算法.

图9对比了preFast-SCL译码算法在不同码长和信噪比条件下的FER 和时间效率性能.由图9 可见，在低信噪比条件下，preFast-SCL译码算法的长码译码速率低于短码译码速率.码长为N的码字，单位比特译码时间的复杂度为O(lbN)，即码字越长，译码速率越低.但另一方面，当相同信噪比时，码长增长，则码长较长的极化码的Pe(γ)值会降低.由式（12）可得，preFast-SCL译码算法的平均复杂度会下降，随着信噪比提升，长码译码的复杂度会有很大改善.

图9 信噪比与码长对preFast-SCL性能影响（a）可靠性；（b）译码耗时Fig.9 Influence of SNR and code length on the performance of preFast-SCL for(a)reliability and(b)time consuming.

图10为preFast-SCL算法、BP算法和SC算法的在码长N分别为256、512 和1 024 时的可靠性仿真对比.由图10 可见，preFast-SCL 算法比传统的SC和BP算法，可靠性能上有较大提升.

图10 PreFast-SC与传统算法可靠性对比Fig.10 Reliability comparison between preFast SC and traditional algorithms.

图11 给出了在码长N分别为512 和1 024 时，preFast-SCL、SC、CA-SCL 和Fast-SC 算法的复杂度比较.N=512，Eb/N0=2.0 dB 时，preFast-SCL 算法需执行的操作数约为CA-SCL 算法的45%，而在N=1 024，Eb/N0=2.0 dB 时，preFast-SCL 算法需执行的操作数仅是CA-SCL 算法的30%，且该值随着信噪比和码长的增加仍会继续降低.

图11 PreFast-SCL与传统算法时间性能对比（a）N=512；（b）N=1 024Fig.11 Time performance comparison between preFast-SCL and traditional algorithms for(a)N=512 and(b)N=1 024.