基于多段CRC和部分路徑拓展的極化碼譯碼算法

付辰軒, 武霄泳, 費聚鋒, 林加濤, 張志龍

(1.北京郵電大學(xué),北京 100876;2.上海無線電設(shè)備研究所,上海 201109)

0 引言

極化碼是2009年由ARIKAN[1]提出的一種新型糾錯編碼技術(shù)。與低密度奇偶校驗(low density parity check,LDPC)碼[2]、Turbo碼[3]通過實驗證明達(dá)到香農(nóng)極限[4]不同,極化碼是第一種能夠通過理論證明達(dá)到香農(nóng)容量的編碼方案,并且憑借較低的編譯碼復(fù)雜度,成為了學(xué)術(shù)界的研究熱點。

連續(xù)刪除(successive cancellation,SC)極化碼譯碼算法[1]具有O(NlogN)的復(fù)雜度,并且在碼長N趨于無窮時,譯碼性能接近香農(nóng)極限。但由于實際條件下碼長受限,以至于信道極化不夠徹底,導(dǎo)致SC譯碼算法的誤碼率性能不理想。文獻(xiàn)[5]提出了連續(xù)刪除列表(successive cancellation list,SCL)譯碼算法。該算法通過在譯碼過程中盡可能保留更多的譯碼路徑,解決了SC譯碼算法在有限碼長下性能不足的問題,但同時也提高了算法復(fù)雜度。文獻(xiàn)[6]在SCL的基礎(chǔ)上引入循環(huán)冗余校驗(CRC),提出了CRC輔助的SCL(CRC-aided SCL,CA-SCL)譯碼算法。該算法進(jìn)一步提升了譯碼性能,但仍然沒有解決算法復(fù)雜度較高的問題。此后,對譯碼二叉樹進(jìn)行提前剪枝[7]和在SCL譯碼中插入兩段CRC的方法被提出[8],這兩種方法能夠在一定程度上降低譯碼算法復(fù)雜度。

針對傳統(tǒng)極化碼譯碼算法無法兼顧復(fù)雜度和性能的弊端,提出一種多段CRC的部分路徑拓展(multi-segment CRC-aided and partial path expansion SCL,MCA-PE-SCL)譯碼算法。該算法的核心思想是通過引入部分路徑拓展規(guī)則[9],在譯碼比特足夠可靠時進(jìn)行硬判決,在其余情況下進(jìn)行路徑拓展,目的是降低達(dá)到路徑上限L的速度,降低譯碼算法的復(fù)雜度。在此基礎(chǔ)上再引入循環(huán)冗余校驗,在CRC總的校驗位數(shù)一致的原則下,設(shè)計多段CRC策略,確保錯誤譯碼結(jié)果能夠被剔除,從而提升譯碼的可靠性。同時由于每次CRC后只會保留一條譯碼路徑,可進(jìn)一步降低譯碼算法復(fù)雜度。

1 極化碼

極化碼是基于信道極化提出的信道編碼方式。信道極化由信道聯(lián)合和信道分裂兩個階段組成。

信道聯(lián)合階段是以遞歸的方式組合N個給定的B-DMC,產(chǎn)生一個N維輸入、N維輸出的矢量信道WN:XN→YN,其中XN,YN分別表示N次信道輸入和輸出符號構(gòu)成的集合,N=2k,k為正整數(shù)。

信道分裂是將WN分裂成具有相互依賴關(guān)系的N個分裂子信道1≤i≤N。定義子信道的的轉(zhuǎn)移概率為

2 基于部分路徑拓展和多段CRC的極化碼譯碼算法

2.1 部分路徑拓展策略

SCL算法在譯碼路徑數(shù)未達(dá)到上限L時,同時保留“0”和“1”兩種譯碼結(jié)果,總體譯碼復(fù)雜度較高。而SC算法在譯碼過程中,每個比特譯碼時只進(jìn)行硬判決,保留“0”或“1”中的一種譯碼結(jié)果,總體譯碼復(fù)雜度較低。因此,考慮定義一個路徑拓展規(guī)則,通過比較每個譯碼比特的對數(shù)似然比L(ui)與其期望E(L(ui))的大小關(guān)系,進(jìn)行硬判決。如果當(dāng)前信息比特對數(shù)似然比L(ui)＞0,并且相對于E(L(ui))足夠大,則硬判決為0;如果當(dāng)前信息比特滿足L(ui)＜0,且相對于E(L(ui))足夠小,則硬判決為1;其余情況,則保留兩種可能的譯碼路徑。這就是部分路徑拓展的基本原理。圖1為部分路徑拓展譯碼樹示意圖。

圖1 部分路徑拓展譯碼樹示意圖

由文獻(xiàn)[10]可知,高斯信道條件下,當(dāng)輸入比特全為0時,可以證明每個信息比特的SC對數(shù)似然比都服從均值為、方差為的高斯分布,其中表示分裂子信道的對數(shù)似然比的期望。每個比特對數(shù)似然比的期望的計算公式可以由文獻(xiàn)[5]中對數(shù)似然比的遞推公式得出,表達(dá)式為

其中

式中:φ(·)是在[0,+∞)上連續(xù)單調(diào)遞減的函數(shù),且有φ(0)=1,φ(+∞)=0;σ為高斯白噪聲信道的標(biāo)準(zhǔn)差;u為微分變量。

設(shè)部分路徑拓展系數(shù)為α,極化碼譯碼部分路徑拓展規(guī)則滿足

式中:為第i個信息比特的譯碼判決結(jié)果;Ll(ui)為第l條路徑上第i個比特位的對數(shù)似然比。

當(dāng)α較小時,信息比特的對數(shù)似然比達(dá)到可靠條件較容易,會有更多的路徑進(jìn)行硬判決;反之,若α較大,信息比特的對數(shù)似然比達(dá)到可靠條件較困難,只有較少的路徑會進(jìn)行硬判決。

2.2 多段CRC策略

循環(huán)冗余校驗可以用來檢測數(shù)據(jù)傳輸過程中可能出現(xiàn)的錯誤。在信息比特序列末尾加上CRC,使得組合后的新信息比特序列能夠整除設(shè)定好的生成多項式。在極化碼接收端,將部分路徑拓展譯碼后的序列與生成多項式進(jìn)行模2除法,如果余數(shù)不為0,說明極化碼譯碼結(jié)果出現(xiàn)錯誤,則剔除當(dāng)前譯碼結(jié)果,從而降低譯碼誤幀率。

傳統(tǒng)的CA-SCL譯碼算法采取在整段信息比特后添加CRC的方式,相對于SCL譯碼算法,僅僅提高了性能,并沒有解決SCL復(fù)雜度較高的問題。本文設(shè)計的多段CRC策略采取在信息比特的不同特定位置分別插入CRC的方式,通過多段循環(huán)冗余校驗,達(dá)到降低譯碼算法復(fù)雜度的目的。

多段CRC的設(shè)計應(yīng)該遵循總校驗位數(shù)相同的原則,也就是在不同的CRC分段策略下,CRC的總校驗位數(shù)是相同的,這樣才能保證在不同分段情況下CRC所占的空間資源是相等的,從而保證整個極化碼譯碼流程中的碼率R不變。本文設(shè)計了五種校驗位分段策略,用a段b位代表CRC總校驗位共分為a段,每一段包括b位校驗位。具體包括:1段24位、2段12位、3段8位、4段6位、6段4位。每種分段策略中的CRC編碼器都遵循:將極化碼信息比特位按照CRC分段數(shù)平均拆分成若干段,然后將每段信息比特和對應(yīng)的CRC生成多項式傳入CRC編碼器,得到整合的序列,最后將此序列送入極化碼編碼器,進(jìn)行后續(xù)的編譯碼操作。

2.3 MCA-PE-SCL譯碼算法

本文所提的MCA-PE-SCL算法在部分路徑拓展的基礎(chǔ)上,引入多段CRC策略進(jìn)行校驗,進(jìn)而達(dá)到從兩方面共同降低極化碼譯碼復(fù)雜度的目的。MCA-PE-SCL算法的譯碼流程如圖2所示。其中部分路徑拓展譯碼器和循環(huán)冗余校驗器的個數(shù)n由CRC分段數(shù)確定。

圖2 MCA-PE-SCL算法流程圖

MCA-PE-SCL譯碼算法的實現(xiàn)步驟如下。

首先在輸入端將信息比特平均分為n段,每一段后加入相等數(shù)量的CRC校驗位。這里添加的n段CRC校驗位之和應(yīng)該與其他分段策略的總CRC位數(shù)m0相等,即m1+m2+…+mn=m0。完成信息比特和校驗位的序列聯(lián)合后,輸入序列依次進(jìn)入極化碼編碼器和調(diào)制器,再經(jīng)過加性高斯白噪聲信道的傳輸后開始譯碼。

譯碼階段相當(dāng)于在譯碼樹上分n段比特進(jìn)行譯碼。其中每段比特的譯碼又要經(jīng)過部分路徑拓展譯碼和CRC兩個步驟。當(dāng)?shù)趖(1≤t＜n)段譯碼序列經(jīng)過部分路徑拓展譯碼器時,通過式(2)得到每個比特的對數(shù)似然比期望,再通過式(4)來選擇進(jìn)行硬判決或者路徑拓展。隨后從部分路徑拓展譯碼器中存活的路徑按照度量值大小進(jìn)行降序排列,依次進(jìn)入循環(huán)冗余校驗器。當(dāng)?shù)谝粭l譯碼路徑通過校驗時,將此路徑作為最可靠路徑進(jìn)行保留,并結(jié)束第t段CRC環(huán)節(jié),以保留路徑作為唯一存活路徑,進(jìn)行第t+1段比特序列的譯碼。

第t+1段序列的對數(shù)似然比計算全部依賴于前t段比特譯碼后所存活下來的序列,相當(dāng)于此時的譯碼二叉樹上,從根節(jié)點到第t段最后一個比特之間僅存在一條譯碼路徑。而第t+1段比特的譯碼方法與第t段相同,以此類推,直到最后一段,即第n段比特序列,經(jīng)過第n個部分路徑拓展譯碼器和循環(huán)冗余校驗器,將每段循環(huán)冗余校驗器輸出的唯一存活譯碼序列進(jìn)行整合,即為最終的極化碼譯碼結(jié)果。在整個譯碼過程中,若存在任意一段比特序列,在經(jīng)過部分路徑拓展譯碼后,沒有能夠通過CRC的譯碼路徑,則證明當(dāng)前幀譯碼失敗,提前終止并進(jìn)行下一幀譯碼。

3 仿真與分析

為了驗證所提譯碼算法的復(fù)雜度與誤幀率性能,進(jìn)行了仿真實驗。相關(guān)實驗參數(shù)設(shè)定為:極化碼碼長N=1024,碼率R=0.5,譯碼路徑列表上限L=8,譯碼幀數(shù)為104,信噪比Eb/N0∈[1DB,3DB],調(diào)制方式采用二進(jìn)制相移鍵控(BPSK),信道條件為加性高斯白噪聲信道,部分路徑拓展系數(shù)α∈[0.1,0.6],CRC分段數(shù)n∈{1,2,3,4,6}。

3.1 復(fù)雜度仿真

在MCA-PE-SCL算法譯碼過程中,時間復(fù)雜度主要由每個譯碼比特對數(shù)似然比的計算,以及對數(shù)似然比與其期望的對比過程決定。而上述兩個過程的時間復(fù)雜度與譯碼路徑數(shù)量成正比。因此本文以譯碼過程中存活的路徑數(shù)量來衡量極化碼譯碼算法的復(fù)雜度,并分兩種情況對比分析不同分段策略下的MCA-PE-SCL算法與CASCL算法的復(fù)雜度。

第一種是相同信噪比、相同部分路徑拓展系數(shù)α情況下,不同CRC分段策略的譯碼存活路徑數(shù)對比。取信噪比Eb/N0=2DB,部分路徑拓展系數(shù)α=0.2,譯碼路徑數(shù)隨分段策略變化的仿真結(jié)果如圖3所示。

由圖3可以看出,隨著CRC校驗位分段數(shù)的增加,譯碼過程中存活路徑被剔除到只剩一條的情況越來越多,每一次經(jīng)過分段循環(huán)冗余校驗器后,后續(xù)比特進(jìn)行譯碼時存活路徑數(shù)均明顯減少,相當(dāng)于開始新的一次部分路徑拓展SCL算法。在Eb/N0=2DB,α=0.2條件下,CA-SCL算法的總譯碼路徑數(shù)為6799,不同分段策略的MCAPE-SCL算法總譯碼路徑數(shù)如表1所示。

可知,譯碼復(fù)雜度隨校驗位分段數(shù)增多呈遞減趨勢。相同初始參數(shù)與信道環(huán)境下,相對于傳統(tǒng)CA-SCL算法,不同分段策略的MCA-PE-SCL算法的復(fù)雜度分別降低了55.36%,71.53%,76.08%,79.95%,82.02%。

第二種是相同信噪比、相同分段策略情況下,不同α的譯碼存活路徑數(shù)對比。取信噪比Eb/N0=1DB,CRC分段策略為2段12位,譯碼路徑數(shù)隨α變化的仿真曲線如圖4所示。

圖4 譯碼路徑數(shù)隨α變化仿真圖

可知,隨著α的降低,每層比特對應(yīng)的存活譯碼路徑數(shù)越來越少。原因是α越小,對應(yīng)的路徑拓展要求就越低。根據(jù)2.1節(jié)中的路徑拓展規(guī)則,譯碼過程直接進(jìn)行硬判決的比特就越多,總的譯碼存活路徑則越少,所對應(yīng)的譯碼復(fù)雜度也越低。

基于本文仿真參數(shù),在不同信噪比下,CASCL算法的總譯碼路徑數(shù)均為6799。當(dāng)α=0.2時,譯碼路徑列表上限L=8,不同信噪比下MCA-PE-SCL算法對應(yīng)的總路徑數(shù)如表2所示。

表2 不同信噪比下MCA-PE-SCL算法對應(yīng)的總譯碼路徑數(shù)

由表2可知,與CA-SCL算法相比,MCAPE-SCL算法的復(fù)雜度大大降低。定義路徑數(shù)占比為MCA-PE-SCL算法路徑數(shù)與CA-SCL算法路徑數(shù)之比,取信噪比為2DB,部分路徑系數(shù)為0.2,CRC分段策略為3段8位,可以得出路徑數(shù)占比為30.61%,即與CA-SCL算法相比,MCAPE-SCL算法復(fù)雜度降低了69.39%。

在低信噪比情況下,多段CRC對復(fù)雜度的優(yōu)化效果大于部分路徑拓展。取信噪比為1DB,部分路徑系數(shù)為0.2,整段24位CRC,可以得出其路徑數(shù)占比為95.15%,相比于CA-SCL算法,復(fù)雜度只降低了4.85%,優(yōu)化效果相對較差。但如果在此基礎(chǔ)上,引入2段、3段、4段、6段的CRC,所降低的復(fù)雜度百分比分別為21.45%,31.85%,40.20%,46.60%,復(fù)雜度優(yōu)化程度有大幅提升。

隨著信噪比的增大,對于降低復(fù)雜度,部分路徑拓展起到的作用逐漸增大,多段CRC起到的作用逐漸減小。以表2中最后一列路徑數(shù)據(jù)為例,在信噪比提升到3DB時,從上到下,每種分段策略譯碼算法對應(yīng)前一分段方法的復(fù)雜度分別只有1.13%,0.35%,0.11%,0.08%的提升。

可知,引入部分路徑拓展和多段循環(huán)冗余校驗的MCA-PE-SCL算法能夠在全信噪比區(qū)間下有效降低譯碼復(fù)雜度。

3.2 誤幀率仿真

為了驗證MCA-PE-SCL算法的可行性,將其在預(yù)設(shè)幀數(shù)下與CA-SCL算法進(jìn)行誤幀率仿真對比。

當(dāng)α=0.2時,不同分段策略的MCA-PESCL譯碼算法與傳統(tǒng)的CA-SCL算法的誤幀率對比仿真結(jié)果如圖5所示。

圖5 不同情況下各譯碼算法誤幀率對比仿真圖

由圖5可知,在所取信噪比區(qū)間內(nèi),分段策略為1段24位的MCA-PE-SCL算法的誤幀率一直處于最高的狀態(tài)。隨著分段數(shù)的增加,MCA-PESCL算法的誤幀率有所下降,并且存在誤幀率低于CA-SCL算法的情況,此時前者在譯碼復(fù)雜度和可靠性方面均優(yōu)于后者。綜合對比所提算法與CA-SCL算法的復(fù)雜度和誤幀率可以得出,在α=0.45,CRC分段策略為6段4位時,兩種算法誤幀率均為4×10-4,前者復(fù)雜度相對于后者降低了約81.00%。

MCA-PE-SCL算法在引入多段CRC分段策略時,存在兩種影響:一是校驗位數(shù)越多,校驗位的部分路徑拓展譯碼出錯的概率越大;二是校驗位數(shù)越多,經(jīng)CRC得出的譯碼路徑正確的概率越大。圖6為不同信噪比條件下的MCA-PE-SCL算法誤幀率仿真結(jié)果。

圖6 不同信噪比下的MCA-PE-SCL算法誤幀率仿真圖

由圖6可知,在α=0.2的情況下,除信噪比為0時,MCA-PE-SCL算法的誤幀率隨分段數(shù)增加而減小,其他信噪比條件下誤幀率都隨著校驗位分段數(shù)的增加,先下降后上升。誤幀率先下降說明,在前三種分段較少的策略中,影響一的作用大于影響二,此時誤幀率大小主要由分段數(shù)所主導(dǎo);接下來的上升趨勢說明當(dāng)分段數(shù)過多時,影響二帶來的作用大于影響一,誤幀率大小主要由單次CRC的校驗位數(shù)所決定。隨著信噪比的增大,對應(yīng)的誤幀率最低的MCA-PE-SCL算法的CRC分段數(shù)逐漸減小,不同信噪比下的最低誤幀率CRC分段策略如表3所示。

表3 不同信噪比下的最低誤幀率CRC分段策略

4 結(jié)論

本文針對SCL、CA-SCL算法復(fù)雜度過高的弊端,提出了一種基于多段循環(huán)冗余校驗和部分路徑拓展的極化碼譯碼算法。該算法定義部分路徑拓展規(guī)則,并引入循環(huán)冗余校驗,設(shè)計五種多段CRC插入方案,通過將接收序列按照校驗位分段數(shù)依次通過兩種譯碼器,達(dá)到了降低譯碼復(fù)雜度的目的。與CA-SCL算法的對比仿真結(jié)果證明,選取合適的部分路徑拓展參數(shù)和分段策略,MCA-PE-SCL算法可在保證誤幀率滿足要求的前提下極大地降低譯碼復(fù)雜度,為極化碼譯碼在權(quán)衡復(fù)雜度和誤幀率性能的方案提供了一種具有參考價值的算法。