一种基于奇偶校验码级联极化码的低复杂度译码算法

刘顺兰 王 燕

(杭州电子科技大学电子信息学院 杭州 310018)

1 引 言

极化码于2009年由Arikan[1]首次提出，是唯一可以理论上证明可达到任意二进制离散无记忆对称信道容量的新型高效信道编码技术，并且由于其较低的编、译码复杂度等优势，受到了广泛的关注，因此，极化码成为近年来最具吸引力的信道编码之一[2-4]，成功入选5G标准，作为增强移动宽带场景中控制信道的编码方案[5]。当极化码的长度趋于无穷时，才能更好地达到信道容量，然而在中短码长时性能不佳。为了提高极化码的纠错性能，先后提出了许多不同的译码方法。文献[1]提出采用串行抵消(Successive Cancellation, SC)译码算法，由于SC译码算法是一种次优的译码算法，在有限长码长中性能有待提升，并且在译码时前面的信息位一旦判决出错，将会影响后面的译码结果，造成错误传播。为了解决这一问题，文献[6,7]提出了串行抵消列表(Successive Cancellation List, SCL)译码算法，该算法通过扩张译码路径，提高了译码结果的正确性，但增加了时间复杂度和空间复杂度，成为一套功能强大并在不断改进的一种算法[8]。文献[9]引入循环冗余校验码与极化码级联，提出CRC辅助SCL译码算法(Cyclic redundancy Check Aided SCL, CA-SCL)，有助于在SCL译码的列表中挑选出正确的译码结果。此后文献[10]提出的奇偶校验码级联极化码引入校验比特，在译码过程中能够实时校验译码路径，即奇偶校验码辅助SCL译码算法(Parity Check Aided Successive Cancellation List,PC-SCL)。这两种译码算法虽然在性能上优于SC译码和SCL译码，但是与SCL译码一样，有着较大的复杂度。

根据极化码极化原理可知，在码长趋于无穷时，一部分信道的信道容量趋于1，另一部分的信道容量趋于0，在信道容量趋于1的信道上传输信息比特，趋于0的信道上传输冻结比特，而对于有限码长，存在着未被完全极化的子信道，这些子信道的可靠性较低。基于上述分析，本文提出了一种基于奇偶校验码级联极化码的低复杂度译码算法，即基于奇偶校验码级联极化码的串行抵消局部列表算法(Parity Check aided Partial Successive Cancellation List, PC-PSCL)，对于可靠性较低的信息子信道进行SCL译码，并加入奇偶校验比特辅助校验，其余可靠性较高的信息子信道仅采取SC译码算法，该算法降低了复杂度，并在性能上逼近PCSCL译码算法。

2 极化码

极化码的构造是编码中的一个重要步骤，根据极化码的构造可以进行极化子信道的选择。目前常用的子信道可靠性估计算法有：Arikan[1]首次提出极化码时给出了一种只针对二进制擦除信道的巴氏参数法；Mori等人[11]借鉴对 LDPC码的研究成果，提出了密度进化法(Density Evolution, DE)；Trifonov[12]提出的适用于高斯信道的高斯近似法(Gaussian Approximation, GA)，目前已成为一种比较有效的度量方法；Schürch[13]揭示极化码子信道间的偏用通序关系，华为提出了利用极化权重(Polarization Weight, PW)，并引入参数β扩展，来计算AWGN信道下子信道可靠度的算法[14]。在构造完成后，就可以根据极化码极化原理将信息比特与冻结比特混合，即可靠性比较高的子信道传输信息比特，可靠性比较低的子信道传输冻结比特。

对于给定的码长N，极化码的编码方式为

SCL 译码算法通过对信息位进行路径扩展，相对于 SC 译码算法提高了译码的可靠性，PC-SCL译码算法在SCL译码算法的基础上添加了PC校验比特，辅助路径筛选，进一步提高了译码算法的性能，但与SCL译码算法一样，L倍路径的增加带来了较大的复杂度。本文提出的PC-PSCL译码算法在保持与PC-SCL译码算法相近性能的情况下，复杂度有了较大的下降，如下文所述。

3 PC-PSCL译码算法

3.1 理论分析

图1 PC-Polar级联方案

3.2 外码构造

本文提出的PC-PSCL译码算法，在极化码编码前，需构造外码块，包括在传输信息比特的子信道中选择相对较不可靠信息子信道以及奇偶校验位。构造算法如下：

步骤1 根据高斯近似，子信道错误概率小于目标概率的子信道传输信息比特，在传输这些信息比特中的子信道仍存在有些信道相对而言较不可靠，用其索引下标值构成集合B，B ⊂A，在B中选择M −1个可靠性最高的信息子信道放置奇偶校验位，则B集合以奇偶校验比特为限，被分成M个外码块，第M位奇偶校验位取B中的最后一位索引，保证检验B中所有的信息比特。如图2所示，pj ∈B, j=1,2,...,M表示第j个奇偶校验位的索引，因此B集合被划分为M个外码块，表示为Tj ⊂B,j=1,2,...,M。

图2 PC-PSCL译码算法外码构造示意图

例如，在码长N=256，信噪比(Signal to Noise Ratio, SNR)等于1.5 dB时，经过高斯近似得到的子信道错误概率如图4所示。子信道错误概率越接近0，说明该信道越可靠，反之，子信道错误概率越接近0.45，说明该信道越不可靠，而子信道错误概率处于0到0.45之间的信道称为未完全极化信道。假设码率R=1/2，选定目标概率0.0425，子信道错误概率低于0.0425的信道传输信息比特，反之传输冻结比特。在信息比特中选择较不可靠信息位，取信息比特总数的50%，此时b=50%，集合B为子信道错误概率低于0.0425的64个信道，取奇偶校验比特个数M为5，按照上述的步骤1选取奇偶校验比特集合P，P中前4个奇偶校验位选择集合B中子信道错误概率较低的信道，第5位取集合B中的最后一个比特，则P={64,119,159,217,233}，因此外码块T={T1,T2,...,TM}的取值如表1所示。

3.3 PC-PSCL译码具体实现

由上述构造算法可知，本文提出的级联极化码包含多个外码块，以一个外码块为例阐述译码过程，具体算法流程图如图5所示，多个译码块类似。假设外码块为T={t1,t2,...,tm}，i表示译码比特索引值。

当1≤i

当t1≤i ≤tm时，该段主要有两种情况：

图3 含有外码块码长为N的极化码示意图

图4 N = 256信道极化示意图

表1 外码块T的取值

图5 PC-PSCL译码算法流程图

(1)i ∈T。说明第i位是外码块中的比特，此时有两种情况，一是被选取的较不可靠的信息位，将该信息位进行路径扩展，同时保留0和1两条路径，并记录路径度量值。假设此时扩展路径一共有l条，当l大于设定的最大保留路径数Lmax时，选择路径度量较小的Lmax条路径保留；二是第i位是奇偶校验位，根据式(23)奇偶校验方程得到奇偶校验估计值，保留一条或多条通过奇偶校验的路径，路径数记为Lp，若奇偶校验均未通过，则选择路径度量最小的Lp条路径作为外码块区间内的估计序列。

(2)i∈/T。表明第i位是冻结位或者较可靠的信息位，若该位是信息位则进行SC译码判决，记录对数似然比，若是冻结位直接判为0。

当tm

由上述的译码过程分析可知，PC-PSCL译码算法只对外码块中的信息比特分支扩展、奇偶校验，其余比特均只进行SC译码。本文的译码算法利用了SC译码具有较低复杂度这一优点，在外码块中引入SCL译码和奇偶校验，弥补了SC译码性能不佳的问题，相对于PC-SCL译码算法既降低了复杂度，又保持了较好的性能。

3.4 PC-PSCL译码算法复杂度分析

4 仿真结果和分析

本文在加性高斯白噪声信道下对比了几种不同译码算法的误帧率(Frame Error Rate, FER)，仿真次数为15000次。

图6 在不同译码算法下存储空间占用情况

表2 3种译码算法复杂度对比

图7 不同码长、不同L p情况下译码算法的性能

图7是不同码长，码率为1/2，Lmax=8，奇偶校验比特数M为5，b=50%的仿真结果，其中Lp取值分别为1, 2, 4。如图7(a)中N=512，由图7(a)可知：在PC-PSCL译码算法中，当Lp逐渐增大时，性能越来越好，但复杂度也增加，具体复杂度情况如表3所示。在Lp=2时，PC-PSCL译码算法性能已经优于SCL译码算法，与PC-SCL译码算法有着较小的差距，但空间复杂度节省了近63.09%；Lp=4时，PC-PSCL译码算法性能逼近PC-SCL译码算法，比SCL译码算法获得了0.5 dB的增益，但较PC-SCL译码算法空间复杂度节省了近38.09%，时间复杂度节省了近15.63%。若考虑到性能和复杂度的折中，以牺牲较小的性能为代价，Lp=2也不失为一个较好的选择。图7(b)考虑N=128和N=1024的情况，由图7(b)可以看到码长越长，译码性能越好，在Lp=4时PC-PSCL译码算法的性能与PC-SCL译码算法的性能相近，可以推断出在Lp=4时，PC-PSCL译码算法中经过奇偶校验保留的路径已经较为准确。

图8是码长为256，码率为1/2，Lmax=8，奇偶校验比特数M为5，Lp=4，选取的较不可靠信息比特占比b分别为20%, 30%, 50%的仿真结果。由图8可以看出：在b=20%和30%的时候，PCPSCL译码算法的性能较PC-SCL译码算法有着一定的差距，但b增大至50%时，PC-PSCL译码算法的性能逼近PC-SCL译码算法。因此，随着b的增大，扩展信息比特变多，PC-PSCL译码算法性能逐渐变好，同时复杂度也增大，如表4所示。

表3 N = 512时两种译码算法复杂度对比

图8 N = 256时不同b译码算法的性能

表4 N = 256时两种译码算法复杂度对比

5 结束语

基于PC码辅助的SCL译码算法，本文提出了一种低复杂度译码算法-PC-PSCL译码算法，对选取的局部信息比特进行奇偶校验和SCL译码。仿真结果显示，本文提出的译码算法在奇偶校验后保留合适的路径情况下有着和PC-SCL译码算法相近的性能，但是复杂度大大降低。