【正文】 輸出為 0)的概率與 輸入無關(guān)： 二進制刪除信道 (BEC)：輸入為二值變量 0、 1，輸出或為輸入的二值變量 0、1，或為刪除 E，且通常傳輸過程中不同輸入被刪除的概率相同； 二進制輸入高斯信道 (BIAWGN)：輸入為二值變量，輸出為連續(xù)變量，且信道中的加性噪聲為服從 N(O，萬 2)的高斯隨機變量。 在過去的幾十年里，移動通信技術(shù)得到了迅猛的發(fā)展和廣泛的應用，至今已發(fā)展了三代。第一代移動通信（ 1G）是以模擬傳輸?shù)姆绞竭M行語音通話，主要是采用以蜂窩結(jié)構(gòu)網(wǎng)為核心的模擬技術(shù)和頻分多址（ FDMA）動態(tài)尋址技術(shù)。第二代移動通信（ 2G）以數(shù)字傳輸?shù)姆?式進行語音通話和數(shù)據(jù)業(yè)務， 2G 系統(tǒng)采用的是數(shù)字的時分多址（ TDMA）或碼分多址（ CDMA）實現(xiàn)動態(tài)尋址功能，以GSM、 CDMA 系統(tǒng)為代表，實現(xiàn)了從模擬到數(shù)字系統(tǒng)的跨越。第三代移動通信（ 3G）是著重實現(xiàn)傳統(tǒng)的移動通信與開放式的因特網(wǎng)融合，各個國家的網(wǎng)絡將融合為一個整體。 而在移動通信更新?lián)Q代中，信道編碼技術(shù)是其中非常重要的一項。本文所論述的 LDPC 碼即是信道編碼的其中之一 。 MATLAB 將高性能的數(shù)值計算和可視化集成在一起，并提供了大量的內(nèi)置函數(shù)，從而被廣泛地應用于科學計算、控制系統(tǒng)、信息處理等領(lǐng)域的 分析、仿真和設計工作，而且利用 MATLAB 產(chǎn)品的開放式結(jié)構(gòu)，可以非常容易地對 MATLAB 的功能進行擴充。 MATLAB 的數(shù)據(jù)分析和處理功能十分強大， 運用它對所涉及到的 LDPC 編譯碼進行仿真。 3 2 LDPC 碼 概述 線性分組碼 因為低密度奇偶校驗碼是一種特殊的線性分組碼，所以本章將首先對 線性分組碼做一個概述，為討論 LDPC 碼作鋪墊。 定義 l：整數(shù) 0， l， 2， ?， q． 1， q 是自然數(shù)，在模 P 加和乘運算下構(gòu)成 一 個伽邏華域 GF(q)。 定義 2：如果一個分組碼 C，包含 N 個由 GF(q)中 的元素構(gòu)成的碼字 ( 0C ， 1C ，?， N1C )，則當且僅當 C 構(gòu)成一個 GF(q)上的矢量子空間時，稱 C 為 q 進制線性碼。在 本 篇論文里，只考慮二進制碼，所以 q=2。 定義 3：線性碼的維數(shù)等于對應的矢量空間的維數(shù)，一個長度為 N，維數(shù)為K 的線性碼總共包括 k2 個長度為 N 的碼字。 線性碼還有如下一些有用的性質(zhì)： 性質(zhì) 1：任意碼字的 線性組合仍然是一個碼字。此性質(zhì)的一個結(jié)論是線性碼必然包含一個全零碼字。 性質(zhì) 2：線性碼的最小距離等于其中一個最輕非零碼字的漢明重量。這一性質(zhì)表明確定線性碼的最小距離 (決定檢錯和糾錯能力 )要比一般的分組碼要容易的多。 性質(zhì) 3：線性碼中不可檢測的錯誤圖案與傳輸?shù)拇a字無關(guān)，且由所有的非零碼字組成。 假設 ( 0g ， 1g ， ， K1g 是組成 (N， K)進制碼空閉的一組基底，對任意一個碼字 c∈ C，存在唯一的表達形式 C= 0a 0g + 1a 1g + + K1a K1g （ 21） 因為所有基元的線性組合仍然是一個碼字，所以存在長度為 K 的碼組 ? ?0 1 K1 a a ...a， ， 和 C 中碼字之間的一一映射。以下矩陣 G 就是由基矢按行排列而成。 4 低密度奇偶校驗碼 (LDPC碼 ) LDPC 碼定義 LDPC 碼是線性分組碼中較為特殊的一種，但是目前 LDPC 碼并沒有嚴格的數(shù)學定義?？紤]到其結(jié)構(gòu)上的特點和敘述上的方便，本文對 LDPC 碼做如下的定義。 LDPC 碼是一個 m 行 n 列的稀疏矩陣 H 的零空間， H 稱為 LDPC 碼的校驗矩陣，并 且滿足： l、矩陣的行重、列重與碼長的比值遠小于 1； 任意兩行 (列 )最多只有 1 個相同位置上的 1； 任意線性無關(guān)的列數(shù)盡量的大。 這樣的 LDPC 碼碼長為 n，校驗位長度大約為 m，信息位長度為 k ? nm。 一個規(guī)則 LDPC 碼是指校驗矩陣 H 滿足列重和行重分別等于常數(shù) vd ，和 c d ，因為我們并沒有要求校驗 H 是滿秩矩陣，所以其碼率為： r? 1mn =1 vcdd (22) ()式是一個 n=10， vd =2， cd =4 ， r= 規(guī)則 LDPC 碼的校驗矩陣 。 1 1 1 1 0 0 0 0 0 01 0 0 0 1 1 1 0 0 0H 0 1 0 0 1 0 0 1 1 00 0 1 0 0 1 0 1 0 10 0 0 1 0 0 1 0 1 1????????? (23) 如果校驗矩陣 H 的列重和行重并不是常數(shù)，我們就稱其為不規(guī)則 LDPC 碼，我們可以認為規(guī)則 LDPC 碼是不規(guī)則 LDPC 碼中的一個特例。不規(guī)則 LDPC 碼可以用重量分布多項式來方便的描述。假設最大列重和最大行重分別是 maxvd 和maxcd ，則 H 的列重分布多項式 ? (x)可以表示為： ? (x)= maxvd i1ii2x? ??? （ 24） 其中， i? 是重量為 i 的列所占的比例，同時 ? (x) (1)=1。類似的， H 的行重分布多項式 ? (x)可以表示為： 5 ? (x)= maxcd i1ii2x? ??? （ 25） i? 是重量為 i 的行所占的比例， ? (x)也滿足 ? (1)=1。此時，碼率 r 滿足 ： r? 1 ? ?? ?1010x dxx dx???? （ 26） 值得注意的是，對于一個給定的碼長 n 和行、列重量分布多項式，我們得到的是一類 LDPC 碼而不是一個特定的 LDPC 碼。 我們得由上面的敘述我們知道， LDPC 碼是由其校驗矩陣 H 定義的。 對于一個線性分組碼，其校驗矩陣并不是唯一的。也就是說如果對于線性分組碼的校驗矩陣做行變換，得到的矩陣也是這個碼的校驗矩陣。但是，對于 LDPC 碼這種特殊的線性分 組碼而言，由于譯碼算法的設計和性能分析的需要，我們僅僅關(guān)心其屬于稀疏矩陣的這個校驗矩陣，因此，定義一個 LDPC 碼必須給出這個稀疏的校驗矩陣才有意義。對于 LDPC 碼的生成矩陣，并沒有其他特殊的限制。 為了分析的方便，我們可以用因子圖來表示一個 LDPC 碼。圖中的變量節(jié)點ic (i=0， l，．．．， n1)與校驗矩陣的列 (也即碼字中的每一位 )一一對應，校驗節(jié)點j(j=0， 1，．．．， m1)與校驗矩陣的行 (也即各個校驗方程 )一一對應。 ic 和 jf ；相連接，當且僅當校驗矩陣中對應位置的元素是 1。這樣，該因子圖是一個偶圖，其鄰接矩陣就是該校驗矩陣。圖 2． 1 是 (2． 7)式中校驗矩陣的因子圖。由于 LDPC碼定義中的第 2 條的限制，因子圖中不會存在長度等于 4 的圈 (對任意一個偶圖，圈的最小長度為 4)。 圖 LDPC 碼的因子圖表示 6 一般而言，不規(guī)則碼的性能要優(yōu)于規(guī)則碼，但是實現(xiàn)的復雜度和分析的復雜度都要大得多。非規(guī)則碼的編譯碼方法與規(guī) 則碼相似，而其性能卻優(yōu)于規(guī)則碼，這是因為非規(guī)則碼的“波浪效應”，在 LDPC 碼的隨機雙向圖中，對信息節(jié)點來說，其度數(shù)越高，它從校驗節(jié)點所獲得的信息也就越多，也就能更準確的判斷其校驗值；反之，從校驗節(jié)點的角度來看，希望度數(shù)低，其度數(shù)越低，那么傳播到相鄰節(jié)點的有用信息也就越多。而非規(guī)則碼的隨機雙向圖就很好的平衡了信息節(jié)點與校驗節(jié)點二者對度數(shù)的要求。而所謂的“波浪效應”也就是度數(shù)大的信息節(jié)點首先獲得正確值，然后度數(shù)小的信息節(jié)點也可以獲得正確值。非規(guī)則碼的產(chǎn)生，使規(guī)則 LDPC 碼的定義產(chǎn)生了變化。在非規(guī)則碼中，度的變化 范圍很大，往往最大度可達幾十或上百，因此，我們更廣泛地把度的變化很微小的 LDPC 碼都稱之為規(guī)則的。 非規(guī)則碼的產(chǎn)生，使規(guī)則 LDPC 碼的定義產(chǎn)生了變化。在非規(guī)則碼中，度的變化范圍很大，往往最大度可達幾十或上百，因此，我們更廣泛地把度的變化很微小的 LDPC 碼都稱之為規(guī)則的。 3 LDPC 碼的編碼算法 基于生成矩陣的編碼算法 (線性分組碼編碼 ) 設 m n 的較驗矩陣 H 的所有行都是線性無關(guān)的。根據(jù)分組碼定義，對于 輸入信源 u， u nmF? ，編碼后得到 的碼字 c， c nF? ，滿足方程： H Tc = 0 為了在接受端易于區(qū)分信息位和校驗位，通常采用系統(tǒng)碼。但是，對于任意一個隨機構(gòu)造的校驗矩陣 H,它具有非系統(tǒng)碼的形式，因此首先需要對給定的校驗矩陣 H 進行行列變換，分解成 AB????的形式，其中 A 為 m ? (n m)維的矩陣， B 為 m? m的滿秩矩陣，則碼字 c= up????滿足 uA B =0p?????????? 即 Au + Bp = 0 因此，得到校驗位 p = 1B Au 7 其中“ ”表示向量 1B Au 的逆元，在二進制編碼中逆元是其本身。 3. 2 基于校驗矩陣的編碼算法 (LU 分解法 ) 利用矩陣 B 的系數(shù)特性，對校驗位 p = B1Au 的求解采用以下方法：首先對 B 矩陣進行 LU 分解，即 B = LU，其中 L 為下三角矩陣， U 為上三角矩陣，則校驗位滿足 LUp = Au，然后通過以下步驟計算校驗位： 1． z = Au，由于 A 是稀疏矩陣，所以計算復雜度正比于 m。 2．令 Up = y，則 Ly = z，通過前向遞歸運算得到 y 的值。 3．通過后向遞歸運算，解方程 Up = y 得到校驗位 p。 基于 校驗矩陣的 編碼 算法 (RU算 法 ) 在對 LDPC 碼進行編碼的時候，人們希望校驗矩陣是下三角矩陣，如圖 3． 1所表 示。但在實際情況 中，校驗矩陣往往不能化為下三角矩陣。 Richardson 和Urbankc 在提出了一種很好的編碼算法，即 RU 算法。 RU 算法僅僅通過行列置換將一般的低密度奇偶校驗矩陣化為一個近似下三角矩陣，可以使編碼復雜度從高斯消元法的 o(m2)降為 o(n+92)，其中 g 為近似下三角矩陣與下三角矩陣的差距，并且在最惡劣的情況下，它也只是與碼長行的一小部分成比例。 8 首先， 通過行變換與列變換的方法將奇偶檢驗矩陣重新排列為近似下三角形式，如圖 所示。由于原矩陣 J5r 非常稀疏，而且在矩陣變換中只有行列交換，因此變換后的校 驗矩陣仍是稀疏矩陣， A、 B、 C、 D、 E、 T 分別是 （ mg） ?（ nm）、（ mg） ? g、 g ?（ nm）、 g ? g、 g ?（ mg）、（ mg） ?（ mg） 維稀疏矩陣。并且 T 是下三角矩陣矩陣且對角線上 的元素全部為 l。 H= A B TC D E?????? (32) 長度為 k=nm的信源向量 s 被編碼成一個碼字向量 x=（ s， 1p ， 2p ）， 1 p 、 2p分別定義一個校驗向量， 1p 長為 g， 2p 長為 mg。編碼步驟如下： 計算信源向量的上校正子 Az =A Ts （ 33） 找出第二個校驗向量的臨時值 A2P ，使得上校正子為零 A2P = 1ATZ (34) 通過回代算法可以在線性時間內(nèi)得出這個向量，即計算 A2P 的第一個比特，然后是第二個比特，然后是第三個，如此等等。 計算向量 A2S, O, P????的下校正子 TAB2z =Cs Ep? （ 35） 現(xiàn)在準備求第一個檢驗向量 1p 。 定義矩陣 F=E 1T B+D 并求出它的逆矩陣 1F ，這個計算只需要完成一次 而它的復雜度 O( 2g )，這個逆矩陣是一個 gxg 維高密度矩陣。 9 設第一個校驗向量 1p 為 T 11Bp F z? (36) 這個操作的復雜度為 o( 2g )。注意這時找第一個校驗向量 1P 的正確值。 拋棄臨時檢驗向量西并找出新的上校正子 c A 1z z Bp?? (37)