LDPC的BP譯碼算法

1、 課程名稱：現(xiàn)代編碼理論 任課教師：王琳洪少華 論文題目：LDPC碼的BP譯碼算法 姓名：曹沙沙趙卜寒 學號：學32013115324323320131153274 2014年07月06日目錄 摘要II. AbstractIII 第一章LDPC碼的概述1 1.1 LDPC碼的發(fā)展史1 1.2 、LDPC的表示1 1.3 二進制LDPC的編碼方法3 1.3.1 校驗矩陣的生成3 1.3.2 編碼算法4 第二章LDPC碼譯碼算法6. 1.1 . Gallager概率譯碼基本思路6 1.2 BP算法研究8 1.3 用對數(shù)似然比表示的BP算法11 第三章LDPC的性能分析14 LDPC的仿真模型14

2、LDPC的譯碼性能15 碼長對性能的影響15 迭代次數(shù)對譯碼性能的影響16 結論18 參考文獻H9摘要 低密度奇偶校驗碼是Gallager提出的一種線性分組碼，其性能可以非常接近香農(nóng)極限。 它是根據(jù)低密度稀疏校驗矩陣H和二分圖來構造的， 本文詳細的闡述了二進制，規(guī)則的LDPC勺BP譯碼算法，其校驗矩陣每一行和每一列的1的個數(shù)是相同的，分別為p和q,其Tanner圖中比特節(jié)點的度和校驗節(jié)點的度分別對應著一個固定值，通常用(min,p,q)表示。BP譯碼算法是一種迭代的概率譯碼算法，本文著重于BP譯碼算法及其簡化運算。 本論文主要介紹了LDPCK的構造、編碼和譯碼基本原理。闡述了LDP訴譯碼的過程

3、，并通過MATLAB&真工具對LDPCK在AWG陸道的誤比特率性能進行了仿真，分析了信噪比、碼長和迭代次數(shù)對誤比特率性能的影響。 關鍵詞：二進制LDPCBP算法迭代概率譯碼后驗概率Abstract LowDensityParityCheck(LDPC)codesareaclassoflinearblockcodesproposedbyGallager,whichperformatarateextremelyclosedtotheShannoncapacity.Itisbasedonlow-densityparitycheckmatrixHandsparsebipartitegraphi

4、sconstructed,thepaperelaboratedbinary,LDPCdecodingalgorithmofBPrule,thenumberofoneofitscheckmatrixeachrowandeachcolumnisthesame,respectively,pandq,theTannergraphofbitnodesandchecknodesofdegreecorrespondstoafixedvalue,respectively,usuallyexpressedas(m,n,p,q).BPdecodingalgorithmistheprobabilityofanite

5、rativedecodingalgorithm,Thispaperfocusesonitssimplifiedoperation. Thispaperdescribesthestructure,thebasicprinciplesoftheencodinganddecodingofLDPCcodes.DescribestheLDPCencodinganddecodingprocess,andthroughMATLABsimulationtoolforLDPCcodesinthebiterrorrateperformanceAWGNchannelsimulation,analysisofthei

6、mpactofsignaltonoiseratio,codelengthandnumberofiterationsofthebiterrorrateperformance. Keywords:binaryLDPCBP-decodingalgorithmiterativeprobabilityposteriorprobability第一章LDPC碼的概述 LDPC碼的發(fā)展史 1、1963年，Gallager發(fā)現(xiàn)的LDPCB被稱作古典碼型：規(guī)則LDPC 199外,MacKayandSpielman發(fā)明了不規(guī)貝U的LDPC 3、RichardsonandUrbanke開創(chuàng)了用譯碼分析設計碼型的方法。

7、 4、針對B-LDPC碼優(yōu)異的糾錯性能，M.Davey和D.Mackay進一步將B-LDPC碼一般化到多進制域上，并且研究結果表明Q-LDPC碼在低碼率(R0.50.5, ,則判X Xl,(l=1,2,.,N). A 若HTX=0,或者迭代次數(shù)達到最大迭代次數(shù)，則結束迭代，把輸出，否則轉到步驟(2)繼續(xù)迭代。 2.3用對數(shù)似然比表示的BP算法 上述介紹的BP算法比較復雜。一方面該算法需要在每個變量節(jié)點和校驗 XX 節(jié)點分別計算各比特為0或者為1的概率，并且在計算心和q ql時，要選擇合適的系數(shù)“ml和1使之滿足概率和為1的條件；另一方面，算法的表述太過復雜，采用很多相乘運算，耗費較多的運算時間

8、和硬件資源，不利于硬件實現(xiàn)。采用對數(shù)似然比描述的BP算法會有一個非常簡單明了的形式。 考慮一個隨機變量X,它的對數(shù)似然比L(X)定義為 L(x)=ln3) P(X)1) 根據(jù)對數(shù)似然比的定義，令 f0 0l v=lnTT fl 0 Vml二ln乎 qml v=lnq7 l1 q 0 r. Uml=ln不 r 1ml A X作為譯碼 那么根據(jù)式(2.2)和(2.3)得 01 qmlTml 01 qml7ml l ,J/、1I/1x tanh（x）=.ln（） 因為反曲正切函數(shù)21-x在開區(qū)間（-1.1）內單調增加，是 關于原點對稱的奇函數(shù)。這樣上式變?yōu)楹啙嵭问? Uml=ln 1-II 1 1r

9、uml=2tanh l ”(q：l4)fL(ml 因為 qml+qml=1,上式右端各項除以 0.1 口同qml,右端各項分母 1 再除以qml,可得下式: 0qml 1 1qml uml2tanhH 三L(mlqml qml -1 1r uml=2tanh再 引用Vml的定義得下式： n ld_(m ev-1 4 eml.1 這里為了使形式更簡潔，引用雙曲正切函數(shù): sh(x)e-etanh(x)=-x ch(x)ee 同理有:它是在（.已*）內單調增加，函數(shù)值三（1,1）,以 y=+1,-1為漸近線，關于原點 對稱的奇函數(shù)。最后得到: 1tanhuml=2tanh2 一 l二L(ml (2

10、.12) 根據(jù)式（1.8）和（1.9）有 Vml=Vl umim二M(lm (2.13) 0- Vl=V|uml m三M(l) BP算法的步驟整理如下：對于校驗矩陣元素hmlhml=1=1 的m,l執(zhí)行如下步驟運 _0 (1)初始化：Vml=vl Vml tanh 2 l (2)校驗節(jié)點更新: (5)比特判決：如果Vl0Vl0, ,則判XlXl=0;=0;否則判x x=1,=1,(l=1,2,.,N) 若HTx=0,或者迭代次數(shù)達到最大迭代次數(shù),則結束迭代,把x作為譯碼輸出,否則轉到步驟(2)繼續(xù)迭代。 上述是完整的的 LDPCLDPC 碼譯碼的BP算法，但還沒有說明如何去求得在x0 譯碼的初

11、始化過程中所需要的flfl或VlVl,這些值是與信道有關的。下面以 AWGAWG N N 信道為例，說明如何計算或VlVl0的值。flflx=P(xP(x= =x|y)x|y)表示不考慮比特之間的相關性，僅根據(jù)比特xlxl的接收信號值以及信道特性而得出的比特xlxl取值為 x x 的概率，其中 x x 的取值為0 0 或 1 1。 假設 AWGNAWGN 信道是二進制無記憶對稱信道，其輸入是來自信源的二進制 0 0、1 1 數(shù)字信號，經(jīng)發(fā)端的二相 BPSKBPSK 調制器后變?yōu)?1,1,1 1 對極信號。經(jīng)收端的二相相干解調器又把 1 1, ,- -1 1 對極信號變?yōu)?0,10,1 數(shù)字信號

12、還原輸出。由于 AWGNAWGN 高斯白噪聲的存在，相干解調的檢測可能出現(xiàn)錯誤。用信號加噪以后的條件概率密度分布函數(shù)來分析誤碼的產(chǎn)生比較清楚。(2.14) 1r Uml=2tanh 一 l 三 L(m (3)變量節(jié)點更新： (4)似后驗概率更新 0 vml=V+Uu, mllml m二M(lm 0,. Vl=Vl工Uml 第三章LDPC的性能分析 LDPC的仿真模型 圖3-1LDPC仿真模型圖 其中第二章詳細介紹了LDPCK的譯碼算法，可知LDPCt碼一般包括以下5個步驟：1、初始化2、校驗節(jié)點更新3、變量節(jié)點更新4、判決5、停止。實際操作時發(fā)現(xiàn)判決時只需用到本輪迭代的校驗節(jié)點的更新結果，變量

13、節(jié)點的更新在 下一輪迭代中才起作用。因此可以把步驟4和5安排在步驟3之前進行，這樣可以節(jié)省一次變量節(jié)點的更新工作，譯碼流程圖如下： / 、收完畢, 何始化 校獨F點更新 軟判決 勒閭束 圖3-2譯碼流程圖 LDPC的譯碼性能 通過前面幾章的介紹，LDPC的譯碼基本完成，為了了解實現(xiàn)的譯碼性能，下文中給出了LDPC勺譯碼Tt能圖。LDP編譯碼實現(xiàn)的編碼輸入是函數(shù)rand()產(chǎn)生的二進制隨機序列，并記錄LDPC碼在不同性噪比下的誤碼率，再在matlab中畫圖。 仿真時LDPCK列重選擇3,最大迭代次數(shù)設置為5次時進行仿驗，分析研信噪比對LDPCK誤碼性能的影響，隨著信噪比的增加，LDPCB的性能不

14、斷提高。BP譯碼算法下，可以看成是無窮比特量化譯碼，它充分利用接收的信道信息，信道信息利用率得到了極大的提高。信道信息的充分利用，極大地提高了譯碼性能，使得譯碼可以迭代進行，充分挖掘接收的信道信息，最終獲得出色誤碼性能 信噂比由 圖3-3BP算法的BER曲線 碼長對性能的影響 將LDPCK列重選擇3,最大迭代次數(shù)設置為5次且信噪比為0.5dB時進行仿真實驗,分析研究碼長對LDPC碼誤碼性能的影響，仿真得到了不同碼長對LDPC 碼的性能仿真結果如下圖所示。從圖中可以看出，在同樣的信噪比條件下，隨著碼長的增加，LDPC碼的性能不斷提高。在小信噪比區(qū)域，碼長的增加對誤碼率 的改進不大，但隨著信噪比的

15、增大，LDPC碼的誤碼率得到了明顯改善。但隨著碼長的增加，LDPC碼性能的提高是相對的，當達到一定碼長后，性能將會有很小的提高。這是因為一定碼長下編碼性能有一定的極限，隨著碼長的增大，編碼和譯碼的復雜度也增加，編碼性能就會更接近極限，性能隨碼長增加改善的就更少。 圖3-4碼長對LDPC性能的影響 迭代次數(shù)對譯碼性能的影響 將碼長為400的LDPCK,歹 J重為3,信噪比為0dB的情況下進行了仿真實驗。 圖中給出了上述情況下的不同迭代次數(shù)對LDPCK的性能仿真結果?？梢钥闯?，在相同的信噪比下，LDPCK的性能隨著迭代次數(shù)的增加而逐漸提高。但是LDPC碼的誤碼率并不能隨著迭代次數(shù)的增加無限地減小，

16、當?shù)螖?shù)足夠大的時候，再增加LDPCK的迭代次數(shù)，只能增加系統(tǒng)的時延和復雜度，而LDPCB的性能不會再有提高。 圖3-5迭代次數(shù)對性能的影響 結論 LDPC碼是迄今為止發(fā)現(xiàn)的最接近香農(nóng)限的信道編碼之一， 在現(xiàn)代通信和數(shù)據(jù)傳輸系統(tǒng)中擁有廣闊的應用前景。本文主要介紹了LDPC勺基礎知識包括構造、編碼、譯碼。著重介紹了LDPCK的高斯消去法編碼原理和概率譯碼算法，并在AWGH道下對其進行了性能仿真，比較了LDPC3相又t于Turbo碼的優(yōu)越性能。 作為一種優(yōu)秀的碼型，LDPC碼只有在實際中得到應用才能體現(xiàn)其真正的價值，糾錯編碼技術在通信系統(tǒng)中起著關鍵的作用，為可靠性信息傳輸提供保障，這一技術不管在

17、移動通信還是衛(wèi)星通信抑或是磁盤存儲中都得到了廣泛的應用。 1王新梅，肖圉鎮(zhèn).糾錯碼一原理與方法.西安：西安屯子科技大學出版社， 1991. 2樊昌信， 張甫翊， 徐炳祥， 吳成柯.“通信原理”(第五版) 【M.國防工業(yè)出版社，2001. 3王育民，粱傳甲.“信息與編碼理論.西北電訊工程學院，1986. R.G.Gallager,Low-DensityParity-CheckCodesD.Cambridge,MAMrrPress,1963. R.G.Gallager,Low-DcmityParity-CheckCode.IRETransactionsonInformationTheory,1962.8(1):21-28. 王單.LDPCK編譯碼算法研究D.西安：西安電子科技大學,2006:1432 7劉利軍.LDPCS碼算法研究D.廣州:華南理工大學,2011,52-5