基于子集矩陣的LDLC短環消除方法

朱聯祥，李 想

(重慶郵電大學信號與信息處理重慶市重點實驗室，重慶 400065)

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

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

1 LDLC中H矩陣與Tanner圖的關系

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

2 基于子集矩陣的短環消除算法

圖1 Tanner圖

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

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

2.1 LDLC中的子集矩陣

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

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

式中:mod是模Base1計算。

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

圖2 由子集矩陣得到Tanner圖

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

2.2 LDLC中消除4環、6環的方法

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

則該矩陣的Tanner圖中沒有k環存在［11］，這里的mod是模Base1計算。因此，對所有封閉路徑長度為6的6個元素進行對應的運算，如果所有的計算結果都不為0，那么Tanner圖中沒有6環存在。

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

圖3 封閉路徑長度為6的8種情況

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

2.3 無4環、6環LDLC碼的實現

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

S1中無4環存在，那么能得到一個d·Base1=25階無4環H1矩陣。

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

由h1得到H1，此時H1沒有4環，存在6環，因此將H1轉換為另一個子集矩陣S0。要構造一個碼長為1 000的LDLC碼，Base2的取值為1 000/(d·Base1)=40。S0是一個25階矩陣，度為5，將所有的非0元素進行0～(Base2－1)的隨機賦值，零元素用N代替(不參與運算)。用圖4的算法消除6環，可以得到無6環的矩陣，如圖6所示S0。

圖4 算法描述

圖5 位置矩陣

S0矩陣已經消除了6環，結合Base2的取值得到這個子集矩陣所對應的Tanner圖，由Tanner圖就得到無6環，度為5，碼長為1 000的校驗矩陣H0以及H0對應的位置矩陣h0。H0的輸出結果如圖7所示(橫坐標為校驗矩陣的列，縱坐標為校驗矩陣的行)。

圖6 無6環子集矩陣

圖7 無6環LDLC校驗矩陣

H0是無6環的校驗矩陣，但是與LDPC不同的是，此時的H0還不能參與譯碼計算，因為在LDLC中，校驗矩陣中非0 元素的值應從生成序列中取得。{r1，r2，r3，r4，r5}是生成序列的5個值，在對H0的非0元素賦值時，應該保證每一行和每一列沒有重復的賦值，賦值完畢以后，再給這些非0元素隨機賦上正負號［4］。接下來對H0進行標準化處理，讓H0的行列式為1。經過上述步驟處理以后的H0可以參與譯碼。

3 仿真結果

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

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

圖8 仿真結果

4 小結

本文采用基于子集矩陣的方法消除LDLC碼中存在的4環和6環，與窮盡搜索的方法相比，本文計算復雜度大大降低，并且可以保證不產生新的短環。與準循環的方法相比，在構造碼長較大的LDLC碼時，本文的方法更具有優勢。

采用基于子集矩陣消除短環的方法，復雜度并不取決于碼長，而是基于S0矩陣，S0僅與度數d以及Base1有關，即使碼長增加，去除6環的步驟仍然在S0中進行，與碼長的大小無關。隨著碼長的增加，雖然存在額外的運算量，不過該部分運算量很小，可以忽略不計。

當無6環存在時，選定的值可以構造任意長度的LDLC碼，而算法復雜度不會增加，這是本文算法的一大優點。

采用基于子集矩陣消除短環的方法可以靈活得到各種長度的碼長，并且具有更低的復雜度和較好的譯碼性能，這對于LDLC碼的推廣和應用具有積極的意義。

:

［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，FEDER 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］朱聯祥，楊海燕.一種構造八環準循環LDLC碼的搜索算法［J］.重慶郵電大學學報:自然科學版，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.