基于BCJR網格的3×3核極化碼簡化連續消去譯碼算法

李逸飛,黃志亮,張莜燕,周水紅

(浙江師范大學 物理與電子信息工程學院,浙江 金華 321004)

0 引言

極化碼最早由Arikan教授提出,是一種理論上證明在離散無記憶信道中可以達到信道容量的編碼方案[1]。2016年,3GPP會議選擇了極化碼作為5G控制信道增強移動寬帶場景的編碼方式[2]。Arikan教授提出的極化碼的編譯碼是基于2×2核矩陣構造的,其碼長只能為2n。2010年Korada等人[3]指出基于核矩陣構造出的極化碼可以擁有更優的糾錯性能。

對于任意的ε>0,碼長為2n的極化碼在連續消去(Successive Cancellation,SC)解碼下的誤幀率為o(2-2n(β-ε)),β為極化因子,其中2×2核矩陣的β值為0.5。極化因子的定義同時可以推廣至任意的大核矩陣,并且可以設計出具有更大極化因子的大核矩陣[3-6]。不同大小的大核矩陣(m×m(m>2)核矩陣)分別對應不同的最優極化速率。一般來講,更大的核可以有更大的極化速率,在相同碼長下,極化速率越大,對應碼性能越好。

文獻[3]同時指出,大核矩陣在譯碼中往往會有更高的復雜度,直接的SC譯碼對于大核矩陣是不實際的。極化碼的核內部運算可以借助于網格圖來計算,網格是一種有向分層圖,最早出現在計算復雜性理論的有限自動機的研究理論中。研究結果表明通過網格可以有效地降低SC譯碼運算量,節省運算時間[7]。針對大核矩陣帶來的復雜度增加的問題,將傳統網格與極化碼的譯碼過程結合起來,提出用BCJR(Bahl,Cocke,Jelinek,Raviv construction)網格計算來替代傳統SC譯碼過程中信道轉移概率的計算,通過搭建SC譯碼樹來降低算法的計算量。

1 極化碼簡單回顧

1.1 極化碼

圖1 極化碼模型圖Fig.1 Model diagram of polar code

對于任意給定的信道,基于不同的核矩陣設計出對應的極化碼都有一組對應的參數(N,K,A,uAc)。N是極化碼碼長,K是信息位位數,集合A是由K個信息位序號組成的,uAc為凍結位的取值[10-13]。

大核矩陣的譯碼方式與原G2核矩陣的譯碼方式大致相同。對于一個給定的m×m核矩陣Gm,針對SC譯碼,信道轉移概率的計算公式為：

(1)

式中：ui∈{0,1},i=1,2,…,m。

以Gm為核矩陣構造的極化碼的 SC譯碼通過直接計算的復雜度為O(2mNlogmN),它隨核大小m呈指數增長。本文提出的網格譯碼就是通過計算網格起點到終點所有路徑的流量和來替代式(1),降低計算成本[14-16]。

1.2 最小網格構造

① 網格

網格是一種特殊的圖結構。用T=(V,E,∑)表示,其中集合V稱為T的狀態(頂點集),E稱為邊(分支),∑為邊的符號集。且必須滿足以下條件：網格T的狀態集合V,由n+1個子集的并集構成,由式(2)表示[17]：

V=V0∪V1∪…∪Vn∪Vn+1。

(2)

在頂點Vi和Vi+1中會有一條邊連接,記作ei,同時在邊上可能會有一些特殊的標記值,用來進行計算或者存儲網格的其他信息,記作α(ei)。

② 最小網格

目前,最小網格的構造方法已經十分成熟,常用的構造方法有4種,本文用到的BCJR構造方法就是其中一種,除此之外還有Forney構造方法、Massey構造方法及KS(Kschischang-Sorokine)構造方法[7]。

1.3 BCJR網格構造

設碼C是一個在IFq上長度為n的線性碼,H=[h1,h2,…,hn]是碼C的奇偶校驗矩陣,則BCJR網格圖T可以通過標記節點Vi集合來構造。

時刻i的頂點集合由式(3)指出：

(3)

V0={φ}={0},

(4)

Vn={φ}={0},

(5)

式中：V0和Vn都是0的集合。

從開始節點V∈Vi-1到下一節點V′∈Vi有一條邊e∈Ei當且僅當存在碼字(c1,c2,…,cn)∈C滿足下式：

c1h1+c2h2+…+ci-1hi-1=v,

(6)

c1h1+c2h2+…+ci-1hi-1+cihi=v′。

(7)

介于Vi-1與Vi的邊記作ei,這條邊的邊標記α(ei)=ci。

式(2)指出了節點的定義,具體的計算過程如下：

(8)

式中：Gi為碼C生成矩陣的前i列,Hi為碼C奇偶校驗矩陣的前i列。通過上式的計算,可以得出各結點的向量組合,然后得出網格構造[16-18]。

為求出網格,須進行以下幾個步驟：

② 根據頂點的計算公式進行各個頂點的計算,其中V0={0},V5={0}。

(9)

③ 根據式(6)和式(7)對網格圖進行邊標記,根據邊標記定義式,繪制出線性碼C的網格,如圖2所示。

圖2 線性碼C的網格圖Fig.2 Trellis of linear code C

2 基于BCJR網格構造的極化碼譯碼算法

本節介紹通過BCJR網格來進行極化碼的譯碼過程,運用網格結構替代了極化碼中的直接運算,根據生成矩陣構造出最小網格,該方法可以有效地降低高維極化碼譯碼復雜度。

作為線性碼的核矩陣[5]。

2.1 譯碼u1

譯碼u1的過程中只有兩個可能性：一種是u1=0的概率;另一種u1=1的概率。

① 譯碼u1=0的概率

根據式(8),可以求出頂點集合V,根據得出的結點求出其他的列向量組合,具體計算過程如下：

(10)

根據式(6)和式(7),可求解出邊標記c,根據邊標記可以繪制出譯碼u1網格,如圖3所示。

圖3 譯碼u1網格圖Fig.3 Decoding u1 trellis

② 譯碼u1=1的概率

2.2 譯碼u2

譯碼u2的過程中,同樣u2譯碼只有兩個可能性：一種是u2=0的概率;另一種u2=1的概率。分為兩種情況進行,又因為在譯碼u2時u1已知,需要將情況進行細分。

① 譯碼u2=0的概率

根據式(8),可以求出頂點集合V,根據得出的結點求出其他的列向量組合,具體計算過程如下：

(11)

根據式(6)和式(7),計算出邊標記,繪制出網格,如圖4所示。

圖4 譯碼u2網格Fig.4 Decoding u2 trellis

② 譯碼u2=1的概率

2.3 譯碼u3

上述就是將BCJR網格構造方法應用于極化碼譯碼的大致流程。

3 實驗結果與分析

本次實驗基于3×3的生成矩陣,設置幀數為1 000 000,在考慮二進制相移鍵控(BPSK)調制和二進制加性高斯白噪聲(BI-AWGN)信道。

具體來說,二進制碼字x=(x0,x1,…,xN-1)通過n= 1-2xn映射到傳輸序列s=(s0,s1,…,sN-1)。在接收端,得到接收向量y=(y0,y1,…,yN-1)。其中yn=sn+zn和z=(z0,z1,…,zN-1)是獨立分布的均值為0且方差為N0/2的高斯隨機變量集。

實驗結果給出了3×3核二進制內核的極化碼的誤幀率(Frame Error Ratio,FER),設置SNR步進為0.5,INIT_SNR設置為1.0,FINAL_SNR設置為6.0。通過對比傳統SC譯碼的仿真結果,BCJR構造的網格極化碼同樣有著不錯的性能。

表1記錄了計算機CPU的性能參數。在實驗消耗時間上,設置SNR步進為1,INIT_SNR設置為1.0,FINAL_SNR設置為5.0。統計每輪的計算時間,結果如表2所示。

表1 計算機性能參數

表2 譯碼消耗時間對比

表3 基于BCJR網格和直接計算式的運算量比較

從圖5中可以看出,傳統SC譯碼與BCJR網格譯碼在SNR相同時FER差異不大。

圖5 傳統SC譯碼與基于BCJR網格譯碼的方法 構造的極性碼的FERFig.5 FER of polar code constructed by traditional SC decoding and BCJR trellis decoding method

從上述結果可以分析得出,基于BCJR網格的代碼運行時間要遠遠低于傳統SC譯碼所消耗的時間。在算法運行時間上,在相同SNR條件下,綜合對比直接計算式運行時間平均減少了79.14%,節省了14.2%的計算成本,有效降低了算法的復雜度。

4 結論

為了解決大核矩陣帶來的譯碼復雜度增加的問題,將傳統的BCJR網格與極化碼的譯碼過程相結合,利用網格圖的特性,通過計算出起點到終點所有路徑的流量和來替代SC譯碼過程中位信道轉移概率的遞推計算式,有效地降低計算量。對于3×3核矩陣構造的極化碼,仿真結果表明該方法有效降低了算法的運行時間,降低了計算成本。在后續研究過程,將基于此方案將算法推進到更高維的大核矩陣中。