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

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

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

0 引言

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

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

1 相關(guān)工作

1.1 符號(hào)說明

(1)

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

(2)

(3)

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

1.3 極化碼的BP譯碼算法

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

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

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

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

(4)

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

(5)

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

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

(6)

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

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

(7)

(8)

(9)

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

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

2.1 基于3×3核的最小計(jì)算單元

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

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

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

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

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

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

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

(10)

右信息更新如下：

(11)

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

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

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

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

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

表1 仿真參數(shù)

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

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

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

表2 SC譯碼算法與 BP 譯碼算法時(shí)延對(duì)比

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

4 結(jié)論

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