1、桂林電子科技大學碩士研究生糾錯碼理論課程學生： 王廣耀 學號： 1502201054專業： 信息與通信工程題目： 基于PEG算法的LDPC碼構造教師： 王俊義職稱： 教授時間：基于PEG算法的LDPC碼構造及改進摘要：漸進邊增長(PEG)算法構造的低密度奇偶校驗碼(LDPC)在保證局部圍長最大時仍有較多數目的短環。針對該問題，提出一 種新的準循環LDPC碼構造方法。該方法在PEG算法中采用環多項式(PC)標記，利用PC-PEG方法構造的矩陣作為基矩陣，并對 其進行準循環擴展，以消除基矩陣中的短環。實驗結果表明，該方法構造的LDPC碼可大幅減少短環的數目。同時由于引入了準 循環結構，能降低編碼復

2、雜度。為了兼顧LDPC碼較高的糾錯性能和較簡單的硬件實現，提出了一種基于PEG算法的準循環LDPC碼校驗矩陣的構造方法，該方法首先利用PEG算法構造基矩陣，然后利用提出的移位參數公式來構造循環移位矩陣，再用循環移位矩陣和全零矩陣對基矩陣進行優化擴展，形成的校驗矩陣最短環長至少為8環。該方法具有與PEG算法非常接近的糾錯性能，尤其是當信噪比高于1.2 dB時要優于PEG直接構造法，而硬件實現比PEG算法簡單，且參數選擇靈活方便。關鍵詞：低密度奇偶校驗碼；漸進邊增長算法；準循環結構；短環；循環置換矩陣；基矩陣1、概述PEG (progress edge growth)算法是當前公認的對中、短碼長L

3、DPC碼構造非常有效的算法之一，它采取逐邊添加的力一式構造碼的Tanner圖，在滿足給定度分布的條件下能使Tanner圖中短環數量盡可能少，使碼的圈長盡可能大。但由于其采用隨機構造的做法，使該類碼的H矩陣缺乏結構性，編碼復雜度高，尤其是對長碼而言，其構造及編碼實現的運算量更是劇增。基于PEG算法的QC-LDPC碼是首先以PEG算法構造，一個維數較小的一致校驗矩陣，稱為基矩陣，再將基矩陣中的“基矩陣維數由編碼后的碼長n和循環置換矩陣的維數P及碼率決定。文獻fl給出了一種基于PEG算“1”元素和0元素分別替換為px p維的循環置換矩陣(或單位矩陣的循環移位)和全零矩陣。法的QC-LDPC碼構造力一

4、法，但在擴展的過程中只消除了部分6環，沒有將圈長擴大。文獻fl給出了另一種擴展PEG算法構造的基矩陣的力一法，但由于PEG算法的非結構化，這種算法只是擴大了基矩陣中的一部分環的長度，不能確定是否擴大了圈長。本文提出的基于PEG算法的 QC-LDPC碼構造力一法成功擴大了圈長，同時擴大了部分其他長度的環。算法中用到了PEG算法，環搜索算法，單位矩陣的循環移位值的選擇算法，并通過仿真驗證了改進力一法的有效性。胡曉宇等人提出了PEG算法，MacKay認為PEG碼是目前最佳的Gallager碼(碼長在500以上)。我們可以用圖例和算法流程來解釋這種構造力一法。PEG算法不僅可以構造規則碼，而且可以構造

5、非規則碼，算法和上面基本類似，只要把變量節點按度數升序排列即可。PEG算法可以獲得盡量大的局部最小圈長。本文的環搜索算法采用的是迪科斯徹算法(Dijkstra)的思想，該算法是由荷蘭計算機科學家艾茲格·迪科斯徹(Edsger Wybe Dijkstra) 1959年發明的。算法解決的是有向圖中最短路徑問。通過該算法可以找到所有長度為L的環長。但是上述算法的計算量很高，與校驗矩陣的列數成線性關系，計算過程中的存儲量要求也很高。由式(1)準循環矩陣中環的形成條件知，當回路中的各頂點的移位值當且僅當滿足式(1)的等式時矩陣中形成長度為Zt的環·其中，Sak/3k為H矩陣中回路的第

6、k個頂點所在的循環子矩陣的移位值。如果選擇適當的一組循環移位值，使其不滿足上面的等式，就能消除長度為Zt的環。由等式的性質，我們知道當等式中只有一個變量時才能根據等式關系求出它的確切值。在本算法中也是將首先確定上面等式(1)中的2 t-1個值，然后根據式(1)求出不能選擇的循環移位值。由QC-LDPC的校驗矩陣的環結構可以看出，如果依次確定各列中循環子矩陣的移位值，并且只考慮當前列與其前的所有列形成的環，那么通過去除滿足等式(1)的循環移位值，可得到可選的循環移位值的集合，此集合任一個移位值都能消除該列與其前的所有列形成的環。算法的具體步驟如下:1.如果循環矩陣的維數是L，基矩陣中每個塊元素可

7、選的移位值的集合是(1, 2, 3.L-1)o2.矩陣中第一列的循環子矩陣的移位值從他們的移位值集合中隨機產生。3.從矩陣的第二列開始，每一列的第一個循環子矩陣的移位值在1到L-1中隨機產生， 然后產生的記錄循環的矩陣中搜索它與前面的列是否形成環，如果形成環，就根據上面的等式計算出此列的其他循環子矩陣不應該選擇的移位值，并從他的可選的移位值集合中去除這一元素。4.在循環子矩陣可選的移位值集合中隨機選擇移位值。5.逐列進行步驟3中的操作，確定矩陣中所有塊元素的移位值。利用上述算法，若一個塊元素被包含在小于L-1個環中，必然會消除矩陣中包含這一塊元素的所有長度為2t的環;若大于L一1也有很大可能消

8、除所有長度為2t的環。構造基于PEG算法的準循環低密度奇倡檢驗碼的步驟如下: 1.根據要生成的準循環低密度奇倡奇倡校驗碼的碼長，碼率，校驗矩陣的行重，列重的要求確定基矩陣的碼長、碼率、行重、列重，以及循環置換矩陣的維數L; 2.利用PEG算法生成一個基矩陣; 3.利用環搜索程序找到矩陣中的短環; 4.利用搜索到的記錄環的矩陣統計出經過每一列的環的數量，按照環數的降序對矩陣的列重新排序; 5.搜索新生成的校驗矩陣中的短環; 6.應用移位值選擇程序確定塊元素的移位值; 7.將列的順序重排恢復成原矩陣; 8.根據不同的移位值選擇循環置換矩陣進行擴展，對于基矩陣中的零元素用L維的全零力一陣擴展。利用上

9、述算法可以使生成的準循環低密度奇倡校驗碼的圈長增加2，使矩陣中的短環減少。此算法的缺點是計算量較大，適用于在基矩陣較小，需要消除的環長也較小的情況。本論文中利用此力一法構造了列重為3,圈長為8,碼率為0.5，碼長分別為504,1008以及碼率為0.33，碼長為816的準循環低密度奇倡校驗碼。2、PEG構造法 PEG算法是一種逐邊增加的算法，每增加一條邊時按照樹形圖展開'展開終止的條件為當前校驗節點集合的補集不為空集，再展開一步，校驗節點集合的補集為空集則終止，或者展開到校驗節點數不再隨展開而增加時停止。這樣雖然可以保證每增加一條邊可以使局部圍長最大，但是該構造方法短環數較多，較多的短環

10、數將嚴重影響譯碼性能，為此，本文引入一種PC標記法以減少短環的數目。 圖1是以變量節點K為根節點展開的樹形圖，節點的環多項式計算方法如下：(1) 初始化根節點的多項式值為1,圖中PC(K) = 1; (2)子節點的多項式PC值等于父節點乘以尤，如果1個子節點有2個或者更多的父節點，則該節點的多項式PC值計算如下：首先把所有父節點的PC值相加；然后把得到的值乘以X，即為該子節點的C值，例如：7有 2個父節點，則7的值為2x3。同一個校驗節點可能在展開的樹形圖中多次出現，則校驗節點c7的多項式PC值可以描述如下：PC(Cj) = wxx2kx + w2x2(t+1)-1 + ，A= 1,2，其中，

11、wvc241表示添加叫條:的環；w2x2(t+1H表示添 加w2條2(k +1)的環。如果校驗節點Cp在樹形圖中沒有出現，則Cp的多項式PC值為0，選擇Cp建立邊將不會導致任何環長小于2(/ + 2)的環，I為樹形圖展開的最大層數。 PCPEG構造法采用比較各校驗節點的多項式PC值進行新增邊的選擇：比較校驗節點的環多項式的最小冪次，然后從各校驗節點的最小冪次集合中選擇其中的最大值，這樣可以保證該校驗節所形成的最短環最大。如果這樣的校驗節點不唯一，進一步比較系數值，選擇系數值最小的可以保證該短環的數目最小。在實際構造中，可以給x賦 一個值(令x = 0.1)，將多項式簡化為一個代數值，從而將比較

12、環多項式的冪次和系數值簡化為比較環多項式的值，將兩步簡化為一步比較。簡化后PCPEG構造法的復雜度沒有明顯增加，其性能也不會發生惡化。采用PCPEG構造法構造一個碼長為n包含個校驗式的LDPC碼，具體步驟如下所示:對于每一個變量節點= 1,2，(1) 為變量節點K添加第一條邊時，選擇度數最小的校驗節點連接，添加其他邊時轉步驟 (2)變量節點和校驗節點PC值初始化。1) 變量節點值初始化2)校驗節點PC值初始化，PC(Ck) = 0(3)以G為頂點按樹形圖展開，并逐層更新變量節點和校驗節點的PC值。(4)若校驗節點Cj由變量節點V;展開得到，校驗節點的PC值更新如下：PC(CJ) = PC(CJ

13、) + xPC(Vi)(5)若變量節點&由校驗節點展開得到，變量節點 1的C值更新如下：PC(Vq) = PC(Vq) + xPC(Cp)(4)選擇PC值最小的校驗節點作為新增連接邊，即Cj = arg min(PC(C)。其中，Vc為可選校驗節點的集合。(5) 返回步驟(2)完成變量節點其他邊的建立。2.1 PEG算法的原理PEG (Progressive Edgerowth)算法9是一種能有效構造具有較大環長LDPC碼校驗矩陣的算法，被Mackay稱為是目前所知道的最好的LDPC碼的構造方法，尤其對構造短長度的LDPC碼，如500,1 000,2 000等是十分有效的。 PEG算法

14、是在Tanner圖上某一個節點(比如變量節點)出發，不斷添加節點的邊，給每個節點添加邊時，保證在該節點處的環長最大，從而使最終構造的Tanner圖的短環數量盡可能少而碼的Girth盡可能大。盡管PEG算法每次添加新邊時能保證環長度最大，但不能對Tanner圖中的環結構進行全局優化，所以采用PEG算法構造的LDPC碼，其Tanner圖中的環結構復雜，特別是在長碼長時由于環交織的問題，存在大量公共節點，會在一定程度上降低迭代譯碼算法性能，因此PEG算法一般適用于短碼的構造。2.2 LDPC碼校驗矩陣的構造方法 PEG算法在短碼時表現出優異的性能，準循環LDPC碼具有實現方便的特點，但準循LDPC碼

15、在構造檢驗矩陣時要先構造出基矩陣。本文將兩者相結合來構造基于PEG算法的準循環校驗矩陣，即先用PEG算法構造出短碼的校驗矩陣基矩陣A，然后用循環置換矩陣I Phi)和全0”方陣對其擴展而得到準循環LDPC碼校驗矩陣H，這樣不但彌補了PEG算法在長碼構造時的缺陷，還可用簡單的線性移位寄存器對LDPC碼進行編碼，減少了校驗矩陣的存儲空間，從而便于硬件實現。具體的構造步驟如下: (1)確定需要設計的準循環LDPC碼校驗矩陣H的行數mb(也即準循環LDPC碼的校驗位長度)、列數nb(也即準循環LDPC碼的碼長)、節點度分布等參數。 (2)應用PEG算法構造滿足度分布要求的基矩陣A，其維數為mXn，搜索

16、并記錄最短的環及其中頂點的位置。 (3)對基矩陣A的優化擴展。先根據基矩陣A中元素1”的位置，按式(6)計算循環移位次數的值;再找出基矩陣A中各短環頂點元素“1”的的值后判斷是否滿足式(5)，如果不滿足則對其中的值進行修正，直到滿足為止;最后對基矩陣A中的元素“1”用維數為bxb的對單位方陣右循環，(修正值)次后的循環置換矩陣代替。 (4)重復步驟(3)，直到環記錄中所有環的“1 "元素被替換。 (5)對基矩陣A中不屬于短環的“ 1”元素用維數為bxb的循環置換矩陣代替。(6)對基矩陣A中的元素0o用維數為bxb的全“0”方陣代替。 這樣就構造出了維數為mb x nb，碼率為R= (

17、nb-mb) /nb=l-m/n=l-dv/dc,的準循環LDPC校驗矩陣H。可見，這種方法對LDPC碼參數的設置比較靈活，通過改變n值、m值或b值，可以構造出不同的準循環LDPC碼校驗矩陣H;通過對P，的優化設計，來保證所設計的準循環LDPC碼校驗矩陣H中不含6環，即最短的環為8環。3、基于PCPEG算法的準循環擴展假設擴展后的校驗矩陣具有如下形式：其中，1表示單位矩陣循環移位Rhj次后得到的循環置換矩陣，-/在/-為置換矩陣的維數。/(-I) 表示pxp維的全零矩陣，/(0)為單位矩陣。定理若矩陣的樹形圖中包含一個長為2/的環，當 且僅當好矩陣中包含一個長為2?的閉合回路，且有：其中，&a

18、mp;為h矩陣中回路的第&個頂點所在塊元素的移位值。構造開矩陣時，若能保證任意長為2的閉合路徑均不滿足定理中的條件，則構造出的LDPC碼的圍長最大為2。因此，在對基矩陣進行準循環擴展時，適當選擇各個循環移位矩陣的移位值可以進一步消除基矩 陣中的短環。通過上面的分析，可以得到構造丑矩陣的準循環擴展算法步驟如下:(1)通過PCPEG算法設計出滿足度分布要求的基矩陣，搜索并保存環的路徑。以基矩陣中的環為單位逐步完成對T元素的替換，即在所記錄的環中取出長度最短的環，將環中“1”元素逐個用循環置換矩陣替換，設定各循環置換矩陣的移位值，使其不滿足定理1的約束條件。(3)重復步驟(2)，直到環記錄中

19、所有環的“1”元素均被替換。1基矩陣中不屬于任何環的“1”元素用隨機移位次數的循環置換矩陣替換，“0”元素用全零矩陣替換。2搜索矩陣對應樹形圖的圍長，檢測長度為圍長的環包含的變量節點數是否滿足設計要求，若不滿足，則回到步驟(1)重新構造，若滿足，則輸出丑矩陣。 4、迭代編碼算法若LDPC碼的校驗矩陣具有如圖1所示的下三角結構,在圖中對角線的位置上為全 1!,而其余的 1!均在對角線的左邊,則可以直接采用迭代編碼算法進行編碼.設碼字向量為xFn ,將其分為2個部分,即信息位向量sF n-m 和校驗位向量pFm ,亦即x(s,p)Fn-m。則該碼的編碼過程可具體描述為 圖1 具

20、有下三角結構的LDPC碼的校驗矩陣1) 直接將信息比特的值賦給信息位向量s; 2)采用后項迭代的方式確定所有校驗位的值,即對所有的l0,n-k-1,從小到大依次計算下式 式中:hi,j表示第i行,第j列上的元素.實際上,該編碼過程就是在從上到下依次利用校驗矩陣各行的約束關系.對于每一個校驗約束關系,其中涉及的變量除了對角線上的 1!所對應的校驗位外,其余的變量要么是信息位,要么就是前面已經求出的校驗位,也就是說,該校驗關系中只有一個未知變量,因此可以很容易求出校驗位的值.當校驗矩陣的平均行重相對于碼長可以看做很小的常數時,該編碼方法就具有線性的復雜度;同時該編碼算法不需要對校驗矩陣進

21、行預處理。5、改進度的PEG構造算法基于高斯消去的編碼算法和基于近似下三角結構的有效編碼算法適用于一般的校驗矩陣,但在編碼的過程中需要對校驗矩陣進行一定的預處理,兩種算法都包括對矩陣的求逆,求逆的過程不僅計算量大,硬件難以實現,同時還要求矩陣滿秩,在實際應用中,很多情況下并不能滿足上述條件.因此,直接構造性能優異的、具有下三角結構的校驗矩陣且可采用迭代編碼算法的LDPC碼具有重要的實踐意義.針對此,文中提出了一種直接構造具有下三角結 構的非規則LDPC 碼的方法-改進的PEG算法。PEG構造方法是迄今為止構造性能優異的構造中短碼長LDPC碼的有效方法.該算法在已有Tanner圖上添加邊來構造最

22、終的Tanner圖,每次添加時都盡可能減少對已有Tanner圖的影響,及盡可能使LDPC碼的圍長較大.它不但適用于規則LDPC碼的構造,同樣也適用于非規則LDPC碼的構造.本文提出的構造算法基本與PEG的算法流程相同.主要的改進有如下幾點: 1)在添加比特節點時,即添加H矩陣的每列時,順序是沿著列號由大到小的順序依次進行. 2)在添加圖1所示的下三角部分的比特節點時,每個比特節點的第1校驗位必須添加在對角線 的位置上,其余的校驗位添加在對角線的下方,即添加H矩陣中具有下三角結構的那些列時,每列的第1個 “1”在對角線的位置上,其余的 “1”在對角線的下方。 3)為了盡量滿足

23、給定的度分布,同時為了使構造的LDPC碼的圍長盡量大,在構造非下三角部分的節點時,按照節點度數遞減的次序依次添加剩余的比特節點,即H矩陣的每列。6、編碼復雜度分析基于高斯消去的編碼算法復雜度計算包含2個部分:一是將校驗矩陣高斯消去成下三角矩陣的結構即對校驗矩陣進行預處理,運算復雜度為o(n3 ),其中n為碼長.二是編碼復雜度為o(n2 ),這是因為該編碼算法的編碼復雜度取決于生成矩陣的稀疏性,設生成矩陣的平均列重為w,則整個編碼過程中大約需要wn次與運算,(w-1)n次異或運算.盡管LDPC碼的校驗矩陣是非常稀疏的,但它的生成矩陣卻并不稀疏,通常w與n的比值是一個不可忽略的常數,這使得其編碼復

24、雜度往往與其碼長的平方呈正比. 而迭代編碼算法的編碼復雜度完全取決于LDPC碼的校驗矩陣的稀疏性,設校驗矩陣的平均列重為w,則整個編碼約需要w(n-k)次與運算,(w-1)(n-k)次異或運算,其中n為碼長,k為信息為長,當w相對于n可以看作很小的常數時,該編碼算法就具有線性的復雜度.本文提出的改進的PEG算法能夠直接構造出具有下三角結構的校驗矩陣,不僅避免了對校驗矩陣的預處理,同時保證了矩陣的稀疏性,因此平均列重w相對于碼長n就可以看作一個很小的常數,即可實現LDPC碼的線性復雜度編碼. 由上述分析可知,雖然改進的PEG構造算法在性能上并不能超越PEG構造算法,但其最大的優勢在于其編碼復雜度

25、低,更易于實現。7、仿真結果及分析圖2所示的是在MSK調制,誤碼率在r=1/2和r=2/3情況下的性能仿真曲線.其中LDPC碼的信息位長均為1024,譯碼采用BP譯碼算法,為了 給硬件實現提供參考,最大譯碼迭代次數取為25,信道為高斯白噪聲信道.PEG構造算法采用基于高斯消去的編碼算法,而改進的PEG構造算法采用迭代編碼算法.其中1/2誤碼率的LDPC碼的變量節點度分布服從(x)=0.30013x+0.28395x2 +0.41592x7 ;2/3誤碼率的LDPC碼變量節點度分布服從(x)=0.25105x+0.30938x2 +0.00104x3 +0.43853x9 .從圖中可以看出,采用

26、改進PEG構造方法與直接應用PEG構造方法構造出的LDPC碼的誤碼率曲線基本重合,即這2個LDPC碼的糾錯性能非常接近,從而表明改進的PEG算法構造的具有下三角結構的LDPC碼可以具有較強的糾錯能力. 圖2 改進的PEG構造方法構造的LDPC碼的性能本節對基于PEG算法循環置換矩陣擴展的QC-LDPC碼進行了仿真，并與MacKay隨機碼，PEG隨機碼，PEG單純擴展的QC-LDPC碼進行了比較分析。在仿真結果中，本文構造的基于PEG算法循環置換矩陣擴展的QC-LDPC碼表示為PEG-E-LDPC，原論文中構造的QC-LDPC碼表示為PEG-OE-LDPC Mackay隨機碼表示為Mackay-

27、LDPC PEG算法直接構造的LDPC碼表示為PEG-LDPC純擴展生成的QC-LDPC碼表示為EG-PE-LDPC oE61No(dB)圖IAWGN信道下PEG-E-LDPC(504,252)的誤碼性能。基于高斯消去的LDPC碼編碼算法復雜度較高,在中短碼長時不易實現.對此,T.J.Richardson等提出了一種基于近似下三角矩陣的有效編碼算法(也叫貪婪算法).該算法雖然可以實現在線性時間內編碼,但其應用條件受一定的限制,成為實用化過程中的一個阻礙.因此,近年來出現了一種低編碼復雜度Quasi Cyclic LDPC碼的編碼算法.QC碼編碼可以用簡單的移位寄 存器實現,其生成矩陣具有循環或

28、準循環的特性,因此可以實現線性復雜度編碼.QC碼雖然有簡單的編碼結構,但是其碼長和碼率的參數選擇不夠靈活,導致該算法構造出的碼字不具有兼容性,實用性較差.隨后王鵬等在提出了迭代編碼算法，該編碼算法不僅具有線性編碼復雜度,且不會改變矩陣的稀疏性,同時克服了碼長和碼率的參數選擇不夠靈活的缺陷.在本文中,將進一步對迭代編碼算法進行研究,并針對該編碼算法提出一種具有下三角結構的非規則LDPC碼校驗矩陣的構造方法-改進的PEG構造算法。低密度奇偶校驗(Low Density Parity Check, LDPC)碼以其低復雜度的迭代譯碼算法和可逼近信道容量限的糾錯性 能而得到眾多學者的關注。目前性能優良

29、的LDPC碼大都通過隨機構造方法構造，但是這種碼編碼復雜度高，不利于硬件實現文獻4提出的漸進邊增長(Progressive Edge Growth, PEG)算法是一種隨機構造算法，其參數構造方便靈活，并且在每次添加一條邊時使局部圍長都保持最大，但是PEG算法以及后來人們在其基礎上修改的其他算法都只 考慮了圍長，忽視了短環的數目，如果短環的數目偏多， 即使圍長較大，也將嚴重影響譯碼性能。文獻7提出了基PEG算法的準循環碼(Quasi-cycle Low Density Parity Check, QCLDPC)構造方法，具有與隨機碼相近的性能，同 時由于引入準循環結構減少了存儲空間，降低了編譯碼復雜度。但該方法沒有進一步研究準循環碼的環結構，進而減少碼中短環的數量。本文在分