基于BP算法的LDPC碼性能仿真

淮南師范學(xué)院 王千春

前言

1965年Gallager在他提出了Gallager碼，當(dāng)時(shí)人們對(duì)他的發(fā)現(xiàn)沒(méi)有任何重視，認(rèn)為他是天方夜譚，以至于這么偉大的發(fā)現(xiàn)在當(dāng)時(shí)被忽視了，由于科學(xué)技術(shù)的進(jìn)步和相關(guān)理論的發(fā)展，后人發(fā)現(xiàn)他在和其他譯碼相結(jié)合的情況下可以接近于香農(nóng)極限，因?yàn)長(zhǎng)DPC碼有著劃時(shí)代的意義。LDPC碼的特點(diǎn)是，比之前的譯碼方法更加靈活，接近于香農(nóng)極限，在即將到來(lái)的5G時(shí)代，LDPC碼必將通過(guò)它獨(dú)特的優(yōu)勢(shì)，為人類(lèi)進(jìn)入新的信息時(shí)代做出貢獻(xiàn)[1]。

1.LDPC碼的原理

LDPC代碼是一個(gè)非常特殊的線性分組碼。通過(guò)生成矩陣G，必須將線性分組碼的信息s轉(zhuǎn)換為轉(zhuǎn)移碼t，并且對(duì)應(yīng)于G的校驗(yàn)矩陣H滿足H×t = 0。LDPC碼驗(yàn)證矩陣的0個(gè)元素分量的個(gè)數(shù)大于非零元素的個(gè)數(shù)，屬于稀疏矩陣范疇[2]。

LDPC碼包括常規(guī)和非常規(guī)兩種編碼形式。假設(shè)LDPC碼的驗(yàn)證矩陣B是J×K的滿秩矩陣，則LDPC碼長(zhǎng)度為J，驗(yàn)證位K，則信息位是H= j-k，碼率r= h/ k。用Tanner圖表示如圖1所示。所謂的信息點(diǎn)（比特點(diǎn)）即是下邊N個(gè)節(jié)點(diǎn)所代表的N個(gè)碼字。因此，非規(guī)則碼包括規(guī)則碼，是它的一個(gè)特例。

圖1 校驗(yàn)矩陣對(duì)應(yīng)的Tanner圖

2.LDPC碼校驗(yàn)矩陣構(gòu)造

在介紹LDPC碼校驗(yàn)矩陣的構(gòu)造之前，首先闡述一下girth的概念。圖2中，粗線部分構(gòu)成了長(zhǎng)度為6的環(huán)，其中最短環(huán)的環(huán)長(zhǎng)稱(chēng)為該圖的girth。girth是構(gòu)造校驗(yàn)矩陣的非常重要的指標(biāo)[3]。二部圖中g(shù)irth的值越大，校驗(yàn)矩陣的性能就越好，一般要求girth最小為6。

圖2 校驗(yàn)矩陣的隨機(jī)構(gòu)造

本文采用Gallager構(gòu)造法，Gallager基于GF（2）域上定義的（n，j，k）LDPC碼，其校驗(yàn)矩陣H的構(gòu)造如下：

（1）將Gallager碼的監(jiān)督矩陣按行劃分成j個(gè)部分（每部分包含相同的行數(shù)），每一部分的每一列中只包含一個(gè)“1”。

（2）第一部分構(gòu)造的矩陣中，“1”比特在行中按降冪排列，在第一行中，第1到k個(gè)元素為“1”，其余為0；在第2行中，從第k+1到2k個(gè)元素為“1”，其余為0；如此安排，第i行中，從第k+1到第i個(gè)元素為“1”，其余為0。

（3）其余j-1部分的構(gòu)造是對(duì)第一部分進(jìn)行列的隨機(jī)重排。

該構(gòu)造法可以保證每列有j個(gè)“1”，每行有k個(gè)“1”。圖3給出了由Gallager構(gòu)造法構(gòu)造的（20，3，4）的LDPC碼校驗(yàn)矩陣，碼長(zhǎng)為20，j=3，k=4。

圖3 Gallager構(gòu)造的（30，5，6）的LDPC碼校驗(yàn)矩陣

3.LDPC碼的編碼

本文采用隨機(jī)構(gòu)造的LDPC碼的LU分解法[4]。對(duì)于LU分解法的想法，在I是非特異性隊(duì)伍的情況下，I可以分解為上三角隊(duì)U和下三角隊(duì)L的積，L和U也是MxN維的稀疏排列。

基本步驟如下：

（1）對(duì)H矩陣進(jìn)行LU分解，得到重排后的H、B、L、U。

（2）計(jì)算Z=BS。

（3）解方程得到Y(jié)，其中Y是M維列向量。

（4）通過(guò)反向消除法求解UC = Y，得到C。

LU分解的一個(gè)基本算法如下所示：

（1）設(shè)U和L為全零矩陣。

（2）設(shè)F=H。

（3）for i=1 to m

在F矩陣中找到同一列的非零元素。

對(duì)矩陣F和H的行列進(jìn)行重新組合，注意此元素必須位于他之前的位置，不可變化。

（4）把B矩陣設(shè)置為重排后的H矩陣最后N-M列。

4.LDPC碼的譯碼

LDPC碼的迭代譯碼方法是LDPC碼能夠得以迅速發(fā)展的主要原因，該譯碼方法使得LDPC碼不僅描述簡(jiǎn)單，譯碼復(fù)雜度低，而且可以并行操作，便于硬件實(shí)現(xiàn)，具有接近Shannon極限的優(yōu)異性能。

譯碼采用UMP BP-Based算法（最小和或最大積），LLR BP算法中節(jié)點(diǎn)[5]可變化為：

由于：

所以：

UMP（Uniformly Most Powerful）BP-Based算法又稱(chēng)為最小和（Min Sum）算法或最大積（Max Product）算法，該算法是用式來(lái)處理LLR BP算法中校驗(yàn)節(jié)點(diǎn)的消息，此時(shí)校驗(yàn)節(jié)點(diǎn)的迭代只有比較算法和加法運(yùn)算，計(jì)算的復(fù)雜度就大大降低了。對(duì)于加性高斯白噪聲信道，該算法不需要信道估計(jì)。

5.LDPC碼的仿真

在其他條件一定時(shí)，將碼長(zhǎng)設(shè)置為300、500以及1000，列重和迭代次數(shù)分別設(shè)置為2和20，進(jìn)行仿真，得到的結(jié)果如圖4所示。

圖4 碼長(zhǎng)不同時(shí)的仿真結(jié)果

從圖4的仿真圖像可以清楚地看出：在相同的SNR件下，LDPC碼的性能與代碼成正比，但與具有任何數(shù)值的情況相比，誤碼率不會(huì)根據(jù)代碼長(zhǎng)度的變化而改變，但是如果信噪比是與高于特定數(shù)值的情況相比，誤碼率開(kāi)始顯明顯著上升。這是因?yàn)榇a具有上限，隨著碼長(zhǎng)的增加，編碼的繁瑣程度也不斷提高，此時(shí)性能的增加便不會(huì)很明顯。

簡(jiǎn)言之，在相同的信噪比下，LDPC碼的性能與碼長(zhǎng)成正比，但是一旦信噪比低于某個(gè)值，誤碼率不會(huì)隨著代碼長(zhǎng)度而改變。但當(dāng)信噪比高于某個(gè)值時(shí)，誤碼率開(kāi)始迅速增加。這是因?yàn)槿魏未a長(zhǎng)度都有其自己理論上的編碼上限。

當(dāng)列重和代碼長(zhǎng)度選擇一定值時(shí)，Matlab軟件選擇三次不同的迭代次數(shù)進(jìn)行多次迭代。20，40，列重選擇2，代碼長(zhǎng)度選擇500，仿真結(jié)果如圖7所示。

圖5 迭代次數(shù)不同時(shí)的影響

從圖5所示的仿真結(jié)果可以看出：在相同的信噪比下，LDPC碼的性能與迭代次數(shù)成正比。然而，雖然誤碼率和迭代次數(shù)之間的關(guān)系成正比，但是實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)?shù)螖?shù)已經(jīng)改變到上限時(shí)，繼續(xù)增加，誤碼率不改變，在這種情況下，系統(tǒng)延時(shí)變長(zhǎng)，并且即使LDPC碼的性能不受影響，系統(tǒng)的準(zhǔn)確度也會(huì)降低。