一種簡化的極化碼串行消除列表譯碼算法

李小文，李文彬

(重慶郵電大學(xué) 重慶市移動通信技術(shù)重點實驗室，重慶 400065)

0 引 言

極化碼(polar codes)是目前唯一被證明能夠達(dá)到信道容量的新型信道編碼，憑借較低的復(fù)雜度，3GPP在RAN1#87次會議上將其確定為5G增強(qiáng)移動寬帶場景下的信道編碼。極化碼的結(jié)構(gòu)可由P(N,K)表示，其中，N為碼字的長度；K為編碼中的信息比特數(shù)。由于極化碼具有二元線性分組碼的基本編碼要素，因此，編碼可通過生成矩陣乘法表示為x=uG?n，其中,u為原始比特序列；G?n為矩陣G的n次克羅內(nèi)克積，x={x0,…,xN-1}為編碼后的比特序列，即極化碼。在編碼過程中，選擇K個可靠信道發(fā)送信息比特，常用數(shù)字1表示；而剩下的比特信道發(fā)送凍結(jié)比特，常用數(shù)字0表示[1]。

最常見的極化碼譯碼方法為串行消除(successive cancellation, SC)譯碼,但僅適用于碼長較長的情況。隨后，最大似然(maximum-likelihood, ML)譯碼算法被提出，由于復(fù)雜性較高，以至于僅適用于極短碼長的極化碼。為了減小SC譯碼和ML譯碼糾錯性能之間的差距，Tal和Vardy提出使用串行消除列表(successive cancellation list, SCL)譯碼算法進(jìn)行極化碼譯碼，主要通過存儲更多條可能的譯碼路徑來確保譯碼糾錯性能；其次，陳凱等提出使用循環(huán)冗余校驗(cyclical redundancy check, CRC)碼與極化碼級聯(lián)，通過犧牲一定的碼率，在SCL譯碼結(jié)束后使用CRC校驗從而提升譯碼性能。結(jié)果顯示,在某些情況下其譯碼性能甚至與低密度奇偶校驗碼相當(dāng)，且隨著存儲路徑數(shù)目的增加其譯碼性能甚至接近于ML譯碼；隨后，Seyyed等提出使用碼樹來表示極化碼的譯碼過程，將其看作是從碼樹上根據(jù)相應(yīng)的路徑度量值進(jìn)行路徑選擇的過程。從碼樹上每層保留的路徑數(shù)目來看，SCL譯碼算法是寬度優(yōu)先譯碼算法，但其譯碼過程中存在著大量的冗余計算[2]。為減少SCL譯碼所需的時間步數(shù)，本文在Fast-SSC譯碼算法基礎(chǔ)上提出對SCL譯碼樹中特殊節(jié)點的簡化，用于識別和消除冗余計算。

特別地，在傳統(tǒng)SCL譯碼算法中對于特殊節(jié)點：Rate-1(信息比特)節(jié)點、Rate-0(凍結(jié)比特)節(jié)點和Rep(混合比特)節(jié)點其譯碼所需的時間步數(shù)分別為3Ns-2，2Ns-2和2Ns-1，其中，Ns=2s指碼長，s指譯碼樹中當(dāng)前階段的標(biāo)號，而簡化后的SCL譯碼算法所需的時間步數(shù)分別為min(L-1,Ns)，lbNs和lbNs+1，其中，L指搜索寬度，也稱存儲路徑數(shù)目。通過仿真和實驗結(jié)果分析，在保證糾錯性能的前提下，簡化后的SCL譯碼算法顯著降低了傳統(tǒng)SCL譯碼算法整個譯碼所需的時間步數(shù)。

1 SC譯碼和SCL譯碼

1.1 SC譯碼

在極化碼中，基于串行消除譯碼算法可以表示為二叉樹的遍歷。圖1a為P(8,4)的極化碼結(jié)構(gòu)圖，其中，凍結(jié)比特用灰色表示，信息比特用黑色表示。轉(zhuǎn)化為相應(yīng)的譯碼樹如圖1b，其中，白色節(jié)點對應(yīng)于凍結(jié)比特，黑色節(jié)點對應(yīng)于信息比特，灰色節(jié)點表示組合2個比特的級聯(lián)操作。SC譯碼算法從根節(jié)點開始，采用深度遍歷的方式對二叉樹進(jìn)行遍歷，從而譯碼。

圖1 極化碼的結(jié)構(gòu)圖和譯碼樹Fig.1 Polar codes structure diagram and decoding tree

各個節(jié)點的消息傳遞如圖1b，軟消息α包含從父節(jié)點傳遞給子節(jié)點的對數(shù)似然比值(log-likelihood ratio, LLR)，而從子節(jié)點傳給父節(jié)點的為硬判決消息值β，且第i位左邊軟消息αl和右邊軟消息αr的值通過如下公式計算

(1)

(2)

而第i位的硬判決消息值β通過(3)式計算，其中，⊕表示按位異或，i<2s-1用于區(qū)分左右子節(jié)點。

(3)

隨后，文獻(xiàn)[2]提出了快速簡化串行消除譯碼(fast simplified successive cancellation, Fast-SSC)，將其譯碼樹分為4種特殊節(jié)點進(jìn)行分別處理，避免遍歷整個譯碼樹，從而簡化了SC譯碼，如圖2。圖2中，白色圓圈是Rate-0節(jié)點，其葉子僅包含凍結(jié)比特；而黑色圓圈為Rate-1節(jié)點，其所有葉子均為信息比特；白色三角形表示Rep節(jié)點，只有最右邊的葉子節(jié)點是信息比特；正方形表示SPC節(jié)點，即除了最左邊的葉子節(jié)點都為信息比特。其中，所有的葉子節(jié)點為Rate-0或Rate-1節(jié)點，且SPC節(jié)點和Rep節(jié)點在s=1階段相同。

圖2 Fast-SSC譯碼樹Fig.2 Fast-SSC decoding tree

1.2 SCL譯碼

為了提高中等碼長的糾錯性能，文獻(xiàn)[3]提出了串行消除列表譯碼算法。在每層估計一個比特時，其可能值0和1都必須被考慮，所以在每次估計產(chǎn)生的2L個候選者中，都會有一半被舍棄，剩下的L個候選者被存儲，因此，SCL譯碼等價于對L個SC譯碼的并行搜索，其中，L為搜索寬度。因此，定義了選擇路徑的標(biāo)準(zhǔn)，即路徑度量值(path metrics, PM)。將它與每條路徑相關(guān)聯(lián)，并在每次估計時被更新，且PM值計算公式為

(4)

(5)

2 簡化的SCL譯碼

基于對譯碼樹節(jié)點分類的思想，在確保糾錯性能相同的情況下，分別對SCL譯碼樹的Rate-1節(jié)點、Rate-0節(jié)點和Rep節(jié)點做簡化處理，并對其路徑度量值PM重新計算，使得PM僅依賴于各自節(jié)點的譯碼樹頂部的LLR，從而避免對整個二叉樹遍歷。當(dāng)譯碼過程中遇到特殊節(jié)點時，用簡化的節(jié)點去代替原來譯碼樹的節(jié)點，從而減少了SCL譯碼所需的時間步數(shù)。

2.1 Rate-1節(jié)點

對于Rate-1節(jié)點簡化的思想來自文獻(xiàn)[5]中的List-SD譯碼，為了證明SCL譯碼列表大小和所需比特估計的最大數(shù)目相關(guān)，對SCL譯碼樹的Rate-1特殊節(jié)點提出一種新的假設(shè)。

在不影響任何糾錯性能的前提下，能夠以min(L-1,Ns)個時間步數(shù)譯碼長度為Ns=2s的Rate-1節(jié)點，并且在路徑l上Rate-1節(jié)點的路徑度量值為

(6)

以下通過2部分證明假設(shè)，首先證明路徑度量值的計算，再證明所需時間步數(shù)的假設(shè)。

2.1.1 采用歸納法證明路徑度量值的計算

對于Ns=2的譯碼樹，左右子節(jié)點的LLR如下，為避免混淆，暫時將路徑l的標(biāo)記先從(6)式中省略。

(7)

(8)

ln(1+e-η0α0)+ln(1+e-η1α1)

(9)

即(9)式等于(6)式。因此，(6)式的PM計算對于Ns=2的譯碼樹成立。

現(xiàn)假設(shè)(6)式PM的計算對于長度為2s-1的譯碼樹成立，則通過(2)—(4)式可得2個長度為2s-1的Rate-1節(jié)點的左、右PM為

(10)

(11)

對于譯碼樹中的s階段的任何節(jié)點來說，可將第i個比特和第i+2s-1個比特配對，并將其視為Ns=2的極化碼。因此，將(10)式和(11)式中的比特配對，并當(dāng)做長度為2的2s-1型的Rate-1節(jié)點的極化碼，通過(9)式表示2s-1型的總和為

(12)

(12)式等于(6)式，即(6)式其PM值的計算對于Ns=2s-1的譯碼樹成立，則對于Ns=2s也成立。因此，證得(6)式對于Rate-1節(jié)點路徑度量值的計算。

2.1.2 現(xiàn)通過反證法證明所需時間步數(shù)的假設(shè)

為證明提出的假設(shè)，不妨設(shè)PMi和對數(shù)似然比值αl有如下排序，即

PMi1≤PMi1+1,0≤l≤L-1

(13)

(14)

即在第i步時，第l+1處的PM大于等于第l處的PM；在路徑l上，第i+1處的LLR大于等于第i處的LLR。

因此，假設(shè)在第L-1處通過不同的判決值將路徑l分割成2條路徑，相應(yīng)的PM為

(15)

(16)

(17)

(18)

因此，(17)式可通過(18)式得

(19)

單獨分析第ω步的PM可得

PML-1vv

(20)

由于0≤ω≤L-2，因此，ω有L-1個值可以選擇，那么對于分割路徑l，(20)式的路徑p表示其比特序列的所有比特與對應(yīng)的LLR的硬判決一致，則至少有L個比特序列其PM比PML-1q值更小，所以L≤p。然而p

換句話說，當(dāng)L-1

因此，通過上述2部分證明了Rate-1節(jié)點路徑度量值的計算和時間步數(shù)的假設(shè)。

2.2 Rate-0與Rep節(jié)點

對Rate-0節(jié)點和Rep節(jié)點的簡化譯碼所需的時間步數(shù)分別為lbNs和lbNs+1，并且對于長度為Ns=2s的Rate-0節(jié)點和Rep節(jié)點的路徑度量可以分別計算為

(21)

(22)

(21)—(22)式中：αi為Rep節(jié)點的父節(jié)點傳來的LLR；η2s-1為Rep節(jié)點樹中信息比特的判決值的變形。其證明方法同Rate-1節(jié)點類似，不再累述。

3 性能仿真結(jié)果及分析

3.1 糾錯性能

由于碼率較大時存在的信息比特節(jié)點更多，編碼長度Ns更大，所以，為驗證簡化后的SCL譯碼算法的糾錯性能往往取min(L-1,Ns)?2，使得搜索寬度L和碼長的取值也較大。因此，根據(jù)3GPP38.212協(xié)議取碼長數(shù)目為1 024，信息比特數(shù)目為860，分別采用SC譯碼、Fast-List譯碼以及SCL譯碼和簡化的SCL譯碼。為盡可能的保證可靠性，對于SCL譯碼與簡化的SCL譯碼其搜索寬度值L取128，且都與長度為32的CRC級聯(lián)。因此，獲得的誤碼率(bit error rate, BER)和誤幀率(frame error rate, FER)的曲線如圖3和圖4所示。

圖3 BER性能比較Fig.3 BER performance comparison

圖4 FER性能比較Fig.4 FER performance comparison

顯然，當(dāng)信噪比從4 dB開始Fast-List譯碼的誤碼率與誤幀率相對其他譯碼算法都較高，從而導(dǎo)致Fast-List譯碼的糾錯性能損失，且隨著信噪比的增加這種趨勢越明顯。而簡化后的SCL譯碼仍與SC譯碼和傳統(tǒng)的SCL譯碼保持較好的糾錯性能。因此，表明簡化后的SCL譯碼算法與傳統(tǒng)的SCL譯碼算法在糾錯性能方面相當(dāng)。

3.2 簡化處理與時間步數(shù)

下面通過舉例分析SCL譯碼算法的簡化處理。圖5表示P(2,2)的SCL譯碼過程，由于SCL譯碼過程可以看做L條并行的SC譯碼，所以將其SC譯碼樹也給出，便于分析和比較。

但按照SCL譯碼算法的簡化處理，對于節(jié)點v在進(jìn)行簡化的SCL譯碼時判定為Rate-1節(jié)點且s=1，則根據(jù)公式(6)得

(23)

圖5 P(2,2)的SCL譯碼過程Fig.5 SCL decoding process of P(2,2)

對于SCL譯碼算法的時間復(fù)雜度可以通過譯碼碼字所需的時間步數(shù)來表示。假設(shè)所有可并行化的指令都在一個時鐘周期內(nèi)執(zhí)行，則譯碼一個碼字所需的時間步數(shù)可以計算為

TSCL=2Ns+K-2

(24)

(24)式中：K為信息比特的數(shù)目；K=Ns時譯碼Rate-1節(jié)點所需的時間步數(shù)為3Ns-2；K=0時譯碼Rate-0節(jié)點所需的時間步數(shù)為2Ns-2；由于Rep節(jié)點中包含1個信息比特，所以，K=1，因此，譯碼Rep節(jié)點所需的時間步數(shù)為2Ns-1。圖2中，對于P(8,5)且L=2的二叉樹，分別采用傳統(tǒng)的SCL譯碼和簡化的SCL譯碼對其整個譯碼所需的時間步數(shù)計算如下。

1)傳統(tǒng)SCL譯碼所需的時間步數(shù)為

Ns=8,K=5，2Ns+K-2=19

(25)

因此，整個譯碼共需要19個時間步數(shù)完成。

2)簡化的SCL譯碼所需的時間步數(shù)如下。

①對于正常節(jié)點a，b和c的關(guān)系為a→b，a→c，b→d，b→e，c→f，c→g都需要1個時間步數(shù)；

②對于節(jié)點d，e和f，都為Rep節(jié)點且Ns=2，其所需的時間步驟都為lbNs+1=2；

③對于Rate-1節(jié)點g，s=1，Ns=2s=2則所需時間步數(shù)為min(L-1,Ns)=1。

因此，簡化的SCL譯碼總共需要13個時間步數(shù)，相對傳統(tǒng)的SCL譯碼算法其所需的時間步數(shù)減少了6個。表1展示了不同譯碼方式每個節(jié)點所需的時間步數(shù)。

在實際譯碼中，時間步數(shù)還得根據(jù)自身的編碼結(jié)構(gòu)來確定，表2展示了對于Eb/N0=2 dB，N=2 048的極化碼在不同的速率、不同列表大小下進(jìn)行傳統(tǒng)SCL譯碼和簡化的SCL譯碼所需的時間步數(shù)。

表1 不同譯碼算法下的不同節(jié)點譯碼所需的時間步數(shù)

表2 各個譯碼算法在不同情況下的譯碼所需的時間步數(shù)

由表2可知，傳統(tǒng)的SCL譯碼所需的時間步數(shù)僅與碼率有關(guān)，而簡化后的SCL譯碼所需的時間步數(shù)與列表大小L正相關(guān)，并且碼率Rate較大時信息比特節(jié)點更多，編碼長度更大，譯碼所需的時間步數(shù)也更多。綜上，簡化后的SCL譯碼所需的時間步數(shù)相對于傳統(tǒng)的SCL譯碼較少。

4 結(jié)束語

在極化碼的譯碼方面，本文對傳統(tǒng)SCL譯碼算法的譯碼樹進(jìn)行了簡化剪枝研究，通過確定3個特殊節(jié)點：Rate-1節(jié)點、Rate-0節(jié)點和Rep節(jié)點，證明對它們路徑度量值的簡化計算不會改變傳統(tǒng)SCL譯碼的糾錯性能，并且使得其譯碼所需的時間步數(shù)從傳統(tǒng)的3Ns-2分別降為min(L-1,Ns)，lbNs和lbNs+1。最后，通過仿真和實驗結(jié)果表明：在保證糾錯性能的前提下，簡化后的SCL譯碼算法顯著降低了傳統(tǒng)SCL譯碼算法整體譯碼所需的時間步數(shù)。