低密度奇偶校驗(yàn)碼編碼研究

《低密度奇偶校驗(yàn)碼編碼研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、低密度奇偶校驗(yàn)碼的編碼研究StudyonEncodingofLDPCcodes報(bào)告人：何善寶東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室2004年9月東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第1頁內(nèi)容提綱?第一部分：LDPC碼的發(fā)展歷史?第二部分：LDPC碼的編碼介紹?第三部分：隨機(jī)化的構(gòu)造方法?第四部分：系統(tǒng)化的構(gòu)造方法?第五部分：稀疏序列構(gòu)造方法?第六部分：總結(jié)與展望東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第2頁一、LDPC碼的發(fā)展歷史?1962年前后Gallager首先提出LDPC碼[1,2]，并給出LDPC碼的簡單構(gòu)造和硬判決概率譯碼；?1981年Tan

2、ner建立了編碼的圖模型概念[6]，證明了和積算法在無環(huán)圖中譯碼的最佳性并提出了構(gòu)造適合和積譯碼的圖模型的代數(shù)方法；?1996年前后MacKay和Neal[12][3]，Spiser和Spielman[10]，Wiberg[11]重新發(fā)現(xiàn)了LDPC碼的良好性能；?1998年Davey和MacKay提出了基于GF(q)的LDPC碼[4]；?1998年Luby等人提出了基于非正則圖的LDPC碼[5];?2001年專輯“基于圖的碼和迭代解碼”,IEEETrans.onInform.Theory,vol.47,Feb.2001;?200

3、4年文集“LDPC碼構(gòu)造等”，IEEETrans.onInform.Theory,vol.50,June2004.東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第3頁二、LDPC碼的編碼介紹?LDPC碼基礎(chǔ)簡介?校驗(yàn)矩陣完全隨機(jī)的編碼方法?校驗(yàn)矩陣具有循環(huán)和準(zhǔn)循環(huán)結(jié)構(gòu)的編碼方法東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第4頁LDPC碼基礎(chǔ)簡介?LDPC碼就是一種普通的線性分組碼，可以用生成矩陣和校驗(yàn)矩陣來表征；?LDPC碼又是一種特殊的分組碼，特殊性就在于它的奇偶校驗(yàn)矩陣中‘1’的數(shù)目遠(yuǎn)小于‘0’的數(shù)目，稱為稀疏性，“低密度”也來源于此；?LDPC碼又稱為

4、稀疏圖碼，它可以用一個二分圖來表征，在圖論中一個圖是由頂點(diǎn)和邊組成的，二分圖：圖中所有的頂點(diǎn)分為兩個子集，任何一個子集內(nèi)部各個頂點(diǎn)之間沒有邊相連，任意一個頂點(diǎn)都和一個不在同一個子集里的頂點(diǎn)相連；?LDPC碼的二分圖又稱為Tanner圖，這是由Tanner在1982年首次用它來表示低密度碼的，一個Tanner圖和一個校驗(yàn)矩陣完全對應(yīng)；東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第5頁?線性分組碼(6,3,3)為例的校驗(yàn)方程和其二分圖?x1?x2?x3?0?x1x2x3x4x5x6?x3?x4?x5?0?x?x?x?0?561?x?x?x?0?2

5、46東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第6頁v1v2v3v4v5v6cccc1234?這也是一個簡單的(6,3,3)碼字的二分圖，上面是變量節(jié)點(diǎn)，下面為校驗(yàn)節(jié)點(diǎn)；?圈：由變量節(jié)點(diǎn)、校驗(yàn)節(jié)點(diǎn)和邊首尾相連組成的閉合環(huán)路，即文獻(xiàn)中的cycle；?Girth的定義：碼字二分圖或Tanner圖中最短圈的圈長；?圖中粗線構(gòu)成了一個長度為6的圈，如果沒有長度為4的圈，那么這個圖的最小圈長，即girth，就是6；?給出一個碼的校驗(yàn)矩陣后，可以用文獻(xiàn)[19]中MaoYongyi提的搜索方法得到該LDPC碼的girth及其分布。東南大學(xué)移動通信國家重點(diǎn)

6、實(shí)驗(yàn)室第7頁?為什么提到LDPC碼的girth？答：因?yàn)槟壳癓DPC碼的最好的解碼方法是Sum-Product算法或者BeliefPropagation(BP)算法，這種算法是一種漸進(jìn)最大似然的算法，如果Tanner圖中不存在圈，也就是girth是無窮大，則這種算法等效于最大似然算法；當(dāng)然，在碼長固定的情況下，對于適用的碼字來說無圈是不可能的；但是通過增大最小圈的圈長，也就是增大girth，可以提高碼字的性能，girth達(dá)到一定的值就可以接近無圈時的性能。顯然決定碼字性能的是碼間距，但是我們無法去直接約束控制碼間距；控制Tann

7、er圖的girth雖然也有很大的難度，但卻是可以通過一些方法消除長度較短的圈；一般來說，girth大的碼字其碼間距也大，但是碼間距大的其girth不一定就很大。因此，girth是目前設(shè)計(jì)LDPC碼最常用到的關(guān)鍵詞之一。東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第8頁校驗(yàn)矩陣完全隨機(jī)的LDPC碼編碼方法LDPC碼所面臨的一個主要問題是其較高的編碼復(fù)雜度和編碼時延。對其采用普通的編碼方法，LDPC碼具有二次方的編碼復(fù)雜度，在碼長較長時這是難以接受的，幸運(yùn)的是校驗(yàn)矩陣稀疏性使得LDPC碼的編碼成為可能。T.J.Richardson和R.L.Urb

8、anke在文獻(xiàn)[7]中給出了利用校驗(yàn)矩陣的稀疏性對校驗(yàn)矩陣進(jìn)行一定的預(yù)處理后，在線性時間內(nèi)編碼的有效算法，初步解決了LDPC碼的應(yīng)用所面臨的一個主要問題。東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室第9頁基于高斯消去的直接編碼LDPC碼的直接編碼方法就是利用高斯消去法，產(chǎn)生一