LDPC 碼譯碼算法及性能分析應(yīng)用設(shè)計(jì)

0 引言

信道編譯碼技術(shù)可以檢測(cè)并且糾正信號(hào)在傳輸過(guò)程中引入的錯(cuò)誤，能夠保證數(shù)據(jù)進(jìn)行可靠的傳輸[1].

LDPC碼的校驗(yàn)矩陣具有稀疏的特性，因此存在高效的譯碼算法，其糾錯(cuò)能力非常強(qiáng)。1981年，Tanner提出了基于圖模型描述碼字的概念，將LDPC碼的校驗(yàn)矩陣對(duì)應(yīng)到Tanner圖的雙向二部圖上。采用Tanner圖構(gòu)造的LDPC碼，通過(guò)并行譯碼可大大降低譯碼復(fù)雜度。Mack-ay 和Neal利用隨機(jī)構(gòu)造的Tanner 圖研究了LDPC 碼的性能，發(fā)現(xiàn)采用和積算法(SPA)的LDPC 碼具有優(yōu)異的譯碼性能，在長(zhǎng)碼時(shí)甚至超過(guò)了Turbo 碼[2].本文采用Mackay 基于二分圖提出的改進(jìn)方案構(gòu)造LDPC 碼的校驗(yàn)矩陣?；谥眯艂鞑?BP)算法，給出了一種簡(jiǎn)化的BP算法--對(duì)數(shù)域迭代APP LLR 算法，復(fù)雜度大大降低。目前，LDPC碼是最有希望在廣泛的信道范圍取得香農(nóng)容量的誤差糾正技術(shù)[3],在保證LDPC 碼糾錯(cuò)性能的前提下，降低編譯碼器實(shí)現(xiàn)的復(fù)雜度是研究的重點(diǎn)，引發(fā)了信道編碼界的研究熱潮。

1 LDPC 碼編碼

LDPC碼是一種性能非常接近香農(nóng)極限的“好”碼，它是惟一用校驗(yàn)矩陣來(lái)表示的線性分組碼。LDPC碼的編碼主要分兩步進(jìn)行，首先構(gòu)造奇偶校驗(yàn)矩陣，然后是基于奇偶校驗(yàn)矩陣的編碼算法。

1.1 校驗(yàn)矩陣的構(gòu)造

根據(jù)式子n*j = m*k 可知，規(guī)則的LDPC碼(n,j,k)，當(dāng)參數(shù)n, j, k 確定后，可以得到校驗(yàn)方程的數(shù)目m,則校驗(yàn)矩陣H 的大小就可以定為m × n.構(gòu)造LDPC 碼校驗(yàn)矩陣的一般步驟為：先生成一個(gè)m 行n 列的全0矩陣，然后隨機(jī)地將每列中的j 個(gè)0換成1,每行中的k 個(gè)0換成1.但在隨機(jī)置l的過(guò)程中，必須避免出現(xiàn)長(zhǎng)度為4的環(huán)[4].

如果最小環(huán)長(zhǎng)為4,在迭代中非常容易造成錯(cuò)誤信息的擴(kuò)散傳播，從而導(dǎo)致譯碼性能的下降[5].

Mackay 為了消除校驗(yàn)矩陣中長(zhǎng)度為4 的環(huán)，基于Tanner圖提出了改進(jìn)的構(gòu)造方案。采取的準(zhǔn)則是：在構(gòu)造時(shí)必須保證任意兩列間的交疊重量不超過(guò)1.本文采用的是Mackay的1A構(gòu)造方法，按照此方法構(gòu)造的一個(gè)LDPC碼(3,6)碼如圖1所示。

Mackay的1A構(gòu)造方法是最基本的一種構(gòu)造方法，它要求保證固定列重為γ ,而行重盡可能均勻的保持為ρ .

利用Mackay構(gòu)造方法得到的LDPC碼距離特性很好，且沒(méi)有短環(huán)。

1.2 基于奇偶校驗(yàn)矩陣的編碼算法

LDPC碼的直接編碼方法就是利用高斯消去法，產(chǎn)生一個(gè)下三角矩陣，然后進(jìn)一步初等變換得到右邊單位陣形式H = [P|I] ,由G = [I|P] 得到生成矩陣，再利用信息碼元向量u 和生成矩陣G 相乘可得到完整碼字C,即C = M*G 直接編碼[5].

2 LDPC 碼譯碼[4,6-7]

BP 算法是在Gallager提出的概率譯碼算法基礎(chǔ)上發(fā)展而來(lái)的。BP算法每次迭代包括2步：變量節(jié)點(diǎn)的處理和校驗(yàn)節(jié)點(diǎn)的處理。概率域就是在節(jié)點(diǎn)間傳遞的是概率信息，采用很多乘法運(yùn)算，運(yùn)算量大;而對(duì)數(shù)域的和積算法實(shí)現(xiàn)是將概率值通過(guò)對(duì)數(shù)似然比變化為軟信息值(LLR)，再進(jìn)行傳遞，這樣就將大量乘法運(yùn)算變?yōu)榧臃ㄟ\(yùn)算，大大簡(jiǎn)化了譯碼復(fù)雜度，利于硬件實(shí)現(xiàn)。下面重點(diǎn)介紹對(duì)數(shù)域迭代APP LLR譯碼算法。

2.1 迭代APP LLR譯碼算法的變量定義

對(duì)于(N,K) LDPC碼，定義變量U 取值為0和1時(shí)的對(duì)數(shù)似然比(LLR)為：

設(shè)發(fā)端發(fā)送的碼字為u = [u1,u2 ,…，uN ] ,接收碼字為y = [y1,y2 ,…，yN ] ,由此可以得出在迭代中傳遞的校驗(yàn)節(jié)點(diǎn)和信息節(jié)點(diǎn)的軟信息為：

2.2 迭代APP LLR譯碼算法

迭代APP LLR譯碼算法的迭代過(guò)程如下：

(1)初始化：設(shè)每個(gè)變量節(jié)點(diǎn)n 的軟信息為：

對(duì)于矩陣中H(m,n) = 1,相應(yīng)的變量節(jié)點(diǎn)的軟信息初始化為信道輸出的軟信息，即λmn (un ) = L(un )，Λmn (un ) = 0.

(2)校驗(yàn)節(jié)點(diǎn)更新：根據(jù)每個(gè)變量節(jié)點(diǎn)n,向與該變量節(jié)點(diǎn)相連的所有校驗(yàn)節(jié)點(diǎn)傳遞更新的軟信息，計(jì)算校驗(yàn)節(jié)點(diǎn)信息：

(3)判決：當(dāng)λn (un ) 0,則u-n = 0 ,否則u-n = 1,此時(shí)判決出的碼為：u- ={u-1,u-2 ,…，u-N}.最后根據(jù)校驗(yàn)矩陣來(lái)判斷所譯出的碼字是否正確。如果u-H T = 0,那么譯碼正確，此時(shí)，停止迭代;否則繼續(xù)迭代進(jìn)行譯碼，直到迭代次數(shù)達(dá)到所設(shè)定的最大次數(shù)。如果此時(shí)仍未正確譯碼，則譯碼失敗。

由以上所述可見，在變量節(jié)點(diǎn)更新時(shí)只有加法運(yùn)算，但是還可以再進(jìn)一步降低算法的實(shí)現(xiàn)復(fù)雜度。采用迭代APP LLR 算法，將LLR BP 算法中的λn (un ) 代替λmn′(u ) n′ 參與校驗(yàn)信息的迭代。即λn (un ) 不僅用于硬判決，還用于校驗(yàn)信息的更新。這樣所傳遞的變量消息之間便引進(jìn)了相關(guān)性，傳遞的變量消息就不再是外部消息，僅僅需要計(jì)算和存儲(chǔ)一個(gè)變量消息的數(shù)值，可以大大地降低算法的復(fù)雜度。

3 LDPC 碼在高斯信道下不同譯碼算法的仿真結(jié)果和分析

基于Matlab按照上述的編譯碼方法，在高斯信道下分別對(duì)LDPC 碼概率域的SPA 和對(duì)數(shù)域的迭代APPLLR 譯碼算法進(jìn)行了誤碼性能仿真。然后由所得到的性能仿真圖形進(jìn)行分析比較。

3.1 概率域的SPA的仿真結(jié)果和分析高斯信道下，用BPSK 調(diào)制，采用概率域的迭代譯碼算法，迭代次數(shù)為20,該程序的優(yōu)點(diǎn)是譯碼效率高，其關(guān)鍵地方利用了LOG 函數(shù)，提高了譯碼效率。相同碼率均為1 2,碼長(zhǎng)分別為36,256,512,用概率域的迭代譯碼算法時(shí)的編譯碼系統(tǒng)的誤碼率隨信噪比變化的曲線如圖2所示。

由圖2 可見，譯碼前的誤碼率最高，采用概率域的迭代譯碼算法后，誤碼率大幅度降低，譯碼性能較好。碼長(zhǎng)為512的LDPC碼糾錯(cuò)性能最好，碼長(zhǎng)為36的LDPC碼糾錯(cuò)性能最差。由此可得：在相同碼率下，隨著碼長(zhǎng)的增加，LDPC碼的糾錯(cuò)性能逐漸改善。

3.2 迭代APP LLR譯碼算法的仿真結(jié)果和分析

高斯信道下，用BPSK 調(diào)制，采用對(duì)數(shù)域的迭代譯碼算法，迭代次數(shù)為10,可以設(shè)置誤碼碼字的最大數(shù)量來(lái)計(jì)算每個(gè)信噪比點(diǎn)，程序簡(jiǎn)明了，容易理解，而且譯碼效率非常高。相同碼率為1/2,碼長(zhǎng)分別為36、256、512,用對(duì)數(shù)域的迭代APP LLR譯碼算法時(shí)的編譯碼系統(tǒng)的誤碼率隨信噪比變化的曲線如圖3所示。