楊衛(wèi)國

(海軍航空大學, 山東 煙臺 264001)

基于減少過估計的改進LDPC碼最小和譯碼算法*

楊衛(wèi)國

(海軍航空大學, 山東 煙臺 264001)

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

LDPC碼; 最小和算法; 過估計; 最小值; 次小值

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

1 最小和(MS)譯碼算法

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

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

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

(1)

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

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

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

(2)

2)校驗節(jié)點更新:根據(jù)式(3),對在第l次迭代時的校驗節(jié)點信息進行更新。

(3)

3)變量節(jié)點更新:根據(jù)式(4),對在第l次迭代時的校驗節(jié)點信息進行更新。

(4)

4)譯碼判決

計算所有變量節(jié)點的判決消息

(5)

1.2 最小和譯碼算法

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

(6)

1.3 改進的MS譯碼算法

(7)

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

(8)

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

2 本文的改進最小和譯碼算法

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

(9)

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

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

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

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

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

證明如下:

(10)

式中,符號“⊙”表示和積運算,基本關(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的對數(shù)函數(shù)和指數(shù)函數(shù)均為單調(diào)增函數(shù),因此,當a和b均為正數(shù)時,式(12)的值為負數(shù),證明了最小和算法是對對數(shù)域置信傳播算法的過估計。

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

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

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

2.2 改進算法

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

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

(13)

改進后的最小和算法流程圖如圖2所示。

圖2 改進MS譯碼算法流程圖

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

3 仿真分析

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

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

表2 兩種算法估計值與真實值

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

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

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

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

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

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

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

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

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

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

圖6 不同譯碼算法性能對比

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

4 結(jié)束語

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

[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].遙測遙控,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] 張立軍,劉明華,盧萌.低密度奇偶校驗碼加權(quán)大數(shù)邏輯譯碼研究[J].西安交通大學學報,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].華中科技大學學報(自然科學版),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

國家自然科學基金資助項目(61671463)

楊衛(wèi)國(1987-),男,山東煙臺人,碩士研究生,研究方向為信道編碼。