一種具有較大圍長的正則LDPC碼構造方法

1962年Gallager提出低密度校驗(Low DensityParity Check，LDPC)碼，后來Tanner對它進行了很有價值的補充，直到1995年又被Mackey重新提出。如果采用和積迭代譯碼算法，LDPC碼具有非常接近香農限的性能。如果在LDPC碼的Tanner圖中存在環，在迭代譯碼的過程中錯誤信息將會膨脹，對于LDPC的譯碼性能相當有害，尤其是較短環的存在，所產生的危害尤為嚴重。所以，在構造LDPC的過程當中，要盡量避免短環的出現。為了盡量減小Tanner圖中環的存在對相應LDPC碼在和積譯碼算法下所得性能的影響，一些研究學者基于代數方法和啟發式搜索方法，提出了一些具有較大圍長的LDPC碼構造方法。研究表明，通過增大LDPC碼的圍長，在一定程度上可以改善碼的糾錯性能。本文構造了正則LDPC碼，在構造過程中討論了設計圍長的參數選舉，使得滿足一定的條件就可以避免校驗矩陣的小圍長出現，使得所構造的矩陣具有較大圍長。

1．LDPC碼的構造理論

考慮長為16的(2，4)正則LDPC碼對應的Tanner，如圖1所示。


從圖1中很顯然可以看出，該Tanner中環的最小長度為8，因此對應LDPC碼的圍長也為8。

按圖1將其中的變量結點和校驗結點依次編號，可以得到對應LDPC碼的校驗矩陣，如圖2所示。


圖2矩陣很有規律，可以看作是由兩個行重為2、維數為8×8的循環方陣拼接而成。因此可以猜想，采用某些有規律的矩陣合并成校驗矩陣，這樣生成的LDPC碼很可能會具有較大的圍長。或者說，將LDPC碼的校驗矩陣分裂為若干個子矩陣，然后每個子矩陣再按照某種規律構造，就有可能避免小環的出現。

這里采用矩陣分裂的思想。設要構造一個長為72(n=ρUU∈N)的(λ，ρ)正則LDPC碼，將該碼的校驗矩陣分裂為(λ，ρ)個U×U的子矩陣。



式中：每個子矩陣Hi,j=I(ai,j)(0≤i<λ，0≤j<ρ)均為一個單位陣或者單位陣的循環移位ai,j表示該單位陣的各行循環右移的位數。顯然，這樣構造的校驗矩陣也不可能為滿秩，至多為λρ-λ-1。
為便于描述，用A=(ai,j)表示由各個子方陣的循環移位參數組成的矩陣，用(I，J，i，j)表示校驗矩陣中的元素，其中(I，J)為該元素所屬的子矩陣的坐標，(i，j)為該元素在它所屬的子矩陣中的坐標。稱Tanner圖中每個變量結點參與的所有環的最小長度為該變量結點的環長，則顯然相應LDPC碼的圍長就等于各個變量結點環長的最小值。將n個變量結點分為P組，每一組變量結點對應一列子矩陣，則考慮到各個子矩陣的循環特性，有如下定理成立。

定理1? 屬于同組的變量結點具有相同的環長。

證明：設任意兩個同組的變量結點x和y，分別對應一列子矩陣的第x列和第y列，且y-x=dmodU，其環長分別為C(x)和C(y)，并設變量結點x的最小環路徑如圖3所示。



根據各個子矩陣的循環特性，可以找到另一個環的路徑如圖4所示。



顯然該環路長度為C(x)且經過變量節點y，故有：

C(x)≥C(y)??? (2)
同理可得：
C(x)≤C(y)??? (3)

綜合上面兩式，有C(x)=C(y)即對任意兩個同組的變量節點，它們的環長均相等，證畢。

由定理1可知，按照上述方法構造的校驗矩陣所對應的LDPC碼，所有變量節點的環長至多有ρ種情況，因此對這樣構造的矩陣只需要分別從各組中抽取一個變量節點，然后只對這ρ個變量節點進行檢測，即可確定整個碼的圍長。

2校驗矩陣中循環移位參數的選取

下面討論4環的情況。如果一個LDPC碼含有4環，則它所對應的校驗矩陣中必然有4個“1”處于某個矩形的四個頂點，該環路路徑可表示為：


定理2? 按照式(1)所示矩陣分裂方法構造的矩陣所對應的LDPC碼不含長為4的環的充要條件有式(6)成立：


該定理的正確性從前面的描述中即可得知，這里不再贅述。

由定理2很容易得到下面推論：

推論1：按照式(1)所示矩陣分裂構造方法構造的矩陣所對應的LDPC碼不含長為2l的環的充要條件為：


在編碼設計時，可以首先確定所構造LDPC碼設計圍長，然后根據上面的定理和推論列出相應的不等約束，進而尋找滿足這些不等約束的參數即可。

在進行參數選擇時，可以根據上面分析和設計的圍長列出各參數所對應滿足的約束方程，然后尋找滿足這些約束方程的參數取值。然而，由于這些約束方程均為不等約束，因而無法采用一般的方程組求解法；如果采用窮舉的方法去遍歷各個參數的所有可能組合，繼而從中找出滿足約束的一組，搜索的范圍將有己U(λ-1)(ρ-1)，這樣即使U的取值范圍很小(如102)，總的搜索范圍也將很大，因而無法實現。

為了實現參數的快速選取可以采用下述逐參試探算法：???

(1)令ai,0=0(i=0，1，…，λ-1)及a0,j=0(j=1，2，…，ρ-1)；

(2)隨機在{0，1，…，U-1)中選取a1,1取值，然后判斷a1,1是否滿足給定的不等約束，若滿足則確定取值，否則重新執行(2)

(3)按照(2)的方法一次確定剩余子矩陣的循環移位參數。

按照上面算法，每個參數至多需要U次試探，這樣總共的試探次數至多為(λ-1)(ρ-1)U，遠遠小于整個搜索空間U(λ-1)(ρ-1)。

由于該算法采用逐個確定參數的方法，顯然最后確定的參數受到的約束是最多的，定義N(l)為考慮消除Tanner圖中長度為2l的環時最后一個參數受到的約束方程個數，則有：



由于各個約束方程均為不等約束，每個約束只能限制參數不能取某個特定的值，因此所有不等約束限制參數所不能取的值的個數至多為約束方程數目的兩倍。考慮到所要構造的LDPC碼的碼長，U的取值一般在100左右，因此消除六環一般都可行。

3仿真及性能分析

取U=168，按照上面的方法構造長度為1 008的(3，6)正則LDPC碼，通過計算機搜索檢測發現，得到子方陣的循環參數為：

檢測發現LDPC碼的圍長為10，為了保證所構造碼的碼率嚴格等于0.5，可以從生成的檢驗矩陣中刪去2個“1”。該碼在AWGN信道下的糾錯性能如圖5所示，圖中的另外兩條曲線分別為相同長度、隨即構造、不消除4環的(3，6)正則LDPC碼的性能曲線。其中，girth表示圍長；ave表示所有變量節點的平均環長。

文獻[8，9]采用PEG算法所構造的長度為1 008的(3，6)正則LDPC碼的圍長為8，平均環長為9.66，稍劣于上面構造的LDPC碼，因此該方法用于正則LDPC碼的構造時要優于其他的構造方法。

通過分析發現，采用該方法構造的正則LDPC碼與文獻[10]所述方法一樣，其圍長存在一個上限，下面進行詳細介紹。考慮一個維素為2U×3U的矩陣，將其分裂成6個維素為U×U的子方陣，每個方陣均為單位陣或單位陣的行循環移位，則可以得到一個行重為3、列重為2的矩陣。不失一般性，令第一行子方陣均為單位陣，其余兩個方陣的行右循環移位參數分別為a1,1和a1,2，則不論a1,1和a1,3如何取值，該矩陣始終存在如圖6所示的12環。


將圖6環上各個的非零元素依次編號，并令編號為1的元素坐標為(0，0，x，x)，則環上各節點的坐標如圖7所示。



因此，若采用上面的方法構造(λ，ρ)正則LDPC碼，只要λ≥2，ρ≥2且λ+ρ≥5，相應的校驗矩陣中也就必然包含圖所示的字矩陣或其轉置矩陣，于是得到的LDPC碼的圍長也就必然不可能超過12。

4結? 語

給出了一種高圍長的正則LDPC碼的構造方法，具體分析了去環方法和循環移位參數的選取。用這種方法構造的LDPC碼的H矩陣具有很好的結構。仿真表明，用該方法構造的碼在AWGN信道下性能要優于隨機構造的碼。