基于BCJR網(wǎng)格的3×3核極化碼簡化連續(xù)消去譯碼算法

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

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

0 引言

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

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

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

1 極化碼簡單回顧

1.1 極化碼

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

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

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

(1)

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

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

1.2 最小網(wǎng)格構(gòu)造

① 網(wǎng)格

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

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

(2)

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

② 最小網(wǎng)格

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

1.3 BCJR網(wǎng)格構(gòu)造

設(shè)碼C是一個在IFq上長度為n的線性碼,H=[h1,h2,…,hn]是碼C的奇偶校驗矩陣,則BCJR網(wǎng)格圖T可以通過標(biāo)記節(jié)點(diǎn)Vi集合來構(gòu)造。

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

(3)

V0={φ}={0},

(4)

Vn={φ}={0},

(5)

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

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

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

(6)

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

(7)

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

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

(8)

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

為求出網(wǎng)格,須進(jìn)行以下幾個步驟：

② 根據(jù)頂點(diǎn)的計算公式進(jìn)行各個頂點(diǎn)的計算,其中V0={0},V5={0}。

(9)

③ 根據(jù)式(6)和式(7)對網(wǎng)格圖進(jìn)行邊標(biāo)記,根據(jù)邊標(biāo)記定義式,繪制出線性碼C的網(wǎng)格,如圖2所示。

圖2 線性碼C的網(wǎng)格圖Fig.2 Trellis of linear code C

2 基于BCJR網(wǎng)格構(gòu)造的極化碼譯碼算法

本節(jié)介紹通過BCJR網(wǎng)格來進(jìn)行極化碼的譯碼過程,運(yùn)用網(wǎng)格結(jié)構(gòu)替代了極化碼中的直接運(yùn)算,根據(jù)生成矩陣構(gòu)造出最小網(wǎng)格,該方法可以有效地降低高維極化碼譯碼復(fù)雜度。

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

2.1 譯碼u1

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

① 譯碼u1=0的概率

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

(10)

根據(jù)式(6)和式(7),可求解出邊標(biāo)記c,根據(jù)邊標(biāo)記可以繪制出譯碼u1網(wǎng)格,如圖3所示。

圖3 譯碼u1網(wǎng)格圖Fig.3 Decoding u1 trellis

② 譯碼u1=1的概率

2.2 譯碼u2

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

① 譯碼u2=0的概率

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

(11)

根據(jù)式(6)和式(7),計算出邊標(biāo)記,繪制出網(wǎng)格,如圖4所示。

圖4 譯碼u2網(wǎng)格Fig.4 Decoding u2 trellis

② 譯碼u2=1的概率

2.3 譯碼u3

上述就是將BCJR網(wǎng)格構(gòu)造方法應(yīng)用于極化碼譯碼的大致流程。

3 實(shí)驗結(jié)果與分析

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

具體來說,二進(jìn)制碼字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)是獨(dú)立分布的均值為0且方差為N0/2的高斯隨機(jī)變量集。

實(shí)驗結(jié)果給出了3×3核二進(jìn)制內(nèi)核的極化碼的誤幀率(Frame Error Ratio,FER),設(shè)置SNR步進(jìn)為0.5,INIT_SNR設(shè)置為1.0,FINAL_SNR設(shè)置為6.0。通過對比傳統(tǒng)SC譯碼的仿真結(jié)果,BCJR構(gòu)造的網(wǎng)格極化碼同樣有著不錯的性能。

表1記錄了計算機(jī)CPU的性能參數(shù)。在實(shí)驗消耗時間上,設(shè)置SNR步進(jìn)為1,INIT_SNR設(shè)置為1.0,FINAL_SNR設(shè)置為5.0。統(tǒng)計每輪的計算時間,結(jié)果如表2所示。

表1 計算機(jī)性能參數(shù)

表2 譯碼消耗時間對比

表3 基于BCJR網(wǎng)格和直接計算式的運(yùn)算量比較

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

圖5 傳統(tǒng)SC譯碼與基于BCJR網(wǎng)格譯碼的方法 構(gòu)造的極性碼的FERFig.5 FER of polar code constructed by traditional SC decoding and BCJR trellis decoding method

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

4 結(jié)論

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