基于PEG算法的LDPC碼構造及改進

《基于PEG算法的LDPC碼構造及改進》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、基于PEG算法的LDPC碼構造及改進桂林電子科技大學碩士研究生《糾錯碼理論》課程學生：王廣耀學號：1502201054專業(yè)：信息與通信工程題目：基于PEG算法的LDPC碼構造教師：王俊義職稱：教授時間：2015.11.1710基于PEG算法的LDPC碼構造及改進基于PEG算法的LDPC碼構造及改進摘要：漸進邊增長(PEG)算法構造的低密度奇偶校驗碼(LDPC)在保證局部圍長最大時仍有較多數(shù)目的短環(huán)。針對該問題，提出一種新的準循環(huán)LDPC碼構造方法。該方法在PEG算法中采用環(huán)多項式(PC)標記，利用PC-PEG方法構造的矩陣作為基矩陣，并對

2、其進行準循環(huán)擴展，以消除基矩陣中的短環(huán)。實驗結果表明，該方法構造的LDPC碼可大幅減少短環(huán)的數(shù)目。同時由于引入了準循環(huán)結構，能降低編碼復雜度。為了兼顧LDPC碼較高的糾錯性能和較簡單的硬件實現(xiàn)，提出了一種基于PEG算法的準循環(huán)LDPC碼校驗矩陣的構造方法，該方法首先利用PEG算法構造基矩陣，然后利用提出的移位參數(shù)公式來構造循環(huán)移位矩陣，再用循環(huán)移位矩陣和全零矩陣對基矩陣進行優(yōu)化擴展，形成的校驗矩陣最短環(huán)長至少為8環(huán)。該方法具有與PEG算法非常接近的糾錯性能，尤其是當信噪比高于1.2dB時要優(yōu)于PEG直接構造法，而硬件實現(xiàn)比PEG算法簡單，

3、且參數(shù)選擇靈活方便。關鍵詞：低密度奇偶校驗碼；漸進邊增長算法；準循環(huán)結構；短環(huán)；循環(huán)置換矩陣；基矩陣1、概述PEG(progressedgegrowth)算法是當前公認的對中、短碼長LDPC碼構造非常有效的算法之一，它采取逐邊添加的力一式構造碼的Tanner圖，在滿足給定度分布的條件下能使Tanner圖中短環(huán)數(shù)量盡可能少，使碼的圈長盡可能大。但由于其采用隨機構造的做法，使該類碼的H矩陣缺乏結構性，編碼復雜度高，尤其是對長碼而言，其構造及編碼實現(xiàn)的運算量更是劇增。基于PEG算法的QC-LDPC碼是首先以PEG算法構造，一個維數(shù)較小的一致校驗

4、矩陣，稱為基矩陣，再將基矩陣中的“基矩陣維數(shù)由編碼后的碼長n和循環(huán)置換矩陣的維數(shù)P及碼率決定。文獻f}l給出了一種基于PEG算“1”元素和‘0’元素分別替換為pxp維的循環(huán)置換矩陣(或單位矩陣的循環(huán)移位)和全零矩陣。法的QC-LDPC碼構造力一法，但在擴展的過程中只消除了部分6環(huán)，沒有將圈長擴大。文獻f}l給出了另一種擴展PEG算法構造的基矩陣的力一法，但由于PEG算法的非結構化，這種算法只是擴大了基矩陣中的一部分環(huán)的長度，不能確定是否擴大了圈長。本文提出的基于PEG算法的QC-LDPC碼構造力一法成功擴大了圈長，同時擴大了部分其他長度的

5、環(huán)。算法中用到了PEG算法，環(huán)搜索算法，單位矩陣的循環(huán)移位值的選擇算法，并通過仿真驗證了改進力一法的有效性。胡曉宇等人提出了PEG算法，MacKay認為PEG碼是目前最佳的Gallager碼(碼長在500以上)。我們可以用圖例和算法流程來解釋這種構造力一法。PEG算法不僅可以構造規(guī)則碼，而且可以構造非規(guī)則碼，算法和上面基本類似，只要把變量節(jié)點按度數(shù)升序排列即可。PEG算法可以獲得盡量大的局部最小圈長。本文的環(huán)搜索算法采用的是迪科斯徹算法(Dijkstra)的思想，該算法是由荷蘭計算機科學家艾茲格·迪科斯徹(EdsgerWybeDijkst

6、ra)1959年發(fā)明的。算法解決的是有向圖中最短路徑問。通過該算法可以找到所有長度為L的環(huán)長。但是上述算法的計算量很高，與校驗矩陣的列數(shù)成線性關系，計算過程中的存儲量要求也很高。由式(1)準循環(huán)矩陣中環(huán)的形成條件知，當回路中的各頂點的移位值當且僅當滿足式(1)的等式時矩陣中形成長度為Zt的環(huán)·10基于PEG算法的LDPC碼構造及改進其中，Sak/3k為H矩陣中回路的第k個頂點所在的循環(huán)子矩陣的移位值。如果選擇適當?shù)囊唤M循環(huán)移位值，使其不滿足上面的等式，就能消除長度為Zt的環(huán)。由等式的性質，我們知道當?shù)仁街兄挥幸粋€變量時才能根據(jù)等式關系求出

7、它的確切值。在本算法中也是將首先確定上面等式(1)中的2t-1個值，然后根據(jù)式(1)求出不能選擇的循環(huán)移位值。由QC-LDPC的校驗矩陣的環(huán)結構可以看出，如果依次確定各列中循環(huán)子矩陣的移位值，并且只考慮當前列與其前的所有列形成的環(huán)，那么通過去除滿足等式((1)的循環(huán)移位值，可得到可選的循環(huán)移位值的集合，此集合任一個移位值都能消除該列與其前的所有列形成的環(huán)。算法的具體步驟如下:1.如果循環(huán)矩陣的維數(shù)是L，基矩陣中每個塊元素可選的移位值的集合是(1,2,3...L-1)o2.矩陣中第一列的循環(huán)子矩陣的移位值從他們的移位值集合中隨機產生。3.從

8、矩陣的第二列開始，每一列的第一個循環(huán)子矩陣的移位值在1到L-1中隨機產生，然后產生的記錄循環(huán)的矩陣中搜索它與前面的列是否形成環(huán)，如果形成環(huán)，就根據(jù)上面的等式計算出此列的其他循環(huán)子矩陣不應該選擇