基于原模圖擴展的QC-LDPC構造方法

龔險峰 陶孝鋒 邱樂德

（中國空間技術研究院西安分院，西安710000）（中國空間技術研究院，北京100094）

1 引言

在多數情況下，衛星通信都屬于功率受限的通信系統，因而信道編碼技術在衛星通信中占有舉足輕重的地位。低密度奇偶校驗碼（LDPC）和Turbo碼一樣具有逼近Shannon門限的糾錯性能，但與Turbo碼相比還有一些優勢，比如：可以高度并行處理、更低的誤碼平層等。因此，LDPC引起了廣泛的關注，成為繼Turbo碼后信道編碼界的又一研究熱點。

校驗矩陣從根本上決定了LDPC的糾錯性能。國內外學者提出多種校驗矩陣構造方法，其中基于原模圖的構造方法具有許多優點。由同一原模圖擴展構造的任意長度的LDPC都具有類似的結構，其性能上限取決于原模圖，可以通過密度演進算法或外部信息轉移圖分析計算門限值。對于原模圖設計，文獻[1]提出用模擬退火法優化原模圖，文獻[2]構造了大量性能逼近Shannon限的原模圖。但是，一個好的原模圖并非意味著所構造出來的LDPC必然具有優異的性能。實際上，擴展方法不僅影響碼的性能，而且還決定了編譯碼器的硬件實現復雜度。因此，以降低譯碼門限和誤碼平層為目標，本文提出了一種基于原模圖擴展構造QC-LDPC的方法。

2 原模圖與LDPC

LDPC是由稀疏奇偶校驗矩陣定義的一種線性分組碼，其校驗矩陣可以用圖來表示，稱為Tanner圖，如圖1所示。Tanner圖是一種雙向圖，由G＝｛（V，E）｝定義，其中V是節點的集合，（V＝Vb∪Vc），E是節點之間相連的邊的集合。對于維數為M×N的校驗矩陣，Vb＝（v0，v1，…，vN-1）稱為變量節點；Vc＝（c0，c1，…，cM-1）稱為校驗節點。

圖1 校驗矩陣及其對應的Tanner圖Fig.1 Parity check matrix and Tanner graph

圍長是影響LDPC糾錯性能的一個重要參數，雖然構造一個最大可能圍長的Tanner圖是一個非常難的組合問題，但是構造一個具有相對較大圍長且計算復雜度較低的次優算法還是存在的，漸進邊增長（PEG）算法是具有此性能的一個常用算法[3]。Tian等人發現，LDPC的誤碼平臺不完全由圍長決定，更主要的是和環路的連通度有關，為此提出了近似環路外信息度（ACE）算法[4]。ACE算法和PEG算法相比，稍許損失了編碼增益，但降低了誤碼平層。ACE測度是用來度量環路連通性的參數，一個環的ACE測度定義為

式中k為環路上變量節點的個數；di為變量節點i的度數。

圖1顯示了一個長度為8的環（v2→c1→v8→c5→v4→c6→v6→c3→v2），其中v2、v4、v6和v8是環上的變量節點，該環路的ACE測度LACE為0。

原模圖類似于節點數目較少的Tanner圖，但其上允許存在重邊。在擴展構造LDPC時，先將原模圖復制若干遍，將每個副本稱為一個子圖，再將處于不同子圖中的邊進行置換和擾序，使不同子圖相互連接起來，所得到的新Tanner圖可確定一個LDPC。在原模圖的擴展過程中，邊置換方式的不同將決定所得新Tanner圖中環長及環與周邊節點的連通性，從而影響LDPC糾錯性能；另一方面，置換方式還將決定所得LDPC是隨機的還是結構化的，從而影響編譯碼器的實現復雜度。

3 原模圖擴展算法

對于節點間存在重邊的原模圖需要進行兩步擴展，第一步擴展用于去除節點間的重邊，而第二步擴展則是為了使最終的校驗矩陣具有準循環結構。為方便敘述，下文中以1／2碼率的AR4JA原模圖[2]為例進行說明，其結構如圖2所示。其中，黑實心圓代表變量節點，帶加號的圓代表校驗節點，空心圓代表刪余的變量節點。該原模圖對應的矩陣表達式為

圖2 碼率1／2AR4JA LDPC原模圖Fig.2 Protograph for rate 1／2 AR4JA LDPC

3.1 算法1——原模圖的PEG去重邊擴展

第一步擴展目的是去除節點間的重邊，基本思想是先將原模圖擴展L（L大于等于最大重邊數）倍，然后進行邊置換操作。為了繼承原模圖的性能特性，邊置換只能發生在同一節點擴展出來的L個節點（變量節點或者校驗節點）之間。由于L不小于原模圖中的最大重邊數，只要置換得當就能保證擴展出來的的Tanner圖中不再存在重邊。在擴展過程中采用PEG算法，使局部圍長最大化。但是，與原PEG算法不同的是，擴展過程中要受到上述約束條件的制約。

假設基矩陣的行數和列數分別為M和N，Hs1為第一步擴展后的矩陣。原模圖的第一步擴展算法描述如下：

初始化：基矩陣行號i＝0；基矩陣列號j＝1；擴展倍數計數s＝1；Hs1＝0；對矩陣Hs1的變量節點和校驗節點進行編號 （分別為1～LN和1～LM）。

1）如果i＝M且s≠L，則i＝1、s＝s＋1，跳到第2）步；如果i＝M且s＝L，則i＝1、j＝j＋1、s＝1，跳到第2）步；如果i≠M，則i＝i＋1，跳到第2）步；如果i＝M、j＝N且s＝L，跳到第6）步。

2）令e＝Hbase（i，j），如果e≠0，則執行第3）步；否則，跳到第1）步。

3）從矩陣Hs1編號為（i-1）L＋1～iL的校驗節點中，選擇一個行重最小的與變量節點（j-1）L＋s相連。執行第4）步。

4）e＝e-1。如果e＞0，則執行第5）步；否則，跳到第1）步。

5）對矩陣Hs1對應的Tanner圖從變量節點（j-1）L＋s進行分層展開[3]，直到展開圖中校驗節點停止增長或者展開圖中已經包含校驗節點（i-1）L＋1～iL，展開終止。如果展開終止時，展開圖中包含了編號（i-1）L＋1～iL的全部校驗節點，則從其中選擇一個最后新加入到展開圖且行重最小的節點與變量節點（j-1）L＋s相連；否則，從編號為（i-1）L＋1～iL且沒有加入展開圖的校驗節點中，選擇一個行重最小的與變量節點（j-1）L＋s相連。跳到第4）步。

6）輸出矩陣Hs1，程序終止。

盡管在第一步擴展中采用了PEG算法，但由于擴展倍數較小，矩陣Hs1對應Tanner圖中仍然存在大量的小環，且擴展出來的矩陣是非結構化的。

3.2 算法2——基于環檢測和ACE測度的準循環擴展

為了得到準循環結構的LDPC，需要對Hs1進行第二步擴展。本算法用維數為V×V（V取決于碼長和第一步擴展倍數L）的零矩陣、置換矩陣（單位矩陣及其移位矩陣）分別替換矩陣Hs1中的元素0和1。在擴展過程中，采用PEG算法思想，使局部圍長最大化。只要置換矩陣的偏移量取值得當，就能消除原矩陣Hs1中的短環。舉例：假設對矩陣Hs1進行倍數為3的準循環擴展，對于Hs1對應Tanner圖中的一個長度為4的短環，根據置換矩陣偏移量取值的不同，擴展過程中可能存在多種替換方式，圖3為其中兩種可能情況。在圖3（a）中，替換矩陣Hs1中4個元素1的置換矩陣偏移量分別為0-1-2-1，擴展后的矩陣中依然存在長度為4的短環；在圖3（b）中，置換矩陣偏移量分別為0-1-1-1，擴展后得到1個長度為12的環路。文獻[5]中給出了一般結論：

定理 假設矩陣Hs1對應Tanner圖中存在長度為k的一條封閉路徑：（m1，n1）→（m2，n1）→（m2，n2）→ … → （mk，nk）→ （m1，nk），其中1≤i≤k，（mi，ni）為Hs1中的某個非零元素。經準循環擴展后，路徑上非零元素對應置換矩陣的偏移量依次為s1→s2→…→sk-1→sk。如果滿足條件

式中r是滿足上述條件的最小正整數，則擴展后的準循環矩陣中必存在長度為rk的環。

圖3 不同置換矩陣擴展出來的校驗矩陣Fig.3 Parity-check matrices based on different permutation matrices

對于給定的擴展因子V，要確定矩陣Hs1中非零元素對應置換矩陣的偏移量使QC-LDPC圍長最大化是非常困難的。這里仍然采用PEG算法思想，逐個搜索每個置換矩陣的局部最優偏移量，同時對環路計算ACE測度，從環長和環的連通性兩方面對環路進行約束。由于大環對碼性能影響較小，為了降低搜索算法的時間復雜度，可以預設一個最大搜索路徑長度Kmax，當路徑長度超過該值后便停止繼續搜索；用Hs2記錄第二步擴展后的矩陣，其各元素初始值預置為-1；用矩陣Hs＿temp記錄矩陣Hs1中已經完成準循環擴展的部分，其各元素初始值預設為0。第二步擴展算法描述如下：

初始化 行號i＝1，列號j＝1；定義數組A和Β分別記錄不同偏移量下的最小環長和最小環路ACE測度。

1）逐列從上到下搜索矩陣Hs1，同時行號i（1≤i≤ML）、列號j（1≤j≤NL）也相應地變化。如果已經搜索完畢，則跳到第5）步；否則，執行第2）步。

2）若i＝1或j＝1，則Hs2（i，j）＝δ、Hs＿temp（i，j）＝Hs1（i，j），其中δ為 [0，V-1]范圍內取值的隨機整數（δ也可以取一個固定的值），然后跳到第1）步；否則，令Hs＿temp（i，j）＝Hs1（i，j）、v＝0、A[v]＝∞、B[v]＝∞，然后執行第3）步。

3）令Hs2（i，j）＝v。在矩陣Hs＿temp對應的Tanner圖上，搜索從校驗節點i、變量節點j往下延伸的所有路徑，用變量k記錄每條路徑的長度（對于每條路徑，當k＞Kmax或者路徑無法繼續延伸后停止）。如果沒有止于校驗節點i的封閉路徑，直接跳到第4）步；否則，對于每條止于校驗節點i的封閉路徑，按照公式（3）計算準循環擴展后的環路長度p并按照公式（1）計算其ACE測度值q。如果p＜A[v]，令A[v]＝p；如果q＜B[v]，令B[v]＝q。搜索完成后，執行第4）步。

4）如果v＜V-1，則令v＝v＋1，跳到第3）步；否則，對數組A進行排序，得到A中最大值對應的序號t（若A中存在多個相同的最大值，則比較對應數組Β中的元素，選擇數值大的元素對應的序號），令Hs2（i，j）＝t，跳到第1）步。

5）輸出矩陣Hs2。

對于不存在重邊的原模圖，不需要進行第一步擴展，直接對原模圖進行第二步擴展便能得到QC-LDPC。對于矩陣Hs2中的任意元素，若Hs2（i，j）＝-1，則用V×V的零矩陣替代；否則，用偏移量為Hs2（i，j）、維數為V×V的置換矩陣替代，由此得到QC-LDPC校驗矩陣。

4 性能仿真

利用上述算法，基于AR4JA原模圖構造了兩個QC-LDPC，碼率都為0.5，碼長分別為2 048和8 192。為了降低搜索算法的時間復雜度，最大搜索路徑長度設置為16。仿真條件：加性高斯白噪聲信道（AWGN）和乘譯碼算法（SPA），最大迭代次數為200。在CCSDS 131.1-O-2深空通信標準中，采用的便是AR4JA原模圖擴展構造的QC-LDPC，具有優異的性能[6]。圖4中給出了性能仿真曲線，可以看出誤碼率為10-6時，兩個碼的譯碼門限分別為1.3dB和1.9dB，與CCSDS 131.1-O-2標準上的相同碼率、碼長的碼性能基本一致（標準上對應碼性能分別為1.2dB和1.9dB）。

圖4 誤碼性能仿真Fig.4 BER versus SNR simulation results

5 結束語

經過參數優化得到的原模圖，為構造性能優異的LDPC創造了前提條件，但其最終性能仍然受制于擴展算法。本文提出了一種基于原模圖擴展構造QC-LDPC的方法，在擴展過程中，以環長和環路ACE測度最大化為目標，通過搜索算法規避連通性差的短環。由于參數優化是依次進行的，所述算法在環長和ACE測度方面不是全局最優的，但具有局部最優性。仿真結果表明，采用該方法構造的LDPC，在譯碼門限和錯誤平層兩方面都具有良好的表現，證明了所述算法的有效性。同時，所構造的LDPC具有準循環結構，適于工程實現。但是，在準循環擴展過程中，參數優化次序對碼性能的影響，仍然是一個需要進一步研究的問題。

[1]THORPE JEREMY.Analysis and design of protograph based LDPC codes and ensembles [D].Pasadena：California Institute of Technology，2005.

[2]DARIUSH DIVSALAR，SAMUEL DOLINAR，CHRISTOPHER R JONES，et al.Capacity-approaching protograph codes[J].IEEE Journal on Selected Aeras in Communications，2009，27 （6）：876-888.

[3]HU XIAOYU，ELEFTHERIOU EVANGELOS，DIETER MICHAEL ARNOLD.Progressive edge-growth tanner graphs[C].IEEE GlobeCom，2001，2：995-1001.

[4]TIAN TAO，JONES R CHRISTOPHER，VILLASENOR D JOHN，et al.Selective avoidance of cycles in irregular LDPC code construction [J].IEEE Transactions on Communications，2004，52（8）：1242-1247.

[5]SEHO MYUNG，KYEONGCHEOL YANG，JAEVOEL KIM.Quasi-cyclic LDPC codes for fast encoding [J].IEEE Transactions on Information Theory，2005，51（8）：1788-1793.

[6]THE CONSULTATIVE COMMITTEE FOR SPACE DATA SYSTEMS.Low density parity check codes for use in near-earth and deep space applications [S].CCSDS 131.1-O-2，Orange Book，Issue 2，Washington，DC，2007.