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

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

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

0 引言

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

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

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

1 極化碼

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

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

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

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

2.1 部分路徑拓展策略

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

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

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

其中

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

設部分路徑拓展系數為α,極化碼譯碼部分路徑拓展規則滿足

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

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

2.2 多段CRC策略

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

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

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

2.3 MCA-PE-SCL譯碼算法

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

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

MCA-PE-SCL譯碼算法的實現步驟如下。

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

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

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

3 仿真與分析

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

3.1 復雜度仿真

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

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

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

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

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

圖4 譯碼路徑數隨α變化仿真圖

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

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

表2 不同信噪比下MCA-PE-SCL算法對應的總譯碼路徑數

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

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

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

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

3.2 誤幀率仿真

為了驗證MCA-PE-SCL算法的可行性,將其在預設幀數下與CA-SCL算法進行誤幀率仿真對比。

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

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

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

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

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

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

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

4 結論

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