基于拉丁方陣的準循環LDPC碼構造

陳集煒，趙澤茂，包建榮

(杭州電子科技大學通信工程學院，浙江杭州310018)

0 引言

低密度奇偶校驗碼(Low-Density Parity-Check，LDPC)［1］。證明其具有逼近香農限的好碼［2］。自此，LDPC碼開始成為信道編碼的研究熱點。近年來對LDPC碼的構造方法研究逐漸轉向準循環(Quasi-Cyclic，QC)LDPC碼。QC-LDPC碼是結構化LDPC碼的一類。該類LDPC碼性能優良、編譯碼復雜度較非結構化碼低而受到研究者的關注。QC-LDPC碼因其半結構化分塊矩陣結構，便于硬件實現，同時具有優異的糾錯性能，提出了一種LDPC碼編碼方法［3］。本文主要參考該LDPC碼的基于拉丁方陣的三元系構造方法，提出了一種新的準循環LDPC碼構造方法。方法是一種“Block-in-Block”的結構化構造方法，基矩陣采用拉丁方陣的Block構造思路，通過設定合適的移位系數，去除校驗矩陣的6環。而且，它還可以構造任意碼率、碼長的QC-LDPC碼，也更易于實現。

1 基矩陣的構造

1.1 基于拉丁方陣的構造方法

Milenkovic所提的編碼算法利用斯坦納三元系(Steiner Triple System，STS)，基于等冪、對稱的拉丁方陣特性，并擁有結構化的構造［3］。Steiner三元系的定義:V是一個v元集合，B是V三元子集構成的集族。如果V中任意兩個互異元素恰同時含在B的一個元中，則稱(V，B)為v階的Steiner三元系。拉丁方陣是一個m維方陣，其中每行每列都包含數集{1，2，…，m}。等冪的拉丁方陣是指拉丁方陣的(i，i)位置的元素為i，即方陣的主對角線上的元素為1，2，…，m的順序排列;對稱的拉丁方陣是指方陣的元素沿主對角線對稱。

STS的構造方法具有嚴謹的數學結構:拉丁方陣的維數為2m+1;對應構造的LDPC碼的校驗節點數則為6m+3;對應的三元集數目為(3m+1)(2m+1)=(v(v－1))/6。校驗矩陣的每列擁有2m+1個矩陣塊，每行擁有m(2m+1)個矩陣塊。由拉丁方陣得來的三元集被分成類型1與類型2兩類［3］，第1類在LDPC碼的校驗矩陣中為維數為3的單位矩陣I，第2類則為右移位一位的維數為3的單位矩陣

1.2 構造方法性能分析

根據Steiner三元系定義，V中任意兩個互異元素只同時含在B的一個元中。故文獻3構造的校驗矩陣不存在4環。文獻3同時提出一種減小6環數目的方法:通過刪除擁有最大6環數的列，來減少6環的數目。該方法具有一定的改進，但還存在不足。它僅是減小6環數，而不能完全去除6環。通過刪除列來減少6環的方法，無法構造碼率靈活與性能優異并重的LDPC碼。本文在該構造方法引入QCLDPC碼的特性，改進了該方法的不足。

2 構造QC-LDPC碼

常見的QC-LDPC碼又稱為塊狀LDPC(Block-LDPC)碼。塊狀LDPC碼的校驗矩陣H可表示如下所示。其中，I表示A×A的單位矩陣，又稱循環置換矩陣;pi，j是其循環移位系數。若pi，j=－1，代表I(－1)是一個A×A的全零矩陣;若pi，j≥0，則代表單位矩陣I右移pi，j位。QC-LDPC碼的校驗矩陣H，可用簡化的循環移位系數矩陣等價表示。矩陣P中的每個元素pi，j對應校驗矩陣H中的每個循環置換矩陣的循環移位系數。

QC-LDPC碼的校驗矩陣H中所存在的長度為2l的塊狀環路，可用循環移位系數等價表示為:pi1，j1其中，pia，ja與 pia+1，ja+1在校驗矩陣 H 的同一行或者同一列;pia，ja與 pia+2，ja+2不一定在同一行或同一列;a的取值范圍為0≤a≤2l－2的任意值。

性質一［4］QC-LDPC碼的校驗矩陣H對應的Tanner圖中存在一條長為2l的環路的充要條件是:環路上各基矩陣節點的循環移位系數滿足:

而通過構造合適的移位系數矩陣，可以優化校驗矩陣的環長，去除短環，使環長達到8環及以上。本算法構造的基矩陣不包含4環，所以僅需刪去6環即可。

算法具體步驟如下:

(1)把生成的基矩陣Hb中的0元素置為－1，1元素置0，得到初始移位系數矩陣P0;

(2)初始移位系數矩陣P0的前3行的0元素保持不變，第4—6行的0元素，每行按正整數的順序賦值，即分別賦值為1，2，3，…，p(1≤p≤A)，前6行的－1元素保持不變;

(3)從第7行開始，用式2檢測0元素與以上幾行的非零元素是否形成了小于8的短環。若沒有則保持不變，否則生成一個取值范圍為1≤p≤A的隨機數p替換0元素;

(4)新生成的移位矩陣若滿足式2，則產生另外一個不同的隨機數進行替換，直至消去小于8環的短環。若在一定的次數內無法消去短環，則退回前3行，重新選擇移位系數;在允許的一定次數內仍然無法消去短環，則退回前6行;并以此類推，直至得到矩陣P;

(5)將移位系數矩陣P的－1元素與非負元素分別用維數為A的全零矩陣OA與向右移位pi，j位的維數為A的單位矩陣替換，即得所需的校驗矩陣H。

該移位系數構造法與傳統的隨機構造法不同處在于:因基矩陣是分塊的矩陣，在選擇移位系數的時，每塊可選擇相同的移位系數。

3 仿真及分析

3.1 性能仿真

根據上述編碼構造原理，構造了不同碼長的LDPC碼，并與一些經典的隨機構造LDPC碼的誤碼性能進行了仿真比較。仿真參數如下:信道為二元輸入高斯白噪聲信道;譯碼算法采用置信傳播(Belief-Propagation，BP)譯碼算法;最大迭代次數為50次;每個信噪比仿真誤碼達200個碼字時，仿真結束。

仿真1 用本算法分別構造碼長為480bit、990bit，碼率都為1/2的LATIN QC-LDPC碼，每個移位矩陣的大小分別為16×16與33×33，校驗矩陣列重為3;同時構造對照的參數相同的PEG-LDPC碼，進行局部圍長仿真比較，得仿真結果如圖1所示。

仿真2 用本算法分別構造碼長為480bit、990bit，碼率都為1/2的LATIN QC-LDPC碼，每個移位矩陣的大小分別為16×16與33×33，校驗矩陣列重為3;同時構造對照的參數相同的PEG-LDPC碼，進行誤碼率仿真比較。仿真結果如圖2所示。

圖1 局部圍長仿真

圖2 誤碼率仿真對比圖

3.2 仿真結果分析

PEG算法一直被認為是二元有限碼長下次優的LDPC碼構造方法［5］，故采用PEG算法與本算法對比具較強說服力。圖1中的仿真結果表明，當碼長為480bit時，LATIN QC-LDPC碼平均圍長與PEG算法構造的碼字基本相等;而當碼長為990bit時，LATIN QC-LDPC碼因為其Block-in-Block的結構，平均圍長不變，而PEG算法構造的碼字的平均圍長則大大大于Block-in-Block的結構。

圖2中的仿真結果也表明了在碼長為990bit時，PEG-LDPC碼的誤碼性能稍優于LATIN QC-LDPC碼:在誤碼率為10－5的數量級時，PEGPC-LDPC碼比LATIN QC-LDPC碼只有約0.1dB的增益;但在碼長為480bit時，本算法構造的LATIN QC-LDPC碼性能優于PEG-LDPC碼。且在誤碼率為10－6數量級時，LATIN QC-LDPC碼比PEGPC-LDPC碼約有0.15dB的增益。PEG-LDPC碼是隨機構造的碼字，而本文構造的LDPC碼是“Block-in-Block”的結構，具有準循環特性，更易于硬件實現。

4 結束語

本文參考了拉丁方陣及Steiner三元系LDPC編碼構造法，提出了一種QC-LDPC碼的構造方法。仿真結果表明，本算法在構造的短碼與PEG算法構造的碼字相比，性能更好，且在誤碼率為10－6數量級時無明顯的誤碼平底。同時，本算法所構造的QC-LDPC碼，作為一種結構化構造的編碼方法，非常有利于實際通信系統的硬件實現。

［1］ Gallager R G.Low density parity check codes［M］.Cambridge:MIT Press，1963:21 －28.

［2］ Mackay D J C，Neal R M.Near Shannon limit performance of low-density parity-check codes［J］.Electronics Letters，1996，32(18):1 645 －1 646.

［3］ Milenkovic O，Laendner S.Analysis of the cycle-structure of LDPC codes based on Latin squares［C］.Paris:Proc of IEEE International Conf on，2004:777 －781.

［4］ Myung S，Yang K，Kim J.Quasi-cyclic LDPC codes for fast encoding［J］.IEEE Trans on inf Theory，2005，51(8):2 894 －2 901.

［5］ Hu Xiao-Yu，Evangelos Eleftheriou，Dieter M Arnold.Regular and irregular progressive edge-growth tanner graphs［J］.IEEE Trans Comm，2005，51(1):386 －398.