一種自適應(yīng)快速SSCL極化碼譯碼算法*

王 玲，張治中，鄧炳光

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

Arikan[1]首次提出極化碼(Polar Code)，該碼是人類已知的第一種能夠被嚴格證明達到信道容量的信道編碼方法；同時，他提出的連續(xù)消除(Successive Cancellation,SC)譯碼算法是第一個在Polar碼中碼長接近無窮時能實現(xiàn)信道容量的譯碼算法。然而，對于中等碼長或短碼長的編碼，SC譯碼算法的糾錯性能較差。

SC列表(Successive Cancellation List,SCL)譯碼通過從解碼器生成的候選列表中選擇碼字解決了Polar碼有限碼長的譯碼問題[2]。文獻[3-4]實現(xiàn)了多種組成節(jié)點的快速并行譯碼，包括R1(Rate-1)節(jié)點、R0(Rate-0)節(jié)點以及Rep(Repetition)節(jié)點等特殊節(jié)點，命名為簡化連續(xù)消除(Simplified Successive Cancellation,SSC)譯碼算法以及簡化SCL(Simplified Successive Cancellation List,SSCL)譯碼算法。文獻[5]給出了SSCL譯碼路徑分裂的精確邊界，進一步減少了時間步數(shù)。研究發(fā)現(xiàn)，在循環(huán)冗余校驗(Cyclic Redundancy Check,CRC)碼的輔助下極性碼的糾錯性能優(yōu)于目前最先進的低密度校驗(Low Density Parity Check,LDPC)碼和Turbo碼[6-7]。盡管文獻[8-14]提出的算法都一定程度改善了Polar譯碼性能，降低了時間復(fù)雜度，但隨著5G商用的到來，國際移動通信標準化組織3GPP確定Polar碼作為5G增強移動寬帶(Enhanced Mobile Broadband,eMBB)場景的控制信道編碼方案，其傳統(tǒng)譯碼算法效率也很難達到5G高速率、低時延應(yīng)用場景的需求。基于文獻[15-20]Polar譯碼算法的研究可知，在能夠保證滿足一定譯碼糾錯性能的前提下，5G eMBB控制信道場景亟待更優(yōu)快速的譯碼算法。

本文在SSCL譯碼算法基礎(chǔ)上提出基于路徑度量(Path Metric,PM)的自適應(yīng)SSCL譯碼算法，在不增加任何信道先驗信息計算的前提下有效消除了譯碼過程的冗余計算，進一步提高了譯碼效率。

1 背景算法介紹

1.1 SC譯碼算法

圖1 SC譯碼算法的二叉樹表示規(guī)律

(1)

(2)

在硬件友好型計算中[18]，公式(1)可修改為

(3)

(4)

式中：⊕表示異或運算。在葉節(jié)點，根據(jù)下式判別譯碼輸出[1]：

(5)

1.2 SCL譯碼算法

SCL譯碼算法提高了Polar譯碼在中短碼長情況下的糾錯性能，在SC譯碼算法的基礎(chǔ)上增加每一層路徑搜索后允許保留的候選路徑數(shù)量，最大允許路徑數(shù)為L。L越大，SCL譯碼性能越接近于最大似然譯碼，并且通過CRC校驗輔助，SCL算法的性能得到了很大的提升。在SCL譯碼過程中，存在L條路徑同時進行譯碼搜索，對于任意一條路徑l∈{1,2,…,L}以及任意發(fā)送比特ui，i∈{1,2,…,N}，其對應(yīng)的路徑度量值定義如下[19]：

(6)

(7)

(8)

1.3 SSCL譯碼算法

SSCL譯碼算法對一些特定的碼字提供了有效的譯碼方法，不再需要遍歷完整個譯碼樹，提高了譯碼效率。文獻[5]提出了R0碼(只含凍結(jié)比特)、R1碼(只含信息比特)、Rep碼(最后一位為信息比特，其余為凍結(jié)比特)的簡化譯碼，文獻[15]提出了SPC(Single Parity-Check)碼(第一位為凍結(jié)比特，其余為信息比特)的簡化譯碼。

對于R0極化碼節(jié)點，其PM表示為[5]

(9)

對于R1極化碼節(jié)點，其PM表示為[5]

(10)

式中：ηil表示節(jié)點信息比特的硬判決值。

對于Rep碼節(jié)點，其PM表示為[5]

(11)

對于SPC節(jié)點，初始化PM表示為[5]

(12)

(13)

式中：αilmin為SPC節(jié)點中最不可靠位的LLR值。在完成最不可靠位譯碼之后，其余比特的PM更新表示為[5]

(14)

2 自適應(yīng)SSCL譯碼算法

對于傳統(tǒng)的SCL譯碼算法以及SSCL譯碼算法從2L條候選路徑中篩選出L條保留路徑，路徑選擇復(fù)雜，時間消耗大。為此，本文提出了一種簡化的自適應(yīng)路徑選擇算法，在不需要任何先驗信息、相較SCL譯碼沒有任何糾錯性能損失的前提下，有效降低譯碼算法的排序復(fù)雜度，減少譯碼所需時間步數(shù)。文獻[5]給出了與SCL譯碼性能相同的情況下SSCL譯碼路徑分裂的精確邊界。長度為Nv的R1節(jié)點中比特翻轉(zhuǎn)次數(shù)t為[5]

t=min(L-1,Nv)，

(15)

將產(chǎn)生2t種譯碼結(jié)果。對于高可靠信道對應(yīng)的節(jié)點，大部分翻轉(zhuǎn)后子路徑的正確概率都很低，需要在性能損失很小的情況下刪除這些子路徑。在這種情況下，上述算法路徑分裂次數(shù)太多，排序復(fù)雜度太大。改進的自適應(yīng)譯碼算法假定當前存在L條路徑，其PM按照升序排列為PM1≤…≤PMl≤…≤PML，其每條子路徑都包含原路徑度量值PMl和比特翻轉(zhuǎn)后的路徑度量值PMl+|αl|。

(1)進行下一信息比特翻轉(zhuǎn)時，首先判斷PML-1′與PML的大小，大于PML的路徑直接刪除，小于PML時占位PML，然后比較排序，找到新的PML，再按l減小的方向依次判斷。這樣得出的L條路徑一定是具有最小PM的L條路徑。

(2)當進行到某一信息比特翻轉(zhuǎn)，其翻轉(zhuǎn)后的路徑如果都沒有入選前L條，則該節(jié)點譯碼結(jié)束。若此時R1碼滿足當前翻轉(zhuǎn)次數(shù)小于min(L-1,Nv)，其翻轉(zhuǎn)次數(shù)較文獻[6]減少。

下面給出上述改進算法的理論分析證明。

(16)

(17)

該節(jié)點譯碼結(jié)束，后續(xù)比特?zé)o需翻轉(zhuǎn),因為一定存在

(18)

對于任意路徑l，有

(19)

該算法有效降低了R1節(jié)點譯碼候選路徑排序復(fù)雜度，減少了比特翻轉(zhuǎn)次數(shù)，從而減少了譯碼時間步數(shù)。對于SSCL譯碼，特殊節(jié)點的路徑選擇復(fù)雜度很高，降低復(fù)雜度尤為重要。圖2給出了R1碼(L=4,Nv=4)第1次翻轉(zhuǎn)具體算法實現(xiàn)過程，其余比特翻轉(zhuǎn)PM比較選擇方法一致。

圖2 路徑選擇策略

圖3給出了R1碼(L=4,Nv=4)整個執(zhí)行過程及結(jié)果。該R1碼經(jīng)過3次圖2的比特翻轉(zhuǎn)操作，比文獻[6]提出的最小翻轉(zhuǎn)次數(shù)減少了1次，一共經(jīng)歷了13次比較判決。對于L=4、Nv=4的R1碼，該改進算法在最差情況下只需判決24次，而在傳統(tǒng)排序算法中，都需Ω(NlgN)次比較。該改進自適應(yīng)SSCL譯碼算法比特翻轉(zhuǎn)次數(shù)不是固定值，但一定小于或者等于文獻[6]提出的次數(shù)。同時，判決次數(shù)隨著PMmax逐漸減少，不符合路徑單次判決刪除的可能性較大。

圖3 R1碼路徑分裂規(guī)律(L=4,Nv=4)

在有序路徑集合中，排名靠后的路徑被保留的幾率很小，因為它們的PM較大。此外，對于一個可靠性好的信道，所有的路徑幾乎不可能分裂，因為相加的LLR絕對值很大。因此，該算法可以通過嚴格的約束有效減少譯碼時間步數(shù)，從而降低譯碼延遲。算法偽代碼如下：

input：當前L條路徑升序排序集合W

output:譯碼輸出L條PM最小的L條路徑集合W

1 begin

3 flag=TRUE;

4 for(inti=1;i≤min(L-1,Nv) && flag;i--) do

5 flag=FALSE;

6 for(intj=L-1;j≥1;j--) do

9 else

12 flag=TRUE;

13 end if

14 end for

16 end for

3 實驗結(jié)果與性能分析

為了衡量本文提出的自適應(yīng)SSCL譯碼算法的性能，下面將從譯碼器的糾錯性能和復(fù)雜度兩個方面進行分析。

3.1 糾錯性能比較

誤塊率是評價譯碼結(jié)果是否正確的重要參數(shù)。本節(jié)通過對不同譯碼算法進行仿真實驗，得出各算法的譯碼糾錯性能。仿真中采用二進制加性高斯白噪聲(Additive White Gaussian Noise,AWGN)，調(diào)制方式為二進制相移鍵控(Binary Phase Shift Keying,BPSK) 調(diào)制。其中，N=1 024，編碼速率R=1/2。圖4給出了傳統(tǒng)SCL算法、SSCL譯碼算法以及本文提出的自適應(yīng)路徑選擇譯碼算法在不同列表長度L下的誤塊率(Block Error Rate，BLER)曲線，圖5給出了文獻[20]提出的Fast-SCL算法和自適應(yīng)路徑選擇算法在不同列表長度L下的BLER曲線，圖6給出了文獻[14]提出的基于路徑分裂搜索集快速SCL(Path Splitting Selecting-Search Set Fast Successive Cancellation List,PSS-SS-FSCL)算法及基于路徑分裂決策函數(shù)快速SCL(Path Splitting Selecting-Decision Function Fast Successive Cancellation List,PSS-DS-FSCL)算法與自適應(yīng)路徑選擇算法在不同列表長度L下的BLER曲線。

圖4 傳統(tǒng)SCL、SSCL算法與自適應(yīng)SSCL算法的BLER性能比較

圖5 Fast_SCL與算法自適應(yīng)SSCL算法的BLER性能比較

圖6 PSS-SS-FSCL、PSS-DS-FSCL算法與自適應(yīng)SSCL算法的BLER性能比較

顯然，對于同一譯碼算法，隨著碼長L的增加，BLER值減少，其糾錯性能更好。簡化后的SSCL譯碼算法與SSCL譯碼算法糾錯性能一致，相對傳統(tǒng)的SCL譯碼算法也幾乎沒有任何糾錯性能的損失。因為文中的自適應(yīng)快速譯碼算法基于最新的SSCL譯碼算法，僅改變了PM值的選擇方式，仿真結(jié)果符合理論分析。同時，該算法與基于經(jīng)驗性的Fast-SCL算法相比，在信噪比較高的情況下，前者糾錯性能更高；隨著L增加，兩者糾錯性能差距更大。Fast-SCL譯碼算法在譯碼R1碼時，僅考慮兩比特翻轉(zhuǎn)，隨著L的增加或碼長變長，糾錯性能顯著下降，仿真結(jié)果與實際分析結(jié)果相吻合。文獻[14]給出了基于搜索集和決策函數(shù)的FSCL譯碼算法與傳統(tǒng)SCL譯碼算法糾錯性能基本一致的仿真結(jié)果，本文中仿真得出自適應(yīng)SSCL算法與文獻[14]中兩種算法的譯碼糾錯性能幾乎一致，仿真結(jié)果與實際分析結(jié)果相吻合。

3.2 復(fù)雜度比較

本文提出的自適應(yīng)譯碼算法可以有效降低譯碼算法的PM排序復(fù)雜度，減少譯碼時間步數(shù)，提高譯碼效率。在實際譯碼過程中，依賴碼字本身的架構(gòu)。表1給出了N=1 024、Eb/N0=2 dB的極化碼在不同譯碼速率、不同L下，分別采用傳統(tǒng)SCL譯碼算法、SSCL譯碼算法、文獻[5]提出的Fast-SSCL譯碼算法、文獻[14]提出的PSS-SS-FSCL算法和PSS-DS-FSCL算法以及本文提出的自適應(yīng)路徑選擇譯碼算法所需的時間步數(shù)。

表1 不同譯碼算法所需時間步數(shù)(N=1 024，Eb/N0=2 dB)

從表1可以看出，傳統(tǒng)的SCL譯碼及SSCL譯碼算法所需時間步數(shù)與碼率有關(guān)，與列表長度L無關(guān)。文獻[5]提出的Fast-SSCL算法所需時間步數(shù)與列表長度L和特殊節(jié)點比特個數(shù)有關(guān)。對于本文提出的自適應(yīng)路徑選擇譯碼算法，其所需時間步數(shù)收縮了文獻[6]的邊界，但不同碼字所需時間步數(shù)波動較大，受到碼字結(jié)構(gòu)影響大。同時，相對文獻[14]提出的PSS-DS-FSCL算法，本文提出的自適應(yīng)算法所需時間步數(shù)明顯減少，而相對文獻[14]提出的PSS-SS-FSCL算法，盡管在L較大時其所需時間步數(shù)差別較小，但是考慮到文獻[14]提出算法都是基于算法前期設(shè)置搜索集及決策函數(shù)，一定程度上增大了算法復(fù)雜度，所以本文提出的自適應(yīng)SSCL算法更優(yōu)。綜合圖5可知，在信噪比高的場景下，隨著PMmax不斷變小，排名靠后的路徑幾乎不會保留，單次比較可直接刪除子路徑，降低排序比較復(fù)雜度，減少譯碼步數(shù)，從而提高譯碼效率。

本文提出的自適應(yīng)SSCL譯碼算法，主要改善了譯碼復(fù)雜度，旨在不降低誤碼性能的前提下，提升其譯碼的效率，降低譯碼時間，能更好地應(yīng)對5G高可靠性、低延遲的海量數(shù)據(jù)交互場景下的控制信道譯碼。5G時代的一些終端模擬器、路測儀表儀器等，對用戶資源的靈活支持及時間顆粒的進一步縮短。物理下行控制信道承載下行控制信息是5G系統(tǒng)的調(diào)度核心。Polar譯碼作為PDCCH接收盲檢處理中的重要一環(huán)，檢測算法的復(fù)雜度高低及性能優(yōu)劣直接影響著整個5G儀器系統(tǒng)的效率。

4 結(jié)束語

本文提出的基于路徑選擇的自適應(yīng)SSCL譯碼算法，通過對碼樹路徑分裂后的路徑選擇過程進行去冗余化計算，降低了PM排序復(fù)雜度，有效減少了譯碼時間步數(shù)，在性能和時延方面都超過了現(xiàn)階段應(yīng)用最廣的SSCL譯碼算法和基于經(jīng)驗計算的Fast-SSCL譯碼算法。此外，它較基于先驗消息計算閾值的譯碼算法更加靈活，復(fù)雜度更低。Polar碼作為5G技術(shù)信道編碼技術(shù)之一，隨著5G 3D超高清視頻等大流量移動寬帶業(yè)務(wù)的發(fā)展，譯碼性能亟待優(yōu)化。本文譯碼算法性能盡管較主流譯碼算法得到了顯著提高，但是犧牲了信道利用率，因此如何提高信道利用率是未來工作的一個重點。