基于PEG 算法的準循環LDPC 碼構造研究*

張建斌

(江蘇技術師范學院電氣信息工程學院，江蘇 常州 213001)

無線傳感器網絡中的傳感器節點在實現網絡協議和應用系統時，由于受到電源能量、通信能力、計算和存儲能力的限制，其低功耗設計對于無線傳感器網絡節點尤為重要。因此，一般除了對它們采取動態能量管理措施外，還要采取糾錯編碼方案，來保證數據的可靠傳輸［1］。在糾錯編碼中，LDPC(Low Density Parity Check)碼［2］是迄今為止發現的一種性能最接近Shannon 限的糾錯碼［3］，它幾乎適用于所有信道［4］。將LDPC 碼應用無線傳感器網絡節點作為其糾錯碼，對于降低節點能耗、提高電池使用壽命是一種理想的解決方案。而在LDPC 碼的設計中，校驗矩陣的構造是碼設計的關鍵，目前性能最好的是隨機構造法，其中就包括PEG 算法，但隨機構造法產生的校驗矩陣進行存儲將占用大量硬件資源，且編碼復雜度較高不利于硬件實現［5］。LDPC 碼校驗矩陣的另一類構造法為結構化構造法，其中包括準循環法，這類方法雖然降低了編碼的復雜度，但其只針對具體的碼型來設計，且糾錯性能相對于隨機法有所降低。本文將隨機構造法中的PEG 算法和準循環矩陣構造方法相結合，基于PEG 算法來構造準循環LDPC 碼的校驗矩陣，由此得到的LDPC 碼具有與PEG 算法非常接近的糾錯性能，而硬件實現比PEG 算法簡單，且參數選擇具有較大靈活性，非常適合于無線傳感器網絡節點的應用要求。

1 LDPC 碼的校驗矩陣與樹圖

LDPC 碼是定義在稀疏的奇偶校驗矩陣H 上的一種(n，k)線性分組碼，其中n為碼長，k為信息比特長度。H 的維數為m 行×n 列，m=n－k，其行重(每一行中非0 元素的個數)和列重(每一列中非0元素的個數)與碼長n 的比值遠小于1，而使H 結構表現出稀疏性。LDPC 碼可以分為規則碼和非規則碼，規則碼校驗矩陣H 中的行重、列重固定，非規則碼校驗矩陣H 中的行重、列重不固定［6］。一個二元域GF(2)上的5×10 校驗矩陣H 如圖1所示，當且僅當H·CT=0時，C 才是LDPC 碼的一個碼字。

圖1 5×10 校驗矩陣

LDPC 碼還可用Tanner 圖［7］描述。Tanner 圖是一種雙向圖，由變量節點、校驗節點以及這兩類節點之間相連的邊組成，變量節點對應于校驗矩陣的列，校驗節點對應于校驗矩陣的行。圖1 校驗矩陣對應的Tanner 圖如圖2所示，具有10個變量節點和5個校驗節點，每個變量節點都有2 條邊，每個校驗節點都有4 條邊。Tanner 圖中，與節點相連的邊數目稱為節點的度(Degree)，它與校驗矩陣H 的行重或列重一致，從某個節點出發又回到此節點為一循環(Cycle)，所經過的邊的個數稱為循環長度，其中最短的環的長度稱為Girth。圖2 中Tanner 圖的粗實線部分示出了一個長為6 的環，該環與圖1 校驗矩陣H 中的閉合回路一一對應，該閉合回路中任意兩條臨邊均相互垂直，每條邊的2個頂點位于同一行(或同一列)，所有頂點元素值為“1”。

圖2 校驗矩陣的Tanner 圖表示

為了研究方便起見，有時需要將Tanner 圖從某節點開始展開成樹圖，其基本方法是［8］:選定一個變量節點或校驗節點為根節點;從這個根節點出發，選取和其連接的節點(記為子節點)并用邊相連;再從這些子節點出發，選取和它們連接的節點;如果不能再生長出新的節點，或者節點在以前的樹枝中出現過，則終止生長，否則繼續連接，直到所有的節點都連接而終止。按照這樣的方法，將圖2所示的Tanner 圖從節點b5開始展開成樹圖，如圖3所示。在展開的樹圖中，當某一變量節點或校驗節點出現兩次或兩次以上時，便會構成環。若在展開的第l層中樹中第1 次出現了相同的節點，則2l 便是最短的環。由此可以判斷圖3和圖2 中相對應的一個環為:c2→b1→c1→b3→c4→b6→c2，該6 環與圖1 校驗矩陣中相應環路頂點的連線對應，為樹中最短的環。由環的結構特點可見，校驗矩陣中一個2l 環中的2l個節點分別位于l 行中，每行包含2個節點，這2l個節點同樣平均分布于l 列中。

圖3 Tanner 圖的樹圖表示

LDPC 碼通常使用的譯碼算法是LLR-BP 算法，它采用基于Tanner 圖的最大后驗概率譯碼方法。短環的存在使得對LDPC 碼進行LLR-BP 譯碼時，由于相關節點的信息經過短的路徑很快傳回給本身，破壞了迭代過程中信息傳播獨立性條件，導致迭代譯碼收斂速度減慢甚至無法正確譯碼。而實際中的碼長總是有限的，要實現無環的LDPC 碼幾乎是不可能的。因此在實際構造LDPC 碼時，要消除短環的存在(特別是4 環)，使構造的LDPC 碼中的Girth 盡可能的大。

2 PEG 算法的原理

PEG(Progressive Edge-Growth)算法［9］是一種能有效構造具有較大環長LDPC 碼校驗矩陣的算法，被Mackay 稱為是“目前所知道的最好的LDPC 碼的構造方法，尤其對構造短長度的LDPC 碼，如500、1 000、2 000 等，是十分有效的”［10］。

PEG 算法是在Tanner 圖上某一個節點(比如變量節點)出發，不斷添加節點的邊，給每個節點添加邊時，保證在該節點處的環長最大，從而使最終構造的Tanner 圖的短環數量盡可能少而碼的Girth 盡可能大。

PEG 算法流程如下:

盡管PEG 算法每次添加新邊時能保證環長度最大，但不能對Tanner 圖中的環結構進行全局優化，所以采用PEG 算法構造的LDPC 碼，其Tanner圖中的環結構復雜，特別是在長碼長時由于環交織的問題，存在大量公共節點，會在一定程度上降低迭代譯碼算法性能，因此PEG 算法一般適用于短碼的構造。

3 準循環LDPC 碼校驗矩陣的特點

3.1 準循環LDPC 碼校驗矩陣的結構

準循環LDPC 碼［11］的校驗矩陣具有準循環移位矩陣的特點，由許多b×b 維的循環方陣組成。一類mb×nb 維的準循環LDPC 碼的校驗矩陣H 可以由式(1)來表示:

其中，I(Pij)(1≤i≤m，1≤j≤n)是一個右循環移位的b×b 維方陣，稱為循環置換矩陣，它可由b×b 維的單位陣I 的每一行經過Pij次右移后得到，而Pij∈{0，1，2，…，b－1，∞}，Pij=0 時表示I(Pij)為單位方陣，Pij=∞時表示I(Pij)為全“0”方陣。

將校驗矩陣H 中的循環置換矩陣I(Pij)用循環移位次數Pij代替，得到移位參數矩陣P，其維數為m×n:

將移位參數矩陣P 中的∞元素用0 來代替，非∞元素用1 來代替，得到基矩陣A，其維數為m×n:

其中Aij∈{0，1}，1≤i≤m，1≤j≤n

由此可見，當基矩陣A和循環移位參數矩陣P確定后，準循環LDPC 碼的校驗矩陣H 也就確定了。

3.2 準循環碼的性質

定理1［12］準循環LDPC 碼校驗矩陣H和基矩陣A 的度分布相同。

由于循環置換矩陣I(Pij)每行(列)有且僅有一個非零元素“1”，所以用循環置換矩陣I(Pij)代替基矩陣A 中的“1”元素，用維數為b×b 的全0 方陣代替基矩陣A 中的“0”元素，得到的準循環LDPC 碼校驗矩陣H和基矩陣A 的度分布相同。

定理2［11］準循環LDPC 碼校驗矩陣H 中長度至少為2(l+1)的環的充分必要條件是:

其中pik，jk為基矩陣A 的環路中第k個頂點對應的循環移位參數矩陣P 中循環方陣的移位次數，b為循環方陣的邊長。

定理2 也可以這樣理解:若基矩陣A 中任意長度為2l 的環的各頂點對應的循環置換矩陣I(Pij)的循環移位次數按式(4)計算的模b和不等于0，那么由基矩陣A 擴展得到的準循環LDPC 碼校驗矩陣H中一定不存在長度為2l 的環長，存在的環長至少為2(l+1)。

定理2 實際上給出了循環移位次數的約束條件，即在對基矩陣A 進行準循環擴展時，適當選擇循環置換矩陣I(Pij)的移位值Pij，可以使原來存在于基矩陣A 中的短環在準循環LDPC 碼校驗矩陣H中得到消除。

推論:若基矩陣A 中的最小環長為6(即無4環)，則準循環LDPC 碼校驗矩陣H 中不含6 環的充分必要條件為:

Pij的確定方式不唯一，以下給出一種算法:

其中，Aij為基矩陣A 中的元素，Pij為右移次數。i表示Aij在基矩陣A 中的行號，w 表示Aij在基矩陣A 中每一行出現的序號。如將圖1 中的校驗矩陣作為基矩陣A 時，則由式(6)確定的移位次數矩陣P為

式(7)中，元素“0”表示對維數為b×b 的單位方陣循環次數為0(無循環右移)，元素“1”、“2”、“3”等表示對維數為b×b 的單位方陣右循環次數，元素“∞”表示維數為b×b 的全“0”方陣。式(7)是在b＞16 的情況下得到，當實際的Pij＞b 時，要進行“modb”處理。

4 基于PEG 算法的準循環LDPC 碼校驗矩陣的構造方法

PEG 算法在短碼時表現出優異的性能，準循環LDPC 碼具有實現方便的特點，但準循環LDPC 碼在構造檢驗矩陣時要先構造出基矩陣。本文將兩者相結合來構造基于PEG 算法的準循環校驗矩陣，即先用PEG 算法構造出短碼的校驗矩陣——基矩陣A，然后用循環置換矩陣I(Pij)和全“0”方陣對其擴展而得到準循環LDPC 碼校驗矩陣H，這樣不但彌補了PEG 算法在長碼構造時的缺陷，還可用簡單的線性移位寄存器對LDPC 碼進行編碼，減少了校驗矩陣的存儲空間，從而便于硬件實現。具體的構造步驟如下:

(1)確定需要設計的準循環LDPC 碼校驗矩陣H 的行數mb(也即準循環LDPC 碼的校驗位長度)、列數nb(也即準循環LDPC 碼的碼長)、節點度分布等參數。

(2)應用PEG 算法構造滿足度分布要求的基矩陣A，其維數為m×n，搜索并記錄最短的環及其中頂點的位置。

(3)對基矩陣A 的優化擴展。先根據基矩陣A中元素“1”的位置，按式(6)計算循環移位次數Pij的值;再找出基矩陣A 中各短環頂點元素“1”的Pij的值后判斷是否滿足式(5)，如果不滿足則對其中的Pij值進行修正，直到滿足為止;最后對基矩陣A中的元素“1”用維數為b×b 的、對單位方陣右循環Pij(修正值)次后的循環置換矩陣I(Pij)代替。

(4)重復步驟(3)，直到環記錄中所有環的“1”元素被替換。

(5)對基矩陣A 中不屬于短環的“1”元素用維數為b×b 的循環置換矩陣I(Pij)代替。

(6)對基矩陣A 中的元素∞用維數為b×b 的全“0”方陣代替。

這樣就構造出了維數為mb×nb，碼率為R=(nb－mb)/nb=1－m/n=1－dv/dc的準循環LDPC 碼校驗矩陣H?？梢?，這種方法對LDPC 碼參數的設置比較靈活，通過改變n值、m值或b值，可以構造出不同的準循環LDPC 碼校驗矩陣H;通過對Pij的優化設計，來保證所設計的準循環LDPC 碼校驗矩陣H中不含6 環，即最短的環為8 環。

5 仿真結果與分析

仿真中構造的規則準循環LDPC 碼的變量節點的度dv=3，校驗節點的度dc=6，碼率R=0.5，選取碼長256、512、1024，三種相應的校驗矩陣維數分別為128×256、256×512、512×1024。為了便于比較，分別采用本文提出的基于PEG 算法的準循環擴展法(仿真圖中標記為“準循環PEG”)和文獻［9］提出的PEG 直接構造法(仿真圖中標記為“PEG”)，輸入信號采用二進制偽隨機序列，經過RU 編碼［13］后，進行BPSK 調制，經AWGN 信道后，接收端先進行BPSK 解調，再進行LLR-BP 譯碼［6］，最大迭代次數為30 次，譯碼后的結果進行判決并統計誤碼率，仿真結果曲線分別如圖4～圖6所示。

圖4 校驗矩陣維數為128×256 時兩種構造算法的LDPC 碼BER 性能比較

圖5 校驗矩陣維數為256×512 時兩種構造算法的LDPC 碼BER 性能比較

圖6 校驗矩陣維數為512×1024 時兩種構造算法的LDPC 碼BER 性能比較

圖4～圖6 中的“準循環PEG”校驗矩陣都是由維數為8×16 的PEG 校驗矩陣作為基矩陣擴展而來，其中圖4 中的循環方陣維數16×16，圖5 中的循環方陣維數32×32，圖6 中的循環方陣維數64×64;三個圖中的“PEG”校驗矩陣維數與各圖中“準循環PEG”校驗矩陣維數相同。

由仿真結果曲線可見，不同長度的LDPC 碼，采用本文提出的基于PEG 算法的準循環LDPC 碼與文獻［9］提出的PEG 直接構造法的LDPC 碼性能非常接近，在信噪比低于1.2 dB 時，三幅圖反映出的兩種算法的BER 幾乎一樣;尤其當信噪比高于1.2 dB 時，圖5、圖6 反映出本文提出的算法要優于文獻［9］提出的PEG 算法;在圖4 中，當信噪比在1.4 dB至1.7 dB 之間時，本文提出的方法比文獻［9］提出的PEG 直接構造法的LDPC 碼性能稍差些，但是，前者具有準循環結構，更適合于硬件實現。

6 結論

本文提出了一種基于PEG 算法的準循環LDPC校驗矩陣的構造方法。該方法充分利用了PEG 算法在短碼構造時的優勢，并通過對循環移位矩陣循環移位參數的優化設計，來進一步消除所構造的準循環LDPC 碼的短環，仿真結果顯示了該方法具有與PEG 直接構造法非常接近的糾錯性能，特別是在信噪比高于1.2 dB 時糾錯性能優于PEG 直接構造法。同時該方法通過改變基矩陣的n值、m值或單位陣的邊長b值，可以構造出不同的準循環LDPC碼校驗矩陣，因而在LDPC 碼參數的選擇上具有較大的靈活性。該方法所構造的校驗矩陣由于準循環特點而具有確定的結構，而PEG 直接構造法屬于隨機構造法，產生的校驗矩陣沒有確定的結構，存儲會占用大量的硬件資源，其編譯碼實現復雜度大，因此，在相同碼長的情況下，該方法的準循環結構特點將使得編碼和譯碼更容易實現，具有比PEG 直接構造法更低的實現復雜度，它尤其適合于類似無線傳感器網絡節點中對低能耗要求的應用場合。

［1］杜曉通.無線傳感器網絡技術與工程應用［M］.北京:機械工業出版社，2010:143－168.

［2］Gallager R G.Low-Density Parity-Check Codes［D］.Cambridge，MA:M.I.T.Press，1963.

［3］MacKay D J C，Neal R M.Near Shannon Limit Performance of Low Density Parity Check Codes［J］.Electronics Letters，1996(8):1645－1646.

［4］肖揚.Turbo 與LDPC 編解碼器及其應用［M］.北京:人民郵電出版社，2010:5－14.

［5］楊華，田應洪，張小軍，等.基于范德蒙矩陣的LDPC 碼構造［J］.電子器件，2009(2):413－416，421.

［6］袁東風，張海剛.LDPC 碼理論與應用［M］.北京:人民郵電出版社，2008:30－91.

［7］Tanner R M.A Recursive Approach to Low Complexity Codes［J］.IEEE Transactions On Information.Theory，1981(9):533－547.

［8］張煥明，葉梧，馮穗力.LDPC 碼的樹圖法構造［J］.電訊技術，2007(4):166－168.

［9］Xiao Yu Hu，Eleftheriou E，Arnold D M.Regular and Irregular Progressive Edge-Growth Tanner Graphs［J］.IEEE Trans.Info.Theory，2005(1):386－398.

［10］Mackay D J C.Good Error-Correcting Codes Based on Very Sparse Matrices［J］.IEEE Trans.Info.Theory，Vol.IT－45，1999(3):399－431.

［11］Fossorier M.Quasicyclic Low Density Parity Check Codes［J］.IEEE Trans.Inform.Theory，2005(8):1788－1793.

［12］管武，項海格.具有大碼間距和大環路的QC-LDPC 碼的構造［J］.電路與系統學報，2011(4):1－5.

［13］Richardson T，Urbanke R.Efficient Encoding of Low-Density Parity-Check Codes［J］.IEEE Trans.Info.Theory，2001(2):638－656.