基于PEG算法的LDPC碼構(gòu)造及改進(jìn)

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

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

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

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

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

6、k個(gè)頂點(diǎn)所在的循環(huán)子矩陣的移位值。如果選擇適當(dāng)?shù)囊唤M循環(huán)移位值，使其不滿足上面的等式，就能消除長度為Zt的環(huán)。由等式的性質(zhì)，我們知道當(dāng)?shù)仁街兄挥幸粋€(gè)變量時(shí)才能根據(jù)等式關(guān)系求出它的確切值。在本算法中也是將首先確定上面等式(1)中的2 t-1個(gè)值，然后根據(jù)式(1)求出不能選擇的循環(huán)移位值。由QC-LDPC的校驗(yàn)矩陣的環(huán)結(jié)構(gòu)可以看出，如果依次確定各列中循環(huán)子矩陣的移位值，并且只考慮當(dāng)前列與其前的所有列形成的環(huán)，那么通過去除滿足等式(1)的循環(huán)移位值，可得到可選的循環(huán)移位值的集合，此集合任一個(gè)移位值都能消除該列與其前的所有列形成的環(huán)。算法的具體步驟如下:1.如果循環(huán)矩陣的維數(shù)是L，基矩陣中每個(gè)塊元素可

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

8、除所有長度為2t的環(huán)。構(gòu)造基于PEG算法的準(zhǔn)循環(huán)低密度奇倡檢驗(yàn)碼的步驟如下: 1.根據(jù)要生成的準(zhǔn)循環(huán)低密度奇倡奇倡校驗(yàn)碼的碼長，碼率，校驗(yàn)矩陣的行重，列重的要求確定基矩陣的碼長、碼率、行重、列重，以及循環(huán)置換矩陣的維數(shù)L; 2.利用PEG算法生成一個(gè)基矩陣; 3.利用環(huán)搜索程序找到矩陣中的短環(huán); 4.利用搜索到的記錄環(huán)的矩陣統(tǒng)計(jì)出經(jīng)過每一列的環(huán)的數(shù)量，按照環(huán)數(shù)的降序?qū)仃嚨牧兄匦屡判? 5.搜索新生成的校驗(yàn)矩陣中的短環(huán); 6.應(yīng)用移位值選擇程序確定塊元素的移位值; 7.將列的順序重排恢復(fù)成原矩陣; 8.根據(jù)不同的移位值選擇循環(huán)置換矩陣進(jìn)行擴(kuò)展，對于基矩陣中的零元素用L維的全零力一陣擴(kuò)展。利用上

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、LDPC PEG算法直接構(gòu)造的LDPC碼表示為PEG-LDPC純擴(kuò)展生成的QC-LDPC碼表示為EG-PE-LDPC oE61No(dB)圖IAWGN信道下PEG-E-LDPC(504,252)的誤碼性能?；诟咚瓜サ腖DPC碼編碼算法復(fù)雜度較高,在中短碼長時(shí)不易實(shí)現(xiàn).對此,T.J.Richardson等提出了一種基于近似下三角矩陣的有效編碼算法(也叫貪婪算法).該算法雖然可以實(shí)現(xiàn)在線性時(shí)間內(nèi)編碼,但其應(yīng)用條件受一定的限制,成為實(shí)用化過程中的一個(gè)阻礙.因此,近年來出現(xiàn)了一種低編碼復(fù)雜度Quasi Cyclic LDPC碼的編碼算法.QC碼編碼可以用簡單的移位寄 存器實(shí)現(xiàn),其生成矩陣具有循環(huán)或

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

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