低時間復雜度的極化碼譯碼算法

陳發(fā)堂，趙昊明，石 丹，陳 洋

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

0 引 言

極化碼設計的核心理論是對信道的極化方案，信道極化過程主要包括2部分：信道聯(lián)合過程和信道分裂過程。通過信道聯(lián)合和信道分裂，各個子信道的二進制對稱容量將呈現(xiàn)兩極分化形式。隨著信道聯(lián)合數的增加，一部分信道的容量趨近于1；另一部分則趨近于0。正是利用這種極化現(xiàn)象，我們用趨近于1的信道傳送信息，而趨近于0為凍結位，一般為0[1]。理論推導證明，隨著碼長N趨于無窮大，極化碼是一種可以達到香農信道容量的理想碼字。

串行消除(successive cancellation，SC)譯碼是最早提出的極化碼譯碼方法[1]，它可以被看做是一種樹的遍歷。在SC譯碼中，以深度優(yōu)先的方式訪問碼樹的節(jié)點，因此，采用這種方式會有較大的時間復雜度。所以對不必要的子樹進行修剪是提高SC譯碼性能的關鍵，在文獻[2-4]中對SC譯碼做了優(yōu)化，在滿足特定條件時可以停止子樹的遍歷，從而降低時間復雜度。

極化碼串行抵消列表譯碼(successive cancellation list，SCL)[5]是目前極化碼應用最廣泛的譯碼器?？梢哉J為SCL是L個并行SC譯碼器，尤其是極化碼在加了冗余循環(huán)校驗(cyclic redundancy check，CRC)之后[6]，大幅度地提高了SCL譯碼器的糾錯性能，但是復雜度和時延很高。球形譯碼(sphere decoding, SD)找到傳輸數據的ML(maximum-likelihood)估計，但是球形譯碼的時間復雜度是可變的，并且譯碼延遲是不可預期的。SD譯碼過度依靠半徑的選擇，半徑過大，候選路徑過多算法復雜過大。半徑過小，SD無法找到ML估計。為了克服這些問題，提出了列表球形譯碼[7](list sphere decoding，LSD)。

本文改進了文獻[10]中的一種剪枝算法并與文獻[9]中的聯(lián)合譯碼算法相結合，提出了SC-SCSL(syndrome check-successive cancellation sphere list)譯碼，相比于CA-SCL譯碼在幾乎不損失性能的情況下，時間復雜度降低了50%以上。

1 極化碼簡介

Arikan所提出的信道極化理論被認為是編碼理論中的一個重大突破。因為它是經過嚴格證明，具有能力實現(xiàn)香農信道容量和低復雜度的編碼和解碼算法[1]。

1.1 極化碼編碼

圖1 長度為4的極化碼編碼Fig.1 Polar code of length 4

1.2 SC譯碼

SC譯碼算法可以解釋為對二進制樹的遍歷，如圖2，子節(jié)點通過接收母節(jié)點的軟信息圖中的α，經過計算似然比(logarith-mic likelihood ratios,LLR)，硬判決后傳回β。樹是通過深度優(yōu)先搜索且左邊的優(yōu)先級高。

圖2 SC譯碼樹Fig.2 SC decoding tree

(1)

(2)

(1)—(2)式中:

f(a,b)≈sign(a)sign(b)min(|a|,|b|)，

g(β,a,b)=(-1)βa+b

(3)

對于子節(jié)點β，通過硬判決得到

(4)

(5)

保留的L條路徑，其中最小PM值對應的路徑為譯碼結果。但SCL譯碼的復雜度很高，文獻[8]所提出的綜合檢測串行消除(syndrome check successive cancellation，SCSC)譯碼極大地提高了SC譯碼的性能。對于非葉子節(jié)點若滿足了綜合檢測

(6)

(6)式中：β為Nv位硬判決值得到的矩陣；H為奇偶校驗矩陣，可由生成矩陣得到。

該節(jié)點下的葉子節(jié)點譯碼結果可直接得到

(7)

(7)式中：u為Nv位譯碼結果；GNv為行數與列數為Nv位的方陣生成矩陣。

(8)

(9)

將會與文獻[10]中的結果相矛盾。

1.3 LSD譯碼

利用GN的下三角結構，SD譯碼從uN-1開始，并行分裂路徑0和1[11]。計算出根節(jié)點到子節(jié)點的歐氏距離，作為下一比特估計球的半徑。所有在球內的候選路徑被用于下個比特的估計，重復此過程，直到找出歐式距離最小的候選比特。路徑度量值的近似表達式為

(10)

球形譯碼可以找到傳輸數據的ML估計，但復雜度不可預期。為了克服這個問題，提出了LSD[12]譯碼。LSD譯碼有固定時間復雜度。每次都有一個新比特被估計，它可能的值0和1都需要被考慮。由于存在L組碼字候選，所以每次更新的后產生2L組候選路徑，其中一半丟棄，沒有涉及半徑。

2 SC-SCSL譯碼

首先對ESSCL譯碼進行了改進，提出了SC-SCL譯碼；并聯(lián)合了LSD譯碼，提出SC-SCSL譯碼，極大地減少了時間復雜度。

2.1 SC-SCL譯碼

2.2 SC-SCSL譯碼

SC-SCSL譯碼：結合上文所述，將長度為N的碼字{u1,u2,…,uN}分成2段進行譯碼。其中,{u1,u2,…,uM}使用SC-SCL(L=LS)譯碼,而{uM+1,uM+2,…,uN}使用LSD(L=LD)譯碼，兩者并行進行。對結果的LS條路徑和LD進行組合，選出通過CRC校驗的碼字為最終譯碼結果。如圖3，由于譯碼并行進行，SC-SCSL譯碼所需的時間為

圖3 SC-SCSL譯碼Fig.3 SC-SCSL decoding

t=MAX(tSC-SCL,tLSD)

(11)

由于引入了CRC，結果可能出現(xiàn)同時滿足檢測的情況；對此，通過LLR作為可靠性的度量方式，選擇LLR最小的為最終結果。

2.3 仿真結果分析

圖4 未出現(xiàn)同時滿足綜合檢測時的誤幀率比較Fig.4 Comparison of FER when syndrome check is not met at the same time

圖5 出現(xiàn)相同點同時滿足綜合檢測時的誤幀率比較Fig.5 Comparisons of FER when the same points are met with syndrome check at the same time

對(1 024,512)型極化碼運用SC-SCSL的FER性能仿真，如圖6。其中，SCL,CA-SCL,LSD的搜索路徑數相同L=4；SC-SCSL的SC-SCL部分LS=4，LSD部分LD=4，M取683，并且設定CRC校驗碼類型為CRC-24。

圖6 碼長1 024的幾種算法誤幀率比較Fig.6 Comparison of frame error rates of several algorithms with code length 1 024

從圖6可以看出，在相同情況下，SC-SCSL的性能明顯優(yōu)于SC，SCL和LSD。雖然相比于CA-SCL在高信噪比時，有一定的性能損失，如在信噪比為2 dB時，有約0.4 dB的性能損失，但由于此算法的并行特性，可極大地降低譯碼時間復雜度。

3 復雜度分析

作為復雜度的度量標準，本節(jié)分別給出了SCL，SC-SCL，LSD的加法次數，乘法次數，和比較次數計算公式。將所提出的SC-SCSL與CA-SCL運算次數進行比較。結果表明，在幾乎不損失性能的情況下，時間復雜度降低了50%～55%。

3.1 SCL譯碼復雜度

(12)

(12)式中：K，Ng，Nf，SASCL，SMSCL，SCSCL分別表示冒泡序列排序時的信息比特數；(3)式中g,f算法的運算次數、加法次數、乘法次數和比較次數。

3.2 SC-SCL譯碼復雜度

(13)

3.3 LSD譯碼復雜度

(14)

(14)式中：A是信息比特集合；AC是凍結比特集合；ki為第i個訪問比特位置。

3.4 SC-SCSL復雜度比較

由(11)式，SC-SCSL的時間復雜度為LSD和SC-SCL的最大值。表1給出了(512,256)的極化碼在LS=LD=4,M=342時，分進行CA-SCL，SC-SCSL,LSD譯碼仿真時，通過計數器累計的所需加法次數，乘法次數，比較次數。雖然SC-SCSL加入了CRC會在高信噪比時，有輕微的性能損失，但卻降低了50%～55%的時間復雜度。仿真結果表明，M=2N/3左右時，SC-SCSL性能最佳。

表1 碼長512時幾種譯碼算法運算器次數Tab.1 Number of decode algorithm operators for code length 512

4 結束語

為了避免在長碼字時同時滿足綜合檢測，采用ESSCL譯碼導致的錯誤譯碼結果，本文提出了一種SC-SCL算法。仿真結果表明，在出現(xiàn)同時滿足綜合檢測時，SC-SCL性能明顯優(yōu)于ESSCL。并聯(lián)合了LSD譯碼，提出的SC-SCSL譯碼在高信噪比時，會有較低的性能損失，但采用并行的方式降低了50%～55%的時間復雜度。接下來將研究LSD譯碼的剪枝算法，進一步減少復雜度。