基于減少過估計(jì)的改進(jìn)LDPC碼最小和譯碼算法*

楊衛(wèi)國

(海軍航空大學(xué), 山東 煙臺(tái) 264001)

基于減少過估計(jì)的改進(jìn)LDPC碼最小和譯碼算法*

楊衛(wèi)國

(海軍航空大學(xué), 山東 煙臺(tái) 264001)

為了更好地在LDPC碼的譯碼中使用最小和算法,盡量減少最小和算法譯碼過程中的性能損失,對(duì)最小和譯碼算法進(jìn)行了深入研究,通過對(duì)最小和算法的原理分析得出,其性能損失的根源是算法過程中產(chǎn)生了過估計(jì),而過估計(jì)的大小與最小值和次小值之間的差值相關(guān),基于此,提出了一種減少過估計(jì),以提高最小和算法性能的改進(jìn)譯碼算法,通過仿真分析,該算法在幾乎不增加復(fù)雜度的情況下獲得了較好的譯碼性能。

LDPC碼; 最小和算法; 過估計(jì); 最小值; 次小值

低密度奇偶校驗(yàn)碼(Low-Density Parity-Check Codes)是一類性能接近香農(nóng)極限的線性糾錯(cuò)碼,由于其擁有優(yōu)于Turbo碼的良好性能,使得LDPC碼在目前許多通信系統(tǒng)中得以應(yīng)用,并在去年被國際移動(dòng)通信標(biāo)準(zhǔn)化組織確定為5G數(shù)據(jù)信道編碼方案。當(dāng)LDPC碼的碼長趨于無限長且校驗(yàn)矩陣對(duì)應(yīng)的Tanner圖中無環(huán)時(shí),置信傳播(Belief Propagation,BP)譯碼算法是其最優(yōu)迭代譯碼算法。BP譯碼算法雖然性能優(yōu)異,但算法本身需要大量的乘法運(yùn)算,計(jì)算復(fù)雜度較高,硬件實(shí)現(xiàn)困難,這也是Gallager在提出LDPC碼初期不被人們認(rèn)可的主要原因之一。后來人們提出了對(duì)數(shù)域BP譯碼算法,將原算法中大量的乘法運(yùn)算變成了加法運(yùn)算,大大降低了運(yùn)算量的同時(shí)引入了雙曲正切函數(shù),工程實(shí)踐中仍然難于實(shí)現(xiàn),直到1999年Fossorier等學(xué)者提出了最小和(Min Sum,MS)譯碼算法,較好地平衡了譯碼性能和譯碼復(fù)雜度之間的矛盾,使硬件實(shí)現(xiàn)變得簡(jiǎn)單。之后又出現(xiàn)了一系列改進(jìn)的MS算法,都是基于縮小MS算法與BP算法之間的性能差距。

1 最小和(MS)譯碼算法

1.1 對(duì)數(shù)域BP譯碼算法

最小和譯碼算法是基于對(duì)數(shù)域BP譯碼算法提出的,對(duì)數(shù)域BP譯碼算法是將概率域BP譯碼算法傳遞的概率信息變換為對(duì)數(shù)似然比信息,這樣可以將大量的乘法運(yùn)算變?yōu)榧臃ㄟ\(yùn)算,降低譯碼復(fù)雜度,減少運(yùn)算時(shí)間,具體的LLR-BP譯碼算法如下:

首先定義對(duì)數(shù)似然比,對(duì)二元LDPC碼,其接收信號(hào)對(duì)數(shù)似然比的表達(dá)式為

(1)

據(jù)此,將概率域BP譯碼算法的步驟轉(zhuǎn)換到對(duì)數(shù)域得：

1)初始化:根據(jù)來自信道的碼字信息y=(y1,y2,…yn),初始化所有變量節(jié)點(diǎn)信息

L(0)(qij)=L(yi),i=1,2,…,n

(2)

2)校驗(yàn)節(jié)點(diǎn)更新:根據(jù)式(3),對(duì)在第l次迭代時(shí)的校驗(yàn)節(jié)點(diǎn)信息進(jìn)行更新。

(3)

3)變量節(jié)點(diǎn)更新:根據(jù)式(4),對(duì)在第l次迭代時(shí)的校驗(yàn)節(jié)點(diǎn)信息進(jìn)行更新。

(4)

4)譯碼判決

計(jì)算所有變量節(jié)點(diǎn)的判決消息

(5)

1.2 最小和譯碼算法

前文提到,LLR-BP譯碼算法一定程度上降低了譯碼復(fù)雜度,當(dāng)引入了雙曲正切函數(shù),實(shí)際應(yīng)用中計(jì)算量仍然比較大,Fossorier等人根據(jù)雙曲正切函數(shù)的特點(diǎn),將概率域BP譯碼算法中的校驗(yàn)節(jié)點(diǎn)更新規(guī)則式(3)改寫為式(6),其中復(fù)雜的乘除運(yùn)算就可以簡(jiǎn)化為加法運(yùn)算和比較運(yùn)算,大幅度降低了譯碼復(fù)雜度。

(6)

1.3 改進(jìn)的MS譯碼算法

(7)

在式(6)中加入加性因子β(β>0),即得偏置最小和(OMS)譯碼算法:

(8)

兩種算法均在幾乎不增加MS算法復(fù)雜度的情況下,一定程度地改善了譯碼性能。

2 本文的改進(jìn)最小和譯碼算法

通過對(duì)上述兩種改進(jìn)MS算法的分析,MS譯碼算法是將LLR-BP譯碼算法中校驗(yàn)節(jié)點(diǎn)的更新值進(jìn)行了過估計(jì),即

(9)

2.1 影響MS譯碼算法性能的主要因素

由于MS譯碼算法是對(duì)LLR-BP譯碼算法中校驗(yàn)節(jié)點(diǎn)輸出消息可靠度的過估計(jì),不妨直接用計(jì)算機(jī)求出兩種譯碼算法中校驗(yàn)節(jié)點(diǎn)的輸出消息,觀察影響MS譯碼算法估計(jì)值的因素。

例假設(shè)某校驗(yàn)節(jié)點(diǎn)c1的輸入信息為(0.7,8.5,5.1,2.3)(由于只討論兩種算法數(shù)值之間的差距,故全部取正值),分別對(duì)應(yīng)變量節(jié)點(diǎn)v1,v2,v3和v4,則兩種算法對(duì)應(yīng)的變量節(jié)點(diǎn)的輸入信息如表1所示。

表1 兩種算法數(shù)值比較

通過觀察表1后三行不難發(fā)現(xiàn),MS算法取值不變,但LLR-BP算法取值變化范圍較大,變量節(jié)點(diǎn)v2和v3對(duì)應(yīng)的值幾乎相等,與最小值之間的差距超過了0.1,而變量節(jié)點(diǎn)v4對(duì)應(yīng)的值幾乎與最小值相等,相差不到0.01。三組數(shù)據(jù)最大的不同在于最小值與次小值之間的距離,不妨大膽猜測(cè):影響MS譯碼算法估計(jì)值與真實(shí)值之間差距的主要因素是最小值與次小值之間的距離,距離越大,估計(jì)值越接近真實(shí)值。表1變量節(jié)點(diǎn)v1對(duì)應(yīng)的值也間接證明了猜測(cè)的觀點(diǎn)。

證明如下:

(10)

式中,符號(hào)“⊙”表示和積運(yùn)算,基本關(guān)系式如上式所示。

考慮到tanh(a/2)=(ea-1)/(ea+1),

=min(a,b)+f(|a+b|)-f(|a-b|)

(11)

式(11)中,f(x)=ln(1+e-x),代入式(11)后半部分得

f(|a+b|)-f(|a-b|)

=ln(1+e-(a+b))-ln(1+e-(b-a))

(12)

通過圖1可以看出,e的對(duì)數(shù)函數(shù)和指數(shù)函數(shù)均為單調(diào)增函數(shù),因此,當(dāng)a和b均為正數(shù)時(shí),式(12)的值為負(fù)數(shù),證明了最小和算法是對(duì)對(duì)數(shù)域置信傳播算法的過估計(jì)。

圖1 e的對(duì)數(shù)函數(shù)和指數(shù)函數(shù)圖

繼續(xù)對(duì)式(12)進(jìn)行分析,當(dāng)a和b之間的距離逐漸增大到無窮大時(shí),即b-a?∞,此時(shí)-(b-a)?-∞,-(a+b)?-∞,則e-(b-a)=0,e-(a+b)=0,式(12)等于0,估計(jì)值與實(shí)際值相等;當(dāng)a和b之間的距離逐漸縮小到無窮小時(shí),即b-a?0,此時(shí)-(a+b)?-2a,式(12)轉(zhuǎn)化為ln(1+e-2a)-ln2,因?yàn)閘n2>ln(1+e-2a)>0,因此估計(jì)值與實(shí)際值之間的差值不會(huì)超過ln2=0.6931,當(dāng)最小值a較大時(shí),基本可以忽略不計(jì),而當(dāng)a較小時(shí),這個(gè)差值的影響就會(huì)比較明顯。

由此可得,影響MS譯碼算法估計(jì)值與真實(shí)值之間差距的主要因素是最小值與次小值之間的距離以及最小值a的大小。此外,當(dāng)最小值與次小值之間的距離較小,且各值之間的方差較小時(shí),對(duì)估計(jì)值也有一定的影響。

2.2 改進(jìn)算法

根據(jù)前文提到的理論,MS譯碼算法其他步驟不變,校驗(yàn)節(jié)點(diǎn)更新規(guī)則如下:

1)首先將校驗(yàn)節(jié)點(diǎn)cj的外置信消息的絕對(duì)值|L(qij)|,按照從小到大的順序進(jìn)行排序,并確定門限值d;

(13)

改進(jìn)后的最小和算法流程圖如圖2所示。

圖2 改進(jìn)MS譯碼算法流程圖

從圖2中可以看出,改進(jìn)后的MS算法只是在原有的MS算法基礎(chǔ)上增加了排序和判斷兩個(gè)步驟,新的水平更新規(guī)則在每次迭代過程中增加了一次減法運(yùn)算和乘法運(yùn)算,算法復(fù)雜度基本沒有改變。

3 仿真分析

任意選取幾組數(shù)字,按照式(13)的更新規(guī)則進(jìn)行的估計(jì)值與實(shí)際值之間的差距如表2所示,根據(jù)前文的分析,當(dāng)β最大時(shí),取α+β/10=1,因此門限值d的取值為d=(1-ln2)*10≈3。

通過觀察表中數(shù)字不難發(fā)現(xiàn),本文提出的G-MS算法的估計(jì)值比MS算法更接近LLR-BP算法的真實(shí)值,且在β趨于3時(shí),MS算法的估計(jì)值與LLR-BP算法的真實(shí)值之間的差距已經(jīng)基本可以忽略,說明門限值d的取值也是合理的。

表2 兩種算法估計(jì)值與真實(shí)值

分別取碼長為114,570和1710的三種碼進(jìn)行性能仿真,碼率均為1/2,采用BPSK調(diào)制,傳輸信道選用高斯信道,采用本文提出的譯碼算法(G-MS算法)進(jìn)行譯碼仿真,迭代次數(shù)為10次,仿真結(jié)果如圖3所示。

圖3 G-MS算法譯碼性能仿真

從圖3中可以看出,無論是短碼還是長碼,三種碼在使用本文所提出的譯碼算法的情況下,均有較好的譯碼性能,當(dāng)碼長達(dá)到1710,在僅迭代10次的情況下,信噪比為3時(shí)的誤碼率已經(jīng)達(dá)到了10-6數(shù)量級(jí),譯碼性能比較優(yōu)異。

同等仿真條件下,對(duì)MS算法和本文提出譯碼算法進(jìn)行性能仿真,選取碼長為512的中短碼,仍然采用BPSK調(diào)制,傳輸信道為高斯信道,圖4所示為迭代10次的譯碼性能仿真。

圖4 MS算法與G-MS算法性能仿真

由于對(duì)MS算法中產(chǎn)生的過估計(jì)進(jìn)行了削弱,G-MS算法相比于傳統(tǒng)的MS算法更接近于LLR-BP譯碼算法的真實(shí)值,從仿真圖4中可以清楚地看出,本文所提出的譯碼算法在譯碼性能上比MS算法有較大的提高,在誤碼率為10-3數(shù)量級(jí)時(shí),有接近0.4dB的性能增益。

將本文提出的改進(jìn)型譯碼算法同LLR-BP譯碼算法進(jìn)行性能比較,碼字仍然選取1/2碼率,碼長為512的碼。采用BPSK調(diào)制,傳輸信道為高斯信道,迭代次數(shù)為10次,仿真結(jié)果如圖5。

圖5 LLR-BP算法與G-MS算法性能比較

從圖5中可以看出,在誤碼率小于1時(shí),兩種算法的性能幾乎一致,隨著信噪比的增大,LLR-BP算法的性能稍好于G-MS算法,當(dāng)信噪比達(dá)到3dB時(shí),本文提出的G-MS算法已經(jīng)有了超過LLR-BP譯碼算法的譯碼性能。

為了更好地觀察本文提出的譯碼算法的性能,分別采用LLR-BP譯碼算法、MS譯碼算法、NMS譯碼算法、OMS譯碼算法和本文提出的改進(jìn)MS譯碼算法(G-MS譯碼算法)對(duì)碼長為1024,碼率為1/2的碼進(jìn)行譯碼仿真,同樣采用BPSK調(diào)制,傳輸信道選用高斯信道,迭代次數(shù)為10次,其中NMS譯碼算法修正因子取α=0.8,OMS譯碼算法修正因子取β=0.2,仿真結(jié)果如圖6所示。

圖6 不同譯碼算法性能對(duì)比

從圖6中可以看出,低信噪比時(shí),本文提出的G-MS算法的譯碼性能與LLR-BP譯碼算法和NMS譯碼算法性能接近,在信噪比達(dá)到3dB時(shí),G-MS算法的誤碼率已經(jīng)優(yōu)于其他兩種算法,且由于NMS算法對(duì)于不同碼字、不同信噪比條件下的不同α值,譯碼性能會(huì)有不同的表現(xiàn),因此其穩(wěn)定性不及本文提出的譯碼算法;與OMS算法相比,本文提出的譯碼算法的誤碼率明顯優(yōu)于OMS算法的誤碼率。

4 結(jié)束語

本文通過對(duì)MS算法的原理分析,針對(duì)MS算法中對(duì)LLR-BP譯碼算法校驗(yàn)節(jié)點(diǎn)更新規(guī)則的過估計(jì),提出了改進(jìn)型MS譯碼算法,改進(jìn)后的譯碼算法在算法復(fù)雜度上并沒有太大增加,且通過仿真分析不難看出,本文所提出的譯碼算法,在誤碼率上與LLR-BP譯碼算法并沒有太大差距,甚至在大信噪比條件下有優(yōu)于LLR-BP譯碼算法的性能,與傳統(tǒng)MS譯碼算法和幾種改進(jìn)算法相比在性能上都有一定的優(yōu)勢(shì),且不需要根據(jù)碼字性能和信噪比調(diào)整修正因子,穩(wěn)定性較好,很好地做到了譯碼復(fù)雜度與譯碼性能的平衡。

[1] Gallager R.Low-density parity-check codes[J].Information Theory,IRE Transactions on Information Theory,1962,8(1):21-28.

[2] MacKay D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Transactions on Information Theory,1999,45(2):399-431.

[3] Ma Ke-xiang,Zhang Peng.Low-Delay Loop Detection Algorithm for LDPC Codes[J].Journal of CAEIT,2015,4(2):341-349.

[4] 李化營,王健,劉焱.LDPC碼改進(jìn)高速譯碼算法[J].遙測(cè)遙控,2015,36(2):47-53.

[5] Fossorier M P C.Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J].IEEE Transactions on Information Theory,2004,50(8):1788-1793.

[6] Tanner R M,Sridhara D,Sridharan A,et al.LDPC block and convolutional codes Based on circulant matrices[J].IEEE Transactions on Information Theory,2004,50(12):2966-2984.

[7] Gallager R G.Low-Density Parity-Check Codes[D].Cambridge,M A:MIT Press,1963.

[8] Chen X, Kang J, Lin S,et al.Memory System Optimization for FPGA-Based Implementation of Quasi-Cyclic LDPC Codes Decoders[J].IEEE Transactions on Circuits and Systems I:Regular Papers,2011,58(1):98-111.

[9] 張立軍,劉明華,盧萌.低密度奇偶校驗(yàn)碼加權(quán)大數(shù)邏輯譯碼研究[J].西安交通大學(xué)學(xué)報(bào),2013,47(4):35-38,50.

[10] Kumar,Pravin R.An efficient methodology for parallel concatenation of LDPC codes with reduced complexity and decoding delay[C]∥2013 National Conference on Rakhesh Singh Communications(NCC),2013.

[11] 黃勝,穆攀,賈雪婷,等.基于BIBD與基區(qū)組元素組合的QC-LDPC碼[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,44(9):16-19.

Modified LDPC Codes Min-sum Algorithm Based on Reducing the Over-estimation

YANG Wei-guo

(Navy Aeronautics University,Yantai 264001,China)

In order to reduce the loss so that we can make full use of the min-sum algorithm in LDPC codes decoding, this paper deeply researches in the min-sum algorithm. The analysis of the min-sum algorithm’s principle comes to that it is the over-estimation which is related to the difference of the minimum value and the second minimum value that leads to the loss. Thus, this paper proposes a modified min-sum algorithm by reducing the over-estimation.Simulations show that this algorithm is better than the traditional MS algorithm without increasing complexity.

LDPC codes; min-sum algorithm; over-estimation; minimum value; second minimum value

1673-3819(2017)06-0053-05

TN911.22；E917

A

10.3969/j.issn.1673-3819.2017.06.012

2017-08-20

2017-09-18

國家自然科學(xué)基金資助項(xiàng)目(61671463)

楊衛(wèi)國(1987-),男,山東煙臺(tái)人,碩士研究生,研究方向?yàn)樾诺谰幋a。