資源描述：
《LDPC碼及其譯碼實現(xiàn).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、LDPC碼及其譯碼實現(xiàn)一、LDPC碼簡介LDPC碼最早在20世紀(jì)60年代由Gallager在他的博士論文中提出，但限于當(dāng)時的技術(shù)條件，缺乏可行的譯碼算法，此后的35年間基本上被人們忽略，其間由Tanner在1981年推廣了LDPC碼并給出了LDPC碼的圖表示，即后來所稱的Tanner圖。1995年前后MacKay和Neal等人對LDPC碼重新進行了研究，提出了可行的譯碼算法，從而進一步發(fā)現(xiàn)了LDPC碼所具有的良好性能，迅速引起強烈反響和極大關(guān)注。LDPC碼（低密度奇偶校驗碼）本質(zhì)上是一種線形分組碼，它通過一個生成矩陣G將信息序列映射成發(fā)送序列，
2、也就是碼字序列。對于生成矩陣G，完全等效地存在一個奇偶校驗矩陣H，所有的碼字序列C構(gòu)成了H的零空間?(nullspace)，即HCT=0。LDPC碼的奇偶校驗矩陣H是一個稀疏矩陣，相對于行與列的長度，校驗矩陣每行、列中非零元素的數(shù)目(我們習(xí)慣稱作行重、列重)非常小，這也是LDPC碼之所以稱為低密度碼的原因。由于校驗矩陣H的稀疏性以及構(gòu)造時所使用的不同規(guī)則，使得不同LDPC碼的編碼二分圖(Taner圖)具有不同的閉合環(huán)路分布。而二分圖中閉合環(huán)路是影響LDPC碼性能的重要因素，它使得LDPC碼在類似可信度傳播(BeliefProPagation)算
3、法的一類迭代譯碼算法下，表現(xiàn)出完全不同的譯碼性能。當(dāng)H的行重和列重保持不變或盡可能的保持均勻時，我們稱這樣的LDPC碼為正則LDPC碼，反之如果列、行重變化差異較大時，稱為非正則的LDPC碼。根據(jù)校驗矩陣H中的元素是屬于GF(2)還是GF(q)(q=2p)，我們還可以將LDPC碼分為二元域或多元域的LDPC碼。二、LDPC譯碼算法2.1、Gallager概率譯碼算法Gallager當(dāng)初為了介紹LDPC碼，同時還提出了一種迭代的概率譯碼算法，Gallager概率譯碼算法，后來在此基礎(chǔ)上又發(fā)展出了置信度傳播譯碼算法（BPA，也稱SPA或者MPA）。
4、假設(shè)一個二進制序列是一個LDPC碼字，那么這n個比特就要滿足由該碼字的校驗矩陣所確定的一系列的校驗方程。并且，包含某一比特的校驗方程可能不止一個，這些校驗方程中的其他比特又可能包含在其他更多的校驗方程中。為了直觀的表示這種關(guān)系，Gallager引入了校驗集合樹的概念。圖2.1所示為某一比特的校驗集合樹。圖2.1校驗集合樹根節(jié)點表示比特d，和d相連的每一條邊表示包含d的一個校驗方程，在圖2.1中，d包含在3個校驗方程中；第一層中的每一線段上的節(jié)點表示這一校驗方程中除d以外的其他比特，因此包含d的3個校驗方程分別是：校驗方程中的加法是模2加。即為比
5、特d的數(shù)值，即為比特（1,1）的數(shù)值。與第一層各節(jié)點相連接的每條邊同樣表示包含該比特的一個校驗方程，第二層中的每一線段上的節(jié)點同樣表示該校驗方程中除第一層比特以外的其他比特。以比特（2,2）為例，和比特（2,2）相連接的邊有3條，其中一條與本層節(jié)點（2,1），（2,3），及根節(jié)點d相連，另外兩條與第二層中節(jié)點u,v,w和x,y,z相連。因此包含比特（2,2）的3個校驗方程分別為：第三層（圖中未畫出）及以后的各層依此類推，每個比特都有相應(yīng)的以該比特為根節(jié)點的校驗集合樹。假設(shè)信道是無記憶信道，僅與及信道噪聲有關(guān)，考慮根節(jié)點和第一層節(jié)點組成的集合，這
6、些比特組成了包含比特的個校驗方程，每個校驗方程由個比特組成（包含比特），顯然發(fā)送的這些比特滿足這個校驗方程。因此假設(shè)當(dāng)發(fā)送的碼字是時，那么在以上情況下接收到的符號即為。這樣在傳送碼字時，碼字中的各比特滿足包含比特的個校驗方程。當(dāng)接收到相應(yīng)的符號序列時，比特為1的條件概率可以表示為。同理，比特為0的條件概率表示為。又令當(dāng)不考慮發(fā)送比特間的相關(guān)性時，為1的概率表示為，它與信道模型有關(guān)。令，表示的校驗集合樹第一層中包含的第個校驗方程的第個比特為1的概率，那么有：根據(jù)式2.1，只要知道了圖2.1的第一層中各比特為1的概率，就可以算出比特的條件概率。在其
7、他根節(jié)點的校驗樹里比特又作為一個節(jié)點參與到根節(jié)點的概率計算中去，即比特從與其有關(guān)的節(jié)點中獲取信息計算出概率，再將其計算出的概率信息傳出用于計算其他的節(jié)點，由于在計算其他節(jié)點時同樣會用到計算比特時所用過的運算，所以可以通過共享計算的中間結(jié)果而使計算量大為降低，進而發(fā)展出了BPA（也稱SPA或MPA）。2.2BP算法（也稱SP或MP算法）校驗集合樹雖然比較直觀，但對于每一個節(jié)點都有不同的校驗集合樹，因此在描述并行計算整個碼字各比特的后驗概率時，使用校驗集合樹并不方便，因此介紹一種新的圖形表示法，Tanner圖。對應(yīng)于圖2.1的Tanner圖如圖2.
8、2所示。該圖僅畫出部分變量節(jié)點和校驗節(jié)點。Tanner圖中變量節(jié)點對應(yīng)于校驗集合樹中的節(jié)點，校驗節(jié)點對應(yīng)于校驗集合樹中的邊。圖2.2對應(yīng)于圖2.1校驗
