LDPC碼全面介紹PPT課件

1、密碼學(xué)概述密碼學(xué)概述1LDPC碼（ Low Density Parity Check Code ）李風(fēng)光李風(fēng)光 LDPC簡(jiǎn)介簡(jiǎn)介L(zhǎng)DPC規(guī)則碼的對(duì)角線構(gòu)造方法規(guī)則碼的對(duì)角線構(gòu)造方法Gallager概率譯碼算法概率譯碼算法LDPC編碼編碼BP算法算法 LDPC歷史歷史19601960年，由年，由GallagerGallager提出。但是由于計(jì)算復(fù)雜度提出。但是由于計(jì)算復(fù)雜度超出當(dāng)時(shí)的計(jì)算能力，超出當(dāng)時(shí)的計(jì)算能力，LDPCLDPC碼被人們所遺忘。碼被人們所遺忘。19811981年，年，TannerTanner提出編碼的圖形結(jié)構(gòu)表示方法，提出編碼的圖形結(jié)構(gòu)表示方法，這為這為L(zhǎng)DPCLDPC解碼算法的

2、簡(jiǎn)化奠定了基礎(chǔ)，促進(jìn)了解碼算法的簡(jiǎn)化奠定了基礎(chǔ)，促進(jìn)了LDPCLDPC的復(fù)蘇。的復(fù)蘇。19961996年，年，MacKayMacKay和和NealNeal重新發(fā)現(xiàn)重新發(fā)現(xiàn)LDPCLDPC碼，并指出碼，并指出LDPCLDPC的優(yōu)秀性能可以逼近的優(yōu)秀性能可以逼近ShannonShannon極限。極限。LDPCLDPC重新重新進(jìn)入大家的視野，并受到廣泛重視。進(jìn)入大家的視野，并受到廣泛重視。 定義定義 定義：定義：LDPCLDPC規(guī)則碼規(guī)則碼(N,p,q)(N,p,q)定義為具有如下特性的定義為具有如下特性的校驗(yàn)矩陣校驗(yàn)矩陣H HMXNMXN的零空間：的零空間： 每一行含有每一行含有q q個(gè)個(gè)1 1；

3、 每一列含有每一列含有p p 個(gè)個(gè)1 1； 任兩行（列）之間位置相同的任兩行（列）之間位置相同的1 1的個(gè)數(shù)的個(gè)數(shù) 不大于不大于1 1即即 0 0，1 1 q N q N ，p M pq2,m/n=p/qp,pq2,m/n=p/q。(2)(2)任意兩行（列）位置相同非零元素的個(gè)任意兩行（列）位置相同非零元素的個(gè)數(shù)不大于數(shù)不大于1.1.(3)(3)非零元素個(gè)數(shù)盡量隨機(jī)排列，且分布稀非零元素個(gè)數(shù)盡量隨機(jī)排列，且分布稀疏。疏。(4)(4)某個(gè)矩陣的逆矩陣存在（在二元域上存某個(gè)矩陣的逆矩陣存在（在二元域上存在在） 2GF 對(duì)角線法對(duì)角線法思想：對(duì)于思想：對(duì)于1 1的分布及個(gè)數(shù)的滿(mǎn)足采用先以對(duì)角的分布及

4、個(gè)數(shù)的滿(mǎn)足采用先以對(duì)角線滿(mǎn)足個(gè)數(shù)，再把小塊的稀疏矩陣隨機(jī)打亂線滿(mǎn)足個(gè)數(shù)，再把小塊的稀疏矩陣隨機(jī)打亂以規(guī)則碼以規(guī)則碼H(8,3,4)H(8,3,4)為例為例矩陣的行數(shù)為矩陣的行數(shù)為6 6，先進(jìn)行矩陣布局設(shè)計(jì)，設(shè)，先進(jìn)行矩陣布局設(shè)計(jì)，設(shè)a,b,ca,b,c為三個(gè)長(zhǎng)為為三個(gè)長(zhǎng)為8 8的全的全1 1矢量，使矢量，使a a在左邊方陣在左邊方陣主對(duì)角線下距離主對(duì)角線下距離1 1的位置，的位置，b b在主對(duì)角線位置，在主對(duì)角線位置，c c在上距離為在上距離為2 2的位置。每一矢量的剩余部分，的位置。每一矢量的剩余部分，折斷往上分布，適當(dāng)調(diào)整使任意兩行、列相重折斷往上分布，適當(dāng)調(diào)整使任意兩行、列相重疊的個(gè)數(shù)不

5、大于疊的個(gè)數(shù)不大于1 1，如圖，如圖(a)(a)。然后可以對(duì)矩陣。然后可以對(duì)矩陣的行或列隨機(jī)排序（都是初等變換）得到圖的行或列隨機(jī)排序（都是初等變換）得到圖(b)(b)所示所示 101001101101000101101010001101010101101010001101a 101001010111001011001100100100110100111000111001b 100000000100000000100000000100000000100000000100a 100000001100000001100000001100000001100000001100a 10100000110

6、1000001101000001101000001101000001101a LDPC系統(tǒng)碼的編碼系統(tǒng)碼的編碼n一般系統(tǒng)線性分組碼的編碼一般系統(tǒng)線性分組碼的編碼C = mG = m mP C = mG = m mP n一般編碼方法用于一般編碼方法用于 LDPCLDPC碼會(huì)產(chǎn)生的問(wèn)題碼會(huì)產(chǎn)生的問(wèn)題 G G的的維數(shù)巨大，維數(shù)巨大，G G一般也并不稀疏。比如一個(gè)（一般也并不稀疏。比如一個(gè)（1000010000，50005000） LDPCLDPC碼，碼，P P矩陣將是矩陣將是5000500050005000矩陣矩陣。假設(shè)。假設(shè)“1”1”的密度是的密度是0.50.5，編碼所作的運(yùn)算也有，編碼所作的運(yùn)算

7、也有 0.50.5(5000(50005000)=12.55000)=12.510106 6 次（注：次（注：H H在在系統(tǒng)化之前是稀疏矩陣，系統(tǒng)化后不一定。）系統(tǒng)化之前是稀疏矩陣，系統(tǒng)化后不一定。）n簡(jiǎn)化編碼的方法之一是利用代數(shù)或幾何途徑來(lái)簡(jiǎn)化編碼的方法之一是利用代數(shù)或幾何途徑來(lái)設(shè)計(jì)設(shè)計(jì)LDPCLDPC碼碼. . 近似下三角矩陣編碼近似下三角矩陣編碼交換行和列交換行和列可以將可以將H H轉(zhuǎn)化成一個(gè)近似下三角矩轉(zhuǎn)化成一個(gè)近似下三角矩陣陣gTBCDEA0n-mm-ggm-g保證T是可逆的 將變換后的矩陣將變換后的矩陣H H左乘左乘 其中其中I I是單位矩陣，得到是單位矩陣，得到10IETI110

8、ABTETACET BD 設(shè)編碼碼字設(shè)編碼碼字 ，其中，其中t t為信息位，為信息位， 為檢驗(yàn)位。為檢驗(yàn)位。12,St p p12,p p10,THSET BD根據(jù)若可逆?？傻?1111TTpET BDETAC t 121TTTPTAtBp 注意兩點(diǎn)：g應(yīng)當(dāng)盡可能的小，0.02746n；保證 可逆。1ETBD LDPC編碼方法的研究：如何利用校驗(yàn)矩陣的稀疏性有效的進(jìn)行編碼，其目的是使編碼復(fù)雜度隨碼長(zhǎng)呈線性增長(zhǎng)。上述近似下三角方法的復(fù)雜度近似為：2nOg LDPC譯碼譯碼Gallager概率譯碼算法概率譯碼算法BP算法算法 硬判決：對(duì)信道的輸出作出是硬判決：對(duì)信道的輸出作出是0 0還是還是1 1

9、的判決。的判決。軟判決：不作出軟判決：不作出0101判決，只輸出有關(guān)信息，如判決，只輸出有關(guān)信息，如0 0、1 1的后驗(yàn)概率。的后驗(yàn)概率。軟判決譯碼算法：對(duì)信道輸出的軟判決序列軟判決譯碼算法：對(duì)信道輸出的軟判決序列進(jìn)行譯碼的算法就叫軟判決譯碼算法。進(jìn)行譯碼的算法就叫軟判決譯碼算法。GallagerGallager概率譯碼算法和概率譯碼算法和BPBP算法都是軟判決算法都是軟判決譯碼算法。其目的都是利用碼字中其他所有譯碼算法。其目的都是利用碼字中其他所有比特的信息來(lái)修正該比特的后驗(yàn)概率，就可比特的信息來(lái)修正該比特的后驗(yàn)概率，就可能得到該比特的最佳后驗(yàn)概率，然后判決它能得到該比特的最佳后驗(yàn)概率，然后

10、判決它為為0 0或或1 1。 Gallager概率譯碼算法概率譯碼算法對(duì)碼字的某一比特，包含它的校驗(yàn)方程可能不對(duì)碼字的某一比特，包含它的校驗(yàn)方程可能不止一個(gè)，這些校驗(yàn)方程的其他比特又可能包含止一個(gè)，這些校驗(yàn)方程的其他比特又可能包含在更多的校驗(yàn)方程之中。為表示這種關(guān)系，引在更多的校驗(yàn)方程之中。為表示這種關(guān)系，引入入校驗(yàn)集合樹(shù)校驗(yàn)集合樹(shù)概念概念。d(1,1)(1,2)根節(jié)點(diǎn)d表示比特d，和d相連的每一條邊表示包含d的一個(gè)校驗(yàn)方程，如1 11 20dccc Gallager概率譯碼算法概率譯碼算法其中其中S S表示包含表示包含d d的所有校驗(yàn)方程成立這一事件的所有校驗(yàn)方程成立這一事件令1|ddPP

11、cy dd1ilPl表示 的校驗(yàn)集合樹(shù)第一層中包含 的第i個(gè)校驗(yàn)方程的第 個(gè)比特為 的概率，那么有：111111120| ,11| ,112kjilddlkiddillPP cy SPP cy SPP d1| ,dP cy S如何求比特 的最佳后驗(yàn)概率？ Gallager概率譯碼算法概率譯碼算法證明：我們先證以下結(jié)論m1llPlm 一個(gè)長(zhǎng)為的相互獨(dú)立的二進(jìn)制序列，其中第 個(gè)比特為1的概率為，那么序列中包含偶數(shù)個(gè)1的概率是11122mllevenPP考慮關(guān)于t的m次多項(xiàng)式 11mlllftPPt Gallager概率譯碼算法概率譯碼算法由二項(xiàng)式分布知道 的系數(shù)正是序列中包含i個(gè)1的概率。再考慮：

12、it 11mlllg tPPt差別僅在于其 的奇次冪系數(shù)是負(fù)的。把兩多項(xiàng)式相加，然后令t=1，并除以2 ，就得到 序列中包含偶數(shù)個(gè)1的概率是：it11111211222mmmlllllllevenPPPPP Gallager概率譯碼算法概率譯碼算法同理，可以得到序列中包含奇數(shù)個(gè)同理，可以得到序列中包含奇數(shù)個(gè)1 1的概率為的概率為111212mlloddevenPPP根據(jù)條件概率定義有根據(jù)條件概率定義有0 |,0,1|,1,ddddP cy SP cy SP cy SP cy S 0| |0, 1| |1, ddddP y P cy P S cyP y P cy P S cy Gallager概

13、率譯碼算法概率譯碼算法|0,1|1,ddddP S cyPPP S cy當(dāng)當(dāng) ，包含，包含d d的的j j個(gè)校驗(yàn)方程成立的條件是每個(gè)校驗(yàn)個(gè)校驗(yàn)方程成立的條件是每個(gè)校驗(yàn)方程中其余方程中其余k-1k-1個(gè)比特中含有偶數(shù)個(gè)個(gè)比特中含有偶數(shù)個(gè)1 1，由前面的公式有：，由前面的公式有：0dc 111112|0,2kljldlPP S cy Gallager概率譯碼算法概率譯碼算法同理有同理有111112|1,2kljldlPP S cy代入即得代入即得111111120| ,11| ,112kjilddlkiddillPP cy SPP cy SPP Gallager概率譯碼算法概率譯碼算法概率譯碼算法

14、：概率譯碼算法：對(duì)每一比特，給出校驗(yàn)集合樹(shù)，利用公式從頂對(duì)每一比特，給出校驗(yàn)集合樹(shù)，利用公式從頂層開(kāi)始逐層計(jì)算各節(jié)點(diǎn)后驗(yàn)概率，直到求出根層開(kāi)始逐層計(jì)算各節(jié)點(diǎn)后驗(yàn)概率，直到求出根節(jié)點(diǎn)的后驗(yàn)概率，然后判決該比特是節(jié)點(diǎn)的后驗(yàn)概率，然后判決該比特是0 0還是還是1 1。11| ,0.50dddcP cy Sc若其他 BP算法算法符號(hào)的定義： :1mllmlL mL mxH設(shè)表示與校驗(yàn)節(jié)點(diǎn)s 相連的所有變量節(jié)點(diǎn)x的集合即 :1lmmmlM lM lsH設(shè)表示與變量節(jié)點(diǎn)x相連的所有校驗(yàn)節(jié)點(diǎn)s 的集合即 0,1xmlxmllx imllmlmqM lmxxxqxsqixs，表示基于接收信號(hào)并根據(jù)校驗(yàn)節(jié)點(diǎn)集合

15、得出的的概率，可以認(rèn)為，表示第 次迭代是 向傳遞的信時(shí) 向息傳遞的信息 BP算法算法 :sxxmllmlmxmlmlx imlmlrxxqlL mlrisrxsx，表示，并給定其他比特的一組概率時(shí)，校驗(yàn)節(jié)點(diǎn)對(duì)應(yīng)的方程成立的概率，表示第 次迭可以看作是 向 傳遞的信息代時(shí) 向 傳遞的信息 0 ,1,0 ,12iim lm llLmlim lqqr 0 ,1,1,12iim lm llLmlim lqqr BP算法算法 1, 00, 01111(1),1mlmllmlllqfqff 對(duì)所有滿(mǎn)足H的m,l執(zhí)行以下步驟初始化：， 為信道得到的概率 0,1,0,1,0,1,1122iiiimlmlmlm

16、llL m llL m liimlmlqqqqrr(2)校驗(yàn)節(jié)點(diǎn)信息更新：， 0,10,1,11,010,11,1(3)1iiiimlmllmlmllm lm lmM lmmM lmiimlmlmlqaprqapraqq變量節(jié)點(diǎn)信息更新：其中是一個(gè)使的值。 BP算法算法 0,10,1,10,010,11,1(4)1iiiilllmllllmlm M lm M liilllqa prqa praqq計(jì)算后驗(yàn)概率其中為使成立的值。0,1(5)0.5,0,11,20,illTqxlnxx比特判決：若則判反之為，。若H或者迭代次數(shù)到達(dá)最大值，則結(jié)束迭代，輸出 ；否則轉(zhuǎn)到第二步繼續(xù)迭代。 BP算法算法1s2s3s4s1x2x3x4x5x6x7x8x1110001121111211(1),qqfqqf初始化0101013355770101011111313151(2),2ffffff計(jì)算rr ,rr ,r BP算法算法00 011 1011111 1 211111 1 21111111(3)(1qa f rqa f r aqq計(jì) 算為 使的 值 )0001110111 11 2111 11 21111(4)(1qar rqar raqq計(jì)算為使的值)0111(5)0.50,