魏浩，張夢潔，王東明

（1.中興通訊股份有限公司，廣東 深圳 518055；2.移動網絡和移動多媒體技術國家重點實驗室，廣東 深圳 518055；3.東南大學移動通信國家重點實驗室，江蘇 南京 210096；4.網絡通信與安全紫金山實驗室，江蘇 南京 211111）

0 引言

2008 年，土耳其學者Arikan 基于信道極化的思想提出了極化碼[1]，并證明了其在二進制輸入對稱離散無記憶信道下信道容量漸次可達[2]，引發(fā)學術界與工業(yè)界的高度關注。其作為信道編碼方案寫入第五代移動通信系統(tǒng)（5G）國際標準第一版（3GPP NR Rel-15 版本），并于2018年9 月正式發(fā)布[3]。極化碼通過信道分裂和信道合并操作引入相關性，從而構造出可靠度不同的極化信道[4]。5G標準給出了不同母碼長度的可靠度序列[3]，可靠度較高的極化信道承載信息比特進行數(shù)據傳輸，而可靠度較低的極化信道承載凍結比特進行前向糾錯，從而實現(xiàn)數(shù)據的可靠傳輸。為了實現(xiàn)任意碼長傳輸，5G 標準設計了速率匹配方案，相應定義了重復、打孔和縮短三種類型比特，可根據碼率和可靠度序列進行靈活配置。同時，將循環(huán)冗余校驗（Cyclic Redundancy Check，CRC）比特與奇偶校驗（Parity Check，PC）比特引入標準方案中，作為級聯(lián)碼的外碼提升譯碼性能[5]。

隨著5G 商用部署的日臻成熟，業(yè)界的研究熱點已經開始轉向下一代移動通信系統(tǒng)（6G）。相較于5G，6G 時代將面對更高程度的場景多樣性和需求差異性，高速率大容量廣連接等各項性能指標都將全面提升。其中，超高可靠低時延（Ultra Reliable Low Latency Communication，URLLC）的業(yè)務需求受到重點關注，要求中斷概率小于10-6且通信時延達到50～100 μs[6,7]。因此，已被嚴格證明可以沒有誤碼平臺的極化碼，其有限碼長的性能逼近香農容量極限，可以滿足超高可靠傳輸?shù)男枨?，?G 最有潛力的信道編碼候選方案之一[8]。目前，極化碼的主流譯碼方案是串行消除列表（Successive Cancellation List，SCL）算法[2,9]。當譯碼列表數(shù)較大時，SCL 譯碼的時間復雜度、計算復雜度和存儲復雜度都很高。同時，由于SCL 譯碼時序的串行特點，也較難實現(xiàn)高吞吐量的譯碼器[10]。因此，為了應對6G 提出的挑戰(zhàn)，業(yè)界對高效低時延的極化碼譯碼方案的需求變得愈發(fā)迫切。

本文首先介紹極化碼原理和5G 標準中極化碼的相關概念。其次，定義自由比特和確信比特，提出靈活串行消除列表（Flexible SCL，F(xiàn)SCL）譯碼算法，實現(xiàn)低時延譯碼方案。然后，對FSCL 算法譯碼流程進行闡述。同時，通過仿真實驗進行性能驗證，并給出譯碼時延分析。最后總結全文，對極化碼的未來應用和研究方向進行展望。

1 低時延譯碼方案

根據極化現(xiàn)象的信道分裂與合并過程，Arikan 提出采用串行消除（Successive Cancellation，SC）算法進行極化碼的譯碼[2]。通過引入廣度優(yōu)先搜索機制，對于每一個葉節(jié)點比特進行多條路徑的譯碼，并分別計算和更新路徑度量（Path Metric，PM）值，擴展形成SCL 算法[9]。同時在編碼時引入CRC 比特作為級聯(lián)碼，在譯碼的最后階段對多條候選路徑進行CRC 校驗，PM 值最小且通過CRC 校驗的譯碼路徑對應的碼字作為最終譯碼結果輸出[9,11]?；贑RC 輔助的SCL 算法，相對于Turbo 碼、LDPC 碼都有顯著的性能增益[8]，事實上成為了標準推薦和業(yè)界公認的極化碼主流譯碼方案。然而，高性能的譯碼方案也會帶來較高的復雜度。設計高效低時延的譯碼方案，實現(xiàn)高吞吐量的譯碼器，是應對6G 超高可靠低時延挑戰(zhàn)的必然要求。

SCL 算法的譯碼過程主要包括碼樹中非譯碼節(jié)點的f/g函數(shù)計算和比特遞歸更新計算，以及譯碼節(jié)點的路徑PM 值排序[8,9]。具體實現(xiàn)中，由于計算和存儲復雜度可以通過增加硬件資源來解決需求，業(yè)界更加關注的是f/g函數(shù)的計算量[8,12]。由于SCL 算法基于碼樹的譯碼架構和串行譯碼的特點，碼樹的每一個非譯碼節(jié)點都需要串行地進行f/g函數(shù)的計算，然后再進行比特更新遞歸信息至其父節(jié)點，由此限定了譯碼過程的時序。因此，盡可能在碼樹的上層節(jié)點進行譯碼，從而減少f/g函數(shù)計算和遞歸操作的次數(shù)，是降低譯碼器整體譯碼時延的關鍵。

1.1 譯碼節(jié)點層級提升

相對于原先在葉節(jié)點進行判決譯碼的SCL 算法，業(yè)界提出了固定多比特SCL 算法，每次固定譯碼2/4/8 個比特[13,14]。與單比特算法相比，在相應的碼樹中間節(jié)點就可以進行譯碼，譯碼節(jié)點的下層節(jié)點不需要計算f/g函數(shù)，從而減少譯碼的時間復雜度。然而每次以固定2/4 比特進行譯碼，對碼樹的譯碼節(jié)點層級提升不多（提升1/2個層級），同時固定譯碼8 比特的算法又會使得路徑PM值排序算法的計算復雜度和硬件資源開銷極大增加[15]。

根據碼樹葉節(jié)點中信息比特和凍結比特的組合，可以將碼樹解構為一些特殊類型的節(jié)點（或者子樹）。如圖1(a) 所示，以母碼長度為N=16 的極化碼為例，碼樹結構共有5 層，其中d=4 表示根節(jié)點，d=0 表示葉節(jié)點。根據碼樹的節(jié)點性質，可以將節(jié)點分為4 種類型[16,17]。Rate-0 節(jié)點為純白色節(jié)點，其所屬葉節(jié)點全部為凍結比特；Rate-1 節(jié)點為純黑色節(jié)點，其所屬葉節(jié)點全部為信息比特；REP（Repetition）節(jié)點為內黑外白色節(jié)點，其所屬葉節(jié)點中，只有最右邊一個是信息比特，其他全是凍結比特；SPC（Single-Parity-Check）節(jié)點為內白外黑節(jié)點，其所屬葉節(jié)點中，只有最左邊一個是凍結比特，其他全是信息比特。整個碼樹可以看作是由這些特殊類型的節(jié)點組成，然后對其譯碼方案進行低復雜度優(yōu)化，即是簡化串行消除（Simplified Successive-Cancellation，SSC）算法[18,19]。進一步考慮運用列表擴展方案，可以得到SSCL 算法[20,21,22]。

圖1 N=16極化碼碼樹節(jié)點

SSC/SSCL 算法在碼樹中對特殊節(jié)點進行匹配，盡量實現(xiàn)在上層節(jié)點進行譯碼。其中Rate-0、REP 兩種節(jié)點的譯碼算法得到較大簡化，但其匹配的子樹譯碼節(jié)點通常在靠近葉節(jié)點的位置，譯碼時延降低比較有限。SPC節(jié)點的譯碼算法相對復雜，需要分為多個子類討論，且只有啟發(fā)式的方案[20,21]。而Rate-1 節(jié)點的譯碼算法并不能簡化，其復雜度與固定多比特算法是相同的。實際中，Rate-R 節(jié)點由于其一般性（圖1(a) 中的純灰色節(jié)點），才是碼樹中所占比例最高的，需要重點優(yōu)化。此外，根據5G 標準，除了信息比特和凍結比特，還有PC 比特等其他類型，可能帶來更多的分類和更復雜的節(jié)點間關系。

1.2 自由比特路徑擴展

綜合考慮5G 標準確定的極化碼相關的比特類型，可以將信息比特和CRC 比特統(tǒng)稱為自由比特（Free Bit，F(xiàn)B），在譯碼時進行路徑擴展；凍結比特、PC 比特、打孔位置比特和縮短位置比特由于協(xié)議已經約定其比特值，因此可以統(tǒng)稱為協(xié)定比特（Agreed Bit，AB），在譯碼時不進行路徑擴展[23]。

由前文所述，固定多比特SCL 算法和SSC/SSCL 算法，都是為了提升碼樹的譯碼節(jié)點層級。前者關注于譯碼節(jié)點所屬葉節(jié)點的數(shù)量，但受限于計算復雜度，每次譯碼的比特數(shù)較為有限（業(yè)界一般推薦每次譯碼4 比特的方案）；后者根據譯碼節(jié)點所屬葉節(jié)點的特殊組合進行分類匹配，但這些特殊節(jié)點在碼樹中所占比例不高，而且還需要通過譯碼節(jié)點的比特再計算得到葉節(jié)點的比特。因此，兩種算法雖然一定程度提升了譯碼效率，但并沒有充分利用碼樹的特性。

通過對碼樹特征和SCL 算法的分析可知，譯碼節(jié)點的計算復雜度主要取決于路徑擴展的規(guī)模。由于協(xié)定比特不進行路徑擴展，因此決定路徑擴展規(guī)模的，不是譯碼節(jié)點所屬葉節(jié)點的數(shù)量，而是其中自由比特的數(shù)量。于是，提出一種靈活的SCL（Flexible SCL，F(xiàn)SCL）算法，基于其所屬葉節(jié)點中自由比特的數(shù)量，來判決是否在當前碼樹節(jié)點進行譯碼。以圖1 中的碼樹為例，考慮限制譯碼節(jié)點的最大計算復雜度，設置譯碼節(jié)點所屬葉節(jié)點中自由比特的數(shù)量小于等于4。結果如圖1(b) 所示，固定4比特算法與SSCL 算法，譯碼節(jié)點均為d=2 這一碼樹層級。而FSCL 算法，譯碼節(jié)點則為圖中藍色節(jié)點，在碼字前部提升至d=3。

FSCL 算法是一種通用的方案，考慮的是一般性的Rate-R 節(jié)點，關注其所屬葉節(jié)點中自由比特的數(shù)量，具有普遍意義。同時觀察極化碼可靠度序列可知，可靠度較高的比特位置處于碼字后部，而可靠度較低的位置處于碼字前部。因此，當碼字的碼率較低，自由比特數(shù)量較少時，碼字的前部呈現(xiàn)稀疏特性，使得碼字前部的譯碼節(jié)點層級提升（可以接近于根節(jié)點），有效降低譯碼時延。

1.3 確信比特路徑刪減

通常在實際通信時，主要關注信道碼字整體的誤塊率（Block Error Rate，BLER），極化碼的碼字BLER 可以表示為

是前i-1 個比特譯對時第i個比特的錯誤概率，也可以認為是第i個比特的誤比特率（Bit Error Rate，BER）的近似[24]。

極化碼在編碼時，根據可靠度序列由高到低，放置自由比特。而可靠度參數(shù)的實質為相應比特位置的最大似然譯碼錯誤概率上界[16]。由于極化特性，碼字不同比特位置的可靠度往往相差非常大。仍以母碼長度為N=16 的極化碼為例，設定信噪比為0 dB，計算加性高斯白噪聲信道的巴氏參數(shù)[25]?？梢缘玫桨褪蠀?shù)由低到高排在第1 位的值（表示最可靠）為0.000 3，而排在第8 位的值為0.260 4，幾乎相差3 個數(shù)量級。如果提升信噪比，則巴氏參數(shù)值會相差更大。于是根據式(1)和(2)可知，可靠度較高自由比特的BER 對于碼字BLER 幾乎沒有影響，碼字BLER 主要取決于可靠度較低自由比特的BER。這種可靠度的極化特性可以用來降低譯碼的復雜度。文獻[26]根據每個比特的巴氏參數(shù)得到BER，再轉換為其相應的似然比閾值。采用SCL 算法譯碼時，如果葉節(jié)點信息比特的似然比高于閾值則不進行路徑擴展，即回退到SC 算法。而對于固定4 比特算法，文獻[27] 統(tǒng)計了4 個葉節(jié)點中連續(xù)出現(xiàn)高可靠信息比特的情況，并分別進行排序復雜度的簡化。這兩種方案，本質上是利用可靠度的極化特性對譯碼節(jié)點的路徑擴展進行刪減，但譯碼節(jié)點的位置沒有改變，譯碼時延也沒有從時序方面降低。

對此，將可靠度較高的自由比特稱為確信比特（Trusted Bit），并應用于FSCL 算法中。在譯碼時，先根據自由比特中確信比特的數(shù)量進行路徑刪減，然后再根據剩余的自由比特數(shù)量進行路徑擴展。這樣，基于分階段排序的思想減少了路徑擴展的規(guī)模，降低了排序復雜度[28]。更重要的是，可以在不增加排序實現(xiàn)硬件資源的情況下，每次譯碼更多的比特，進一步的將譯碼節(jié)點上移。對比圖1(a) 和1(b) 中的碼樹，圖1(c) 中綠色節(jié)點表示確信比特。同樣考慮限制譯碼節(jié)點的最大計算復雜度，設置譯碼節(jié)點所屬葉節(jié)點中，自由比特的數(shù)量與其中確信比特數(shù)量的差小于等于4。由圖中藍色節(jié)點可以看到，采用結合確信比特的閾值判斷之后，F(xiàn)SCL 算法的后部碼字譯碼節(jié)點也提升至d=3 這一層級。

根據可靠度的極化特性，當碼率較高時，自由比特數(shù)量較多，同時確信比特也會相應增加。這樣結合前文所述，無論碼字的碼率高低，F(xiàn)SCL 算法都可以同時利用極化碼的稀疏特性和極化特性，提升整體的譯碼節(jié)點，減少f/g函數(shù)的時序數(shù)，有效降低譯碼時延。

2 FSCL算法譯碼流程

考慮一般性，設碼字母碼長度為N=2n，由一個滿二叉樹表示，n為碼樹的層級。設碼字中自由比特數(shù)量為K，其中確信比特數(shù)量為KTB，列表路徑數(shù)為L。對于其中的節(jié)點v，其層級為dv，dv=n表示當前節(jié)點為根節(jié)點，dv=0 表示當前節(jié)點為葉節(jié)點，節(jié)點v所屬的葉節(jié)點數(shù)量為2dv。設維度為2dv×1 的向量ξv為節(jié)點v所屬葉節(jié)點中各類型比特位置標識。令向量α表示對數(shù)似然比（Log likelihood Ratio，LLR）信息，向量β是對應的比特，而向量p表示PM 值信息，具體向量的維度如后文所述。同時，設置碼樹節(jié)點的譯碼判決閾值為KTH。

譯碼流程實現(xiàn)步驟如下：

（1）譯碼過程由根節(jié)點開始，當前節(jié)點v的比特位置向量ξv中自由比特數(shù)為Kv，其中確信比特數(shù)為，于是定義路徑擴展比特數(shù)。由其父節(jié)點傳遞的L條路徑的LLR 信息，分別是L個維度為2dv×1 的向量。同時傳遞的L條路徑的PM 值信息，由維度L×1 的向量pv表示。

其中，為母碼碼字長度為2dv的生成矩陣[2,6]，即將原先葉節(jié)點到譯碼節(jié)點的比特更新遞歸整合成編碼過程。對父節(jié)點傳遞來的L條路徑分別進行上述比特向量擴展，其中第l條路徑擴展出新的2Kv條路徑相應的PM值為：

（3）如果KvEX>KTH，則不在當前節(jié)點v進行譯碼。提取節(jié)點v的比特位置標識向量的前半部分：

得到左子節(jié)點的比特位置標識向量。通過f函數(shù)計算，得到左子節(jié)點vLF的L條路徑分別對應的維度為2dv×1 的LLR 向量：

在左子節(jié)點vLF完成譯碼流程之后，會將經過路徑擴展和刪減之后L條路徑的信息返回至節(jié)點v，包括更新之后的L條路徑PM 值向量，以及相應的比特向量。然后，通過g函數(shù)計算，得到右子節(jié)點vRT的L條路徑分別對應的維度為2dv×1 的LLR 向量：

（4）當根節(jié)點完成譯碼操作之后，譯碼流程結束，輸出譯碼結果。

3 仿真與分析

3.1 性能仿真實驗

本文通過仿真實驗對比了SCL、4b-SCL 與FSCL 三種算法的性能。其中4b-SCL 表示固定4 比特SCL 算法，同時FSCL 算法的譯碼節(jié)點閾值KTH設定為4 比特。為了對比簡潔，設置仿真實驗參數(shù)為加性高斯白噪聲信道，調制方式為QPSK，譯碼路徑列表數(shù)為L=8?？紤]碼率較低和較高的兩個仿真用例，其具體參數(shù)設置如表1 所示。

表1 仿真用例參數(shù)

此外，考慮對譯碼節(jié)點的實現(xiàn)復雜度做一定的限制，設置FSCL 算法每次譯碼時譯碼節(jié)點所屬葉節(jié)點中自由比特的數(shù)量不超過8 比特。為了更加清晰地描述確信比特對性能的影響，將確信比特數(shù)與自由比特數(shù)的比值定義為確信比例，即：

顯然有ηTB∈ [ 0,1]。

圖2 是關于case1 的BLER 性能的仿真。如圖2(a)所示，SCL、4b-SCL 與FSCL 三種算法的性能是一致的。當確信比例ηTB提升到1/6 和1/3 時，在BLER=10-5性能處仍然沒有損失；當μTB提升至2/3 時，出現(xiàn)較小性能損失。圖2(b)驗證了確信比特數(shù)對FSCL 算法性能的具體影響。固定SNR 值分別使得BLER 為10-1，10-2和10-3，可以看到，隨著確信比特數(shù)的增加，BLER 先保持恒定，隨后逐漸提高，到達一個數(shù)值之后會迅速抬升。而設置的BLER值越大，在保持性能恒定的條件下，可以選取的確信比特數(shù)也越多，這樣可以更大程度的降低譯碼時延。

圖2 BLER case1

圖3 是關于case2 的BLER 性能的仿真。由圖3(a)可知，SCL、4b-SCL 與FSCL 三種算法的性能是一致的。而且，確信比例ηTB提升至2/3 時，在BLER=10-4處仍然沒有性能損失。圖3(b)對確信比特數(shù)關于FSCL 算法性能的影響進行了驗證。同樣的，在固定BLER 相應的SNR 條件下，增加確信比特數(shù)，BLER 在保持一段的恒定之后，逐漸提高至一個數(shù)值后迅速抬升。同時可以看到的是，在相同的性能條件下，case2 可以設置的確信比例明顯高于case1。

圖3 BLER case2

由上述仿真可以看出，當自由比特越高，碼率越高時，可以選取的確信比特數(shù)也越多。通過大量的仿真和統(tǒng)計分析，給出確信比特的經驗公式如下：

其中，E表示傳輸碼字長度，R=K/E是碼字的碼率。參數(shù)ω1,ω2,ω3,均為實數(shù)，可以根據不同的性能和時延需求進行調整，同時將結果進行向下取整。當需要保持的恒定性能為BLER=10-2時，可以給出推薦的參數(shù)配置為ω1=0.2,ω2=0.6,ω3=-6。這樣，對于case1 可以得到確信比特數(shù)為9；而對于case2 可以得到確信比特數(shù)為54。當然，如果能夠接受一定程度的性能損失，則可以配置更多的確信比特。

3.2 時延分析

在實際實現(xiàn)過程中，通常以時鐘周期（Clock Cycle，CC）為單位來評估譯碼過程的時間復雜度，即完成譯碼必須要進行的時序數(shù)。對于以SCL 算法為框架的譯碼方案，碼樹中從根節(jié)點到譯碼節(jié)點之間每一個節(jié)點，進行f/g函數(shù)計算都需要各消耗一個CC[29]。以母碼長度為N=2n的碼字為例，對于SCL 算法，其譯碼過程的CC 數(shù)為[36]：

而對于4b-SCL 算法，譯碼節(jié)點提升兩個層級，但同時由于譯碼節(jié)點的實現(xiàn)復雜度增加，因此需要消耗一個CC[30,31]，于是可以得到其譯碼過程的CC 數(shù)為：

可以看到，SCL 算法與4b-SCL 算法的時延量級均為O(N)，但4b-SCL 算法相對于SCL 算法時延降低超過兩倍。

對于FSCL 算法，較難得到關于譯碼CC 數(shù)的理論表達式。如表2 所示，根據仿真實驗的兩個用例，對SCL、4b-SCL 和FSCL 三種算法的CC 數(shù)進行了統(tǒng)計。其中，由于FSCL 算法也是利用碼樹的結構，可以認為SSCL 算法與FSCL 算法（ηTB=0）的CC 相接近?？梢钥吹?，F(xiàn)SCL 算法的CC 數(shù)明顯小于SCL 算法和4b-SCL 算法。隨著確信比特的增加，CC 數(shù)量持續(xù)降低。雖然沒有準確的閉式解，但可以近似認為，F(xiàn)SCL 算法的CC 數(shù)與路徑擴展比特數(shù)有線性關系，即：

表2 譯碼CC數(shù)

由上述分析可知，譯碼的計算復雜度主要取決于譯碼節(jié)點所屬葉節(jié)點的比特擴展和路徑排序。FSCL 算法正是利用碼樹的稀疏特性和極化特性，在保證性能的條件下有效識別出真正需要路徑擴展的比特，從而提升譯碼節(jié)點層級，實現(xiàn)了高效低時延的譯碼器。

4 結束語

為了應對未來6G 系統(tǒng)超高可靠低時延的要求，本文提出FSCL 算法譯碼方案，可以通過調整確信比特的比例，靈活實現(xiàn)譯碼性能和譯碼時延的自適應優(yōu)化，較好地適用于URLLC 場景的業(yè)務需求。

極化碼在5G 時代進入標準，作為控制信道和廣播信道的編碼規(guī)范，已經證明其巨大的工程實用價值。而對于進一步應用于數(shù)據信道，相應的前瞻性研究已經開展。在數(shù)據傳輸方面，與多天線技術和非正交多址技術相結合，可以獲得更高的頻譜效率和更大的系統(tǒng)容量[4]。同時，基于混合自動重傳請求機制，可以根據信道條件實現(xiàn)鏈路自適應傳輸[32,33]。而在譯碼方案方面，基于可靠度的排序統(tǒng)計譯碼算法（Ordered Statistic Decoding，OSD）可以獲得短碼時近似最大似然譯碼的性能[34]。同時，也可以采用并行譯碼架構的置信傳播算法（Belief Propagation，BP），獲得在低信噪比條件時譯碼性能的提升[2]。但OSD 算法需要解決復雜度高的問題，而BP 算法需要降低在高信噪比時的誤碼平層[10]。

隨著相關技術研究的逐漸成熟，極化碼的潛力和優(yōu)勢也被不斷的發(fā)掘出來。極化碼提出至今僅十余年，作為5G 的編碼標準只是其實用的開始。相信在未來的6G 時代，極化碼將具有更加廣闊的應用前景。