基于PEG 算法的準循環(huán)LDPC 碼構造研究*

張建斌

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

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

1 LDPC 碼的校驗矩陣與樹圖

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

圖1 5×10 校驗矩陣

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

圖2 校驗矩陣的Tanner 圖表示

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

圖3 Tanner 圖的樹圖表示

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

2 PEG 算法的原理

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

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

PEG 算法流程如下:

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

3 準循環(huán)LDPC 碼校驗矩陣的特點

3.1 準循環(huán)LDPC 碼校驗矩陣的結(jié)構

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

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

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

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

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

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

3.2 準循環(huán)碼的性質(zhì)

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

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

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

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

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

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

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

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

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

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

4 基于PEG 算法的準循環(huán)LDPC 碼校驗矩陣的構造方法

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

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

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

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

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

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

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

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

5 仿真結(jié)果與分析

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

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

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

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

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

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

6 結(jié)論

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

［1］杜曉通.無線傳感器網(wǎng)絡技術與工程應用［M］.北京:機械工業(yè)出版社，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］管武，項海格.具有大碼間距和大環(huán)路的QC-LDPC 碼的構造［J］.電路與系統(tǒng)學報，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.