降低SCL譯碼錯誤的級聯(lián)極化碼

王濤　屈代明　江濤

摘要：串行抵消列表（SCL）算法是極化碼的一種近似最大似然（ML）譯碼算法，基于該算法的循環(huán)冗余校驗（CRC）級聯(lián)極化碼、校驗（PCC）級聯(lián)極化碼糾錯性能優(yōu)良，已成為5G極化碼標準編碼方案。總結(jié)了SCL譯碼錯誤類型，并從降低SCL譯碼錯誤的角度揭示了CRC級聯(lián)極化碼、PCC級聯(lián)極化碼，以及CRC輔助的PCC級聯(lián)極化碼，三者提升SCL譯碼性能的原理。仿真結(jié)果表明：CRC輔助的校驗級聯(lián)極化碼可以顯著降低SCL譯碼錯誤，并在較高信噪比（SNR）范圍內(nèi)，呈現(xiàn)出最佳的糾錯性能。

關(guān)鍵詞：極化碼;SCL譯碼;奇偶校驗;CRC;級聯(lián)碼

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

隨著移動通信技術(shù)的日趨進步和智能終端設(shè)備的高速發(fā)展，為了滿足日益增長的各類移動業(yè)務(wù)需求，第5代移動通信技術(shù)（5G）逐漸成為學(xué)術(shù)界和信息產(chǎn)業(yè)界的研究熱點[1-6]。在2015年，國際電信聯(lián)盟無線通信部（ITU-R）明確了5G 3大典型應(yīng)用場景：增強移動寬帶（eMBB）、大規(guī)模機器通信（mMTC）和高可靠低時延通信（uRLLC），并定義了各個業(yè)務(wù)場景的峰值速率和系統(tǒng)容量等關(guān)鍵技術(shù)指標[6]。為了滿足業(yè)務(wù)場景的性能需求，5G信道編碼標準技術(shù)經(jīng)過多方研究和論證后率先于2016年被確定：極化碼和低密度奇偶校驗碼分別被選為5G eMBB場景控制信道和數(shù)據(jù)信道編碼的標準技術(shù)方案[7]。

極化碼于2009年由土耳其學(xué)者E. Arikan教授提出，是第一類被證明容量可達的結(jié)構(gòu)化信道編碼方案[8]，并且因具有較低的編、譯碼復(fù)雜度等優(yōu)勢，受到廣泛的關(guān)注和研究[9-18]。在2011年，I. Tal等學(xué)者提出的串行抵消列表（SCL）譯碼算法是極化碼的一種近似最大似然（ML）譯碼算法[9]，并且基于該算法的循環(huán)冗余校驗（CRC）級聯(lián)極化碼展現(xiàn)出超越低密度校驗碼（LDPC）的糾錯性能[9]。此后，文獻[10]提出的校驗（PCC）級聯(lián)極化碼引入校驗比特，在譯碼過程中實時校驗譯碼路徑，性能可超越CRC級聯(lián)極化碼。這2類級聯(lián)方案由于編、譯碼復(fù)雜度較低且糾錯性能優(yōu)良，成為5G極化碼標準實現(xiàn)方案[7]。鑒于CRC級聯(lián)極化碼和PCC級聯(lián)極化碼的譯碼均基于SCL譯碼算法，本文中我們著重分析了SCL譯碼算法的錯誤類型，并從降低SCL譯碼錯誤的角度解釋了CRC級聯(lián)極化碼、PCC級聯(lián)極化碼，以及二者組合的CRC輔助的校驗級聯(lián)極化碼提升糾錯性能的原理。仿真結(jié)果表明：CRC輔助的校驗級聯(lián)極化碼可以顯著降低SCL譯碼錯誤，尤其在較高信噪比（SNR）范圍內(nèi)，呈現(xiàn)出最佳的糾錯性能。

1 極化碼編碼與SCL譯碼

極化碼的容量可達性建立在信道極化理論[8]上，具體為[N]個獨立同分布的二元離散無記憶信道被極化為[N]個比特信道，且隨著[N]趨于正無窮，[N]個比特信道的信道容量呈現(xiàn)兩極分布：一部分信道容量趨于1，另一部分信道容量趨于0，且極化后的[N]個比特信道總?cè)萘颗c初始的[N]個二元離散無記憶信道總?cè)萘肯嗟?。極化碼編碼的基本思想是在容量趨于1的比特信道上傳輸信息比特，在容量趨于0的比特信道上傳輸收發(fā)雙方已知的固定比特，從而實現(xiàn)可達容量的信道編碼。

極化碼是一類線性分組碼，其生成矩陣為[GN=BNF?n]，其中，[N]為極化碼碼長，[BN]為比特翻轉(zhuǎn)排列矩陣，[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]為信息序列。給定信息比特數(shù)量[M]，根據(jù)極化碼編碼思想，集合[A]對應(yīng)的[M]個比特信道應(yīng)具有更高的信道容量[8]，或者更低的誤判概率[12]，文獻[12-14]分別給出了集合[A]的不同構(gòu)造方法。集合[Ac]為集合[A]的補集，[uAc]一般取值為全0。

SCL譯碼算法是極化碼的一種近似ML譯碼算法[9]。該算法的基本思想是在譯碼過程中保留[L]條似然概率最大的譯碼路徑，當路徑上的比特序列[uN1]判決結(jié)束之后，似然概率最大的路徑上的信息序列作為譯碼結(jié)果被輸出。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譯碼算法以較低的譯碼復(fù)雜度[O（L?Nlog2N）]即可達到極化碼ML譯碼性能[9]。

2 SCL譯碼錯誤分析

SCL譯碼錯誤可根據(jù)正確路徑在譯碼器中的存在狀態(tài)分為2類：消失錯誤和選擇錯誤[15]。消失錯誤是指比特判決之后，[L]條路徑不包含正確路徑，即正確路徑在比特判決過程中從譯碼器中消失（被淘汰）。選擇錯誤具體是指比特判決之后，正確路徑存在于譯碼器中，但是正確路徑的似然概率因小于某條錯誤路徑而未被選擇作為最終的譯碼結(jié)果。

SCL譯碼的消失錯誤和選擇錯誤主要受3個因素的影響：譯碼器路徑總數(shù)[L]、極化碼的最小碼間距[dmin]、SNR。圖1的仿真示例直觀地展示3個因素對譯碼錯誤的影響，該示例為2種不同最小碼間距的極化碼在不同路徑總數(shù)[L]的譯碼器以及不同SNR下的誤幀率、消失錯誤比例對比圖。該仿真中，極化碼碼長[N=256]，信息比特數(shù)量[M=64]，信息比特集合[A]根據(jù)文獻[13]和[14]分別構(gòu)造，且最小碼間距分別為16和32，調(diào)制方式和仿真信道分別為二進制相移鍵控調(diào)制（BPSK）和加性高斯白噪聲（AWGN）信道。

由圖1可知：1）當[dmin]、SNR一定，隨著[L]增加，消失錯誤比例下降，也即[L]越大，則譯碼器越能包容正確路徑，從而降低正確路徑被淘汰的概率;2）當譯碼路徑總數(shù)[L]、SNR一定，[dmin]越大，則消失錯誤比例越高，選擇錯誤比例越低，因為當比特判決之后，正確路徑存在于譯碼器中，此時最小碼間距越大，譯碼器誤輸出錯誤路徑的概率越小，選擇錯誤越少;3）當[dmin]、[L]一定，隨著SNR的增加，消失錯誤比例逐漸降低，即在低SNR下，正確路徑在比特判決過程中往往被淘汰，出現(xiàn)消失錯誤。

根據(jù)上述影響SCL譯碼錯誤的3個因素可知：在給定信道和譯碼器參數(shù)（SNR、路徑總數(shù)[L]一定）的條件下，提升極化碼在SCL譯碼下糾錯性能的一個直接思路是增大[dmin]。對極化碼級聯(lián)外碼是增大[dmin]的一類有效方法[11]，[17]。在當前的級聯(lián)方案中，CRC級聯(lián)極化碼[9]和PCC級聯(lián)極化碼[10]是2類有效的極化碼級聯(lián)方案，其有效性表現(xiàn)在：1）這2類級聯(lián)碼均可采用改進的SCL譯碼算法進行譯碼;2）這2類級聯(lián)碼均可通過碼構(gòu)造而增大[dmin] [11]，[17]，從而降低SCL譯碼錯誤。這2類降低SCL譯碼錯誤的級聯(lián)方案將在下一章節(jié)詳細介紹。

3 降低SCL譯碼錯誤的

級聯(lián)極化碼

3.1 CRC級聯(lián)極化碼

（1）CRC級聯(lián)極化碼編、譯碼系統(tǒng)。

圖2展示的是CRC級聯(lián)極化碼的編、譯碼系統(tǒng)示意圖。在發(fā)送端，[M]長的信息序列[vM1]首先經(jīng)過長度為[LCRC]的CRC編碼器編碼得到長度為[M+LCRC]的CRC碼字，其中CRC碼字的前[M]位為信息比特，后[LCRC]位為CRC比特;其次，CRC碼字經(jīng)過內(nèi)碼極化碼編碼得到級聯(lián)碼碼字[cN1]。在接收端，接收信號[yN1]經(jīng)過CRC輔助的SCL譯碼器輸出信息序列的判決結(jié)果[vM1]。CRC輔助的SCL譯碼算法與傳統(tǒng)的SCL譯碼算法主要區(qū)別在于2點：1）判決CRC比特時，譯碼路徑按照信息比特的方式進行路徑擴展;2）在比特判決結(jié)束之后，若譯碼器中存在滿足CRC校驗的路徑，則能夠輸出滿足CRC校驗且似然概率最大的路徑上對應(yīng)的信息序列作為譯碼結(jié)果，否則則會直接輸出似然概率最大的路徑上對應(yīng)的信息序列。

（2）CRC級聯(lián)極化碼性能提升原理。

CRC輔助SCL譯碼器在比特判決之后，通過CRC校驗輔助選擇正確路徑，從而顯著降低選擇錯誤。此外，需要注意的是：對于長度為[L_CRC]的CRC碼，內(nèi)碼極化碼需要額外采用[L_CRC]個比特信道用于傳輸CRC比特，以此保證整個級聯(lián)碼碼率不變。由于額外引入[L_CRC]個信道質(zhì)量更差的比特信道，因此在相同的碼率下，CRC輔助SCL譯碼器往往比傳統(tǒng)SCL譯碼器具有更多的消失錯誤。

圖3展示的是碼長[N=256]、信息比特數(shù)量[M=64]、[d_min]為16的極化碼，以及CRC長度為[L_CRC=4]的CRC級聯(lián)極化碼的誤幀率、消失錯誤比例對比圖。由圖3可知：1）當路徑數(shù)量較少時（[L=4]），通過級聯(lián)較短的CRC碼幾乎可完全消除選擇錯誤，但是由于[L]較小，消失錯誤為主要成分;因此額外引入4個信道質(zhì)量較差的比特信道之后，CRC級聯(lián)極化碼誤幀率性能相比非級聯(lián)極化碼明顯降低。2）當路徑數(shù)量較多時（[L=16]），通過級聯(lián)較短的CRC碼，可顯著降低選擇錯誤，但不能完全消除選擇錯誤。此外，由于[L]較大，選擇錯誤為主要成分，級聯(lián)CRC碼之后，CRC級聯(lián)極化碼誤幀率性能相比非級聯(lián)極化碼明顯提升。

最后，需要指出的是：在CRC級聯(lián)極化碼中，CRC碼仍具有一定的鏈路層幀校驗?zāi)芰Γ虼送鶠榱吮ＷCCRC不可檢測錯誤率（UER），在給定UER和譯碼器路徑總數(shù)[L]的條件下，CRC長度[L_CRC]滿足[L_CRC=log₂L-][log₂UER][16]。

3.2 校驗級聯(lián)極化碼

（1）校驗級聯(lián)極化碼編、譯碼系統(tǒng)。

圖4展示的是校驗級聯(lián)極化碼編、譯碼系統(tǒng)示意圖。在發(fā)送端，[M]長的信息序列[v^M₁]首先經(jīng)過[K]比特奇/偶校驗碼（本文以偶校驗碼為例進行說明）編碼得到校驗碼碼字，如圖5所示，[K]個偶校驗比特可分散于信息序列中間，而非集中于碼字尾部。其次，校驗碼碼字經(jīng)過極化碼編碼得到級聯(lián)碼碼字[c^N₁]。具體地，校驗級聯(lián)極化碼可采用四元組[（N，I，P，{Tk|k=1，2，...，K}）]表示，其中，[N]表示極化碼碼長，集合[I]表示信息比特索引集合，集合[P]表示校驗比特索引集合，集合[Tk]表示參與第[k]個偶校驗方程的信息比特索引集合。給定校驗級聯(lián)極化碼[（N，I，P，{Tk|k=1，2，...，K}）]，則第[k]個偶校驗比特的編碼公式如式（1）所示：

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

其中，[pk]表示集合[P]的第[k]個元素，對應(yīng)第[k]個偶校驗比特在序列[uN1]中的索引。在接收端，接收信號[yN1]經(jīng)過校驗輔助的SCL譯碼器得到信息序列的判決結(jié)果[vM1]。校驗輔助的SCL譯碼器與傳統(tǒng)SCL譯碼器主要區(qū)別在于：校驗比特的判決值根據(jù)該校驗比特所在的校驗方程以及對應(yīng)的信息比特判決值校驗得到。

（2）校驗級聯(lián)極化碼性能提升原理。

PCC級聯(lián)極化碼相比CRC級聯(lián)極化碼具有更高的設(shè)計靈活性，在不同的構(gòu)造方法下，其降低譯碼錯誤的原理不同。校驗級聯(lián)極化碼的構(gòu)造可分為3類：1）從降低選擇錯誤的角度，以最大化級聯(lián)碼最小碼間距進行構(gòu)造[17];2）從降低消失錯誤的角度，以最小化碼字簇成對錯誤概率（CPEP）的構(gòu)造[15];3）從校驗方程的硬件實現(xiàn)角度，以循環(huán)移位寄存器為基礎(chǔ)的偽隨機構(gòu)造[7]，[18]。第3類構(gòu)造方法一般可同時降低消失錯誤和選擇錯誤。

圖6展示的是碼長[N=256]、信息比特數(shù)量[M=64]、最小碼間距為16的極化碼，以及校驗級聯(lián)極化碼的誤幀率、消失錯誤比例對比圖。其中，校驗級聯(lián)極化碼的構(gòu)造采用的是5G極化碼標準方案中基于5位循環(huán)移位寄存器的偽隨機構(gòu)造[7]，[18]。由圖6可知：1）在較低信噪比下（E_b/N₀=0.5 dB、1 dB），對比極化碼、校驗級聯(lián)極化碼誤幀率和消失錯誤比例可知，消失錯誤比例幾乎不變，但是校驗級聯(lián)極化碼誤幀率明顯較低，這表明偽隨機構(gòu)造的校驗方程可同時降低消失錯誤和選擇錯誤;2）在較高信噪比下（E_b/N₀=1.5 dB），對比極化碼、校驗級聯(lián)極化碼消失錯誤比例可知，校驗級聯(lián)極化碼消失錯誤比例明顯降低，該結(jié)果體現(xiàn)了校驗級聯(lián)極化碼在降低消失錯誤方面的優(yōu)勢。

4 CRC輔助的校驗級聯(lián)

極化碼及其性能

校驗級聯(lián)極化碼可針對不同的SCL譯碼錯誤進行構(gòu)造，相比CRC級聯(lián)極化碼具有更高的設(shè)計靈活性;但是其缺點在于不具備鏈路層幀檢錯能力。一個直接的改進方法是將CRC碼和校驗級聯(lián)極化碼結(jié)合，從而保留CRC碼的幀校驗?zāi)芰Α?/p>

圖7展示的是CRC輔助的PCC級聯(lián)極化碼編、譯碼系統(tǒng)示意圖。在發(fā)送端，CRC輔助的校驗級聯(lián)極化碼可視為傳統(tǒng)的CRC級聯(lián)極化碼、校驗級聯(lián)極化碼的組合。在接收端，CRC-校驗輔助的SCL譯碼器與傳統(tǒng)SCL譯碼器主要區(qū)別在于：1）按照校驗輔助的SCL譯碼器對每條路徑上的比特進行判決;2）按照CRC輔助的SCL譯碼器選擇最終的輸出路徑。

圖8展示了BPSK調(diào)制和AWGN信道下仿真了極化碼及其3種級聯(lián)方案的誤幀率性能。仿真中，碼長[N=256]，信息比特數(shù)量[M=64]，信息比特索引集合按照文獻[13]構(gòu)造，譯碼器路徑總數(shù)[L=8]，系統(tǒng)UER性能設(shè)定為[1×10^-4];因此CRC長度設(shè)定為[L_CRC=16]，CRC生成多項式為[g（x）=x¹⁶+x¹²+x¹¹+x⁹+x⁸+x⁵][+x³+x+1]。在校驗級聯(lián)極化碼、CRC輔助的校驗級聯(lián)極化碼中，校驗方程采用5G極化碼標準方案中基于5位循環(huán)移位寄存器的偽隨機構(gòu)造[7]，[18]。

從圖8可知：1）對比極化碼和校驗級聯(lián)極化碼，對比CRC級聯(lián)極化碼和CRC輔助的校驗級聯(lián)極化碼可知，引入校驗比特可顯著改善對應(yīng)方案的糾錯性能，在誤幀率等于10^-3下，編碼增益接近0.1 dB。2）在較低信噪比下（E_b/N₀<3 dB），由于譯碼錯誤主要為消失錯誤，校驗級聯(lián)極化碼呈現(xiàn)出最佳糾錯性能。由于CRC級聯(lián)極化碼引入16個錯誤概率更高的比特信道傳輸CRC比特，使其消失錯誤更為嚴重，呈現(xiàn)出最差的糾錯性能;3）在較高的SNR下（E_b/N₀>3 dB），由于譯碼錯誤主要為選擇錯誤，其非級聯(lián)極化碼具有最差的糾錯性能，此外，CRC輔助的校驗級聯(lián)極化碼可同時降低消失錯誤和選擇錯誤，因此呈現(xiàn)出最佳的糾錯性能。由于實際系統(tǒng)往往包含CRC碼進行幀校驗，在3種級聯(lián)方案中，CRC輔助的校驗級聯(lián)極化碼展現(xiàn)出更高的實際應(yīng)用價值。

5 結(jié)束語

CRC級聯(lián)極化碼、校驗級聯(lián)極化碼等級聯(lián)方案糾錯性能優(yōu)良，具有較高的實際應(yīng)用價值，因此分析這些級聯(lián)碼降低SCL譯碼錯誤的原理對于改善碼的構(gòu)造具有重要意義。本文中，我們總結(jié)了SCL譯碼錯誤類型，并從降低SCL譯碼錯誤的角度揭示了CRC級聯(lián)極化碼、校驗級聯(lián)極化碼，以及CRC輔助的校驗級聯(lián)極化碼三者提升SCL譯碼性能的原理。最后，需要指出的是：當給定譯碼路徑總數(shù)，使得SCL譯碼器不為SC譯碼器，也不能近似為ML譯碼器時，目前尚缺乏SCL譯碼器的誤幀率性能分析理論表達式，該工作的推進將有助于最優(yōu)級聯(lián)極化碼的構(gòu)造。

參考文獻

[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商用， 蓄勢待發(fā)[J]. 中興通訊技術(shù)， 2018， 24（1）： 2-5. DOI：10.3969/j.issn.1009-6868.2018.01.001

[5] 史治平. 5G先進信道編碼技術(shù)[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