王 玲，張治中，鄧炳光

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

0 引 言

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

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

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

1 背景算法介紹

1.1 SC譯碼算法

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

(1)

(2)

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

(3)

(4)

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

(5)

1.2 SCL譯碼算法

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

(6)

(7)

(8)

1.3 SSCL譯碼算法

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

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

(9)

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

(10)

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

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

(11)

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

(12)

(13)

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

(14)

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

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

t=min(L-1,Nv)，

(15)

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

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

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

下面給出上述改進(jìn)算法的理論分析證明。

(16)

(17)

該節(jié)點(diǎn)譯碼結(jié)束，后續(xù)比特?zé)o需翻轉(zhuǎn),因?yàn)橐欢ù嬖?/p>

(18)

對于任意路徑l，有

(19)

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

圖2 路徑選擇策略

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

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

在有序路徑集合中，排名靠后的路徑被保留的幾率很小，因?yàn)樗鼈兊腜M較大。此外，對于一個(gè)可靠性好的信道，所有的路徑幾乎不可能分裂，因?yàn)橄嗉拥腖LR絕對值很大。因此，該算法可以通過嚴(yán)格的約束有效減少譯碼時(shí)間步數(shù)，從而降低譯碼延遲。算法偽代碼如下：

input：當(dāng)前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 實(shí)驗(yàn)結(jié)果與性能分析

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

3.1 糾錯(cuò)性能比較

誤塊率是評價(jià)譯碼結(jié)果是否正確的重要參數(shù)。本節(jié)通過對不同譯碼算法進(jìn)行仿真實(shí)驗(yàn)，得出各算法的譯碼糾錯(cuò)性能。仿真中采用二進(jìn)制加性高斯白噪聲(Additive White Gaussian Noise,AWGN)，調(diào)制方式為二進(jìn)制相移鍵控(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給出了文獻(xiàn)[20]提出的Fast-SCL算法和自適應(yīng)路徑選擇算法在不同列表長度L下的BLER曲線，圖6給出了文獻(xiàn)[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值減少，其糾錯(cuò)性能更好。簡化后的SSCL譯碼算法與SSCL譯碼算法糾錯(cuò)性能一致，相對傳統(tǒng)的SCL譯碼算法也幾乎沒有任何糾錯(cuò)性能的損失。因?yàn)槲闹械淖赃m應(yīng)快速譯碼算法基于最新的SSCL譯碼算法，僅改變了PM值的選擇方式，仿真結(jié)果符合理論分析。同時(shí)，該算法與基于經(jīng)驗(yàn)性的Fast-SCL算法相比，在信噪比較高的情況下，前者糾錯(cuò)性能更高；隨著L增加，兩者糾錯(cuò)性能差距更大。Fast-SCL譯碼算法在譯碼R1碼時(shí)，僅考慮兩比特翻轉(zhuǎn)，隨著L的增加或碼長變長，糾錯(cuò)性能顯著下降，仿真結(jié)果與實(shí)際分析結(jié)果相吻合。文獻(xiàn)[14]給出了基于搜索集和決策函數(shù)的FSCL譯碼算法與傳統(tǒng)SCL譯碼算法糾錯(cuò)性能基本一致的仿真結(jié)果，本文中仿真得出自適應(yīng)SSCL算法與文獻(xiàn)[14]中兩種算法的譯碼糾錯(cuò)性能幾乎一致，仿真結(jié)果與實(shí)際分析結(jié)果相吻合。

3.2 復(fù)雜度比較

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

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

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

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

4 結(jié)束語

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