奇偶校验和CRC级联的极化码编译码研究

张文宇，郭 锐

(杭州电子科技大学通信工程学院，浙江 杭州 310018)

0 引 言

由Arikan提出的极化码是一种基于信道极化的信道编码方案[1]，是目前理论上唯一能实现香农容量的方法，适用于任意二进制离散无记忆信道(Binary Discrete Memoryless Channel, B-DMC)，在加性高斯白噪声信道(Additive White Gaussian Noise, AWGN)中也具有优异的纠错能力，是未来6G通信的主要候选方案之一[2]。串行抵消(Successive Cancellation, SC)算法[1]译码复杂度较低，但译码性能不够理想。串行抵消列表(Successive Cancellation List, SCL)算法[3]通过保留多条译码路径并从中选取可靠性最高的路径作为输出，性能优于SC算法[4]，但计算复杂度是SC算法的L倍，其中L代表列表数。在SCL算法中引入循环冗余校验(Cyclic Redundancy Check, CRC)可以有效提升译码性能，CRC辅助的列表译码(CRC Aided SCL, CA-SCL)算法[5]将一段很长的CRC比特连接在信息序列尾部。分段CRC辅助的极化码[6]将校验比特均匀插入到信息序列中，可以更及时地检测错误的发生。将奇偶校验和极化码级联，在中短码长的情况下，可以提升一定的译码性能[7]。在SCL译码中引入奇偶校验和CRC，在拥有优于SCL算法译码性能的同时还能实现更低的译码复杂度[8]。双奇偶校验和CRC辅助的SCL算法[9]可以进一步提升译码性能，该算法以每2个奇偶检验比特为1组插入到极化码中。减少路径分裂次数的列表译码(Split Reduced Successive Cancellation List, SR-SCL)算法[10]提出一种新的路径分裂规则，当满足该规则时，说明极化子信道的可靠性足够高，直接执行硬判决而不是进行路径分裂。此外，在路径分裂的过程中还设定了阈值，用于删除那些分裂次数较少的路径。SR-SCL算法还证明，假设在某个特定比特之前的所有译码比特全部正确，在该特定比特之后可以将原有算法替换为SC译码，进而提出增强的SR-SCL(Enhanced Split-Reduced SCL, ESR-SCL)算法[10]，保持相似译码性能的同时降低了复杂度。

虽然SR-SCL算法的译码复杂度低于SCL算法，但译码性能较差。针对这一问题，本文提出一种奇偶校验和CRC辅助的ESR-SCL算法，引入奇偶校验比特及时删除部分错误路径，并通过CRC校验选取可靠性最高的译码路径作为输出，有效提升了译码性能，降低了译码复杂度。

1 极化码的编译码方案

1.1 极化码的构造

1.2 译码原理

(1)

(2)

SC译码器采用的是硬判决方式。在中短码长情况下，信道极化不充分，导致一些信息比特发生译码错误，发生错误传播。针对这一缺点，SCL译码算法将每个译码路径分裂成2个候选路径，通过列表保留L(L代表列表数)条候选路径，当路径数大于列表数时，选取路径度量值最大的L条路径存入列表。路径度量值可通过递归计算得到：

(3)

1.3 SR-SCL译码算法

SR-SCL是一种基于SCL算法的改进算法，在某些条件下不进行路径分裂，判决是否进行分裂的公式为：

(4)

式中，Pe(ui)为第i个信息比特的错误概率。当译码比特的错误概率较低时，将不进行分裂。SR-SCL算法还引入了计数器对路径进行剪枝的操作，对路径在不分裂情况下的生存阶段数ωl[i]进行计数。当路径数大于列表数时，如果ωl[i]达到预先设定的阈值ω，删除计数器的计数值小于ω的路径。

2 奇偶校验和循环冗余校验级联的极化码

2.1 奇偶校验和CRC级联极化码的结构

2.2 奇偶校验位的构造

(5)

式中，σ2表示噪声方差，φ(x)为一个单调递减函数，可以近似计算为：

(6)

取信噪比为1 dB，码长N为256，码率R为0.5，计算得到未冻结比特信道的错误概率如图1所示。图1中，垂直虚线代表根据错误概率绘制的信息段边界，极化码被7条边界分为8个信息段。通过不同信噪比划分不同的突发错误段来构造奇偶校验位，能更好地检测和删除信道产生的错误。

图1 极化码子信道的错误概率分布图

对于(N,K)的极化码，假设共有8个信息段和16个奇偶校验比特，校验方式为奇校验，信息位的长度为K，前i个信息段的长度为Ki，xj表示第j个信息比特，所有的第1校验位由之前所有的信息比特决定，第i(i是奇数)个奇偶校验比特表示为：

(7)

当第1奇偶校验位完成编码后，由于预先设定为奇校验，为了保证第1奇偶校验位进行校验时不受影响，则第2奇偶校验位的编码结果为：

pi=0i=2,4,6,8

(8)

译码阶段首先通过第1奇偶校验位进行校验，若校验不通过则直接删除译码路径，而第2奇偶校验位的译码结果可直接通过硬判决得到，如果和预先已知的编码结果不相符，说明译码发生错误，则调整该路径的路径度量值。采用二进制相移键控(Binary Phase Shift Keying, BPSK)进行调制，流程如图2所示。

图2 奇偶校验和CRC辅助的SR-SCL译码算法流程

2.3 奇偶校验和CRC级联的极化码译码

译码冻结比特和信息比特的过程和SR-SCL算法相同，不同之处在于增加了奇偶校验和CRC校验，译码阶段分为2种情况，当译码信息比特时，遵循式(4)的分裂规则，若满足条件则进行路径分裂，若分裂后的路径数大于L，将保留L条路径度量值较小的路径，同时在第i阶段译码完成后根据计数器中记录的值进行剪枝。由于正确的译码路径只在极少情况下分裂甚至不进行分裂，计数器的阈值ω的大小将直接影响最终的译码性能，因此引入路径分裂次数相对数的概念[13]，其定义为：

(9)

式中，m为路径编号。设定只有在Sl[i]≥T的情况下才会删除路径，T为阈值。当译码校验比特时，若为奇偶校验比特，对于第1奇偶校验比特，校验并删除那些错误的译码路径；对于第2奇偶校验位，硬判决如下：

(10)

如果译码结果不为0，说明译码发生错误，则根据式(3)调整该条路径的度量值，最后通过CRC校验列表中幸存的L条路径。如果只有1条路径通过检测，将其作为最终输出；如果有多条路径通过了检测，选择其中路径度量值最大的一条作为最终输出；如果没有路径通过检测，则直接在所有路径中选择路径度量值最大的一条作为最终输出。为了进一步降低译码复杂度，把一段较长的CRC比特序列插入第N-K/4+1个比特之后，将剩余的信息比特连接在该段CRC比特之后，记录通过CRC校验后的路径，之后的信息比特采用逐位译码的SC译码算法。本文提出的奇偶校验和CRC辅助的ESR-SCL(Parity Check and CRC Aided ESR-SCL, PC-CA-ESR-SCL)译码算法的具体流程描述如下。

输入:信息比特和冻结比特的索引集合B,信息位码长K,列表大小L,阈值T,码长N for i=1 to N-K/4+1 do if i∈B then 执行SR-SCL译码,判断路径是否分裂并根据L和T对路径进行剪枝; else 执行双奇偶校验,删除没有通过检测的候选路径; end if end for 执行CRC校验,如果第k条路径通过了校验则终止算法,仅保留第k条译码路径;如果没有路径通过CRC校验,保留列表中路径度量值最大的一条译码路径; for i=N-K/4+2 to N do 执行SC译码 end for输出:u ^N1

3 仿真实验与分析

仿真实验采用AWGN信道和BPSK调制，实验仿真帧数为105，信噪比的范围设定为0.5～2.5 dB，阈值T=7，列表大小L=8。对于仿真参数，保证所有仿真的有效码率是一致的。例如，对于(512,256)的极化码，R=0.5，校验位的总数目固定为24，奇偶校验比特的数目为P，CRC比特的数目为C，满足P+C=24，则K=232，所有算法中的信息比特数目都是232个，即有效码率Re=232/512。

3.1 仿真实验结果

设定码长N=256，奇偶校验比特的数目P分别为8，12，16，对应的CRC比特数目C分别为16，12，8，组成3种校验比特组合(8，16)，(12，12)，(16，8)，PC-CA-ESR-SCL和CRC辅助的SR-SCL(CA-SR-SCL)算法的译码性能如图3所示，其中EbN0表示信噪比。从图3可以看出，当信噪比较低时，无论奇偶校验比特组合和CRC比特的分配方式如何，PC-CA-ESR-SCL算法的译码性能都优于CA-SR-SCL算法；且在3种组合中，P=16，C=16的组合得到的译码性能最好；与P=8，C=16的组合相比较，在误块率(Block Error Rate, BLER)为10-2处可以获得0.2 dB的性能增益，这是因为增加奇偶校验比特的数目有助于在译码过程中提前检测和删除错误的译码路径。

图3 N=256时，不同校验比特组合下的译码性能

设定奇偶校验位和CRC的组合为P=16，C=8，CA-SR-SCL算法的CRC比特数为24，保证了2种算法信息比特的数目相同，码长N=256，阈值T分别为4和7时，PC-CA-ESR-SCL和CA-SR-SCL算法的译码性能如图4所示。从图4可以看出，和CA-SR-SCL译码算法相比，码长N=256，T=4的情况下，BLER为10-2时，PC-CA-ESR-SCL算法可以获得的性能增益大约为0.25 dB；码长N=256，T=7的情况下，BLER为10-2时的性能增益约为0.21 dB。

图4 N=256时，不同译码算法的性能

取和图4实验相同的参数，码长分别为512和128时，PC-CA-ESR-SCL和CA-SR-SCL算法的译码性能如图5所示。从图5可以看出，在相同信噪比和码长的情况下，阈值T=7的译码性能好于T=4，这是因为增大阈值会在列表中保留更多条路径，从而更有可能得到正确的译码路径；在相同阈值、相同码长和信噪比的情况下，PC-CA-ESR-SCL算法译码性能优于CA-SR-SCL算法，这是因为PC-CA-ESR-SCL算法使用了奇偶校验比特和CRC校验，能及时删除错误的译码路径。

图5 不同码长下，不同算法的译码性能对比

3.2 译码复杂度分析

为了描述译码复杂度，译码每个信息比特的时延用W表示，假定每个阶段幸存的译码路径数为Li，则CA-SR-SCL算法的平均译码延迟为WS=W×Li×Nlog2N，PC-CA-ESR-SCL算法的平均译码延迟为：

(11)

式中，V表示信息比特的段数，经过奇偶校验删除部分错误路径，并在第N-K/4+1个比特之后将译码算法替换为SC算法，这意味着有25%的信息比特通过SC算法译码，显然可以得出Wm

表1 不同算法的平均列表大小

4 结束语

本文提出一种奇偶校验和循环冗余校验级联的极化码编译码方案。采用双奇偶校验和CRC相结合的方式，在一定程度上提升了译码性能；并在某个特定比特之后将原有算法替换为SC算法，降低了算法的译码复杂度。但是，本文是在AWGN信道下进行的仿真实验，其实际应用价值有待进一步探讨，后续将针对本文算法在更多通信系统中的应用展开进一步研究。