第十四章 LDPC碼080614.ppt

1、第十四章 LDPC碼,陸以勤 2008年6月,提綱,一、歷史和特點(diǎn) 1.1 歷史 1.2 特點(diǎn) 二、定義和代數(shù)結(jié)構(gòu) 三、Tanner圖 四、構(gòu)造 五、譯碼 六、隨機(jī)LDPC碼,1.1 歷史,1964年Gallager發(fā)表Low-Density Check-Parity Code, 證明了LDPC碼性能接近于香農(nóng)限，并提出了構(gòu)建H矩陣的一種方法，以及兩種解碼方法和示意性的硬件電路原理圖，但是由于當(dāng)時(shí)科技水平有限，硬件條件的限制，LDPC碼并沒(méi)有得到重視和推廣。 1981年，Tanner從圖的觀點(diǎn)提供了對(duì)LDPC的闡釋?zhuān)缓雎浴?1993年，C.Berrou發(fā)明了Turbo碼及相關(guān)的迭代算法，引起

2、關(guān)注。 1996年D.Mac Kay 和R.Neal根據(jù)人工智能體系使自己的迭代算法和Pearl置信算法建立的聯(lián)系，并證明了LDPC碼性能和成本都優(yōu)于Turbo碼。,1.2 特點(diǎn),性能優(yōu)于Turbo碼，具有較大的靈活性和較低的差錯(cuò)平底特性（error floors）； 不需要深度交織以獲得好的誤碼性能； 描述簡(jiǎn)單，對(duì)嚴(yán)格理論分析具有可驗(yàn)證性； 譯碼不基于網(wǎng)格，復(fù)雜度低于turbo碼，且可實(shí)現(xiàn)完全的并行操作，硬件復(fù)雜底低，因而適合硬件實(shí)現(xiàn)； 吞吐量大，極具高速譯碼潛力。因此，結(jié)合LDPC無(wú)線局域網(wǎng)必將取得更好的性能； 歐洲衛(wèi)星廣播系統(tǒng)DVBS52采用； 認(rèn)為是第四代移動(dòng)通信的信道編碼。,提綱,一

3、、歷史和特點(diǎn) 二、定義和代數(shù)結(jié)構(gòu) 2.1 定義 2.2 代數(shù)結(jié)構(gòu) 三、Tanner圖 四、構(gòu)造 五、譯碼 六、隨機(jī)LDPC碼,2.1 定義,定義1：( , )規(guī)則（regular)LDPC碼定義為具有如下特性的校驗(yàn)矩陣HJXN的零空間： 每一行含有個(gè)1； 每一列含有 個(gè)1； 任兩列之間位置相同的1的個(gè)數(shù)0，1 N ， J (低密度） (注意，HJXN的各行并不要求獨(dú)立） 密度r = /n = /J,2.1 定義,定義：( , )規(guī)則（regular)LDPC碼定義為具有如下特性的校驗(yàn)矩陣HJXN的零空間: 每一行含有個(gè)1； 每一列含有 個(gè)1； 任兩列之間位置相同的1的個(gè)數(shù)0，1; N ， J

4、(低密度）,(15,7,5) LDPC碼,2.2 代數(shù)結(jié)構(gòu),Al= h1,h6, h11 可用大數(shù)邏輯譯碼對(duì)第1位進(jìn)行校驗(yàn),h1,h6,h11,2.2 代數(shù)結(jié)構(gòu),Al= h1,h7, h12 可用大數(shù)邏輯譯碼對(duì)第2位進(jìn)行校驗(yàn),h1,h7,h12,由此可見(jiàn)，每一個(gè)位都有3個(gè)校驗(yàn)和對(duì)其進(jìn)行糾錯(cuò)，所以可以糾一個(gè)錯(cuò)。 一般來(lái)說(shuō)，因?yàn)槊恳涣卸加?個(gè)1，相應(yīng)的行向量可作為校驗(yàn)和，又因?yàn)槠渌?的個(gè)數(shù)最多為1，所以可以構(gòu)成大數(shù)邏輯譯碼，能糾 / 2個(gè)錯(cuò)。,提綱,一、歷史和特點(diǎn) 二、定義和代數(shù)結(jié)構(gòu) 三、Tanner圖（二分圖） 3.1 Tanner圖 3.2 環(huán)的影響 四、構(gòu)造 五、譯碼 六、隨機(jī)LDPC碼,

5、3.1 Tanner圖（二分圖）,矩陣的圖形表示 （循環(huán)碼),V1 V2 V3 V4 V5 V6 V7,不包含長(zhǎng)度為4的環(huán),(碼元)比特節(jié)點(diǎn),符號(hào)節(jié)點(diǎn) （code-bit vertices, symbol nodes) 變量點(diǎn)(variable nodes),校驗(yàn)節(jié)點(diǎn) （check nodes),3.2 環(huán)的影響,含有長(zhǎng)為4的環(huán),含有長(zhǎng)為6的環(huán),不能校驗(yàn)（x0 x00 xx)和（x1x11xx),S2= +v2 +v4 S3= +v2 +v5 S4= +v4+v5 ,提綱,一、歷史和特點(diǎn) 二、定義和代數(shù)結(jié)構(gòu) 三、Tanner圖（二分圖） 四、構(gòu)造 4.1 Gallager 構(gòu)造一類(lèi)碼 4.2

6、通過(guò)行分裂和列分裂的碼構(gòu)造方法 4.3 有限幾何LDPC 五、譯碼 六、隨機(jī)LDPC碼,4.1 Gallager 構(gòu)造一類(lèi)碼,H1 (J1J1),H2 H1 的列置換,H3 H1 的列置換,(J1=5,=4, =3) 構(gòu)成（20，7，6）碼,4.1 Gallager 構(gòu)造一類(lèi)碼,Gallager構(gòu)造一類(lèi)LDPC碼的方法，但Gallager并沒(méi)有提供H1 的列置換的方法，需要計(jì)算機(jī)搜索。,H1 的列置換,H1 的列置換,4.2 通過(guò)行分裂和列分裂的碼構(gòu)造方法,設(shè)H的列分別記為g0,g1,gi,gn-1。將每一列分裂成q列,原始列的1循環(huán)分配到新的列。這樣可降低密度 例如，gi分裂為gi,1,gi

7、,2,gi,q, 的第1個(gè)1分配給gi,1,第2個(gè)1分配給gi,2,第q個(gè)1分配給gi,q,第q+1個(gè)1分配給gi,1,第q+2個(gè)1分配給gi,2, ,.,通過(guò)列(行)分裂操作可以拆散長(zhǎng)度為4的環(huán),4.3 有限幾何LDPC,歐幾里德幾何碼 在組合數(shù)學(xué)領(lǐng)域，GF(ps)上pms個(gè)m維向量a =(a0,a1,am)構(gòu)成m維線性空間（或矢量空間）(定義2.6) 稱(chēng)為m維歐氏幾何( Eudidean-Geometry)，記為EG(m,ps)。 每個(gè)m維向量 a = (a0,a1,am) 稱(chēng)為點(diǎn)(point)，0向量稱(chēng)為原點(diǎn)(origin)。 設(shè)a，a0為EG(m,ps)兩個(gè)線性獨(dú)立的點(diǎn)， 其中a0（不

8、是原點(diǎn))，則ps個(gè)點(diǎn)組成的集合a+a0: GF(ps)稱(chēng)為EG(m,ps)的一條直線(line)或一維平面（1-flat)，記為 a+a0。 對(duì)于每個(gè) GF(ps)，對(duì)應(yīng)于直線a+a0的一個(gè)點(diǎn)a+a0。 EG(m,ps)除a0外共有pms-1個(gè)向量，而每條通過(guò)a0的直線共有ps個(gè)向量，除a0外共有ps-1個(gè)，由于兩條直線不能有兩個(gè)交點(diǎn)，因此EG(m,ps)除a0外的pms-1個(gè)向量分配到所有相交于a0的直線上，即EG(m,ps)中相交于a0的直線數(shù)為：(pms-1)/(ps-1) EG(m,ps)共有p(m-1)s(pms-1)/(ps-1)條直線。,4.3 有限幾何LDPC,點(diǎn),線,HEG

9、=,校驗(yàn)矩陣的行對(duì)應(yīng)歐幾里德集合的線， 列對(duì)用于歐幾里德集合的點(diǎn) 矩陣的元素對(duì)應(yīng)歐幾里德集合的點(diǎn)線的關(guān)聯(lián)向量值(行向量是關(guān)聯(lián)向量） HEG共p(m-1)s(pms-1)/(ps-1)行，n=pms列。 由于每條直線只有ps個(gè)點(diǎn)，因此行重=ps 每一列的總量為 (pms-1)/(ps-1) 密度r= /n=ps/pms=p-(m-1)s =/ p(m-1)s(pms-1)/(ps-1) =p-(m-1)s dmin +1= (pms-1)/(ps-1)+1,HEG =,1 (點(diǎn)在線上） 0 (其它）,提綱,一、歷史和特點(diǎn) 二、定義和代數(shù)結(jié)構(gòu) 三、Tanner圖（二分圖） 四、構(gòu)造 五、譯碼 5.

10、1 大數(shù)邏輯譯碼 5.2 比特翻轉(zhuǎn)譯碼 5.3 加權(quán)大數(shù)邏輯或加權(quán)比特翻轉(zhuǎn)譯碼 5.4 后驗(yàn)概率譯碼 5.5 基于置信度傳播的迭代譯碼 (和積算法） 六、隨機(jī)LDPC碼,5.1 大數(shù)邏輯譯碼,Al= h1,h7, h12 可用大數(shù)邏輯譯碼對(duì)第2位進(jìn)行校驗(yàn),h1,h7,h12,由此可見(jiàn)，每一個(gè)位都有3個(gè)校驗(yàn)和對(duì)其進(jìn)行糾錯(cuò)，所以可以糾一個(gè)錯(cuò)。 對(duì)于每個(gè)比特位置l,H的行向量存在一個(gè)行的子集 Al=h1(l), h2(l), h (l) 在該比特位置正交，即Al每一行的第個(gè)分量都為1，而其他位置的分量最多只在某一行出現(xiàn) 一般來(lái)說(shuō)，因?yàn)槊恳涣卸加?個(gè)1，相應(yīng)的行向量可作為校驗(yàn)和，又因?yàn)槠渌?的個(gè)數(shù)最

11、多為1，所以可以構(gòu)成一步大數(shù)邏輯可譯碼，能糾 / 2個(gè)錯(cuò)。 由于每一列都可找到相應(yīng)校驗(yàn)和式，不需要循環(huán)。,5.2 比特翻轉(zhuǎn)譯碼算法,1. 伴隨式,+,c,r=c+e,e,HcT=0T HrT= H(c+e)T= HcT+HeT= HeT 定義s rHT 稱(chēng)為接收字r 的伴隨式（校正子）,h1,n-1 h1,n-2 h1,0 h2,n-1 h2,n-2 h2,0 . hn-k,n-1hn-k,n-2 hn-k,0,H=,= (hn-1, hn-2, , h1,h0 ),設(shè)e = (en-1, en-2, , e1, e0 ) = (0, , ei1, , ei2, , eit , ,0 ),s

12、= eHT=0, , ei1, , ei2, , eit , ,0 ,hn-1T hn-2T . h1T h0T,= ei1 hi1T+ +ei2 hi2T+ eit hi tT,發(fā)生錯(cuò)誤的位所對(duì)應(yīng)的列向量的線性組合,五、線性分組碼的譯碼2,例：7，3碼， H=,101 | 1000 111 | 0100 110 | 0010 011 | 0001,s = r HT= ( r6 r5 r4 r3 r2 r1 r0 ),101 | 1000 111 | 0100 110 | 0010 011 | 0001,T,r6 + r4 + r3 r6 + r5 + r4 + r2 r6 + r5 + r1

13、 r5 + r4 + r0,=,T,= （s3 s2 s1 s0),五、線性分組碼的譯碼3,c =(1010011) e =(0100000) r =(1110011),s = r HT = e HT = (0100000),101 | 1000 111 | 0100 110 | 0010 011 | 0001,T,=,0 1 1 1,T,c =(1010011) e =(1001000) r = (0011011),s = r HT = e HT = (1001000),101 | 1000 111 | 0100 110 | 0010 011 | 0001,T,=,1 1 1 0,T,+,T

14、,1 0 0 0,=,(0110),5.2 比特翻轉(zhuǎn)譯碼算法,假設(shè)v2,v3有錯(cuò)，則s7, s8, s12,s13都不為0，而其它的sj都為0 (因此f2=f3=2,見(jiàn)后，fj=0,j取115的其它值),h1,h7,h12,h8,h13,5.2 比特翻轉(zhuǎn)譯碼算法,比特翻轉(zhuǎn)譯碼算法 計(jì)算所有奇偶校驗(yàn)和，如果所有的奇偶校驗(yàn)和都和0，則停止譯碼； 對(duì)于接收序列的每個(gè)比特位i，計(jì)算包括它的錯(cuò)誤奇偶校驗(yàn)方程的個(gè)數(shù)，記為fi, i= 0,1,n-1 對(duì)于上例，f2=f3=2, fj=0, j=1,415 選取fi大于某個(gè)參數(shù) 的的比特位，組成集合S; 將S的比特位翻轉(zhuǎn)； 重復(fù)14步，直至所有的奇偶校驗(yàn)和等

15、于0或者達(dá)到最大迭代次數(shù)。 設(shè)計(jì)參數(shù) 稱(chēng)為門(mén)限（threshold),與， ，dmin,和信噪比有關(guān)。,5.3 加權(quán)大數(shù)邏輯或加權(quán)比特翻轉(zhuǎn)譯碼,接收端匹配濾波器輸出的軟判決接收序列y=(y0,y0,yn-1)。對(duì)于加性高斯白噪聲(AWGN)信道，接收符號(hào)yl的幅度| yl |是其可靠性的一種簡(jiǎn)單量度：幅度越大，硬判決數(shù)字zl的可靠度就越高。 定義 | yj |(l)min min | yi |: 0 i n-1, hj,i =1 將在比特位置l正交的校驗(yàn)和式調(diào)整為 加權(quán)檢驗(yàn)和式： 根據(jù)El修改一步大數(shù)邏輯譯碼：,l,H,1,1,1,Al,s1(l),s(l),sj(l),Sl=s1(l), s

16、2(l), sj(l), s(l),5.4 和積算法（sum-product algorithm, SPA),是一種基于置信度傳播的迭代譯碼 （iterative decoding algorithm based on belief propagation, IDPB) 一種逐符號(hào)、軟輸入軟輸出（SISO)的譯碼算法。 對(duì)于每個(gè)符號(hào)的可靠度的量度可以采用其邊緣后驗(yàn)概率、對(duì)數(shù)似然比或者對(duì)應(yīng)接受符號(hào)值。每次譯碼迭代得到的碼符號(hào)的可靠度量度的計(jì)算結(jié)果作為下一次迭代的輸入。譯碼迭代持續(xù)進(jìn)行，直到滿足某個(gè)特定的停止條件。然后，基于碼符號(hào)的可靠度量度的計(jì)算結(jié)果做出硬判決。,比特節(jié)點(diǎn)vl在被激活后把qj,l

17、x,(i)（見(jiàn)后）作為其置信度傳遞給與它相連的校驗(yàn)節(jié)點(diǎn)。 校驗(yàn)節(jié)點(diǎn) sj在被激活后，把j,lx,(i) （見(jiàn)后）作為其置信度傳遞給與它相連的比特節(jié)點(diǎn)。,令hj=(hj,0,hj,1, , hj,n-1), B(hj)= l:hj,l=1, 0 l n-1稱(chēng)為hj的支撐集 對(duì)于軟判決接收序列 y，碼比特的對(duì)數(shù)似然比：L(vl)= log P(vl=1 | y) / P(vl=0 | y) 對(duì)于 0 l n-1， 0 j J 和每個(gè)hjAl ,令qj,lx,(i)為第i次迭代中給定基于Alhj中校驗(yàn)和的條件下，發(fā)送碼比特vl取值為x的條件概率。(在除sj外參與的其它校驗(yàn)點(diǎn)提供的信息上，vl的狀態(tài)為

18、x的置信度。),H,1,1,1,Al,h1,h,hj,1 1,1,B(hj),l,1,41,(i-1),4,41,(i-1),q3,41,(i),1,41,(i-1),4,41,(i-1),q3,41,(i),令,即給定vl=x(0或1）和B(hj)中其他碼比特的可分離的分布qj,lx,(i): tB(hj)l的條件下，校驗(yàn)和sj正確（即sj =0)的條件概率。(比特節(jié)點(diǎn)vl狀態(tài)為x和與校驗(yàn)點(diǎn)sj中相連的其它比特節(jié)點(diǎn)狀態(tài)已知的條件下，校驗(yàn)和為0的概率)。,（1）,3,61,(i),q3,30,(i),q3,40,(i),q3,31,(i),q3,41,(i),qj,lx,(i) :在除sj外參與的其它校驗(yàn)點(diǎn)提供的信息上，vl的狀態(tài)為x的置信度。 j,l0,(i):比特節(jié)點(diǎn)vl狀態(tài)為x和與校驗(yàn)點(diǎn)sj中相連的其它比特節(jié)點(diǎn)狀態(tài)已知的條件下，校驗(yàn)和為0的概率。 取其它校驗(yàn)點(diǎn)/比特節(jié)點(diǎn)：不采用已經(jīng)輸入的信息，避免信息返流，保持信息的獨(dú)立性，增強(qiáng)迭代效果。,得到的j,lx,(i)用來(lái)更新qj,lx,(i1)。,1,41,(i-1),4,41,(i-1),3,41,(i-1),得到的j,lx,(i)用來(lái)更新qj,lx,(i1)。,算法：,初始化 設(shè)定i=0和迭代的最大次數(shù)Imax。對(duì)于滿足hj,