基于校正搜索寬度的極化碼譯碼算法研究

盧麗金, 鄭鑫, 張曉潔，李家海，廖東鳳

（廣西民族師范學院數理與電子信息工程學院，崇左 532200）

0 引言

極化碼（polar code）是目前僅有的一種在數學上被嚴格證明且能實現香農信道容量的信道編碼方式［1］。Turbo碼作為信道編碼方案中的一種，被應用于第三代移動通信系統(tǒng)和第四代移動通信系統(tǒng)。隨著無線通信的發(fā)展，5G 具有超大容量、超大連接性及零時延的特點，因此需要更好的編碼方案。而極化碼具有能夠達到信道容量、可靠性強、超低時延等特點，是5G 技術急需的編碼方案。

為不斷提高性能和降低復雜度，各種各樣的譯碼相繼被提出?；谔岣邩O化碼性能的想法,提出置信度傳播［2-3］和線性規(guī)劃［4］算法。然而, 上述兩種算法僅適合應用于二進制輸入刪除信道（BEC）。針對此情況，串行抵消列表（SCL）譯碼被提出［5-6］，突出搜索寬度（L）的概念，提高譯碼性能。隨后，CRC 輔助的串行抵消列表（CASCL）譯碼被提出［7-10］，利用循環(huán)冗余校驗碼來輔助譯碼，降低譯碼復雜度同時進一步提高譯碼性能。為了深入改進SCL 譯碼，自適應的串行抵消列表（AD-SCL）譯碼被提出［11］，與CA-SCL 譯碼相比，顯著降低了平均譯碼復雜度。

AD-SCL 譯碼在保證性能不變的前提下，出現了明顯的時延問題。從AD-SCL 譯碼思路這個角度來分析，可以得出結論：給定一個最大的L值（Lmax）并設置L的初始值為1，從L=1 開始執(zhí)行譯碼；隨后，對得到的L條譯碼候選路徑進行循環(huán)冗余校驗，當通過校驗時退出譯碼，反之，將原來的搜索寬度更新為2 倍搜索寬度，同時退回到root節(jié)點繼續(xù)執(zhí)行譯碼，直到L=Lmax。在這一整個過程中，一方面，AD-SCL 總是把L的初始值設置為1；另一方面，一旦譯碼候選路徑不能通過CRC 校驗，L會不斷地更新為2L并返回到根節(jié)點繼續(xù)進行譯碼。綜合考慮這兩方面的影響，將會引起非常高的時延。L=1 時， AD-SCL 譯碼算法相當于串行抵消（SC）譯碼算法。誤碼率相當高，譯碼性能亦不理想。針對上述存在的時延問題，假設改變L的初始值總是設置為1 的思路，并且減少執(zhí)行SCL 譯碼的次數，那么，將能夠顯著降低時延。因此，將搜索寬度作為切入點，調整、校正搜索寬度成為研究的關鍵。

本文提出了一種基于校正搜索寬度的極化碼譯碼算法。該算法采用跟蹤歷史數據、采集歷史數據以及對符合條件的歷史數據進行數學運算的方法，不斷調整、校正搜索寬度，降低執(zhí)行串行抵消列表譯碼的次數，進而降低極化碼解碼時延，提高解碼效率。實驗結果表明在保持性能不變的前提下，該算法能明顯降低解碼代價和時延。

1 基礎原理

1.1 譯碼

SC 譯碼的缺點是復雜度低，優(yōu)點是譯碼結構簡單。當碼長N足夠大時，理論上SC譯碼一直被證明能夠達到Shannon 容量；反之，其糾錯性能常常是不理想的。針對這個問題，提出了SCL 譯碼。它是SC譯碼算法升級版中的一種，能用相對低的復雜度來獲取最大似然譯碼性能。

一般地，SCL 譯碼算法的思想以碼樹的形式來呈現。圖1 為SCL 譯碼的碼樹形式。以圖1 為例，一棵深度為4 的滿二叉樹，看成是碼長為4的Polar碼。除葉子節(jié)點外，每一層邊都分別標記一個1或0，其中1表示信息比特，0為固定比特。以root 節(jié)點為出發(fā)點，任一葉子節(jié)點為終點，長度為N的路徑形成一條譯碼序列（包含固定比特）。

圖1 SCL譯碼的碼樹形式

以L=4，N=4為例，簡單介紹SCL譯碼算法的譯碼過程，具體如圖2所示。

結合圖2，將SCL 譯碼算法的譯碼過程歸納為：

圖2 SCL譯碼的具體過程

（1）與SC 譯碼算法類似，從根節(jié)點開始，逐層進行路徑搜索。

（2）當經過第一層邊的擴展時，存在兩條候選路徑（如圖2（i）），由于L=4，所以把這兩條候選路徑都保留下來。

（3）當進行第二層邊的路徑擴展時，產生四條譯碼候選路徑（如圖2（ii）），由于L=4，所以把這四條候選路徑都保留下來。

（4）當經過第三層邊的擴展時，存在八條候選路徑（如圖2（iii）），因L=4，所以只需要保存最有可能的四條譯碼候選路徑，同時舍棄掉其余四條候選路徑（如圖2（iv））。

（5）當經過第四層邊的擴展時，存在八條候選路徑（如圖2（v）），因L=4，所以只需要保存最有可能的四條譯碼候選路徑，同時舍棄掉其余四條候選路徑（如圖2（vi））。

（6）最后，從保留的四條候選路徑里，選出一條具有最大度量值的候選路徑，作為譯碼結果輸出。

1.2 基本公式

談及SCL 譯碼算法時，對數似然比（LLR）和路徑度量值的計算必不可少［12-13］。

那么，LLR的表達式如下：

其中,xi為輸入信號。yi是接收信號。相應地，LLR的遞歸計算方法如下：

經過變換，采用以下公式遞歸地計算，可以得到路徑度量值：

2 基于校正搜索寬度的極化碼譯碼算法

因極化碼能夠達到信道容量，故其編譯碼技術都受到了廣泛關注。隨著移動通信系統(tǒng)的快速發(fā)展，SC、SCL、CA-SCL、AD-SCL 等譯碼方法隨之出現。在保證性能不受影響的前提下，實現平均譯碼復雜度能夠大幅度降低的愿景，ADSCL 總會將搜索寬度的初始值配置為1。當L=1 譯碼失敗時，該算法會將L=1 直接更新為L=2，退回到根節(jié)點，重復前一輪的譯碼操作。若L=2時，譯碼還不成功，則會將L=2 更新為L=4，繼續(xù)進行譯碼。一般地，在AD-SCL 的譯碼過程中，產生幾個不同的搜索寬度值是正?，F象。假設將搜索寬度的初始值設置成1 時，這時的AD-SCL 譯碼相當于SC 譯碼。由于SC 譯碼是逐比特譯碼，故一旦有一個比特判決有誤，那么在之后的譯碼過程中都將處于錯誤的子樹中執(zhí)行譯碼。綜合討論，SC 譯碼固然能實現平均譯碼復雜度顯著降低的愿景，但卻失去性能方面的優(yōu)越性。經過基于L=1的譯碼后，往往還需要更新L值。這樣無疑增加了時延。當譯碼需要更新搜索寬度時，一定程度來說不止更新一次。如當Lmax= 32 時，至多會更新5次左右。換個角度來理解，當Lmax= 32時要進行6 次SCL 譯碼算法。因此，更新次數多是存在高時延的原因之一。因此，如何解決高時延問題成為本文研究內容。而調整、校正搜索寬度是解決高時延的重要切入點。

2.1 確定搜索寬度的理想初始值

本文提出一種能減小時延、降低復雜度的SCL 譯碼算法。新算法與傳統(tǒng)算法的主要區(qū)別在兩方面。第一方面，L的初始值的大小不固定成1；第二方面，當搜索寬度設置為初始值時，譯碼失敗后并不會放棄譯碼或者直接更新為2 倍搜索寬度。為更好地理解，將搜索寬度進行初始化時的值標記為Li。同樣地，對搜索寬度執(zhí)行初始化操作在新算法里也是需要的，不一樣的是Li不總是等于1，Li的大小會視具體情況進行變化。信道質量不同，成功譯碼時所對應的L 值也會有所不同。假設能在理想的Li下譯碼，那么，譯碼的成功率也將會與之俱增。此時，既能夠保證譯碼性能，同時又能降低譯碼時延，是一種理想的搜索寬度。為此，將這一理想的Li稱為搜索寬度的理想初始值，并記為Loi。因此，想要降低時延需調整、校正搜索寬度，確定搜索寬度的理想初始值。

雖然顯著地提高譯碼性能和極大地降低譯碼復雜度很難同時兼得，但是，通過不斷調整、校正搜索寬度，獲取搜索寬度的理想初始值Loi，能使性能和復雜度最大可能實現雙贏。本文提出的Loi通過跟蹤歷史數據、采集歷史數據以及對合格歷史數據進行數學運算的方法來確定。下面首先對上述所提歷史數據作一下說明；其次，闡述Loi的具體確定方法。為易于理解，文中給定Lmax= 32。

對于一次實驗來說，若將總幀數記為TN，則本實驗給定的總幀數為TN= 100000。將Loi、譯碼成功時的搜索寬度值（Ls）等數據記錄下來，完成對歷史數據的跟蹤與歷史數據的采集。第q幀對應的Ls用Ls[q]來表示，1 ≤q≤TN。因此，本文所謂的歷史數據指的是被記錄下來的數據，包括Loi，Ls等。同時，將第q幀對應的Loi用Loi[q]來標記。

通過五個階段來確定搜索寬度的理想初始值Loi。將TN均勻地分為五組，每一組幀對應著一次實驗中的一個階段。五個階段的劃分情況如下所示:

首先分析第一階段。第1 幀、第2 幀和第20000 幀尤為關鍵。注意，對于第1 幀，需要令L=Loi= 1。一般地，譯碼有成功和失敗兩種情況，無論是譯碼成功還是譯碼失敗，均需將Ls[1]記錄下來。注意，本文規(guī)定Ls[q]= 0 代表譯碼失敗。當譯碼運行到第2 幀時（q= 2），前1 幀譯碼成功時，對Loi[q- 1]作一個判斷，若Loi[q- 1]=1， 則 令Loi[q]= 1； 若 1

若前一幀譯碼失敗時，當前的理想初始值為：

同樣地，需要將Ls[q]記錄下來。類似地，第3～19999 幀的操作，如同第2 幀。在第20000 幀，對于初始值的設置與記錄工作，它們的操作與第2～19999 幀相同。不同之處在于，在第20000 幀中加入校正搜索寬度（CSW）公式，該公式為：

其中，Loi= 20,21,…,24，PLs表示當L=Loi時譯碼成功的概率。校正搜索寬度的用意在于校正執(zhí)行完一次譯碼對應的的搜索寬度。通過記錄得到20000 個Ls，分別計算PLs=1，PLs=2，PLs=4，PLs=8，PLs=16。假設統(tǒng)計出Ls= 1，Ls= 2，Ls= 4，Ls= 8，Ls= 16的個數分別為an,bn,cn,dn,en,則它們對應的概率分別計算為：。并將Loi與PLs代入校

正搜索寬度的校正公式中，則有：

將CSW1，CSW2，CSW4，CSW8，CSW16作 一下對比，選出一個最小值。選出的CSWLoi的最小值所對應的Loi記為Lc,并作為下一幀的Loi，即Loi[q+ 1]=Lc。至此，完成第一階段的Loi的確定。 基于第一階段的分析， 可得到Loi[20001] =Lc。第20002～39999 幀的操作如同第一階段中的第二幀一樣。第40000 幀的操作如同第20000 幀的操作一樣。因此，在第三、四、五階段中，涉及的操作都如同第二階段的操作一樣。顯而易見，Loi的確定已全部完成。注意，這TN幀里，每一幀都對應著一個Loi。通過歷史數據來確定Loi，實質上就是根據信道的實際情況來確定的。結合信道實際情況，Loi的確定可以達到最理想化，最終實現性能與復雜度的最佳平衡。為便于理解搜索寬度理想初始值的確定過程，繪制了一個過程框圖。

圖3 繪制出第一階段和第二階段的理想初始值的確定過程框圖。那么，在第三、四、五階段中，涉及的操作都如同第二階段的操作一樣。

圖3 理想初始值的確定過程

2.2 基于校正搜索寬度的SCL譯碼算法

在保證譯碼性能不受影響的前提下，進一步降低極化碼譯碼時延，本文提出基于校正搜索寬度的SCL（CS-SCL）譯碼算法。該算法亦可稱為兩步走算法。前面的文章內容已經介紹如何確定搜索寬度的理想初始值Loi。那么，兩步走方案可以大致理解為，首先是執(zhí)行基于L=Loi的譯碼；若譯碼失敗，會將L=Loi更新為L=Lmax，并執(zhí)行基于L=Lmax的譯碼。換句話理解，本課題的算法最多只需要進行2 次串行抵消列表譯碼方案，進而實現顯著減少時延的的愿景。

本文提出的CS-SCL 譯碼算法的詳細步驟如下所示：

（1）初始化：令L=Loi。

（2）計算度量值與路徑擴展：執(zhí)行SCL 譯碼算法，同時CRC校驗。

（3）譯碼路徑判決：若通過CRC 校驗的候選路徑數大于等于1 時，則輸出具有最大度量值的一條路徑，同時退出譯碼；否則，跳到（4）。

（4）更新判決：判斷搜索寬度L是否等于Lmax，若L不等于Lmax，則把L=Loi更新為L=Lmax，并跳回（2）；否則，退出譯碼。

為幫助梳理思路, 基于校正搜索寬度的極化碼譯碼算法的流程如圖4。

圖4 CS-SCL譯碼算法流程

3 仿真結果與分析

通過分析仿真結果，對CS-SCL 譯碼、SC 譯碼、CA-SCL 譯碼、AD-SCL 譯碼進行性能和復雜度對比。本文擬用文獻［14］中的構造方案來對極化碼進行構造。在本次仿真試驗里，幾種譯碼方案將會接收到一樣的的碼字。譯碼的性能和譯碼的復雜度被用來衡量與驗證CS-SCL 譯碼算法，那么，誤塊率（BLER）、誤比特率（BER）以及平均復雜度是衡量與驗證算法必不可少的幾個評估指標。下面將通過這三個評估指標來對實驗得到的仿真數據進行綜合分析、總結歸納譯碼優(yōu)劣。

如圖5，將幾種譯碼算法的碼長配置為N=1024，碼率均為R= 0.5，且列表譯碼的搜索寬度分別設置成L= 4 與L= 32。在不同列表大小下，對各條BER 曲線進行對比發(fā)現，CS-SCL 譯碼與CA-SCL 譯碼、AD-SCL 譯碼幾乎是重疊在一起的。總結可知， CS-SCL 譯碼方案在上述配置下也能像CA-SCL譯碼、AD-SCL譯碼一樣獲得非常逼近ML譯碼的性能。

圖5 CS-SCL譯碼與其他譯碼方案的BER對比

與BER 曲線類似，在不同列表大小下，對各條BLER 曲線進行對比發(fā)現，CS-SCL 譯碼與CASCL 譯碼、AD-SCL 譯碼幾乎是重疊在一起的，如圖6。詳細地，當L=4 時，CA-SCL、AD-SCL與CS-SCL 的BLER 曲線是重疊的；當L=32 時，CS-SCL、CA-SCL與AD-SCL的BLER曲線也是重疊在一起的。這一重疊現象進一步闡明了CSSCL 譯碼方案能夠獲得與CA-SCL、AD-SCL 譯碼方案幾乎一致的譯碼性能。

圖6 CS-SCL譯碼與其他譯碼方案的BLER對比

如圖7，將幾種譯碼算法的碼長配置為N=1024，碼率均為R= 0.5，且列表譯碼的搜索寬度被配置為L= 32。當SNR 越來越大時，CSSCL 譯碼的平均復雜度曲線幾乎與SC 譯碼的平均復雜度曲線相互重疊。經過對比可知，CSSCL 譯碼可以明顯地減小平均復雜度，尤其在高信噪比下，CS-SCL 譯碼非常逼近SC 譯碼。通過測量平均計算復雜度來評估譯碼復雜度，相當于需要測量路徑度量遞歸操作的次數。當SNR 的范圍為0～1.0 dB 時，CS-SCL 譯碼比AD-SCL 譯碼能更大幅度減小平均復雜度。當SNR=0 dB 時，CS-SCL 譯碼的復雜度可以降低約57.8%；當SNR=1.0 dB 時，CS-SCL 譯碼的復雜度可以降低約13.8%。綜上所述，在低SNR 下，CS-SCL 譯碼能夠在保證譯碼性能不受影響的前提下顯著地降低平均復雜度。在低SNR 下，CS-SCL 譯碼能夠非常接近ML 譯碼性能，同時能極大地降低譯碼時延。

圖7 CS-SCL譯碼與其他譯碼的平均復雜度對比

4 結語

仿真實驗涉及到的譯碼包括：SC、CA-SCL、AD-SCL、CS-SCL 譯碼算法。實驗數據表明，一方面在不同列表大小下，CS-SCL、CA-SCL、AD-SCL 譯碼擁有幾乎相同的BER 與BLER 性能，且可以非常接近ML 譯碼性能。另一方面，當SNR=0dB 時，CS-SCL 譯碼的復雜度可以降低約57.8%；當SNR=1.0 dB 時，CS-SCL 譯碼的復雜度可以降低約13.8%。在低SNR 下，CS-SCL 譯碼能大幅度降低譯碼時延。