基于偏移最小和的LDPC譯碼改進(jìn)算法

陳發(fā)堂, 李賀賓, 李平安

(重慶郵電大學(xué)通信與信息工程學(xué)院, 重慶 400065)

scheduling

0 引 言

低密度奇偶校驗(yàn)碼(low density paritycheck, LDPC)是1963年由Gallarger提出[1],后又被MacKay和Neal研究的線(xiàn)性分組碼[2]。LDPC碼的校驗(yàn)矩陣具有稀疏特性,其碼長(zhǎng)與復(fù)雜度呈線(xiàn)性關(guān)系,當(dāng)碼長(zhǎng)足夠長(zhǎng)時(shí),其性能可以接近理論香農(nóng)極限[3],目前已經(jīng)被多種通信標(biāo)準(zhǔn)所采用[4-6]。

LDPC碼可以使用消息傳遞性算法迭代譯碼,該算法可以被分類(lèi)為最優(yōu)、準(zhǔn)最優(yōu)和次優(yōu)。最優(yōu)迭代譯碼由置信傳播(belief propagation, BP)算法[7-8]執(zhí)行,代價(jià)是復(fù)雜度增加、計(jì)算不穩(wěn)定以及對(duì)熱噪聲估計(jì)誤差的依賴(lài)。最小和(min-sum, MS)算法[9]執(zhí)行次優(yōu)迭代譯碼,比BP算法簡(jiǎn)單,并且獨(dú)立于熱噪聲估計(jì)誤差。MS算法的次優(yōu)性是由于對(duì)校驗(yàn)節(jié)點(diǎn)消息的高估,造成了譯碼性能的損失。為了恢復(fù)MS算法相對(duì)于BP算法的性能損失,學(xué)者們提出了不同的優(yōu)化算法,稱(chēng)這種算法為準(zhǔn)最優(yōu)算法。準(zhǔn)最優(yōu)算法的性能既非常接近BP算法,同時(shí)又保留了MS算法的主要特征,即低復(fù)雜度和相對(duì)于噪聲方差估計(jì)的獨(dú)立性。最基本的校正優(yōu)化算法是歸一化最小和(normalized min-sum,NMS)算法和偏移最小和(offset min-sum,OMS)算法,分別通過(guò)引入歸一化因子和偏移因子來(lái)修正校驗(yàn)節(jié)點(diǎn)消息的幅度,提高譯碼性能[10-11]。文獻(xiàn)[12]利用參數(shù)估計(jì)理論對(duì)MS算法進(jìn)行改進(jìn),使用文獻(xiàn)[13]中的線(xiàn)性最小均方誤差(linear minimum mean square error,LMMSE)準(zhǔn)則提出LMMSE-MS算法,該算法使用黃金分割搜索算法對(duì)參數(shù)進(jìn)行優(yōu)化,在增加少量復(fù)雜度的情況下,提高譯碼性能。文獻(xiàn)[14]在OMS算法的基礎(chǔ)上,提出了一種基于新型偏移因子的MS(new offset min-sum,NOMS)算法,該偏移因子通過(guò)最小均方誤差估計(jì)過(guò)程公式化,然后通過(guò)優(yōu)化均方誤差獲得最優(yōu)的偏移因子值,使用該偏移因子可以提高算法的譯碼性能和收斂速度。文獻(xiàn)[15]在NMS算法的基礎(chǔ)上,提出了基于密度進(jìn)化(density evolution,DE)理論[16]的DE-NMS算法,該算法通過(guò)密度進(jìn)化理論求出歸一化因子序列,通過(guò)對(duì)歸一化因子序列做加權(quán)平均處理得到更精確的歸一化因子以提高譯碼算法的譯碼性能。

雖然以上優(yōu)化算法都提高了譯碼性能,但在校驗(yàn)節(jié)點(diǎn)的更新過(guò)程中沒(méi)有考慮第一最小值和第二最小值的區(qū)別。因此,譯碼性能有待進(jìn)一步提高。本文在OMS算法的基礎(chǔ)上提出了一種基于次序統(tǒng)計(jì)量的OMS(order statistics OMS, OR-OMS)算法,使用兩個(gè)不同的偏移因子分別對(duì)第一最小值和第二最小值進(jìn)行修正,利用次序統(tǒng)計(jì)量理論推導(dǎo)出兩個(gè)偏移因子的值,并且使用分層調(diào)度的消息傳遞方式。仿真結(jié)果表明所提算法與其他改進(jìn)的MS算法相比,擁有更好的譯碼性能和收斂速度。

1 BP算法及其改進(jìn)算法

令H=[hmn]為L(zhǎng)DPC碼的校驗(yàn)矩陣,ρ和γ分別為其行重和列重。變量節(jié)點(diǎn)集合N(m)={n:hmn=1}代表校驗(yàn)矩陣第m行中所有的非0元素;校驗(yàn)節(jié)點(diǎn)集合M(n)={m:hmn=1}代表校驗(yàn)矩陣第n列中所有的非0元素;N(m) 定義為集合N(m)中除了第n個(gè)元素以外的所有元素;M(n)m定義為集合M(n)中除了第m個(gè)元素以外的所有元素。令c={c0,c1,…,cN}為經(jīng)過(guò)編碼后的二進(jìn)制LDPC碼字,經(jīng)過(guò)BPSK調(diào)制后得到傳輸序列x={x0,x1,…,xN},其中xn=1-2cn(n=1,2,…,N)。傳輸序列經(jīng)過(guò)加性高斯白噪聲(additive white Guassian noise, AWGN)信道傳輸后得到接收序列y={y0,y1,…,yN},其中yn=xn+vn,vn為均值為0、方差為N0/2的高斯白噪聲。

1.1 BP算法

BP譯碼算法的譯碼過(guò)程以校驗(yàn)矩陣H為基礎(chǔ),校驗(yàn)矩陣中的每一個(gè)非0元素在Tanner圖[17]中分別代表一條邊,對(duì)數(shù)似然比(log likelihood ratio,LLR)消息沿著Tanner圖中的邊在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間進(jìn)行迭代。在每一次迭代的過(guò)程中,首先將變量節(jié)點(diǎn)消息傳遞給校驗(yàn)節(jié)點(diǎn)并更新校驗(yàn)節(jié)點(diǎn)消息,然后將更新后的校驗(yàn)節(jié)點(diǎn)消息傳遞給變量節(jié)點(diǎn)更新變量節(jié)點(diǎn)消息,接著進(jìn)行下一次迭代,直到達(dá)到最大迭代次數(shù)或者得到正確碼字。BP算法譯碼過(guò)程如下。

(1)初始化

將校驗(yàn)矩陣中每一個(gè)非0元素hmn對(duì)應(yīng)的變量節(jié)點(diǎn)消息Zmn初始化為接收到的信道消息:

(1)

(2)迭代處理

步驟 1校驗(yàn)節(jié)點(diǎn)消息更新(C2V)

(2)

式中:i為第i次迭代過(guò)程。

步驟 2變量節(jié)點(diǎn)消息更新(V2C)

(3)

步驟 3譯碼判決

(4)

硬判決規(guī)則

(5)

(3)終止準(zhǔn)則

1.2 MS算法

BP算法是一種理想算法,在實(shí)現(xiàn)過(guò)程中有兩個(gè)難點(diǎn):一是在式(1)中,噪聲方差應(yīng)該是已知的,但是在實(shí)際應(yīng)用中很難估計(jì)噪聲的精確值,尤其是當(dāng)信噪比比較低時(shí),噪聲估計(jì)的偏差將極大地惡化譯碼性能。二是式(2)的計(jì)算過(guò)于復(fù)雜,不利于硬件實(shí)現(xiàn)。

針對(duì)第二個(gè)問(wèn)題提出了MS算法,其C2V過(guò)程簡(jiǎn)化為

(6)

MS算法將C2V過(guò)程中的非線(xiàn)性計(jì)算修改為比較過(guò)程,計(jì)算復(fù)雜度大大降低。

1.3 OMS算法

雖然MS算法降低了譯碼復(fù)雜度,但在C2V過(guò)程中擴(kuò)大了校驗(yàn)節(jié)點(diǎn)消息的幅度值,導(dǎo)致譯碼性能損失。OMS算法通過(guò)使用偏移因子對(duì)式(6)的結(jié)果進(jìn)行修正,其C2V為

(7)

偏移因子可以通過(guò)下式獲得：

β=E(|L2|)-E(|L1|)

(8)

2 提出的OR-OMS算法

2.1 次序統(tǒng)計(jì)量理論

設(shè)X1,X2,…，XN為N個(gè)獨(dú)立、同分布的隨機(jī)變量,概率密度函數(shù)(probability density function, PDF)為f(x),累積分布函數(shù)(cumulative distribution function, CDF)為F(x)。通過(guò)遞增的順序排列這些變量,獲取相應(yīng)的次序統(tǒng)計(jì)量排序后的結(jié)果記為X1:N,X2:N,…，XN:N,其中X1:N為最小值,XN:N為最大值[18]。X1:N,X2:N,…，XN:N中第i個(gè)次序統(tǒng)計(jì)量Xi:N的PDF為

(9)

Xi1:N,Xi2:N,…，Xik:N(1≤i1

(10)

2.2 OMS算法分析

(11)

(12)

式中:β1和β2分別為第一最小值偏移因子和第二最小值偏移因子;L21和L11是在n≠index的情況下分別通過(guò)式(11)和式(2)獲取;L22和L12是在n=index的情況下分別通過(guò)式(11)和式(2)獲取。

2.3 最優(yōu)β1和β2值計(jì)算

(13)

Xi的CDF為

(14)

根據(jù)式(9),集合{Xi}的第一最小值的PDF為

fX1:ρ(x1:ρ)=ρ(1-FXi(x1:ρ))ρ-1fXi(x1:ρ)

(15)

集合{Xi}的第二最小值的PDF為

fX2:ρ(x2:ρ)=ρ(ρ-1)FXi(x2:ρ)(1-FXi(x2:ρ))ρ-2fXi(x2:ρ)

(16)

因此,E(|L21|)和E(|L22|)的計(jì)算公式為

(17)

(18)

在給定信噪比Eb/N0和碼率的情況下,根據(jù)式(17)和式(18)可以求出E(|L21|)和E(|L22|)的值。同時(shí)可以得到E(|L2|)的表達(dá)式為

E(|L2|)=pE(|L21|)+(1-p)E(|L22|)

(19)

式中:p為變量Xi為集合N(m)第一最小值的概率，p=1/ρ。

接下來(lái)開(kāi)始推導(dǎo)E(|L11|)和E(|L12|)的表達(dá)式,當(dāng)n=index時(shí),根據(jù)式(2)可知L12的表達(dá)式為

(20)

(21)

由式(21)可以得到E(|L12|)的表達(dá)式為

(22)

很明顯可以看出,式(22)只適用于ρ值較小的情況,當(dāng)ρ值過(guò)大時(shí),計(jì)算過(guò)于復(fù)雜,很難計(jì)算出實(shí)際值。此處可以借助大數(shù)定理[19]對(duì)E(|L12|)的值進(jìn)行估計(jì),大數(shù)定理的定義如下:

(23)

根據(jù)上述定理,可以證明當(dāng)重復(fù)次數(shù)非常大時(shí),|L12|的平均值最終會(huì)收斂于E(|L12|)。由此可以得出E(|L12|)具體估計(jì)過(guò)程如下:

步驟 1生成一組滿(mǎn)足式(14)分布的隨機(jī)變量X1,X2,…，Xn。

步驟 2找出這組隨機(jī)序列的最小值Xmin。

步驟 3通過(guò)式(20)計(jì)算L12。

步驟 4重復(fù)上述過(guò)程,直至達(dá)到最大重復(fù)次數(shù)。

步驟 5計(jì)算E(|L12|)的值。

在實(shí)際應(yīng)用中,當(dāng)ρ值較小時(shí)可以使用式(22)計(jì)算E(|L12|)的值;當(dāng)ρ值較大時(shí),通過(guò)大數(shù)定理估計(jì)出E(|L12|)的值。

對(duì)于E(|L11|)的計(jì)算,如果通過(guò)次序統(tǒng)計(jì)量進(jìn)行推導(dǎo),從E(|L12|)的計(jì)算可以看出,E(|L11|)的計(jì)算會(huì)更加復(fù)雜。可以通過(guò)E(|L1|)、E(|L12|)對(duì)E(|L11|)進(jìn)行求解,由式(19)可以得出

E(|L1|)=pE(|L11|)+(1-p)E(|L12|)

(24)

(25)

由式(24)和式(25)可知,只要計(jì)算出E(|L1|)就可以得到E(|L11|),根據(jù)式(2)可以得到E(|L1|)的計(jì)算公式如下:

(26)

為了方便計(jì)算E(|L1|),定義

(27)

由泰勒級(jí)數(shù)可知

(28)

因?yàn)槭?28)中α,α3,α5,…符號(hào)相同,所以

(29)

令μk=E(|α|k),因?yàn)閧Xi}為獨(dú)立、同分布,所以

(30)

通過(guò)式(13)和式(30)可以計(jì)算出對(duì)應(yīng)的μk,由式(29)可知

(31)

一般取式(31)的前幾項(xiàng)就可以估算出E(|L1|)的值,然后通過(guò)式(25)可以計(jì)算出E(|L11|)的值,進(jìn)而可以求出最優(yōu)的β1和β2的值。校驗(yàn)節(jié)點(diǎn)消息更新由式(7)可以?xún)?yōu)化為

(32)

2.4 分層譯碼結(jié)構(gòu)

傳統(tǒng)OMS算法的消息傳遞采用洪泛(flooding)調(diào)度[20]方式,所有校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)消息并行傳播,每次迭代更新的外部消息只能用于下一次迭代過(guò)程,外部消息利用率低。為了充分利用新產(chǎn)生的外部消息,提出的OR-OMS算法采用分層調(diào)度[20]的消息傳遞方式,在迭代的過(guò)程中一次只更新一個(gè)校驗(yàn)節(jié)點(diǎn)消息,然后將新產(chǎn)生的校驗(yàn)節(jié)點(diǎn)消息傳遞給與它關(guān)聯(lián)的變量節(jié)點(diǎn)。文獻(xiàn)[21]已經(jīng)證明分層調(diào)度相比于洪泛調(diào)度收斂速度提升一倍,并且沒(méi)有增加復(fù)雜度。

針對(duì)OR-OMS算法設(shè)計(jì)了合適的分層譯碼結(jié)構(gòu),如圖1所示。圖中FIFO代表先入先出(first input first output)。

首先將每一層的V2C消息并存于FIFO,并且將V2C消息的符號(hào)進(jìn)行存儲(chǔ)。然后對(duì)于校驗(yàn)節(jié)點(diǎn),篩選出V2C消息的第一最小值和第二最小值及其索引,并將它們輸入到C2V selector中更新校驗(yàn)節(jié)點(diǎn)信息。最后通過(guò)更新后的校驗(yàn)節(jié)點(diǎn)信息生成判決消息,同時(shí)將更新后的校驗(yàn)節(jié)點(diǎn)信息存儲(chǔ)在C2V registers中,此時(shí)完成了一層的譯碼。由上可知該譯碼器結(jié)構(gòu)不需要為判決消息分配內(nèi)存空間,并且在V2C消息更新的過(guò)程中,可以直接使用C2V registers中的校驗(yàn)節(jié)點(diǎn)信息和V2C Sign FIFO中的符號(hào)值進(jìn)行計(jì)算,避免對(duì)校驗(yàn)節(jié)點(diǎn)進(jìn)行多次計(jì)算,降低了計(jì)算復(fù)雜度。OR-OMS算法具體流程如算法1所示。

算法 1 OR-OMS算法1:初始化所有L0mn=0,Z0mn=Z0n and Imax2:for m=1:M3: for every n∈N(m)4: 使用式(32)計(jì)算Limn5: end for6: for every n∈N(m)7: 使用式(3)計(jì)算Zimn8: 使用式(4)計(jì)算Zin9: end for10:end for11:通過(guò)式(5)得到硬判決譯碼結(jié)果c^=[c^1,c^2,…,c^n]12:ifA·c^T=0 or i=Imax13: 輸出譯碼結(jié)果c^=[c^1,c^2,…,c^n]14:else15: 返回到步驟216:end if

3 仿真分析

本次仿真使用5G NR標(biāo)準(zhǔn)中的準(zhǔn)循環(huán)LDPC(quasi-cyclic LDPC, QC-LDPC)碼[22],并在Matlab平臺(tái)通過(guò)模擬AWGN信道,使用二進(jìn)制相移鍵控(binary phase shift keying, BPSK)調(diào)制方式進(jìn)行傳輸。通過(guò)大量的仿真對(duì)所提出的OR-OMS算法性能進(jìn)行評(píng)估,并將它與BP算法、MS算法、OMS算法、LMMSE-MS算法、NOMS算法、和DE-NMS算法的性能進(jìn)行比較分析。

圖2和圖3為各譯碼算法在不同信噪比下的誤碼性能對(duì)比,圖2使用的是基圖1情況下的(2 176,704)QC-LDPC碼,偏移因子β1和β2分別為0.304和0.373,最大迭代次數(shù)設(shè)置為20。

從圖2中可以看出,OR-OMS算法、LMMSE-MS算法、NOMS算法、DE-NMS算法4種基于MS算法改進(jìn)的譯碼算法相對(duì)于OMS算法性能都有明顯的提升,其中OR-OMS算法和LMMSE-MS算法的譯碼性能優(yōu)于NOMS算法和DE-NMS算法,但OR-OMS算法的性能更加接近于BP算法。圖3使用的是基圖2情況下的(3 328,640)QC-LDPC碼,偏移因子β1和β2分別為0.326和0.389,最大迭代次數(shù)設(shè)置為20。

從圖3中可以看出,各譯碼算法的譯碼性能相對(duì)于圖2都有所提升,并且分布趨勢(shì)基本相同,所提出的OR-OMS算法譯碼性能更加優(yōu)于LMMSE-MS算法。從圖2和圖3可以看出在誤比特率為10-5時(shí),OR-OMS算法與OMS算法相比可以獲得約0.35 dB左右的增益。

4 復(fù)雜度分析

基于MS算法改進(jìn)的OMS算法、DE-NMS算法、NOMS算法、LMMSE-MS算法、OR-OMS算法本質(zhì)上還是MS算法。主要的區(qū)別在于OMS算法通過(guò)蒙特卡羅方法計(jì)算偏移因子的最優(yōu)值。DE-NMS算法通過(guò)DE理論推導(dǎo)出最優(yōu)偏移因子值。NOMS算法通過(guò)最小均方誤差估計(jì)將偏移因子公式化,然后通過(guò)優(yōu)化均方誤差獲得最優(yōu)的偏移因子值。LMMSE-MS算法通過(guò)利用最小均方誤差估計(jì)準(zhǔn)則對(duì)校驗(yàn)變量信息的大小進(jìn)行建模并計(jì)算估計(jì)參數(shù),進(jìn)而利用黃金分割搜索算法確定最優(yōu)參數(shù)值。OR-OMS算法則通過(guò)次序統(tǒng)計(jì)量理論推導(dǎo)出第一最小值和第二最小值分別對(duì)應(yīng)的最優(yōu)偏移因子值。

表1為一次迭代過(guò)程中,各算法校驗(yàn)節(jié)點(diǎn)更新所需的計(jì)算復(fù)雜度。Nρ為校驗(yàn)矩陣中元素‘1’的總個(gè)數(shù),M為校驗(yàn)矩陣的列數(shù)。從表中可以看出,BP的復(fù)雜度最高,MS算法的復(fù)雜度最低。由于在硬件實(shí)現(xiàn)的過(guò)程中,偏移因子的值先通過(guò)Matlab工具計(jì)算,再存儲(chǔ)到硬件中。因此,OMS算法、DE-NMS算法、NOMS算法、OR-OMS算法的復(fù)雜度相同,LMMSE-MS算法的復(fù)雜度略高于這些算法。

表1 一次迭代過(guò)程校驗(yàn)節(jié)點(diǎn)更新計(jì)算復(fù)雜度

在硬件實(shí)現(xiàn)的過(guò)程中,算法的整體復(fù)雜度不僅與單次迭代過(guò)程中校驗(yàn)節(jié)點(diǎn)更新的復(fù)雜度有關(guān),還和算法總的迭代次數(shù)有關(guān)。圖4為各算法在不同信噪比下的平均迭代次數(shù)。

由于OR-OMS算法采用分層調(diào)度的信息傳遞方式,從圖4中可以明顯看出,OR-OMS算法的收斂性能最好,所需的平均迭代次數(shù)最少，其次為BP算法、OMS算法、DE-NMS算法、NOMS算法、LMMSE-MS算法的收斂性能近似,MS算法的收斂性能最差。結(jié)合單次迭代過(guò)程中校驗(yàn)節(jié)點(diǎn)更新所需的計(jì)算復(fù)雜度,可以得出在實(shí)際應(yīng)用過(guò)程中,所提出的OR-OMS算法總體上來(lái)說(shuō)要擁有更低的復(fù)雜度,具有實(shí)際應(yīng)用價(jià)值。

5 結(jié) 論

本文提出了一種改進(jìn)的OMS算法,所提算法針對(duì)校驗(yàn)節(jié)點(diǎn)更新過(guò)程中第一最小值和第二最小值的問(wèn)題,分別使用兩個(gè)不同的偏移因子對(duì)第一最小值和第二最小值進(jìn)行校正,利用次序統(tǒng)計(jì)量理論推導(dǎo)出兩個(gè)偏移因子的最優(yōu)值,提高譯碼算法的譯碼性能。所提算法使用分層調(diào)度的消息傳遞方式,擁有更快的收斂速度。仿真結(jié)果表明,對(duì)于5G NR標(biāo)準(zhǔn)的QC-LDPC碼,所提算法相比OMS算法擁有更好的譯碼性能,并且降低了譯碼迭代次數(shù);與目前譯碼性能最好的LMMSE算法相比,在具有相似譯碼性能的情況下,擁有更低的計(jì)算復(fù)雜度。