LDPC的BP譯碼算法

1、課程名稱：現(xiàn)代編碼理論任課教師：王琳 洪少華論文題目：LDPC碼的BP譯碼算法姓名：曹沙沙趙卜寒2014 年 07月06日目錄摘要IIAbstractIII第一章 LDPC碼的概述11.1 LDPC碼的發(fā)展史1、LDPC碼的表示11.3 二進制LDPC碼的編碼方法3校驗矩陣的生成3編碼算法4第二章 LDPC碼譯碼算法62.1 Gallager概率譯碼基本思路62.2 BP算法研究82.3 用對數(shù)似然比表示的BP算法11第三章 LDPC的性能分析143.1 LDPC的仿真模型143.2 LDPC的譯碼性能15碼長對性能的影響15迭代次數(shù)對譯碼性能的影響16結(jié)論18參考文獻19摘要低密度奇偶校驗碼

2、是Gallager提出的一種線性分組碼，其性能可以非常接近香農(nóng)極限。它是根據(jù)低密度稀疏校驗矩陣H和二分圖來構造的，本文詳細的闡述了二進制，規(guī)則的LDPC的BP譯碼算法，其校驗矩陣每一行和每一列的1的個數(shù)是相同的，分別為p和q,其Tanner圖中比特節(jié)點的度和校驗節(jié)點的度分別對應著一個固定值，通常用（m，n，p，q）表示。BP譯碼算法是一種迭代的概率譯碼算法，本文著重于BP譯碼算法及其簡化運算。本論文主要介紹了LDPC碼的構造、編碼和譯碼基本原理。闡述了LDPC編譯碼的過程，并通過MATLAB仿真工具對LDPC碼在AWGN信道的誤比特率性能進行了仿真，分析了信噪比、碼長和迭代次數(shù)對誤比特率性能的

3、影響。關鍵詞：二進制LDPC BP算法 迭代概率譯碼 后驗概率AbstractLow Density Parity Check(LDPC) codes are a class of linear block codesproposed by Gallager,which perform at a rate extremely closed to the Shannon capacity.It is based on low-density parity check matrix H and sparse bipartite graph is constructed, the paper ela

4、borated binary, LDPC decoding algorithm of BP rule, the number of one of its check matrix each row and each column is the same , respectively, p and q, the Tanner graph of bit nodes and check nodes of degree corresponds to a fixed value, respectively, usually expressed as (m, n, p, q). BP decoding a

5、lgorithm is the probability of an iterative decoding algorithm, This paper focuses on its simplified operation. This paper describes the structure, the basic principles of the encoding and decoding of LDPC codes. Describes the LDPC encoding and decoding process, and through MATLAB simulation tool fo

6、r LDPC codes in the bit error rate performance AWGN channel simulation, analysis of the impact of signal to noise ratio, code length and number of iterations of the bit error rate performance.Keywords: binary LDPC BP-decoding algorithm iterative probabilityposterior probability第一章 LDPC碼的概述LDPC碼的發(fā)展史1

7、、 1963年，Gallager發(fā)現(xiàn)的LDPC碼被稱作古典碼型：規(guī)則LDPC。2、 1998年，MacKay and Spielman發(fā)明了不規(guī)則的LDPC。3、 Richardson and Urbanke開創(chuàng)了用譯碼分析設計碼型的方法。4、針對B-LDPC碼優(yōu)異的糾錯性能，M. Davey和D. Mackay進一步將B-LDPC碼一般化到多進制域上，并且研究結(jié)果表明Q-LDPC碼在低碼率（R<1/2），AWGN信道下比B-LDPC碼的糾錯性能還要優(yōu)越，Q-LDPC碼的出現(xiàn)為LDPC碼的研究開拓了一個全新的領域。1.2、LDPC碼的表示LDPC是一種分組碼，但是LDPC碼與其他線性分組

8、碼不同的是，其他線性分組碼由生成矩陣表征，而LDPC碼是由校驗矩陣來表征，其奇偶校驗矩陣具有低密度的1。規(guī)則LDPC碼可以用（n,j,k）的形式表示，其中n表示生成的碼字的碼長，j表示H矩陣的列重，k為行重。也可將j用表示，k用表示。如果用m表示H矩陣中的行數(shù)則有。一個規(guī)則的（12，3，4）LDPC碼的H矩陣如下圖所示： 圖11 （12，3，4）LDPC的校驗矩陣我們把H矩陣中的每一行看作一個校驗點(check node)，每一列看作一個變量點(variable node)。則H矩陣反映了變量點與校驗點的連接關系，如在第一行中有，表示模2加，表示第一個校驗點約束、這四個變量點。從而我們可以知道

9、行重k表示一個校驗點約束k個變量點。我們再來看第一列，它表示了第一個變量點受到check2、check5、check7的約束。因此我們又可以推出列重j表示了一個變量點受到j個校驗點的約束。由于LDPC也是一種線性分組碼，因此可以用（n,k）的形式表示。n表示碼長，k表示信息位的個數(shù)。為了更形象的表示LDPC碼中變量點與校驗點的關系，九十年代中期科學家們引入雙邊圖（biparttie graphs）來表示LDPC碼。雙邊圖是LDPC的一個有用的工具。它將節(jié)點分成兩類，節(jié)點之間用無向的邊進行連接，并且連接只存在于不同類的節(jié)點之間即只存在與校驗點與變量點之間，而兩個校驗點之間或者兩個變量點之間不存在

10、邊的連接。我們把LDPC校驗矩陣H的每一行表示一個校驗點用方框表示，每一列表示一個變量點用圓表示。則由上述可知一個校驗點連接k個變量點，一個變量點連接j個校驗點。當對應H矩陣中時，第i個變量點就與第j個校驗點連接，否則不連接。并且校驗點發(fā)出的邊的總數(shù)等于變量點發(fā)出的邊的總數(shù)。每個節(jié)點發(fā)出的邊的個數(shù)稱為這個點的度。如對于（12，3，4）碼其雙邊圖為：圖12 （12，3，4）LDPC碼的因子圖表示當H矩陣中每列1的個數(shù)與（或）每行1的個數(shù)不同時稱為不規(guī)則LDPC碼。在雙邊圖中表現(xiàn)為變量點與校驗點的度允許改變。對于不規(guī)則LDPC碼，它更喜歡具有高密度的變量點，因為它將從校驗點接收更多的信息量，從而能

11、更精確的判斷變量點的值。另外，不規(guī)則LDPC碼喜歡具有低密度的校驗點，在這種情況下，校驗點所傳送的信息對于相鄰點而言更有價值。從上分析可知不規(guī)則LDPC碼比規(guī)則LDPC的性能更好的原因在于不規(guī)則LDPC碼中存在波浪效應。高密度的變量點能夠快速的收斂到正確的值，并且它能夠幫助中等的變量點收斂到他們正確的值，從而由于循環(huán)可以幫助低密度的變量點。最終使得所有點的譯碼速度加快。由于不規(guī)則LDPC碼中行重和列重都不是規(guī)則的，因此就不能用（n,j,k）的形式表示。因此不規(guī)則LDPC中采用度的表示方法。 ， （1.1）其中表示變量點的度的分布，表示校驗方程點的度的分布；()表示從度為()的變量點（校驗方程點

12、）所發(fā)出的邊數(shù)占總邊數(shù)的比例。很顯然。 對于規(guī)則的LDPC碼，也可以用這樣的方式進行表示。例如，對于規(guī)則的LDPC碼(n,3,6)，則，。已知一個度的分布對（）后，可以確定一系列碼字集合，其中校驗方程個數(shù)以及碼率如下式所示：（1.2）（1.3）1.3 二進制LDPC碼的編碼方法對于二進制LDPC碼的編碼，其編碼基本步驟為：（1）、按照一定的設置生成校驗矩陣H。（2）、由校驗矩陣H，按照一定的編碼算法生成最后的碼字u。校驗矩陣的生成由于LDPC碼是以校驗矩陣H為特征的，不同的校驗矩陣H對應不同的碼字集合。因此，LDPC碼的編碼首先需要設計校驗矩陣H，同時這也是LDPC碼編碼的關鍵。在H矩陣的設計

13、過程中，必須避免兩種情況，一是出現(xiàn)短周期的環(huán)主要是長為四的環(huán)，二是避免變量點的連接過于集中，即校驗點的度過大。長為4的環(huán)(圖中存在長度為4的圈)會導致信息在兩組點間反復傳遞，難以更新，違背了迭代譯碼的初衷。長為4的環(huán)反映在H矩陣中是存在2×2的子矩陣。當變量點所連接的校驗方程過于集中時，常常導致LDPC碼錯誤地板的發(fā)生。例如在圖23中，變量點的度為3，但其中三個帶陰影的變量點總共只連接了5個校驗方程；除了最右邊的一個校驗方程以外，其它4個校驗方程中，每個都連接了兩個陰影的變量點。因此，如果這三個陰影的變量點都出錯時，左邊4個校驗方程都不能檢測到錯誤的存在。當分組長度增大時，出現(xiàn)這種拓

14、撲結(jié)構的可能性也隨之減少。圖23 變量點所連接校驗方程過于集中的因子圖下面以準規(guī)則LDPC碼的H矩陣的生成為例說明校驗矩陣的生成步驟。校驗矩陣的生成步驟如下：（1）、選擇參數(shù)（碼長，碼率，列重，行重）。（2）、構造一個全0矩陣。（3）、隨機選擇Wc行加入非0元素。在實際的仿真中采用的是準規(guī)則的H矩陣，既列重相同，行重盡量相同。因此，先在每列選擇Wc行，隨機的插入非0元素。接著再對于低重的行添加非0元素，以避免出現(xiàn)低重的碼字。（4）、對已生成的H矩陣進行消4環(huán)。編碼算法按照上小節(jié)的方法求出校驗矩陣H后，就可以按照一定的編碼方法得到最后生成的碼字。常規(guī)的編碼方法中，當H矩陣被構造出來后，可以得到生

15、成矩陣G，則最后生成的碼字U=S×G。但是實際的編碼過程并不像其表達式這么簡單。我們來看一個例子：一個（10000，5000）線性分組碼，其GI|P矩陣為5000×10000，假設P矩陣中1的密度為0.5，則在P矩陣中將有的1，即有次加法運算。從而所需的寄存器的數(shù)目將是很多的。因此我們在編程的過程中采用的是具有系統(tǒng)形式的H矩陣的快速編碼。假設生成的碼字具有系統(tǒng)形式U=C|S，其中C為校驗位，S表示信息位。則我們將校驗矩陣H變換成A|B的形式，其中A為m×m的單位矩陣，B為（n-m）×m的矩陣，則根據(jù),可得AC+BS=0,從而可以得到。在實驗中，是把隨機生

16、成的校驗矩陣經(jīng)過列變換成系統(tǒng)形式，然后根據(jù)H與G的關系，求出生成矩陣G的前面部分，生成矩陣的后面是一個（n-m）×（n-m）的單位矩陣，從而得到校驗位C。由于A是單位陣，從而降低了計算量。這種方法降低了編碼過程的運算量但是同時也降低了其性能。它要求H具有系統(tǒng)形式，就存在一個m×m的單位矩陣，使得剩余部分具有高密度的1。這就使矩陣的稀疏特性被破壞。但是其生成矩陣H較容易。編碼時間與分組長度呈線性關系。 除了上述的兩種方法外，中外學者還研究出了其他更適合硬件實現(xiàn)的編碼算法。主要集中于H矩陣的設計上，如具有類似下三角的H矩陣的設計，具有線性的編碼復雜度，節(jié)省了對寄存器的要求，易于

17、硬件的實現(xiàn)。第二章 LDPC碼譯碼算法信道編碼的譯碼算法是決定編碼性能和應用前景的一個重要因素，尤其是在長碼的條件下，譯碼算法的復雜度決定了編碼的前途。通常分組碼的譯碼長度與碼長成指數(shù)關系，碼長增加到一定的程度后，復雜度的增加將是不可控制的，無法得到實際的應用。LDPC碼則不同，由于其奇偶校驗矩陣的稀疏性，使它存在高效的譯碼算法，其譯碼復雜度與碼長成線性關系，克服了分組碼在碼長比較長時面臨的巨大譯碼計算復雜度問題。Gallager提出LDPC碼時曾給出兩種譯碼算法：硬判決算法和概率譯碼軟判決算法。硬判決不能達到LDPC碼的最佳性能，軟判決則有非常好的性能。BP算法是在Gallager提出的概率

18、譯碼算法的基礎上發(fā)展起來的。2.1 Gallager概率譯碼基本思路假設發(fā)送端發(fā)送一個碼長為n的二進制序列（）,接收端收到的信號為（），如果發(fā)送的二進制比特是相互獨立的，則可以根據(jù)接收信號和信道模型估計出發(fā)送的各比特位0或1的概率?？紤]其中的某一比特，如果，則就認為發(fā)送的為1，否則為0。這是對應于沒有信道編碼的情況下。如果經(jīng)過了信道編碼，此時的二進制序列各比特之間就不是相互獨立的。假設這個二進制序列是一個LDPC碼字，那么這n個比特就要滿足由該碼的校驗矩陣所確定的一系列校驗方程。假設其中一個校驗方程是（模2加法），此時=1的概率，除了接收信號提供的信息外，還要考慮比特間的相關性。假定，滿足校驗

19、方程這一事件記為S，現(xiàn)要計算概率。根據(jù)條件概率的貝葉斯公式：當然包含比特的校驗方程可能不止一個，這些校驗方程的某些比特又包含在其他更多的校驗方程中。由于碼字中的各比特的相關性，除了利用對于該比特的接收信號外，還可以利用其他比特的接收信號來修正該比特的后驗概率。為了直觀的表示這種關系，引入校驗集合樹的概念。如下圖所示圖2-1校驗集合樹具體算法Gallager的論文中已有詳細的闡述，這里我們只對結(jié)果做下說明。 通過校驗集合樹，在傳送碼字c時，碼字中的各比特滿足包含比特d的j個校驗方程。當接收到相應的符號序列時y時，比特d為1的條件概率可以表示為。同理，比特d為0 的條件概率表示為。令當不考慮發(fā)送比

20、特間的相關性時，d為1的概率表示為，它與信道模型有關。有下面公式：令，表示d的校驗集合樹第一層中包含d的第i個校驗方程的第l個比特位1 的概率，那么有： (2.1)則概率譯碼的步驟可以描述如下：對每一個比特，畫出相應的校驗集合樹，從最高層的節(jié)點開始，應用上式逐層計算出各節(jié)點的后驗概率分布，直至求出根節(jié)點的后驗概率分布。根據(jù)后驗概率分布判決該比特是0或者1：若 其它綜上可見，概率譯碼的算法的運算量是相當大的，因為沒計算一個比特的后驗概率分布，都需要利用所有比特的相關信息，運算量隨碼數(shù)的增加呈指數(shù)增長。2.2 BP算法研究 校驗集合樹雖然在描述計算單個節(jié)點的后驗概率時非常直觀，但針對不同的節(jié)點有不

21、同的校驗集合樹，因此在描述并行的計算整個碼字各比特的后驗概率時，使用校驗集合樹并不方便，我們這里采用Tanner圖來對應前面提過的校驗集合樹。為了方便該圖只畫出了部分節(jié)點和校驗節(jié)點。Tanner圖的變量節(jié)點對應于校驗集合樹的節(jié)點，校驗節(jié)點對應于校驗集合樹的邊。圖2-2 校驗集合樹的部分anner圖 設表示校驗節(jié)點相連的所有變量節(jié)點的集合，即，表示集合去掉變量節(jié)點。設表示與變量節(jié)點相連的所有校驗節(jié)點的集合，即，表示集合中去掉校驗節(jié)點。 圖 2-3 Tanner圖中關于變量節(jié)點和校驗節(jié)點的局部關系圖中表示不考慮比特間的相關性，僅僅根據(jù)比特的接收信號值以及信道特性而得出的比特取值為x的概率，其中。顯

22、然有?？梢园芽闯勺兞抗?jié)點的固有性質(zhì)。 設表示基于接收信號并根據(jù)校驗節(jié)點集合的信息而得出的比特的概率，其中。同樣有?？梢哉J為是變量節(jié)點向校驗節(jié)點傳遞的信息。表示當比特，并給定其他比特的一組概率時，校驗節(jié)點m對應的校驗方程成立的概率?？梢钥醋鲂ｒ灩?jié)點向變量節(jié)點傳遞的信息。根據(jù)和的定義，考慮到校驗方程都是模2加法，校驗節(jié)點m對應的校驗方程成立的概率即為比特序列中包含偶數(shù)個1的概率；校驗節(jié)點m對應的校驗方程成立的概率即為比特序列中包含奇數(shù)個1 的概率。在進行簡易的推導易得）（2.3）根據(jù)式(2.1)以及，以及的定義，可以得到（2.4）完整的BP算法描述。對滿足的m,l執(zhí)行如下步驟。（1）初始化： ,其

23、中表示信道的先驗概率。（2）校驗節(jié)點更新：，則有（2.5）（2.6） （2.7）（3）變量節(jié)點更新：（2.8）（2.9）其中是一個使得的值。（4）似后驗概率更新：（2.10）（2.11）同樣是一個使得的值。（5） 比特判決：如果，則判,(l=1,2,.,N). 若，或者迭代次數(shù)達到最大迭代次數(shù)，則結(jié)束迭代，把作為譯碼輸出，否則轉(zhuǎn)到步驟（2）繼續(xù)迭代。2.3 用對數(shù)似然比表示的BP算法 上述介紹的BP算法比較復雜。一方面該算法需要在每個變量節(jié)點和校驗節(jié)點分別計算各比特為0或者為1 的概率，并且在計算和時，要選擇合適的系數(shù)和使之滿足概率和為1 的條件；另一方面，算法的表述太過復雜，采用很多相乘運算

24、，耗費較多的運算時間和硬件資源，不利于硬件實現(xiàn)。采用對數(shù)似然比描述的BP算法會有一個非常簡單明了的形式?？紤]一個隨機變量x，它的對數(shù)似然比L(x)定義為根據(jù)對數(shù)似然比的定義，令那么根據(jù)式（2.2）和（2.3）得因為反曲正切函數(shù)在開區(qū)間（-1.1）內(nèi)單調(diào)增加，是關于原點對稱的奇函數(shù)。這樣上式變?yōu)楹啙嵭问剑?因為 ，上式右端各項除以 ，右端各項分母再除以 ，可得下式：再引用的定義得下式：這里為了使形式更簡潔，引用雙曲正切函數(shù)：，它是在內(nèi)單調(diào)增加，函數(shù)值，以y=+1,-1為漸近線，關于原點對稱的奇函數(shù)。最后得到： （2.12）根據(jù)式（1.8）和（1.9）有 （2.13）同理有：（2.14）BP算法的

25、步驟整理如下：對于校驗矩陣元素的m,l執(zhí)行如下步驟運算。(1) 初始化：(2) 校驗節(jié)點更新：(3) 變量節(jié)點更新：(4) 似后驗概率更新(5) 比特判決：如果，則判；否則判，（l=1,2,.,N）。若，或者迭代次數(shù)達到最大迭代次數(shù)，則結(jié)束迭代，把作為譯碼輸出，否則轉(zhuǎn)到步驟（2）繼續(xù)迭代。 上述是完整的的碼譯碼的BP算法，但還沒有說明如何去求得在譯碼的初始化過程中所需要的或，這些值是與信道有關的。下面以信道為例，說明如何計算或的值。表示不考慮比特之間的相關性，僅根據(jù)比特的接收信號值以及信道特性而得出的比特取值為的概率，其中的取值為或。假設信道是二進制無記憶對稱信道，其輸入是來自信源的二進制、數(shù)

26、字信號，經(jīng)發(fā)端的二相調(diào)制器后變?yōu)?，對極信號。經(jīng)收端的二相相干解調(diào)器又把，對極信號變?yōu)椋瑪?shù)字信號還原輸出。由于高斯白噪聲的存在，相干解調(diào)的檢測可能出現(xiàn)錯誤。用信號加噪以后的條件概率密度分布函數(shù)來分析誤碼的產(chǎn)生比較清楚。第三章 LDPC的性能分析3.1 LDPC的仿真模型圖3-1 LDPC仿真模型圖 其中第二章詳細介紹了LDPC碼的譯碼算法，可知LDPC譯碼一般包括以下5個步驟：1、初始化2、校驗節(jié)點更新3、變量節(jié)點更新4、判決5、停止。實際操作時發(fā)現(xiàn)判決時只需用到本輪迭代的校驗節(jié)點的更新結(jié)果，變量節(jié)點的更新在下一輪迭代中才起作用。因此可以把步驟4和5安排在步驟3之前進行，這樣可以節(jié)省一次變量節(jié)點

27、的更新工作，譯碼流程圖如下：圖3-2譯碼流程圖3.2 LDPC的譯碼性能通過前面幾章的介紹，LDPC的譯碼基本完成，為了了解實現(xiàn)的譯碼性能，下文中給出了LDPC的譯碼性能圖。LDPC編譯碼實現(xiàn)的編碼輸入是函數(shù)rand()產(chǎn)生的二進制隨機序列，并記錄LDPC譯碼在不同性噪比下的誤碼率，再在matlab中畫圖。仿真時LDPC碼列重選擇3，最大迭代次數(shù)設置為5次時進行仿驗，分析研信噪比對LDPC碼誤碼性能的影響，隨著信噪比的增加，LDPC碼的性能不斷提高。BP譯碼算法下，可以看成是無窮比特量化譯碼，它充分利用接收的信道信息，信道信息利用率得到了極大的提高。信道信息的充分利用，極大地提高了譯碼性能，使

28、得譯碼可以迭代進行，充分挖掘接收的信道信息，最終獲得出色誤碼性能圖3-3BP算法的BER曲線碼長對性能的影響將LDPC碼列重選擇3，最大迭代次數(shù)設置為5次且信噪比為0.5dB時進行仿真實驗，分析研究碼長對LDPC碼誤碼性能的影響，仿真得到了不同碼長對LDPC碼的性能仿真結(jié)果如下圖所示。從圖中可以看出，在同樣的信噪比條件下，隨著碼長的增加，LDPC碼的性能不斷提高。在小信噪比區(qū)域，碼長的增加對誤碼率的改進不大，但隨著信噪比的增大，LDPC碼的誤碼率得到了明顯改善。但隨著碼長的增加，LDPC碼性能的提高是相對的，當達到一定碼長后，性能將會有很小的提高。這是因為一定碼長下編碼性能有一定的極限，隨著碼長的增大，編碼和譯碼的復雜度也增加，編碼性能就會更接近極限，性能隨碼長增加改善的就更少。圖3-4碼長對LDPC性能的影響迭代次數(shù)對譯碼性能的影響將碼長為400的LDPC碼，列重為3，信噪比為0dB的情況下進行了仿真實驗。圖中給出了上述情況下的不同迭代次數(shù)對LDPC碼的性能仿真結(jié)果?？梢钥闯?，在相同的信噪比下，LDPC碼的性能隨著迭代次數(shù)的增加而逐漸提高。但是LDPC碼的誤碼率并不能隨著迭代次數(shù)的增加無限地減小，當