基于子集矩陣的LDLC短環(huán)消除方法

朱聯(lián)祥，李 想

(重慶郵電大學(xué)信號(hào)與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

20世紀(jì)60年代，Gallager在其博士論文中提出了低密度奇偶校驗(yàn)碼(Low Density Parity Check，LDPC)［1］。在二進(jìn)制域的有限字符信道上，擁有一定結(jié)構(gòu)的簡(jiǎn)單碼字能夠有效地接近信道容量［2］，LDPC碼符合這一要求。隨著Mackay［3］對(duì)LDPC碼的重大發(fā)現(xiàn)，LDPC碼在近幾十年憑借其優(yōu)良的性能得到了越來(lái)越廣泛的關(guān)注。受LDPC碼的啟發(fā)，2007 年，N.Sommer，M.Feder和 O.Shalvi提出了低密度格碼(Low Density Lattice Codes，LDLC)［4］。LDLC碼將碼字定義在格域［5－6］，具有較低的編碼復(fù)雜度以及良好的譯碼收斂性，并且同樣能夠接近香農(nóng)限，因此LDLC碼具有廣闊的應(yīng)用前景。

在信道編碼中，編碼是非常重要的一環(huán)，想要進(jìn)行高效的譯碼，就必須首先得到合適的碼字，而碼字要通過(guò)校驗(yàn)矩陣得到。校驗(yàn)矩陣中環(huán)結(jié)構(gòu)的存在，尤其是短環(huán)，會(huì)影響迭代譯碼時(shí)外部交換信息的獨(dú)立性，并且在若干次的迭代譯碼后會(huì)因?yàn)榛ハ嚓P(guān)性而大大降低譯碼的收斂速度，嚴(yán)重影響譯碼的效率以及準(zhǔn)確度。為了能夠有效地消除短環(huán)(4環(huán)以及6環(huán))，本文提出了一種基于子集矩陣的短環(huán)消除方法。使用該方法消除短環(huán)，具有很低的計(jì)算復(fù)雜度，同時(shí)仿真結(jié)果表明，使用這種方式去環(huán)，能夠很大地改善碼字的譯碼性能。

1 LDLC中H矩陣與Tanner圖的關(guān)系

編碼去環(huán)時(shí)，通常是借助Tanner圖來(lái)觀察校驗(yàn)矩陣H中校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)之間的關(guān)系，然后利用相關(guān)的算法達(dá)到去環(huán)的目的［7］。H矩陣中，變量節(jié)點(diǎn)對(duì)應(yīng)著碼字，校驗(yàn)節(jié)點(diǎn)表示校驗(yàn)矩陣的某一行。Tanner圖中，校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)分屬兩個(gè)區(qū)域，若第i行第j列元素非0，Tanner圖中校驗(yàn)節(jié)點(diǎn)i就與變量節(jié)點(diǎn)j相連［8］。與LDPC碼不同，LDLC校驗(yàn)矩陣中的非0元素取值不全為1，而是首先確定一個(gè)生成序列，H矩陣中非0元素的取值就是生成序列中元素的值。非0元素的取值有兩個(gè)原則:第一，每一行每一列的元素不相同;第二，賦值后隨機(jī)給非0元素添上正負(fù)號(hào)。一個(gè)度為3的5階H矩陣，若生成序列為{0.3，0.5，1}，該 Tanner圖如圖1 所示，H 矩陣為

2 基于子集矩陣的短環(huán)消除算法

圖1 Tanner圖

基于Tanner圖可以看到環(huán)的存在，如圖1所示，存在4環(huán)(虛線部分)。環(huán)是由某一個(gè)節(jié)點(diǎn)開(kāi)始并且由這個(gè)節(jié)點(diǎn)結(jié)束過(guò)程中所經(jīng)過(guò)的路徑，通常將所有可能環(huán)的最短長(zhǎng)度稱(chēng)為Girth。迭代譯碼算法中，當(dāng)校驗(yàn)節(jié)點(diǎn)和信息節(jié)點(diǎn)進(jìn)行信息傳遞時(shí)，如果傳遞的信息不包含上一輪迭代過(guò)程中節(jié)點(diǎn)的信息，此時(shí)的譯碼效率最高。但是環(huán)一定存在，經(jīng)過(guò)若干次迭代以后，某一個(gè)節(jié)點(diǎn)一定會(huì)接收到自身的信息。環(huán)的存在破壞了迭代譯碼中外部信息交換的獨(dú)立性，所引起的互相關(guān)性不僅使得收斂過(guò)程變的緩慢，同時(shí)譯碼過(guò)程中產(chǎn)生的誤比特信息會(huì)通過(guò)環(huán)放大返回給這個(gè)比特，破壞了算法的簡(jiǎn)潔性且影響了糾錯(cuò)算法的正確性。學(xué)者通過(guò)實(shí)驗(yàn)得到［4］，在LDLC中，破除6環(huán)以后，破除更大的環(huán)并不能給譯碼性能帶來(lái)明顯的提高，因此本文將重點(diǎn)放在破除4環(huán)以及6環(huán)上。

LDLC的編碼去環(huán)方法已經(jīng)有一些學(xué)者進(jìn)行了研究，其中主要有窮盡搜索［4］以及準(zhǔn)循環(huán)搜索［9］兩種。前一種方法計(jì)算量太大，而且仿真表明在碼長(zhǎng)大于100時(shí)，完全消除4環(huán)非常困難。準(zhǔn)循環(huán)的方法大大降低了復(fù)雜度，但是這種方法的碼長(zhǎng)構(gòu)造并不靈活，而且計(jì)算復(fù)雜度也會(huì)隨碼長(zhǎng)的增加而增大。

2.1 LDLC中的子集矩陣

子集矩陣是將校驗(yàn)矩陣的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)各自分成一定數(shù)量的子集，并且每個(gè)子集中的節(jié)點(diǎn)個(gè)數(shù)相等。每個(gè)子集中元素的個(gè)數(shù)稱(chēng)為Base1，若矩陣的階數(shù)為R，則變量和校驗(yàn)節(jié)點(diǎn)均分為了R/Base1個(gè)子集，Base1應(yīng)該被R整除。當(dāng)知道了校驗(yàn)子集和變量子集的個(gè)數(shù)，可以得到子集矩陣的大小，這里子集矩陣S的階數(shù)為R/Base1，子集矩陣中元素的取值范圍是0～(Base1－1)。

子集矩陣S中，某個(gè)元素的取值就是校驗(yàn)子集中各校驗(yàn)節(jié)點(diǎn)與變量子集中各變量節(jié)點(diǎn)的相對(duì)位置連接關(guān)系。若Si，j=k，0≤k≤(Base1－1)，校驗(yàn)子集Ci與變量子集Vj中元素的連接關(guān)系為 {Ci，m，Vj，n}，1 ≤m≤Base1，1 ≤n≤Base1，那么有

式中:mod是模Base1計(jì)算。

已知一個(gè)3階S矩陣，且Base1取值為5。由矩陣和可以得到H的Tanner圖，如圖2所示。Tanner圖的上半部分是校驗(yàn)節(jié)點(diǎn)子集，下半部分是變量節(jié)點(diǎn)子集。S矩陣為

圖2 由子集矩陣得到Tanner圖

子集矩陣S是一個(gè)全元素3階矩陣，因此由該Tanner圖能夠得到一個(gè)度為3的15階H矩陣。H矩陣的度d與子集矩陣S的階數(shù)相同。

2.2 LDLC中消除4環(huán)、6環(huán)的方法

圖2是一個(gè)較為復(fù)雜的Tanner圖，但是依靠子集矩陣可以得到該 Tanner圖中 Girth的大小。J.Lu和 J.M.F.Moura在文獻(xiàn)［10］中證明了Tanner圖中Girth的大小由S矩陣封閉路徑中各個(gè)元素大小關(guān)系決定，將這些元素進(jìn)行mod運(yùn)算，通過(guò)判斷結(jié)果是否為0，可以得到Girth的值。對(duì)于S中任意封閉路徑長(zhǎng)度為k的k個(gè)元素s1，s2，…，sk，若

則該矩陣的Tanner圖中沒(méi)有k環(huán)存在［11］，這里的mod是模Base1計(jì)算。因此，對(duì)所有封閉路徑長(zhǎng)度為6的6個(gè)元素進(jìn)行對(duì)應(yīng)的運(yùn)算，如果所有的計(jì)算結(jié)果都不為0，那么Tanner圖中沒(méi)有6環(huán)存在。

在S中清除4環(huán)非常容易，清除了以后可以得到無(wú)4環(huán)H矩陣。6環(huán)的可能情況有8種，如圖3所示，清除4環(huán)后，最后兩種6環(huán)情況不存在。在S中直接清除6環(huán)比較困難，去環(huán)過(guò)程中很容易產(chǎn)生新的4環(huán)和6環(huán)。本文利用兩個(gè)子集矩陣S1、S0以及Base1、Base2分兩步去除4環(huán)以及6環(huán)，得到無(wú)6環(huán)度為d的H矩陣。

圖3 封閉路徑長(zhǎng)度為6的8種情況

d值通常較小，選定一個(gè)較小的Base1給S1矩陣賦值，S1矩陣的階數(shù)為d。利用窮盡搜索法迅速消除d階S1矩陣中的4環(huán)，由式(2)得到H1的Tanner圖，然后能夠得到矩陣H1，H1無(wú)4環(huán)。選定Base2，給H1中的元素1賦值，元素0不參與計(jì)算，賦值完畢后，H1變?yōu)榱硪粋€(gè)子集矩陣S0。S0中封閉路徑長(zhǎng)度為6的情況有8種，如圖3所示。任取S0中所有封閉路徑長(zhǎng)度為6的6個(gè)元素，進(jìn)行式(5)計(jì)算，如果為0，某個(gè)元素自增1，循環(huán)若干次，直到S0中的6環(huán)被完全去除。再由式(2)及S0得到H0的Tanner圖，最終可以得到度為d的無(wú)6環(huán)校驗(yàn)矩陣H0。算法描述如圖4所示。

2.3 無(wú)4環(huán)、6環(huán)LDLC碼的實(shí)現(xiàn)

要生成一個(gè)碼長(zhǎng)為1 000、度為5且無(wú)6環(huán)的LDLC碼。首先選定一個(gè)較小的Base1，令Base1=5，然后隨機(jī)生成一個(gè)d階矩陣S1，S1中元素取值范圍為0～(Base1－1)，用窮盡搜索法完全消除S1中的4環(huán)。無(wú)4環(huán)S1可表示為

S1中無(wú)4環(huán)存在，那么能得到一個(gè)d·Base1=25階無(wú)4環(huán)H1矩陣。

LDLC碼利用位置矩陣表示校驗(yàn)方陣，位置矩陣的列數(shù)和方陣的列數(shù)相同，行數(shù)是方陣的度d。位置矩陣第i列的d個(gè)取值分別為方陣第i列所有非0元素的行數(shù)。由S1可以得到H1的Tanner圖，根據(jù)這個(gè)Tanner圖可以得到H1的位置矩陣h1，如圖5所示。

由h1得到H1，此時(shí)H1沒(méi)有4環(huán)，存在6環(huán)，因此將H1轉(zhuǎn)換為另一個(gè)子集矩陣S0。要構(gòu)造一個(gè)碼長(zhǎng)為1 000的LDLC碼，Base2的取值為1 000/(d·Base1)=40。S0是一個(gè)25階矩陣，度為5，將所有的非0元素進(jìn)行0～(Base2－1)的隨機(jī)賦值，零元素用N代替(不參與運(yùn)算)。用圖4的算法消除6環(huán)，可以得到無(wú)6環(huán)的矩陣，如圖6所示S0。

圖4 算法描述

圖5 位置矩陣

S0矩陣已經(jīng)消除了6環(huán)，結(jié)合Base2的取值得到這個(gè)子集矩陣所對(duì)應(yīng)的Tanner圖，由Tanner圖就得到無(wú)6環(huán)，度為5，碼長(zhǎng)為1 000的校驗(yàn)矩陣H0以及H0對(duì)應(yīng)的位置矩陣h0。H0的輸出結(jié)果如圖7所示(橫坐標(biāo)為校驗(yàn)矩陣的列，縱坐標(biāo)為校驗(yàn)矩陣的行)。

圖6 無(wú)6環(huán)子集矩陣

圖7 無(wú)6環(huán)LDLC校驗(yàn)矩陣

H0是無(wú)6環(huán)的校驗(yàn)矩陣，但是與LDPC不同的是，此時(shí)的H0還不能參與譯碼計(jì)算，因?yàn)樵贚DLC中，校驗(yàn)矩陣中非0 元素的值應(yīng)從生成序列中取得。{r1，r2，r3，r4，r5}是生成序列的5個(gè)值，在對(duì)H0的非0元素賦值時(shí)，應(yīng)該保證每一行和每一列沒(méi)有重復(fù)的賦值，賦值完畢以后，再給這些非0元素隨機(jī)賦上正負(fù)號(hào)［4］。接下來(lái)對(duì)H0進(jìn)行標(biāo)準(zhǔn)化處理，讓H0的行列式為1。經(jīng)過(guò)上述步驟處理以后的H0可以參與譯碼。

3 仿真結(jié)果

在本文的仿真中，度為5的LDLC碼所選取的生成序列為{1/2.31 1/3.17 1/5.11 1/7.33 1/11.71}。仿真碼長(zhǎng)分別為500和1 000，仿真環(huán)境為無(wú)功率限制的高斯白噪聲信道［12］，概率密度函數(shù)的分辨率Δ=1/64，譯碼幀數(shù)為250，譯碼的迭代次數(shù)為50，誤比特率作為仿真結(jié)果的縱坐標(biāo)，信號(hào)噪聲σ2與香農(nóng)限的距離(dB)為橫坐標(biāo)。

本仿真所選取的同一碼長(zhǎng)的LDLC碼分別是用窮盡搜索去除4環(huán)和利用子集矩陣消除6環(huán)得到的，仿真結(jié)果如圖8所示。可以看到，去除了6環(huán)的LDLC碼(4環(huán)也被完全清除)的譯碼性能明顯好于只去除了4環(huán)的LDLC碼，這說(shuō)明本文基于子集矩陣的方法能夠有效消除短環(huán)。

圖8 仿真結(jié)果

4 小結(jié)

本文采用基于子集矩陣的方法消除LDLC碼中存在的4環(huán)和6環(huán)，與窮盡搜索的方法相比，本文計(jì)算復(fù)雜度大大降低，并且可以保證不產(chǎn)生新的短環(huán)。與準(zhǔn)循環(huán)的方法相比，在構(gòu)造碼長(zhǎng)較大的LDLC碼時(shí)，本文的方法更具有優(yōu)勢(shì)。

采用基于子集矩陣消除短環(huán)的方法，復(fù)雜度并不取決于碼長(zhǎng)，而是基于S0矩陣，S0僅與度數(shù)d以及Base1有關(guān)，即使碼長(zhǎng)增加，去除6環(huán)的步驟仍然在S0中進(jìn)行，與碼長(zhǎng)的大小無(wú)關(guān)。隨著碼長(zhǎng)的增加，雖然存在額外的運(yùn)算量，不過(guò)該部分運(yùn)算量很小，可以忽略不計(jì)。

當(dāng)無(wú)6環(huán)存在時(shí)，選定的值可以構(gòu)造任意長(zhǎng)度的LDLC碼，而算法復(fù)雜度不會(huì)增加，這是本文算法的一大優(yōu)點(diǎn)。

采用基于子集矩陣消除短環(huán)的方法可以靈活得到各種長(zhǎng)度的碼長(zhǎng)，并且具有更低的復(fù)雜度和較好的譯碼性能，這對(duì)于LDLC碼的推廣和應(yīng)用具有積極的意義。

:

［1］GALLAGER R G.Low－density parity－check codes［J］.IRE Trans.Information Theory，1962，8(1):21－28.

［2］SHANNON C E.A mathematical theory of communication［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2001，5(1):3－55.

［3］MACKAY D J C，NEAL R M.Good codes based on very sparse matrices［EB/OL］.［2013－05－10］.http://link.springer.com/chapter/10.1007/3－540－60693－9_13#page－1.

［4］SOMMER N，F(xiàn)EDER M.Low density lattice codes［J］.IEEE Trans.Information Theory，2008，54(4):1561－1585.

［5］RUDE D B.The upper error bound of a new near－optimal code［J］.IEEE Trans.Information Theory，1975，21(4):441－445.

［6］RUDI D B.Some optimal codes have structure［J］.IEEE Trans.Information Theory，1989，7(6):893－899.

［7］BOUTROSJ，POTHIER O，ZEMOR G.Generalized low density(Tanner)codes［C］//Proc.IEEE International Conference on Communicaitons.Vancouver，BC:IEEE Press，1999:441－445.

［8］TAO Xiongfei，ZHENG Lixin，LIU Weizhong，et al.Recursive design of high Girth(2，k)LDPC codes from(k，k)LDPC codes［J］.IEEE Communications Letters，2008，15(1):70－72.

［9］朱聯(lián)祥，楊海燕.一種構(gòu)造八環(huán)準(zhǔn)循環(huán)LDLC碼的搜索算法［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2011，23(5):570－573.

［10］LU J，MOURA J M F.Structured LDPC codes for high－density recording:large Girth and low error floor［J］.IEEE Trans.Magnetics，2006，42(2):208－213.

［11］FAN Jun，XIAO Yang.A method of counting the number of cycles in LDPC codes［C］//Proc.8th International Conference on Signal Processing.Beijing:IEEE Press，2006:156－163.

［12］SHANNON C E.Communication in the presence of noise［J］.Proceedings of the IEEE Publication，1984，72(9):1192－1201.