降低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