LDPC碼全面介紹PPT課件

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

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

3、 每一列含有每一列含有p p 個個1 1； 任兩行（列）之間位置相同的任兩行（列）之間位置相同的1 1的個數(shù)的個數(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)任意兩行（列）位置相同非零元素的個任意兩行（列）位置相同非零元素的個數(shù)不大于數(shù)不大于1.1.(3)(3)非零元素個數(shù)盡量隨機排列，且分布稀非零元素個數(shù)盡量隨機排列，且分布稀疏。疏。(4)(4)某個矩陣的逆矩陣存在（在二元域上存某個矩陣的逆矩陣存在（在二元域上存在在） 2GF 對角線法對角線法思想：對于思想：對于1 1的分布及個數(shù)的滿足采用先以對角的分布及

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

5、大于疊的個數(shù)不大于1 1，如圖，如圖(a)(a)。然后可以對矩陣。然后可以對矩陣的行或列隨機排序（都是初等變換）得到圖的行或列隨機排序（都是初等變換）得到圖(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碼會產(chǎn)生的問題碼會產(chǎn)生的問題 G G的的維數(shù)巨大，維數(shù)巨大，G G一般也并不稀疏。比如一個（一般也并不稀疏。比如一個（1000010000，50005000） LDPCLDPC碼，碼，P P矩陣將是矩陣將是5000500050005000矩陣矩陣。假設(shè)。假設(shè)“1”1”的密度是的密度是0.50.5，編碼所作的運算也有，編碼所作的運算

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

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

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

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

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

12、it 11mlllg tPPt差別僅在于其 的奇次冪系數(shù)是負的。把兩多項式相加，然后令t=1，并除以2 ，就得到 序列中包含偶數(shù)個1的概率是：it11111211222mmmlllllllevenPPPPP Gallager概率譯碼算法概率譯碼算法同理，可以得到序列中包含奇數(shù)個同理，可以得到序列中包含奇數(shù)個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個校驗方程成立的條件是每個校驗個校驗方程成立的條件是每個校驗方程中其余方程中其余k-1k-1個比特中含有偶數(shù)個個比特中含有偶數(shù)個1 1，由前面的公式有：，由前面的公式有：0dc 111112|0,2kljldlPP S cy Gallager概率譯碼算法概率譯碼算法同理有同理有111112|1,2kljldlPP S cy代入即得代入即得111111120| ,11| ,112kjilddlkiddillPP cy SPP cy SPP Gallager概率譯碼算法概率譯碼算法概率譯碼算法

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

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

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