基于SCL譯碼復(fù)雜度的改進(jìn)算法設(shè)計(jì)*

李怡超，葛萬成

（同濟(jì)大學(xué) 中德學(xué)院，上海 200092）

0 引 言

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

1 連續(xù)刪除列表譯碼算法

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

圖1 SCL算法

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

即該路徑所對應(yīng)的譯碼序列的概率，實(shí)現(xiàn)時往往采用對數(shù)形式。所以，路徑度量值可以隨著譯碼過程遞歸更新為：

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

對于一個BiAWGN信道，輸出yi對應(yīng)的信道對數(shù)似然比LLR可以被表示為：

2 基于SCL譯碼復(fù)雜度的改進(jìn)算法設(shè)計(jì)

2.1 基于LLR的方案設(shè)計(jì)

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

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

2.2 基于PM的方案設(shè)計(jì)

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

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

同樣，在這里討論a2=0與a2=∞兩種特例。當(dāng)a2=0時，需要刪除除了最大路徑度量值的路徑以外的所有路徑，實(shí)際上就是SC譯碼算法，對應(yīng)于完全沒有噪聲的信道傳輸。但是，當(dāng)a2=∞時，不能刪除任何路徑，實(shí)際上等同于原有的SCL譯碼算法。因此，此設(shè)計(jì)方案中能夠使復(fù)雜度隨著信噪比的增大而降低。需要說明的是，未知參數(shù)a2的值的確定很重要，因?yàn)樗鼘绊慡CL譯碼的性能。

3 仿真與分析

3.1 設(shè)計(jì)方案的仿真目標(biāo)

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

例如，假設(shè)待譯碼序列中有3個比特，且它們?nèi)俏垂潭ū忍?，列表大小為L=4。所以，當(dāng)a1=∞、a2=∞時，需要像圖2一樣擴(kuò)展所有的路徑，然后在這8條路徑中選擇L條最好的路徑。很明顯，訪問過的節(jié)點(diǎn)的個數(shù)為14。但是，當(dāng)a1=0、a2=0時，對每一個比特都進(jìn)行了硬判決，如圖3所示。最后，只有一條路徑對應(yīng)的碼字為譯碼序列，假設(shè)為011。這種情況下只有3個訪問過的節(jié)點(diǎn)，所以它的復(fù)雜度比上一張圖的復(fù)雜度要低。

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

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

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

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

圖4 誤碼率對比

圖5 訪問節(jié)點(diǎn)數(shù)對比

3.2 數(shù)值結(jié)果分析

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

圖6 不同參數(shù)設(shè)置的誤碼率對比

圖7 不同參數(shù)設(shè)置的訪問節(jié)點(diǎn)數(shù)對比

3.2.1 a2=15的仿真結(jié)果

首先，假設(shè)a2=15不變，在此基礎(chǔ)上為a1選擇一些變量來仿真，結(jié)果如圖8、圖9所示。其次，根據(jù)仿真結(jié)果畫出在BLER=10-4處使用不同的a1的編碼和原SC譯碼相比的信噪比增益，如表1所示?？梢姡挥挟?dāng)a1=5、a2=15時的性能比原SCL譯碼的性能差的比較明顯。從表2中可以看出，a1越小，訪問過的節(jié)點(diǎn)數(shù)量減少的程度越高。所以，a1越大，該譯碼的性能越好，同時需要訪問的節(jié)點(diǎn)數(shù)越多。在通過權(quán)衡復(fù)雜度后，發(fā)現(xiàn)a1=15時，其性能與原譯碼規(guī)則基本相同，且大大減少了訪問節(jié)點(diǎn)的數(shù)量。

圖8 a2=15時誤碼率仿真

圖9 a2=15時訪問節(jié)點(diǎn)仿真

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

表2 在訪問過的節(jié)點(diǎn)數(shù)為5 000處的信噪比增益

3.2.2 a1=10的仿真結(jié)果

在此仿真中假設(shè)a1=15，然后為a2挑選一些變量進(jìn)行仿真，結(jié)果如圖10、圖11所示。觀察仿真結(jié)果，在不同a2下的譯碼對比SCL譯碼在BLER=10-4處的噪聲比增益和在訪問過的節(jié)點(diǎn)為5 000的信噪比增益，如表3、表4所示。可以直觀看到，當(dāng)a1=10、a2=5時，所對應(yīng)的譯碼性能最差；a2越小，復(fù)雜度越低。因此，認(rèn)為a2=10是最好的選擇，因?yàn)槠湓谧g碼性能幾乎不變的情況下，訪問節(jié)點(diǎn)數(shù)大大減少。

圖10 a1=10時誤碼率仿真

圖11 a1=10時訪問節(jié)點(diǎn)仿真

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

表4 在訪問過的節(jié)點(diǎn)數(shù)為5 000處的信噪比增益

3.2.3 性能與復(fù)雜度權(quán)衡后的仿真結(jié)果

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

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

圖13 a1=15、a2=10時訪問節(jié)點(diǎn)仿真

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

4 結(jié) 語

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