邱開虎,黃志亮,張莜燕,周水紅

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

0 引言

極化碼最早是由Arikan教授[1]提出,是第一個具有多項式級數(shù)的編譯碼復雜度并且可以通過理論證明可達香農(nóng)極限的編碼方案。由于極化碼具有低復雜度的編譯碼方案和較好的糾錯性能,在2016年3GPP會議中被選為5G控制信道eMBB場景編碼方案。Arikan[1]提出了串行消去(Successive Cancellation,SC)譯碼算法。Tal等人[2]提出了串行消去列表 (Successive Cancellation List,SCL)譯碼算法。Chen等人[3]提出采用堆棧的SC譯碼算法。SCL譯碼算法與采用堆棧的SC譯碼算法均為基于SC譯碼改進的譯碼算法。串行譯碼算法由于應用了極化碼特有的鏈式概率模型,可以從理論上被證明可達香農(nóng)極限,但是存在時延較高、吞吐率較低的缺陷,這些缺陷限制了極化碼在5G高速通信時代的應用,學者們針對SC譯碼算法在有限碼長下譯碼性能較差的問題提出了許多有效的方法[4-7]。Gallager[8]提出置信度傳播(Belief Propagation,BP)譯碼算法。Arikan[9]使用BP譯碼算法進行極化碼譯碼。與串行譯碼算法相比,BP譯碼算法性能與串行譯碼性能相當,譯碼時延大幅度降低。

基于2×2核的極化碼BP譯碼算法通過級聯(lián)的方式推廣至基于3×3核矩陣極化碼?；?×2核的極化碼BP譯碼算法信息更新公式,給出了3×3核內(nèi)部最小計算單元的信息更新公式?；谧钚卧畔⒏鹿浇o出了3×3核極化碼的BP譯碼算法流程?；?×3核矩陣下的極化碼,相較于2×2核構(gòu)造的極化碼,碼長更具豐富性,相較于串行譯碼算法中的SC譯碼算法,在35碼長下,BP譯碼算法在1～4 dB的信噪比下,譯碼性能更具優(yōu)勢,在信噪比大于4 dB的情況下,BP譯碼算法性能稍弱于SC譯碼算法,由于BP譯碼算法具有并行譯碼結(jié)構(gòu),相較于SC譯碼算法,BP譯碼時延降低了約50%。

1 相關(guān)工作

1.1 符號說明

(1)

2×2核的極化碼生成矩陣為：

(2)

(3)

1.2 極化碼的構(gòu)造

1.3 極化碼的BP譯碼算法

BP譯碼算法是一種廣泛使用的消息傳遞譯碼算法,主要應用場景有低密度奇偶校驗碼[8](Low Density Parity Check Code,LDPC)以及極化碼,LDPC使用BP譯碼算法進行譯碼是基于奇偶校驗矩陣進行消息更新的,極化碼的BP譯碼算法消息更新是基于因子圖[18]實現(xiàn)的。在2×2核矩陣構(gòu)造的極化碼中,因子圖一共由n=lbN個階段及N×(n+1)個節(jié)點組成,圖1為一個(8,4)極化碼的BP譯碼因子圖[19]。圖2中Li,j表示因子圖中向左傳遞信息,Ri,j表示因子圖中向右傳播信息,0≤i≤n(n=lb(N))表示節(jié)點所在的列序號,0≤j≤N-1表示節(jié)點所在的行序號。

圖1 碼長為8的的極化碼因子圖Fig.1 Polar code factor graph with code length of 8

圖2 BP譯碼算法中最小計算單元Fig.2 Minimum computing unit in BP decoding algorithm

Li,j與Ri,j在因子圖相鄰節(jié)點之間進行信息傳遞以及迭代更新,其中每次迭代更新遵循如下：

(4)

式中：L和R分別表示左右信息的值。

(5)

式中：s,t∈R,為了降低運算復雜度該函數(shù)一般使用基于最小和(Min-Sum)來近似。近似函數(shù)如下：

g(s,t)≈α×sign(s)×sign(t)×min(|s|,|t|),

(6)

式中：α一般取值為0.937 5。

在進行譯碼前,左信息與右信息對數(shù)似然比初始化如下：

(7)

(8)

(9)

2 基于3×3大核的極化碼BP譯碼算法

在2×2核極化碼BP譯碼算法[9]的基礎上,本文提出了3×3核極化碼BP譯碼算法。相較于傳統(tǒng)的SC譯碼算法[12],二者譯碼性能相當,但BP譯碼算法在譯碼時延上更具優(yōu)勢。本節(jié)主要介紹基于3×3核的最小計算單元、BP譯碼算法、左右信息更新公式、譯碼算法流程等核心內(nèi)容。

2.1 基于3×3核的最小計算單元

圖3 基于3×3核極化碼BP譯碼算法的最小計算單元Fig.3 Minimum computing unit of BP decoding algorithm based on 3×3 kernel polar code

2.2 3×3核極化碼BP譯碼算法左右信息更新公式

BP譯碼算法是在變量節(jié)點與校驗節(jié)點之間傳遞外信息,經(jīng)過多次迭代后,達到算法收斂。BP譯碼算法是一種典型的后驗概率譯碼算法,經(jīng)過充分迭代之后逼近最大后驗概率(Maximum a Posteriori,MAP)估計譯碼性能。

BP譯碼算法相較于串行譯碼算法最大的一個特點是可以并行譯碼,由此可以加快譯碼速度。在BP譯碼算法中,主要是通過因子圖中的節(jié)點來實現(xiàn)左右信息的傳遞以及更新,圖4為N=9時的3×3核BP譯碼因子圖。

圖4 碼長為 9 的極化碼因子圖Fig.4 Polar code factor graph with code length of 9

基于消息傳遞算法,圖4中信息更新遵循如下準則：先迭代更新節(jié)點中的左信息,再迭代更新節(jié)點中的右信息。

3×3核極化碼最小計算單元中,左信息更新公式如下：

(10)

右信息更新如下：

(11)

2.3 基于核極化碼BP譯碼算法流程

3×3核矩陣構(gòu)造的極化碼BP譯碼算法流程如算法1所示。

算法1 極化碼BP譯碼算法輸入：LLR(yj),0≤j

3 仿真結(jié)果與分析

將提出的3×3核BP譯碼算法與文獻[12]提出的SC譯碼算法從糾錯能力方面進行比對,從而驗證高維BP譯碼算法的有效性。本文的仿真環(huán)境參數(shù)如表1所示。

表1 仿真參數(shù)

為了評估本文所提出的高維BP譯碼算法的性能,通過仿真碼長為35、碼率為0.5的極化碼的FER以及實際計算不同碼長下所需的計算單元,即為譯碼時延,并復現(xiàn)了文獻[12]的SC譯碼算法結(jié)果作為對比,如圖5所示。

圖5 35碼長下BP譯碼算法與SC譯碼算法性能比較 Fig.5 Performance comparison of BP decoding algorithm and SC decoding algorithm under 35

與串行消去譯碼算法相比,BP譯碼算法具有時延低、吞吐量大、易于實現(xiàn)軟信息交互等優(yōu)勢。本文通過譯碼算法所需計算單元數(shù)量來等效替代譯碼算法的時延?？紤]計算資源充足情況下的具體結(jié)果如表2所示。

表2 SC譯碼算法與 BP 譯碼算法時延對比

由圖5與表2可以看出,BP譯碼算法在低信噪比的情況下,FER性能明顯優(yōu)于SC譯碼算法;在高信噪比的情況下,雖然BP譯碼算法略差于SC譯碼算法方法,但是BP譯碼算法的時延要好于SC譯碼算法。綜上,高維BP譯碼算法在低信噪比、通信條件較差時,將會是優(yōu)于SC譯碼算法的選擇,若通信場景對于時延有著較高的要求,亦可考慮BP譯碼算法。

4 結(jié)論

本文主要將已有的BP譯碼算法推廣至3×3大核BP譯碼算法,并且在35碼長下將其與使用較多的SC譯碼算法性能上做了比較,結(jié)果顯示在低信噪比的環(huán)境下,3×3大核BP譯碼算法FER性能優(yōu)于高維SC譯碼算法性能。同時,3×3大核BP譯碼算法在譯碼時延上相較于SC譯碼算法更具優(yōu)勢,在相同的硬件環(huán)境下,對通信時延有著更高要求的應用場景,可以考慮使用大核BP譯碼算法替代SC譯碼算法。接下來研究的重點是提升高維BP譯碼算法的糾錯能力以及在其他碼長下BP譯碼的糾錯能力。