第十四章-LDPC碼080614.ppt

第十四章LDPC碼 陸以勤2008年6月 提綱 一 歷史和特點1 1歷史1 2特點二 定義和代數(shù)結(jié)構(gòu)三 Tanner圖四 構(gòu)造五 譯碼六 隨機(jī)LDPC碼 1 1歷史 1964年Gallager發(fā)表Low DensityCheck ParityCode 證明了LDPC碼性能接近于香農(nóng)限 并提出了構(gòu)建H矩陣的一種方法 以及兩種解碼方法和示意性的硬件電路原理圖 但是由于當(dāng)時科技水平有限 硬件條件的限制 LDPC碼并沒有得到重視和推廣 1981年 Tanner從圖的觀點提供了對LDPC的闡釋 被忽略 1993年 C Berrou發(fā)明了Turbo碼及相關(guān)的迭代算法 引起關(guān)注 1996年D MacKay和R Neal根據(jù)人工智能體系使自己的迭代算法和Pearl置信算法建立的聯(lián)系 并證明了LDPC碼性能和成本都優(yōu)于Turbo碼 1 2特點 性能優(yōu)于Turbo碼 具有較大的靈活性和較低的差錯平底特性 errorfloors 不需要深度交織以獲得好的誤碼性能 描述簡單 對嚴(yán)格理論分析具有可驗證性 譯碼不基于網(wǎng)格 復(fù)雜度低于turbo碼 且可實現(xiàn)完全的并行操作 硬件復(fù)雜底低 因而適合硬件實現(xiàn) 吞吐量大 極具高速譯碼潛力 因此 結(jié)合LDPC無線局域網(wǎng)必將取得更好的性能 歐洲衛(wèi)星廣播系統(tǒng)DVB S52采用 認(rèn)為是第四代移動通信的信道編碼 提綱 一 歷史和特點二 定義和代數(shù)結(jié)構(gòu)2 1定義2 2代數(shù)結(jié)構(gòu)三 Tanner圖四 構(gòu)造五 譯碼六 隨機(jī)LDPC碼 2 1定義 定義1 規(guī)則 regular LDPC碼定義為具有如下特性的校驗矩陣HJXN的零空間 每一行含有 個1 每一列含有 個1 任兩列之間位置相同的1的個數(shù) 0 1 N J 低密度 注意 HJXN的各行并不要求獨立 密度r n J 2 1定義 定義 規(guī)則 regular LDPC碼定義為具有如下特性的校驗矩陣HJXN的零空間 每一行含有 個1 每一列含有 個1 任兩列之間位置相同的1的個數(shù) 0 1 N J 低密度 15 7 5 LDPC碼 2 2代數(shù)結(jié)構(gòu) Al h1 h6 h11 可用大數(shù)邏輯譯碼對第1位進(jìn)行校驗 h1 h6 h11 2 2代數(shù)結(jié)構(gòu) Al h1 h7 h12 可用大數(shù)邏輯譯碼對第2位進(jìn)行校驗 h1 h7 h12 由此可見 每一個位都有3個校驗和對其進(jìn)行糾錯 所以可以糾一個錯 一般來說 因為每一列都有 個1 相應(yīng)的行向量可作為校驗和 又因為其他列1的個數(shù)最多為1 所以可以構(gòu)成大數(shù)邏輯譯碼 能糾 2 個錯 提綱 一 歷史和特點二 定義和代數(shù)結(jié)構(gòu)三 Tanner圖 二分圖 3 1Tanner圖3 2環(huán)的影響四 構(gòu)造五 譯碼六 隨機(jī)LDPC碼 3 1Tanner圖 二分圖 矩陣的圖形表示 循環(huán)碼 V1V2V3V4V5V6V7 不包含長度為4的環(huán) 碼元 比特節(jié)點 符號節(jié)點 code bitvertices symbolnodes 變量點 variablenodes 校驗節(jié)點 checknodes 3 2環(huán)的影響 含有長為4的環(huán) 含有長為6的環(huán) 不能校驗 x0 x00 xx 和 x1x11xx S2 v2 v4 S3 v2 v5 S4 v4 v5 提綱 一 歷史和特點二 定義和代數(shù)結(jié)構(gòu)三 Tanner圖 二分圖 四 構(gòu)造4 1Gallager構(gòu)造一類碼4 2通過行分裂和列分裂的碼構(gòu)造方法4 3有限幾何LDPC五 譯碼六 隨機(jī)LDPC碼 4 1Gallager構(gòu)造一類碼 H1 J1 J1 H2H1的列置換 H3H1的列置換 J1 5 4 3 構(gòu)成 20 7 6 碼 4 1Gallager構(gòu)造一類碼 Gallager構(gòu)造一類LDPC碼的方法 但Gallager并沒有提供H1的列置換的方法 需要計算機(jī)搜索 H1的列置換 H1的列置換 4 2通過行分裂和列分裂的碼構(gòu)造方法 設(shè)H的列分別記為g0 g1 gi gn 1 將每一列分裂成q列 原始列的1循環(huán)分配到新的列 這樣可降低密度例如 gi分裂為gi 1 gi 2 gi q 的第1個1分配給gi 1 第2個1分配給gi 2 第q個1分配給gi q 第q 1個1分配給gi 1 第q 2個1分配給gi 2 通過列 行 分裂操作可以拆散長度為4的環(huán) 4 3有限幾何LDPC 歐幾里德幾何碼在組合數(shù)學(xué)領(lǐng)域 GF ps 上pms個m維向量a a0 a1 am 構(gòu)成m維線性空間 或矢量空間 定義2 6 稱為m維歐氏幾何 Eudidean Geometry 記為EG m ps 每個m維向量a a0 a1 am 稱為點 point 0向量稱為原點 origin 設(shè)a a0為EG m ps 兩個線性獨立的點 其中a 0 不是原點 則ps個點組成的集合 a a0 GF ps 稱為EG m ps 的一條直線 line 或一維平面 1 flat 記為 a a0 對于每個 GF ps 對應(yīng)于直線 a a0 的一個點 a a0 EG m ps 除a0外共有pms 1個向量 而每條通過a0的直線共有ps個向量 除a0外共有ps 1個 由于兩條直線不能有兩個交點 因此EG m ps 除a0外的pms 1個向量分配到所有相交于a0的直線上 即EG m ps 中相交于a0的直線數(shù)為 pms 1 ps 1 EG m ps 共有p m 1 s pms 1 ps 1 條直線 4 3有限幾何LDPC 點 線 HEG 校驗矩陣的行對應(yīng)歐幾里德集合的線 列對用于歐幾里德集合的點矩陣的元素對應(yīng)歐幾里德集合的點線的關(guān)聯(lián)向量值 行向量是關(guān)聯(lián)向量 HEG共p m 1 s pms 1 ps 1 行 n pms列 由于每條直線只有ps個點 因此行重 ps每一列的總量為 pms 1 ps 1 密度r n ps pms p m 1 s p m 1 s pms 1 ps 1 p m 1 sdmin 1 pms 1 ps 1 1 HEG 1 點在線上 0 其它 提綱 一 歷史和特點二 定義和代數(shù)結(jié)構(gòu)三 Tanner圖 二分圖 四 構(gòu)造五 譯碼5 1大數(shù)邏輯譯碼5 2比特翻轉(zhuǎn)譯碼5 3加權(quán)大數(shù)邏輯或加權(quán)比特翻轉(zhuǎn)譯碼5 4后驗概率譯碼5 5基于置信度傳播的迭代譯碼 和積算法 六 隨機(jī)LDPC碼 5 1大數(shù)邏輯譯碼 Al h1 h7 h12 可用大數(shù)邏輯譯碼對第2位進(jìn)行校驗 h1 h7 h12 由此可見 每一個位都有3個校驗和對其進(jìn)行糾錯 所以可以糾一個錯 對于每個比特位置l H的行向量存在一個 行的子集Al h1 l h2 l h l 在該比特位置正交 即Al每一行的第個分量都為1 而其他位置的分量最多只在某一行出現(xiàn)一般來說 因為每一列都有 個1 相應(yīng)的行向量可作為校驗和 又因為其他列1的個數(shù)最多為1 所以可以構(gòu)成一步大數(shù)邏輯可譯碼 能糾 2 個錯 由于每一列都可找到相應(yīng)校驗和式 不需要循環(huán) 5 2比特翻轉(zhuǎn)譯碼算法 1 伴隨式 c r c e e HcT 0THrT H c e T HcT HeT HeT定義s rHT稱為接收字r的伴隨式 校正子 h1 n 1h1 n 2 h1 0h2 n 1h2 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 eHT 0 ei1 ei2 eit 0 hn 1Thn 2T h1Th0T ei1hi1T ei2hi2T eithitT 發(fā)生錯誤的位所對應(yīng)的列向量的線性組合 五 線性分組碼的譯碼2 例 7 3 碼 H 101 1000111 0100110 0010011 0001 s rHT r6r5r4r3r2r1r0 101 1000111 0100110 0010011 0001 T r6 r4 r3r6 r5 r4 r2r6 r5 r1r5 r4 r0 T s3s2s1s0 五 線性分組碼的譯碼3 c 1010011 e 0100000 r 1110011 s rHT eHT 0100000 101 1000111 0100110 0010011 0001 T 0111 T c 1010011 e 1001000 r 0011011 s rHT eHT 1001000 101 1000111 0100110 0010011 0001 T 1110 T T 1000 0110 5 2比特翻轉(zhuǎn)譯碼算法 假設(shè)v2 v3有錯 則s7 s8 s12 s13都不為0 而其它的sj都為0 因此f2 f3 2 見后 fj 0 j取1 15的其它值 h1 h7 h12 h8 h13 5 2比特翻轉(zhuǎn)譯碼算法 比特翻轉(zhuǎn)譯碼算法計算所有奇偶校驗和 如果所有的奇偶校驗和都和0 則停止譯碼 對于接收序列的每個比特位i 計算包括它的錯誤奇偶校驗方程的個數(shù) 記為fi i 0 1 n 1對于上例 f2 f3 2 fj 0 j 1 4 15選取fi大于某個參數(shù) 的的比特位 組成集合S 將S的比特位翻轉(zhuǎn) 重復(fù)1 4步 直至所有的奇偶校驗和等于0或者達(dá)到最大迭代次數(shù) 設(shè)計參數(shù) 稱為門限 threshold 與 dmin 和信噪比有關(guān) 5 3加權(quán)大數(shù)邏輯或加權(quán)比特翻轉(zhuǎn)譯碼 接收端匹配濾波器輸出的軟判決接收序列y y0 y0 yn 1 對于加性高斯白噪聲 AWGN 信道 接收符號yl的幅度 yl 是其可靠性的一種簡單量度 幅度越大 硬判決數(shù)字zl的可靠度就越高 定義 yj l min min yi 0 i n 1 hj i 1 將在比特位置l正交的校驗和式調(diào)整為加權(quán)檢驗和式 根據(jù)El修改一步大數(shù)邏輯譯碼 l H 1 1 1 Al s1 l s l sj l Sl s1 l s2 l sj l s l 5 4和積算法 sum productalgorithm SPA 是一種基于置信度傳播的迭代譯碼 iterativedecodingalgorithmbasedonbeliefpropagation IDPB 一種逐符號 軟輸入軟輸出 SISO 的譯碼算法 對于每個符號的可靠度的量度可以采用其邊緣后驗概率 對數(shù)似然比或者對應(yīng)接受符號值 每次譯碼迭代得到的碼符號的可靠度量度的計算結(jié)果作為下一次迭代的輸入 譯碼迭代持續(xù)進(jìn)行 直到滿足某個特定的停止條件 然后 基于碼符號的可靠度量度的計算結(jié)果做出硬判決 比特節(jié)點vl在被激活后把qj lx i 見后 作為其置信度傳遞給與它相連的校驗節(jié)點 校驗節(jié)點sj在被激活后 把 j lx i 見后 作為其置信度傳遞給與它相連的比特節(jié)點 令hj hj 0 hj 1 hj n 1 B hj l hj l 1 0 l n 1 稱為hj的支撐集對于軟判決接收序列y 碼比特的對數(shù)似然比 L vl logP vl 1 y P vl 0 y 對于0 l n 1 0 j J和每個hj Al 令qj lx i 為第i次迭代中給定基于Al hj中校驗和的條件下 發(fā)送碼比特vl取值為x的條件概率 在除sj外參與的其它校驗點提供的信息上 vl的狀態(tài)為x的置信度 H 1 1 1 Al h1 h hj 11 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 t B hj l 的條件下 校驗和sj正確 即sj 0 的條件概率 比特節(jié)點vl狀態(tài)為x和與校驗點sj中相連的其它比特節(jié)點狀態(tài)已知的條件下 校驗和為0的概率 1 3 61 i q3 30 i q3 40 i q3 31 i q3 41 i qj lx i 在除sj外參與的其它校驗點提供的信息上 vl的狀態(tài)為x的置信度 j l0 i 比特節(jié)點vl狀態(tài)為x和與校驗點sj中相連的其它比特節(jié)點狀態(tài)已知的條件下 校驗和為0的概率 取其它校驗點 比特節(jié)點 不采用已經(jīng)輸入的信息 避免信息返流 保持信息的獨立性 增強(qiáng)迭代效果 得到的 j lx i 用來更新qj lx i 1 1 41 i 1 4 41 i 1 3 41 i 1 得到的 j lx i 用來更新qj lx i 1 算法 初始化設(shè)定i 0和迭代的最大次數(shù)Imax 對于滿足hj l 1 0 j J 0 l n 1的每對 j l 令qj l0 0 pl0 qj l1 0 pl1 第1步對于0 l n 1 0 j J和每個hj Al 計算概率 j l0 i 和 j l1 i 第2步對于0 l n 1 0 j J和每個hj Al 計算概率qj l0 i 1 qj l1 i 1 P i 1 vl 0 y 和P i 1 vl 1 y 的值 構(gòu)成向量z i 1 并測試z i 1 HT 如果z i 1 HT 0或者i Imax 則轉(zhuǎn)第3步 否則 令i i 1 轉(zhuǎn)第1步 第3步輸出z i 1 作為譯碼的結(jié)果碼字 停止譯碼 提綱 一 歷史和特點二 定義和代數(shù)結(jié)構(gòu)三 Tanner