基于SCL譯碼復雜度的改進算法設計*

李怡超，葛萬成

（同濟大學 中德學院，上海 200092）

0 引 言

為滿足人們對數據傳輸的需求，優化與改進對數據編碼方式十分重要。連續刪除列表（Successive Cancellation List，SCL）譯碼算法是一種改進的遞歸連續刪除（Successive Cancellation，SC）譯碼算法[1]。眾所周知，極化編碼（Polar Code）在碼長趨于無窮時，信道極化才越完全。但是，在有限碼長下，由于信道極化并不完全，依然會存在一些信息比特無法被正確譯碼[2]。當前i-1個信息比特的譯碼中發生錯誤后，由于SC譯碼器在對后面的信息比特譯碼時需要用到之前的信息比特的估計值，將導致較為嚴重的錯誤傳遞，且無法對錯誤進行修改。針對SC譯碼算法的缺點，一個直接的改進方案是增加每一層路徑搜索后允許保留的候選路徑數量，從僅允許選擇“最好的一條路徑進行下一步擴展”改為“最大允許選擇最好的L條路徑”進行下一步擴展，其中L≥1。然而，SCL算法會大大增加編碼復雜度。本文的主要研究內容為通過設置a1和a2兩個閥值，在不影響性能的前提下降低算法復雜度。

1 連續刪除列表譯碼算法

連續刪除列表（Succesive Cancellation List，SCL）譯碼算法中有一個參數L，被定義為列表大小。正如SC算法，對每一個信息比特，它將會把當前的譯碼路徑分列為兩條新的路徑（一條定義為“0”，另一條為“1”）。當路徑數增長到一個已定閥值L時，它將會刪除最差的幾條路徑，僅保留最佳L條路徑。例如，圖1中，假設列表大小為4且所有的比特都是不固定的，在譯第3個信息比特時擴展了8條路徑，如圖1（a）所示。然后，按照計算每個路徑度量（Path Metric，PM）值選擇4條最佳路徑（001，100，110，111），如圖1（b）所示。譯碼列表算法繼續譯圖1（c）中的第4個信息比特，現在又有了8條路徑。所以，需要繼續刪除路徑保持L=4條路徑，如圖1（d）所示。最終，得到碼字（1001，1101，1110，1111）。當列表大小L=1時，實際上SCL譯碼算法相當于SC譯碼算法。

圖1 SCL算法

其中，用每條路徑的路徑度量（Path Metric，PM）值來判定這條路徑是好是壞。對于在i∈N層的每條路徑L路徑度量值被定義為：

即該路徑所對應的譯碼序列的概率，實現時往往采用對數形式。所以，路徑度量值可以隨著譯碼過程遞歸更新為：

對數似然比（Log-Likelihood Ratio，LLR）在通信中常用于軟解碼，不管發送端發射比特1還是比特0，接收端都有可能誤判。如果收到信號正確，正確判為0的概率與正確判為1的概率的比值就是似然比，對其取自然對數就是對數似然比，可表示為：

對于一個BiAWGN信道，輸出yi對應的信道對數似然比LLR可以被表示為：

2 基于SCL譯碼復雜度的改進算法設計

2.1 基于LLR的方案設計

作為計算LLR的初始值，信道輸出端的LLR可由式（4）計算得到。信道的LLR與信噪比相關，如果信噪比非常大、信道情況很好，相應的噪聲方差σn2就很小。所以，信道LLR的絕對值很大。通過譯碼過程中LLR的不斷更新，在算法的每次循環后得到的LLR的絕對值就會非常大。很明顯，LLR越大，對信息比特的判決越可靠，因為對數似然比LLR是正確判為0的概率與正確判為1的概率的比值。如果LLR為正且值很大，代表著判為0的證據更為可靠；反之，如果LLR為負且絕對值|Li|很大，則代表著判為1的證據更為可靠。所以，在每次循環時可以不用按例計算每條路徑的路徑度量值后根據路徑度量值得大小進行判決，而是可以嘗試在每更新一次LLR后，當滿足Li≥a1這一條件時直接進行一次硬判決，這樣SCL譯碼的算法復雜度將會被強制降低。因此，需要找到最合適的閥值a1使算法的復雜度能夠自適應BiAWGN信道的信噪比變化。

極端情況下，如果a1=∞，需要在譯每個信息比特時都擴展路徑，然后選擇L條最有可能的路徑，和原先的SCL譯碼算法相同。如果a1=0，則對于每一次循環，|Li|總是大于0，每個信息比特都需要進行硬判決，如同SC譯碼算法只有一條譯碼路徑，對應的是完全沒有噪聲的信道傳輸。換句話說，帶有未知參數a1的SCL譯碼的性能將會隨著相應復雜度的降低而在某種程度上變差。

2.2 基于PM的方案設計

從路徑度量值的式（2）可知，必須選擇有最大路徑度量值的路徑對應的碼字為譯碼序列。因為0＜Pr{uu1|y1Ni}＜1，所有的路徑度量值PM(ui1)都是負的。當在主函數的每一次i循環時，當計算完L條路徑的路徑度量值PM=[PM0,…PML-1]后，對這些路徑度量值從大到小進行排列，可以得到新的PM=[PM0,…PML-1]，然后計算前后兩個路徑度量值的差值d=[d1,…dL-1][3]。現在設置一個未知參數a2作為閥值，如果dl∈d＞a2，則直接刪去路徑L后面的所有路徑。

例如，設置a2=5，列表大小L=4，則如果d2=5，意味著PM1-PM2≥5，可以刪除PM2和PM3對應的兩條路徑，保留PM0和PM1對應的兩條路徑繼續計算。

同樣，在這里討論a2=0與a2=∞兩種特例。當a2=0時，需要刪除除了最大路徑度量值的路徑以外的所有路徑，實際上就是SC譯碼算法，對應于完全沒有噪聲的信道傳輸。但是，當a2=∞時，不能刪除任何路徑，實際上等同于原有的SCL譯碼算法。因此，此設計方案中能夠使復雜度隨著信噪比的增大而降低。需要說明的是，未知參數a2的值的確定很重要，因為它將會影響SCL譯碼的性能。

3 仿真與分析

3.1 設計方案的仿真目標

綜合考慮提出的兩個方案，可以將a1和a2兩個閥值設計在一個改進算法中實現。發現a1=0且a2=0代表了最壞的性能和相應最低的復雜度。當a1=∞且a2=∞時，可以得到最好的性能和最高的復雜度。很明顯，這兩種情況是改進后的SCL譯碼算法中的兩個極限。仿真將通過對樹搜索（Tree Searching）中的訪問過的節點（Visited Nodes）的數量仿真來估計復雜度。

例如，假設待譯碼序列中有3個比特，且它們全是未固定比特，列表大小為L=4。所以，當a1=∞、a2=∞時，需要像圖2一樣擴展所有的路徑，然后在這8條路徑中選擇L條最好的路徑。很明顯，訪問過的節點的個數為14。但是，當a1=0、a2=0時，對每一個比特都進行了硬判決，如圖3所示。最后，只有一條路徑對應的碼字為譯碼序列，假設為011。這種情況下只有3個訪問過的節點，所以它的復雜度比上一張圖的復雜度要低。

圖2 a1=a2=∞時的路徑樹

圖3 a1=a2=0時的路徑樹

下面給出在這兩種極限情況下的Matlab仿真。

仿真參數的設置如下：N=1 024，L=16，code_rate=0.5。目標是根據給予的工作點（Operating Point）來優化a1和a2。a1和a2必須滿足兩個條件：一是改進后的性能必須要接近原SCL譯碼的性能，如圖4所示；二是訪問過的節點數量將會隨著信噪比的增大明顯減少，當信噪比特別大時，訪問過的節點數量最終靠近SC譯碼算法，如圖5所示。

圖4 誤碼率對比

圖5 訪問節點數對比

3.2 數值結果分析

為了確定a1和a2的最佳閥值，現在挑選不同的a1和a2來仿真它們的性能和對應的訪問過的節點數量。部分結果如圖6、圖7所示，不同的a1和a2的性能均在SC譯碼和原SCL譯碼兩種極限之間。它們對應的訪問過的節點數量均有不同程度的下降，且最終比較接近于SC譯碼的訪問過的節點數量。

圖6 不同參數設置的誤碼率對比

圖7 不同參數設置的訪問節點數對比

3.2.1 a2=15的仿真結果

首先，假設a2=15不變，在此基礎上為a1選擇一些變量來仿真，結果如圖8、圖9所示。其次，根據仿真結果畫出在BLER=10-4處使用不同的a1的編碼和原SC譯碼相比的信噪比增益，如表1所示。可見，只有當a1=5、a2=15時的性能比原SCL譯碼的性能差的比較明顯。從表2中可以看出，a1越小，訪問過的節點數量減少的程度越高。所以，a1越大，該譯碼的性能越好，同時需要訪問的節點數越多。在通過權衡復雜度后，發現a1=15時，其性能與原譯碼規則基本相同，且大大減少了訪問節點的數量。

圖8 a2=15時誤碼率仿真

圖9 a2=15時訪問節點仿真

表1 BLER=10-4的信噪比增益

表2 在訪問過的節點數為5 000處的信噪比增益

3.2.2 a1=10的仿真結果

在此仿真中假設a1=15，然后為a2挑選一些變量進行仿真，結果如圖10、圖11所示。觀察仿真結果，在不同a2下的譯碼對比SCL譯碼在BLER=10-4處的噪聲比增益和在訪問過的節點為5 000的信噪比增益，如表3、表4所示。可以直觀看到，當a1=10、a2=5時，所對應的譯碼性能最差；a2越小，復雜度越低。因此，認為a2=10是最好的選擇，因為其在譯碼性能幾乎不變的情況下，訪問節點數大大減少。

圖10 a1=10時誤碼率仿真

圖11 a1=10時訪問節點仿真

表3 BLER=10-4的信噪比增益

表4 在訪問過的節點數為5 000處的信噪比增益

3.2.3 性能與復雜度權衡后的仿真結果

設置參數a1=15、a2=10。現在找到最優閥值a1和a2，使之能夠很好地適應信噪比的增長。從表3可以看出a1=15、a2=10下的SCL譯碼相比于原SCL譯碼的誤碼率的損失。權衡性能與復雜度，如圖12、圖13所示的帶圓圈的線段是a1和a2最佳選擇的仿真結果。它對應的性能非常接近于原SCL譯碼的性能，且訪問過的節點數量隨著信噪比的增大明顯減少。此外，電腦中此參數下的SCL譯碼算法譯出一個塊的碼字的時間為0.001 4 s，原SCL的譯碼速度為0.026 s，幾乎是SCL譯碼的20倍。

圖12 a1=15、a2=10時誤碼率仿真

圖13 a1=15、a2=10時訪問節點仿真

如果SCL譯碼中存在一個工作點，如要求SCL譯碼算法將會在2.5 dB≤SNR≤3.5 dB工作，在這個范圍中，SCL譯碼的甚至已經接近至SC算法的復雜度，且其誤碼率也可以保持和原算法相同。

4 結 語

本文基于對數似然比LLR和路徑度量值，提出了一種譯碼復雜度可以隨著信噪比增加而降低的改進的SCL算法。通過對算法的仿真分析，提出了最優化后的a1、a2值以及其工作點。改進后的算法可以適應信噪比的變化，且在信噪比高的情況下有較低的復雜度，使改進算法比原SCL算法在保證誤碼率的前提下，在算法復雜度上優勢明顯。