降低SCL译码错误的级联极化码

王涛　屈代明　江涛

摘要：串行抵消列表（SCL）算法是极化码的一种近似最大似然（ML）译码算法，基于该算法的循环冗余校验（CRC）级联极化码、校验（PCC）级联极化码纠错性能优良，已成为5G极化码标准编码方案。总结了SCL译码错误类型，并从降低SCL译码错误的角度揭示了CRC级联极化码、PCC级联极化码，以及CRC辅助的PCC级联极化码，三者提升SCL译码性能的原理。仿真结果表明：CRC辅助的校验级联极化码可以显著降低SCL译码错误，并在较高信噪比（SNR）范围内，呈现出最佳的纠错性能。

关键词：极化码;SCL译码;奇偶校验;CRC;级联码

Abstract： Successive cancellation list （SCL） decoder with the proper list size works nearly as a maximum likelihood （ML） decoder for polar codes. With the modified versions of the SCL decoder， cyclic redundancy check （CRC）-concatenated polar codes （CRC-polar） and parity-check-concatenated （PCC） polar codes （PCC-polar） show the excellent error correction performance， and have been adopted as the standardized coding schemes in 5G technical specification. In this paper， the categories of SCL decoding errors are summarized， and the performance gain of the CRC-polar， PCC-polar and CRC-PCC polar are explained from the perspective of SCL decoding error reduction. The simulation results show that the CRC-PCC polar code could efficiently reduce the SCL decoding errors， and achieve the best error performance among the three concatenation schemes， in higher signal noise ratio （SNR） region.

Key words： polar codes; SCL decoding; prity-check; CRC; concatenated codes

随着移动通信技术的日趋进步和智能终端设备的高速发展，为了满足日益增长的各类移动业务需求，第5代移动通信技术（5G）逐渐成为学术界和信息产业界的研究热点[1-6]。在2015年，国际电信联盟无线通信部（ITU-R）明确了5G 3大典型应用场景：增强移动宽带（eMBB）、大规模机器通信（mMTC）和高可靠低时延通信（uRLLC），并定义了各个业务场景的峰值速率和系统容量等关键技术指标[6]。为了满足业务场景的性能需求，5G信道编码标准技术经过多方研究和论证后率先于2016年被确定：极化码和低密度奇偶校验码分别被选为5G eMBB场景控制信道和数据信道编码的标准技术方案[7]。

极化码于2009年由土耳其学者E. Arikan教授提出，是第一类被证明容量可达的结构化信道编码方案[8]，并且因具有较低的编、译码复杂度等优势，受到广泛的关注和研究[9-18]。在2011年，I. Tal等学者提出的串行抵消列表（SCL）译码算法是极化码的一种近似最大似然（ML）译码算法[9]，并且基于该算法的循环冗余校验（CRC）级联极化码展现出超越低密度校验码（LDPC）的纠错性能[9]。此后，文献[10]提出的校验（PCC）级联极化码引入校验比特，在译码过程中实时校验译码路径，性能可超越CRC级联极化码。这2类级联方案由于编、译码复杂度较低且纠错性能优良，成为5G极化码标准实现方案[7]。鉴于CRC级联极化码和PCC级联极化码的译码均基于SCL译码算法，本文中我们着重分析了SCL译码算法的错误类型，并从降低SCL译码错误的角度解释了CRC级联极化码、PCC级联极化码，以及二者组合的CRC辅助的校验级联极化码提升纠错性能的原理。仿真结果表明：CRC辅助的校验级联极化码可以显著降低SCL译码错误，尤其在较高信噪比（SNR）范围内，呈现出最佳的纠错性能。

1 极化码编码与SCL译码

极化码的容量可达性建立在信道极化理论[8]上，具体为[N]个独立同分布的二元离散无记忆信道被极化为[N]个比特信道，且随着[N]趋于正无穷，[N]个比特信道的信道容量呈现两极分布：一部分信道容量趋于1，另一部分信道容量趋于0，且极化后的[N]个比特信道总容量与初始的[N]个二元离散无记忆信道总容量相等。极化码编码的基本思想是在容量趋于1的比特信道上传输信息比特，在容量趨于0的比特信道上传输收发双方已知的固定比特，从而实现可达容量的信道编码。

极化码是一类线性分组码，其生成矩阵为[GN=BNF?n]，其中，[N]为极化码码长，[BN]为比特翻转排列矩阵，[n=log2N]，矩阵[F=1，01，1]，[F?n]表示矩阵[F]的[n]阶Kronecker积。给定极化码编码器输入序列[uN1=（u1，u2，...，uN）]，极化码码字即为[cN1=uN1GN]。序列[uN1]包含2个子序列[uA=（ui，i∈A）]和[uAc=（ui，i∈Ac）]。集合[A?{1，2，...，][N}]为信息比特索引集合，[uA]为信息序列。给定信息比特数量[M]，根据极化码编码思想，集合[A]对应的[M]个比特信道应具有更高的信道容量[8]，或者更低的误判概率[12]，文献[12-14]分别给出了集合[A]的不同构造方法。集合[Ac]为集合[A]的补集，[uAc]一般取值为全0。

SCL译码算法是极化码的一种近似ML译码算法[9]。该算法的基本思想是在译码过程中保留[L]条似然概率最大的译码路径，当路径上的比特序列[uN1]判决结束之后，似然概率最大的路径上的信息序列作为译码结果被输出。SCL译码过程中，记[ui-1（i=2，3，...，N）]处的[L]条译码路径为[ui-11，l（l=1，2，...，L）]，路径[ui-11，l]判决比特[ui]扩展至[ui1，l]的过程为：若[ui]为信息比特，则每条路径[ui-11，l]在[ui]处分裂为2条子路径[ui1，l=（ui-11，l，0）]和[ui1，l=（ui-11，l，1）]，所得[2L]条子路径中似然概率最大的[L]条路径被保留;若[ui]为固定比特，则每条路径[ui-11，l]在[ui]处直接扩展为[ui1，l=（ui-11，l，0）]。这种列表译码的思想促使SCL译码算法以较低的译码复杂度[O（L?Nlog2N）]即可达到极化码ML译码性能[9]。

2 SCL译码错误分析

SCL译码错误可根据正确路径在译码器中的存在状态分为2类：消失错误和选择错误[15]。消失错误是指比特判决之后，[L]条路径不包含正确路径，即正确路径在比特判决过程中从译码器中消失（被淘汰）。选择错误具体是指比特判决之后，正确路径存在于译码器中，但是正确路径的似然概率因小于某条错误路径而未被选择作为最终的译码结果。

SCL译码的消失错误和选择错误主要受3个因素的影响：译码器路径总数[L]、极化码的最小码间距[dmin]、SNR。图1的仿真示例直观地展示3个因素对译码错误的影响，该示例为2种不同最小码间距的极化码在不同路径总数[L]的译码器以及不同SNR下的误帧率、消失错误比例对比图。该仿真中，极化码码长[N=256]，信息比特数量[M=64]，信息比特集合[A]根据文献[13]和[14]分别构造，且最小码间距分别为16和32，调制方式和仿真信道分别为二进制相移键控调制（BPSK）和加性高斯白噪声（AWGN）信道。

由图1可知：1）当[dmin]、SNR一定，随着[L]增加，消失错误比例下降，也即[L]越大，则译码器越能包容正确路径，从而降低正确路径被淘汰的概率;2）当译码路径总数[L]、SNR一定，[dmin]越大，则消失错误比例越高，选择错误比例越低，因为当比特判决之后，正确路径存在于译码器中，此时最小码间距越大，译码器误输出错误路径的概率越小，选择错误越少;3）当[dmin]、[L]一定，随着SNR的增加，消失错误比例逐渐降低，即在低SNR下，正确路径在比特判决过程中往往被淘汰，出现消失错误。

根据上述影响SCL译码错误的3个因素可知：在给定信道和译码器参数（SNR、路径总数[L]一定）的条件下，提升极化码在SCL译码下纠错性能的一个直接思路是增大[dmin]。对极化码级联外码是增大[dmin]的一类有效方法[11]，[17]。在当前的级联方案中，CRC级联极化码[9]和PCC級联极化码[10]是2类有效的极化码级联方案，其有效性表现在：1）这2类级联码均可采用改进的SCL译码算法进行译码;2）这2类级联码均可通过码构造而增大[dmin] [11]，[17]，从而降低SCL译码错误。这2类降低SCL译码错误的级联方案将在下一章节详细介绍。

3 降低SCL译码错误的

级联极化码

3.1 CRC级联极化码

（1）CRC级联极化码编、译码系统。

图2展示的是CRC级联极化码的编、译码系统示意图。在发送端，[M]长的信息序列[vM1]首先经过长度为[LCRC]的CRC编码器编码得到长度为[M+LCRC]的CRC码字，其中CRC码字的前[M]位为信息比特，后[LCRC]位为CRC比特;其次，CRC码字经过内码极化码编码得到级联码码字[cN1]。在接收端，接收信号[yN1]经过CRC辅助的SCL译码器输出信息序列的判决结果[vM1]。CRC辅助的SCL译码算法与传统的SCL译码算法主要区别在于2点：1）判决CRC比特时，译码路径按照信息比特的方式进行路径扩展;2）在比特判决结束之后，若译码器中存在满足CRC校验的路径，则能够输出满足CRC校验且似然概率最大的路径上对应的信息序列作为译码结果，否则则会直接输出似然概率最大的路径上对应的信息序列。

（2）CRC级联极化码性能提升原理。

CRC辅助SCL译码器在比特判决之后，通过CRC校验辅助选择正确路径，从而显著降低选择错误。此外，需要注意的是：对于长度为[L_CRC]的CRC码，内码极化码需要额外采用[L_CRC]个比特信道用于传输CRC比特，以此保证整个级联码码率不变。由于额外引入[L_CRC]个信道质量更差的比特信道，因此在相同的码率下，CRC辅助SCL译码器往往比传统SCL译码器具有更多的消失错误。

图3展示的是码长[N=256]、信息比特数量[M=64]、[d_min]为16的极化码，以及CRC长度为[L_CRC=4]的CRC级联极化码的误帧率、消失错误比例对比图。由图3可知：1）当路径数量较少时（[L=4]），通过级联较短的CRC码几乎可完全消除选择错误，但是由于[L]较小，消失错误为主要成分;因此额外引入4个信道质量较差的比特信道之后，CRC级联极化码误帧率性能相比非级联极化码明显降低。2）当路径数量较多时（[L=16]），通过级联较短的CRC码，可显著降低选择错误，但不能完全消除选择错误。此外，由于[L]较大，选择错误为主要成分，级联CRC码之后，CRC级联极化码误帧率性能相比非级联极化码明显提升。

最后，需要指出的是：在CRC级联极化码中，CRC码仍具有一定的链路层帧校验能力，因此往往为了保证CRC不可检测错误率（UER），在给定UER和译码器路径总数[L]的条件下，CRC长度[L_CRC]满足[L_CRC=log₂L-][log₂UER][16]。

3.2 校验级联极化码

（1）校验级联极化码编、译码系统。

图4展示的是校验级联极化码编、译码系统示意图。在发送端，[M]长的信息序列[v^M₁]首先经过[K]比特奇/偶校验码（本文以偶校验码为例进行说明）编码得到校验码码字，如图5所示，[K]个偶校验比特可分散于信息序列中间，而非集中于码字尾部。其次，校验码码字经过极化码编码得到级联码码字[c^N₁]。具体地，校验级联极化码可采用四元组[（N，I，P，{Tk|k=1，2，...，K}）]表示，其中，[N]表示极化码码长，集合[I]表示信息比特索引集合，集合[P]表示校验比特索引集合，集合[Tk]表示参与第[k]个偶校验方程的信息比特索引集合。给定校验级联极化码[（N，I，P，{Tk|k=1，2，...，K}）]，则第[k]个偶校验比特的编码公式如式（1）所示：

[upk=i∈Tkui  mod  2，k=1，2，...，K]，   （1）

其中，[pk]表示集合[P]的第[k]个元素，对应第[k]个偶校验比特在序列[uN1]中的索引。在接收端，接收信号[yN1]经过校验辅助的SCL译码器得到信息序列的判决结果[vM1]。校验辅助的SCL译码器与传统SCL译码器主要区别在于：校验比特的判决值根据该校验比特所在的校验方程以及对应的信息比特判决值校验得到。

（2）校验级联极化码性能提升原理。

PCC级联极化码相比CRC级联极化码具有更高的设计灵活性，在不同的构造方法下，其降低译码错误的原理不同。校验级联极化码的构造可分为3类：1）从降低选择错误的角度，以最大化级联码最小码间距进行构造[17];2）从降低消失错误的角度，以最小化码字簇成对错误概率（CPEP）的构造[15];3）从校验方程的硬件实现角度，以循环移位寄存器为基础的伪随机构造[7]，[18]。第3类构造方法一般可同时降低消失错误和选择错误。

图6展示的是码长[N=256]、信息比特数量[M=64]、最小码间距为16的极化码，以及校验级联极化码的误帧率、消失错误比例对比图。其中，校验级联极化码的构造采用的是5G极化码标准方案中基于5位循环移位寄存器的伪随机构造[7]，[18]。由图6可知：1）在较低信噪比下（E_b/N₀=0.5 dB、1 dB），对比极化码、校验级联极化码误帧率和消失错误比例可知，消失错误比例几乎不变，但是校验级联极化码误帧率明显较低，这表明伪随机构造的校验方程可同时降低消失错误和选择错误;2）在较高信噪比下（E_b/N₀=1.5 dB），对比极化码、校验级联极化码消失错误比例可知，校验级联极化码消失错误比例明显降低，该结果体现了校验级联极化码在降低消失错误方面的优势。

4 CRC辅助的校验级联

极化码及其性能

校验级联极化码可针对不同的SCL译码错误进行构造，相比CRC级联极化码具有更高的设计灵活性;但是其缺点在于不具备链路层帧检错能力。一个直接的改进方法是将CRC码和校验级联极化码结合，从而保留CRC码的帧校验能力。

图7展示的是CRC辅助的PCC级联极化码编、译码系统示意图。在发送端，CRC辅助的校验级联极化码可视为传统的CRC级联极化码、校验级联极化码的组合。在接收端，CRC-校验辅助的SCL译码器与传统SCL译码器主要区别在于：1）按照校验辅助的SCL译码器对每条路径上的比特进行判决;2）按照CRC辅助的SCL译码器选择最终的输出路径。

图8展示了BPSK调制和AWGN信道下仿真了极化码及其3种级联方案的误帧率性能。仿真中，码长[N=256]，信息比特数量[M=64]，信息比特索引集合按照文献[13]构造，译码器路径总数[L=8]，系统UER性能设定为[1×10^-4];因此CRC長度设定为[L_CRC=16]，CRC生成多项式为[g（x）=x¹⁶+x¹²+x¹¹+x⁹+x⁸+x⁵][+x³+x+1]。在校验级联极化码、CRC辅助的校验级联极化码中，校验方程采用5G极化码标准方案中基于5位循环移位寄存器的伪随机构造[7]，[18]。

从图8可知：1）对比极化码和校验级联极化码，对比CRC级联极化码和CRC辅助的校验级联极化码可知，引入校验比特可显著改善对应方案的纠错性能，在误帧率等于10^-3下，编码增益接近0.1 dB。2）在较低信噪比下（E_b/N₀<3 dB），由于译码错误主要为消失错误，校验级联极化码呈现出最佳纠错性能。由于CRC级联极化码引入16个错误概率更高的比特信道传输CRC比特，使其消失错误更为严重，呈现出最差的纠错性能;3）在较高的SNR下（E_b/N₀>3 dB），由于译码错误主要为选择错误，其非级联极化码具有最差的纠错性能，此外，CRC辅助的校验级联极化码可同时降低消失错误和选择错误，因此呈现出最佳的纠错性能。由于实际系统往往包含CRC码进行帧校验，在3种级联方案中，CRC辅助的校验级联极化码展现出更高的实际应用价值。

5 结束语

CRC级联极化码、校验级联极化码等级联方案纠错性能优良，具有较高的实际应用价值，因此分析这些级联码降低SCL译码错误的原理对于改善码的构造具有重要意义。本文中，我们总结了SCL译码错误类型，并从降低SCL译码错误的角度揭示了CRC级联极化码、校验级联极化码，以及CRC辅助的校验级联极化码三者提升SCL译码性能的原理。最后，需要指出的是：当给定译码路径总数，使得SCL译码器不为SC译码器，也不能近似为ML译码器时，目前尚缺乏SCL译码器的误帧率性能分析理论表达式，该工作的推进将有助于最优级联极化码的构造。

參考文献

[1] SHAFI M， MOLISCH A F， SMITH P J， et al. 5G： A Tutorial Overview of Standards， Trials， Challenges， Deployment， and Practice [J]. IEEE Journal on Selected Areas in Communications， 2017， 35（6）： 1201-1221. DOI：10.1109/jsac.2017.2692307

[2] BIOGLIO V， CONDO C， LAND I， Design of Polar Codes in 5G New Radio[EB/OL]. [2018-12-20]. https：//arxiv.org/abs/1804.04389

[3] RICHARDSON T， KUDEKAR S. Design of Low-Density Parity Check Codes for 5G New Radio [J]. IEEE Communications Magazine， 2018， 56（3）： 28-34. DOI：10.1109/mcom.2018.1700839

[4] 徐慧俊. 5G商用， 蓄势待发[J]. 中兴通讯技术， 2018， 24（1）： 2-5. DOI：10.3969/j.issn.1009-6868.2018.01.001

[5] 史治平. 5G先进信道编码技术[M]. 北京：人民邮电出版社， 2017

[6] IMT. IMT Vision - Framework and Overall Objectives of the Future Development of IMT for 2020 and Beyond： ITU-R M.2083-0 [S].2015

[7] 3GPP. Technical Specification Group Radio Access Network， NR; Multiplexing and Channel Coding （Release 15） [S]. 2017

[8] ARIKAN E. Channel Polarization： A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels [J]. IEEE Transactions on Information Theory， 2009， 55（7）： 3051-3073. DOI：10.1109/tit.2009.2021379

[9] TAL I， VARDY A. List Decoding of Polar Codes [J]. IEEE Transactions on Information Theory， 2015， 61（5）： 2213-2226. DOI：10.1109/tit.2015.2410251

[10] WANG T， QU D M， JIANG T. Parity-Check-Concatenated Polar Codes [J]. IEEE Communications Letters， 2016， 20（12）： 2342-2345. DOI：10.1109/lcomm.2016.2607169

[11] ZHANG Q S， LIU A J， PAN X F， et al. CRC Code Design for List Decoding of Polar Codes[J]. IEEE Communications Letters， 2017， 21（6）： 1229-1232. DOI：10.1109/lcomm.2017.2672539

[12] MORI R， TANAKA T. Performance of Polar Codes with the Construction Using Density Evolution [J]. IEEE Communications Letters， 2009， 13（7）： 519-521. DOI：10.1109/lcomm.2009.090428

[13] TAL I， VARDY A. How to Construct Polar Codes [J]. IEEE Transactions on Information Theory， 2013， 59（10）： 6562-6582. DOI：10.1109/tit.2013.2272694

[14] LI B， SHEN H， LAND Ingmar， A RM-Polar Codes [EB/OL].[2018-12-20] https：//arxiv.org/abs/1407.5483

[15] WANG T， QU D， JIANG T. Cluster Pairwise Error Probability and Construction of Parity-Check-Concatenated Polar Codes [EB/OL].[2018-12-20]. https：//arxiv.org/abs/1810.04458

[16] Samsung. Performance of Short-length Polar Codes： R1-1609072：3GPP TSG RAN WG1 Meeting #86[R]. Portugal， 2016

[17] PARK J， KIM I， SONG H Y. Construction of Parity-Check-Concatenated Polar Codes Based on Minimum Hamming Weight Codewords [J]. Electronics Letters， 2017， 53（14）： 924-926. DOI：10.1049/el.2017.1037

[18] Huawei HiSilicon. Details of the Polar Code Design： R1-1611254：3GPP TSG RAN WG1 Meeting #87[R]. USA， 2016