一种基于分段CRC码级联Hash极化码的设计

李正杰，刘顺兰，张旭

（杭州电子科技大学电子信息学院，浙江 杭州 310018）

0 引言

极化码是由Arikan E教授于2009年基于信道极化现象而提出的一类线性分组码，当码长趋于无穷时，信息传输速率（或称码率）接近于信道容量[1]。极化码作为首个理论上能达到香农极限的信道编码方法，已被采纳为5G增强型移动宽带（enhance2 mobile broa2ban2，eMBB）场景中控制信道标准的编码方案[2]。Polar码在码长N趋向无穷大时被证明可达信道容量。然而，实际中由于开销的限制，码长总是有限的，极化码在中短码长时性能欠佳。因此，提升Polar码在有限码长条件下的性能对于Polar码能否实际应用非常关键。进一步研究表明，在有限长Polar码下再级联一个外码能够进一步提高其译码性能，设计性能更好的广义级联码作为改善译码性能的一种方案被越来越多的学者所研究。循环冗余校验码级联极化码（CA-Polar）[3]、奇偶校验码级联极化码（PC-Polar）[4]以及Hash校验码级联极化码（Hash-Polar）[5]是当前主流的极化码级联外码方案。

CA-Polar在译码过程中引入串行抵消列表（successive cancellation list，SCL）译码算法[6-7]和循环冗余校验（cyclic re2un2ancy check，CRC），CRC有助于在SCL译码的列表中挑选出正确的译码结果，较大地提升了Polar码的纠错性能。之后参考文献[4]提出奇偶校验码级联极化码（PC-Polar），PC校验比特有类似于冻结比特的判定方法，在译码的过程中起到了译码路径修剪的作用。除了CRC序列和PC序列级联的Polar码，文献[5]提出了基于Hash序列级联的极化码，称为Hash-Polar码，Hash编码器是一个非线性的编码器，前一个编码器的状态会影响到后一个编码器的状态，与CRC辅助校验译码一致，在SCL译码结束时Hash译码器对L条路径进行校验，且Hash的检验比特数量更灵活。3GPP在RAN1#90会议上对这几种方案进行评估，主要考虑的是加性高斯白噪声（a22itive white Gaussian noise，AWGN）信道输入下的误块率（block error rate，BLER）性能，结论是CA-Polar、Hash-Polar误块率性能相仿，而PC-Polar在某些码长、码率下（信息比特很小时）的误块率性能略好。

在Hash校验码级联极化码[5]的基础上，本文提出分段CRC码级联Hash极化码的设计方法。SCL译码算法本身逐比特按顺序译码的特点，使译码过程存在错误传播的现象，降低了译码的正确率，因此，本文建议采用改进的分段CRC辅助的SCL译码算法，分段CRC码在译码过程中对前面已知部分译码结果进行校验，校验不通过，则路径删除，减少了错误传播的现象。另外，分段CRC码还能辅助路径度量筛选可靠度更高的路径，译码结果与生成CRC码结果不一致则路径度量值增加，相比只能在译码的最后阶段筛选路径作为译码结果的Hash辅助译码算法的可靠性更高。

1 极化码及其级联方案

1.1 极化码的基本原理

极化码是一种基于信道极化理论的信道编码方式，利用信道极化产生的极化现象进行信息传输，在信道容量趋近于1的比特信道发送信息比特，在趋近于0的可靠度较低的信道上传输冻结比特，这种编码方式称为极化编码。令码长N= 2n,n＞ 0。每个码字的编码生成如下：

其中，BN为反序置换矩阵，F⊗n为克罗内克积，矩阵，令A为索引集合I的任意一个子集，信息比特序列记为uA，令为冻结比特序。定义比特信道索引集合设列，一般全部置为0，可将式（1）改为：

其中，GN(A)表示由A中元素对应的行构成的GN的子矩阵，GN(Ac)同理。

通过式（3），信源序列u1N编码得到码字c1N，从Polar码信道编码的过程可知，极化码码长为2的整数次幂，缺乏码率兼容的灵活性，不能满足实际需求。目前有凿孔[8]和缩短[9]两种方式可以获得码率兼容的Polar码，但都以牺牲少量误码率为代价，因此需要研究更好的码率兼容解决方案。

根据上述分析，该译码复杂度主要取决于LLR值的计算。SC译码算法的思想解决了极化码的译码问题，也是后续各种改进译码算法的基础，目前应用广泛的SCL译码算法是将SC译码算法和List算法结合的改进译码算法。Polar码的译码算法还有置信传播（belief propagation，BP）算法[10]、堆消去（successive cancellation stack，SCS）译码算法[11]，但都没有SCL译码算法理想，针对降低SCL译码算法的复杂度，还出现了快速SCL译码算法[12]。SCL译码算法虽好，但其本身存在的错误传播现象使得译码正确概率不够理想，高效的译码算法是信道编码能否实用的决定因素，因此，迫切需要研究性能更好的译码方案。

1.2 控制信道的Hash校验码级联极化码

文献[5]提出CRC辅助的Hash校验码级联极化码（Hash-CRC-Polar）方案，Hash-CRC-Polar编码框图如图1所示，极化码作为内码进行编码，CRC和Hash码作为外码进行双校验，双检验能有效提高系统的检错能力。信息比特经过CRC编码器，得到带有C位的循环冗余校验比特的信息序列其次经过Hash编码，得到外码码字Hash-CRC-Polar外码码字结构如图2所示。极化码的信息位上放置外码码字冻结位放置冻结比特，极化码编码后得到码字。 Hash-CRC-Polar码的具体编码过程：CRC编码后的序列分为I＞ 2段依次输入Hash编码器得到Hash状态序列。

图1 Hash-CRC-Polar编码框图

图2 Hash-CRC-Polar外码码字结构

• Hash函数h的两个输入为：第i段的整数表示ki和从第（i-1）段获得的Hash状态Si-1，然后计算第i段的Hash状态：Si=h(Si-1,ki)。

• 所有的段计算完成之后，将SI转换为H比特的序列，这里的H称为Hash状态序列。将该序列附加在序列后作为Hash编码器的输出码字。Hash函数可采用改进的“one-at-a-time”Hash函数[13]。与CRC编码相比，Hash编码器的检验比特数量可以很灵活。

在接收端，采用SCL译码，Hash状态比特当作信息比特译码，在SCL译码结束时，Hash译码器和CRC译码器都将对L条候选路径进行校验，双检验能提高译码结束后路径选择的正确性，但当L值较小，即候选路径较少时，误码性能提升不明显，增大列表大小L，译码的复杂度也会提高。

2 一种基于分段CRC校验码级联Hash极化码的设计

基于参考文献[5]，本文提出了基于分段CRC（segmente2 CRC，SCRC）校验码级联Hash极化码（Hash-Polar）的双校验改进方案，简称Hash-SCRC-Polar。将信息比特分段，CRC对信息比特进行分段校验，CRC参与到了译码时的校验，解决了Hash和CRC在译码结束时重复校验的问题；而且分段级联码中的CRC校验码不光能辅助路径度量筛选可靠度更高的路径，对CRC校验不通过的路径也能及时删除，相对于原有的CRC辅助的Hash-SCL译码算法降低了复杂度。最后Hash校验码对SCL译码结束后的L条路径进行校验，选择最佳译码路径。

2.1 基于分段CRC校验码级联Hash极化码的编码

基于分段CRC校验码级联Hash极化码（Hash-SCRC-Polar）的编码结构如图3所示，其中，编码主要由3部分组成：分段CRC编码、Hash编码、Polar码编码，外码码字结构如图4所示。译码主要采用本文提出的分段CRC辅助的Hash-SCL译码算法。下文主要从编码和译码两个方面详细阐述本文提出的新型编译码方法。

针对分段CRC校验码级联Hash极化码，这里给出两种编码方案，如图3所示。不同的是，图3（a）对分段CRC编码后的信息序列进行Hash编码，图3（b）对分段CRC编码前的信息比特进行Hash编码。相比于图3（a）对分段CRC编码后的信息序列再Hash编码，图3（b）只对原始信息比特进行Hash编码，进行Hash编码的信息比特少了分段CRC校验位，待编码的信息比特数减少，Hash编码时所占内存资源会稍低，开销减少。因此，本文选择图3（b）的设计方案。译码都是采用分段CRC辅助的Hash-Polar译码器，译码性能一致。

图3 Hash-SCRC-Polar编译码框图

图3（b）中，分段CRC和Hash码作为外码，极化码作为内码进行编码。信息比特d2,… ,dK)分成S段后分别经过CRC编码器重组复用，每段得到C位循环冗余检验比特，最后得到带有S×C位的循环冗余校验比特的信息序列其中，qi1,… ,qiC为第i段信息序列的CRC码，i= 1,2,… ,S。其次，信息比特经过Hash编码得到Hash状态序列，与分段CRC编码后序列重组复用，得到外码码字极化码的信息位上放置外码码字，Hash-SCRC-Polar外码码字结构如图4所示。冻结位放置冻结比特，最后极化码编码后得到码字c1N。

图4 Hash-SCRC-Polar外码码字结构

2.2 基于分段CRC校验码级联Hash极化码的极化构造

Polar码在不同译码算法下的误码性能具有差异，但Polar码本身的误码性能在很大程度上受到码构造的影响，即信息位和冻结位的选取。最开始的构造方法有巴氏参数（Bhattacharyya parameter）构造，是Arikan E针对BEC信道下的Polar码构造提出的[1]。由于巴氏参数构造方法只适用于二进制删除信道（binary erasure channel，BEC）。后面陆陆续续出现了计算AWGN比特信道的可靠度的方法。其中包括蒙特卡罗（Monte Carlo，MC）构造[1]、密度进化（2ensity evolution，DE）[14]、高斯近似构造（Gaussian approximation，GA）[15]、极化谱（polarization spectrum）[16]等，根据这些方法构造的Polar序列都依赖于构造时AWGN信道的信噪比，信噪比不同，得到的Polar序列也会不同，这使得码构造不可避免地与信道存在一定的相关性，即所谓的信道敏感性。所以能够有一种序列构造方法与具体的信道无关，在实际应用中会更具有价值，于是华为公司提出了一种基于极化重量（polarization weight，PW）的构造方法[17]，它是基于Polar码生成矩阵的固定行重进行构造的方法，该方法的序列构造方式与具体的信道无关，而且性能与基于高斯近似的码构造方法在AWGN信道几乎一致。另外，极化谱（polarization spectrun，PS）在文献[16]中被提出，是近期极化码构造方面的新进展。

本文采取极化重量（PW）的构造方法估计信道的可靠性。对于第i个子信道，其序号i的二进制表示为 (bn-1bn-2…b0),n=lbN,该极化信道的极化重量被定义为[18]：

式（7）即该信道的可靠度度量值，其中极化重量越大，表示信道的质量越好，最终可以选择极化重量最大的K个信道作为传输信息位的比特信道。由式（7）可知，子信道可靠度的计算复杂度是线性的，且与GA等需要递归运算的方法相比，PW公式的复杂度极低，用PW的方法进行信道排序计算信道质量时，与底层信道类型无关，可以事先算出给定码长N的所有比特信道。

对任意长度N，依次计算，并按照从小到大的顺序排列，对应的就是可靠度由低到高的信道。例如，当码长为64 bit时，n= lb64 = 6，当i= 63时 ,根据上述所得到的信道可靠性排序后，从中挑选K+SC+H个可靠性较高的信道传输非固定比特，其余信道传输冻结比特。将外码码字与冻结比特混合，外码码字映射到可靠度较高的信道，其余信道为冻结位，得到长度为N的序列。对Polar码编码器的输入序列进行极化码编码，得到级联码字c1N，编码完成。

2.3 基于分段CRC校验码级联Hash极化码的译码

文献[5]中Hash辅助的CA-SCL译码算法只有在译码结束后进行校验，基于分段CRC校验码辅助的Hash极化码译码算法弥补了这一不足。在译码过程中引入了分段CRC校验比特，CRC校验比特可通过对前面已知的信息比特译码结果进行CRC得到，相当于一类动态的冻结比特，能在译码过程中辅助路径度量值进行路径的修饰，优化路径选择，提高误码性能，弥补了原有译码算法仅仅依靠译码结束后路径度量值进行译码路径的修饰；另外，当CRC译码结果和CRC校验结果不一致时，检验不通过，记录该条路径的CRC累计不通过次数，若该条候选路径的累计不通过次数达到预设定的上限，则该条候选路径被删除，相对于原有的译码算法降低了复杂度。译码结束时，Hash校验码对SCL译码结束后的L条路径进行校验，选出最佳译码路径。基于分段CRC校验码级联Hash极化码（Hash-SCRC-Polar）译码算法流程如图5所示。

图5 基于分段CRC码级联Hash极化码（Hash-Polar）译码算法流程

2.4 复杂度分析

在编码端，Hash-SCRC-Polar级联方案相比于Hash-CRC-Polar[5]级联方案，SCRC校验比特数量和CRC校验比特数量相同，SCRC比CRC多了S-1次循环冗余校验比特的确定，由于CRC检验比特的确定不涉及复杂的运算，所以编码的计算量增加不多，编码复杂度没有明显的增长，相对于性能的提升是可以接受的。

在译码端，本文的译码算法是在SCL译码算法的基础上改进的，分段CRC校验码会在译码时参与校验，而Hash-CRC-Polar级联方案的CRC校验码是在SCL译码后完成校验，其译码复杂度则为SCL译码器的计算复杂度。SCL译码算法的计算量由式（5）和式（6）总计执行的次数T(5),(6)决定，T(5),(6)有个简单的上界[7]：

因此，SCL译码器的计算复杂度为O(LNlbN)，即Hash-CRC-Polar级联方案的译码复杂度为O(LNlbN)。式（8）之所以成立是因为右边的值是L个SC译码器总是在同时且从头到尾地工作所产生的复杂度，实际上不是L个SC译码器都在运作，例如，译码第一个比特1u时实际上只有一个SC译码器在工作。

本文改进的译码算法在译码过程中能对于CRC校验不通过的路径及时进行删除，提前终止错误的译码路径，对应的SC译码器被清空，暂时处于未被激活状态，因此，改进的译码算法计算量为：

根据式（9），得到本文改进的译码算法复杂度仍为O(LNlbN)，但计算量有所降低。

3 仿真结果和分析

本文在AWGN信道下对比了3种不同方案的纠错性能。不同方案的仿真参数见表1。

表1 不同方案的仿真参数

其中，Hash-CRC-Polar表示参考文献[5]提出的级联极化码方案，Hash-Polar是在文献[5]中Hash-CRC-Polar的基础上删除了CRC编译码部分的方案，Hash-SCRC-Polar表示本文提出的基于分段CRC校验码级联Hash极化码方案，设置S= 4段CRC，每段3位CRC检验比特，该方案不仅能提高系统的检错能力，也能有效降低误码率。在译码过程中，保留路径L=16，保证类比方案的有效码率相同，即真实的信息比特与码长的比值相同，最后根据译码判决结果统计不同方案的误块率（BLER）。

码长为128 bit、256 bit、512 bit，码率不同时通过二进制相移键控（binary prase shift keying，BPSK）调制后在AWGN信道下的性能比较如图6～图8所示。

图6 码长为128 bit、码率不同时在高斯白噪声 信道下的性能比较

图8 码长为512 bit、码率不同时在高斯白噪声 信道下的性能比较

由图6～图8分别可以看出，在码长固定和码率不同情况下，本文提出的Hash-SCRC- Polar的级联方案比Hash-Polar、Hash-CRC-Polar性能更优异；Hash-Polar、Hash-CRC-Polar误块率性能相近，与Hash-Polar相比，Hash-CRC-Polar的双校验虽然能够有效提高检错能力，但不能显著提高系统的误码性能。码长越短，码率越低，本文提出的Hash-SCRC- Polar性能提升效果越明显。

由图6看出，在码长为128 bit、码率为1/2、误块率为 10-3时，本文提出的Hash-SCRC-Polar的设计方案比Hash-CRC-Polar获得了0.252B的增益。

由图7看出，在码长为256 bit、码率为1/2、误块率为 10-3时，本文提出的Hash-SCRC-Polar级联方法较Hash-CRC-Polar能够产生0.22B的增益。

图7 码长为256 bit、码率不同时在高斯白噪声 信道下的性能比较

由图8看出，在码长为512 bit、码率为1/2、误块率为 10-3时，本文提出的Hash-SCRC-Polar比Hash-CRC-Polar有接近0.12B的增益，在编译码复杂度不明显增加的情况下，本文的方案降低了误块率。

综合图6～图8可以看出，在码率为1/2，码长为128 bit、256 bit、512 bit等不同的情况下，即在码率固定、码长不同时,本文提出的Hash-SCRC-Polar设计方案均体现出较优异的性能。

4 结束语

为了进一步提高Hash-Polar码在有限码长下的性能，本文提出了一种基于分段CRC校验码级联Hash极化码设计方案，分段CRC校验码和Hash码作为外码，Polar码作为内码。在Polar码构造方面，使用了不依赖于信道信噪比且复杂度低的PW构造方法；在译码方面，基于SCL译码算法，分段CRC检验码能辅助路径度量值在译码过程中进行路径的修剪，对于CRC校验多次不通过的路径也能及时进行删除，Hash校验码用于L条候选路径中挑选最优的译码序列并输出。仿真结果显示，本文提出的基于分段CRC校验码级联Hash极化码比CRC辅助的Hash-Polar级联极化码更优异，误码性能得到了较为明显的提升，为解决有限码长性能不佳的问题提供了新思路。未来，笔者还可以继续研究设计性能更好的广义级联码，研究Polar码新的极化核以及相应的译码算法，也可以尝试将人工智能和Polar编译码相结合，进一步提高Polar码的译码性能。