LDPC的BP譯碼算法

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

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

3、，并通過MATLAB&真工具對(duì)LDPCK在AWG陸道的誤比特率性能進(jìn)行了仿真，分析了信噪比、碼長和迭代次數(shù)對(duì)誤比特率性能的影響。 關(guān)鍵詞：二進(jìn)制LDPCBP算法迭代概率譯碼后驗(yàn)概率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)了用譯碼分析設(shè)計(jì)碼型的方法。

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

8、和硬件資源，不利于硬件實(shí)現(xiàn)。采用對(duì)數(shù)似然比描述的BP算法會(huì)有一個(gè)非常簡(jiǎn)單明了的形式。 考慮一個(gè)隨機(jī)變量X,它的對(duì)數(shù)似然比L(X)定義為 L(x)=ln3) P(X)1) 根據(jù)對(duì)數(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（） 因?yàn)榉辞泻瘮?shù)21-x在開區(qū)間（-1.1）內(nèi)單調(diào)增加，是 關(guān)于原點(diǎn)對(duì)稱的奇函數(shù)。這樣上式變?yōu)楹?jiǎn)潔形式: Uml=ln 1-II 1 1r

9、uml=2tanh l ”(q：l4)fL(ml 因?yàn)?qml+qml=1,上式右端各項(xiàng)除以 0.1 口同qml,右端各項(xiàng)分母 1 再除以qml,可得下式: 0qml 1 1qml uml2tanhH 三L(mlqml qml -1 1r uml=2tanh再 引用Vml的定義得下式： n ld_(m ev-1 4 eml.1 這里為了使形式更簡(jiǎn)潔，引用雙曲正切函數(shù): sh(x)e-etanh(x)=-x ch(x)ee 同理有:它是在（.已*）內(nèi)單調(diào)增加，函數(shù)值三（1,1）,以 y=+1,-1為漸近線，關(guān)于原點(diǎn) 對(duì)稱的奇函數(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算法的步驟整理如下：對(duì)于校驗(yàn)矩陣元素hmlhml=1=1 的m,l執(zhí)行如下步驟運(yùn) _0 (1)初始化：Vml=vl Vml tanh 2 l (2)校驗(yàn)節(jié)點(diǎn)更新: (5)比特判決：如果Vl0Vl0, ,則判XlXl=0;=0;否則判x x=1,=1,(l=1,2,.,N) 若HTx=0,或者迭代次數(shù)達(dá)到最大迭代次數(shù),則結(jié)束迭代,把x作為譯碼輸出,否則轉(zhuǎn)到步驟(2)繼續(xù)迭代。 上述是完整的的 LDPCLDPC 碼譯碼的BP算法，但還沒有說明如何去求得在x0 譯碼的初

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

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

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

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

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

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

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