3×3核矩陣極化碼的BP譯碼算法

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

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

0 引言

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

基于2×2核的極化碼BP譯碼算法通過級聯的方式推廣至基于3×3核矩陣極化碼。基于2×2核的極化碼BP譯碼算法信息更新公式,給出了3×3核內部最小計算單元的信息更新公式。基于最小單元信息更新公式給出了3×3核極化碼的BP譯碼算法流程。基于3×3核矩陣下的極化碼,相較于2×2核構造的極化碼,碼長更具豐富性,相較于串行譯碼算法中的SC譯碼算法,在35碼長下,BP譯碼算法在1～4 dB的信噪比下,譯碼性能更具優勢,在信噪比大于4 dB的情況下,BP譯碼算法性能稍弱于SC譯碼算法,由于BP譯碼算法具有并行譯碼結構,相較于SC譯碼算法,BP譯碼時延降低了約50%。

1 相關工作

1.1 符號說明

(1)

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

(2)

(3)

1.2 極化碼的構造

1.3 極化碼的BP譯碼算法

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

圖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在因子圖相鄰節點之間進行信息傳遞以及迭代更新,其中每次迭代更新遵循如下：

(4)

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

(5)

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

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

(6)

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

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

(7)

(8)

(9)

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

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

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

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

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

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

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

(10)

右信息更新如下：

(11)

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

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

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

3 仿真結果與分析

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

表1 仿真參數

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

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

與串行消去譯碼算法相比,BP譯碼算法具有時延低、吞吐量大、易于實現軟信息交互等優勢。本文通過譯碼算法所需計算單元數量來等效替代譯碼算法的時延。考慮計算資源充足情況下的具體結果如表2所示。

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

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

4 結論

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