【正文】 ................. 13 比特翻轉(zhuǎn)算法 ................................................................................................ 13 加權(quán)比特翻轉(zhuǎn)譯碼算法 ................................................................................. 14 5 AWGN 信道下 LDPC 碼的性能仿真 ................................................................ 15 仿真軟件簡介（ MATLABamp。有擾通信信道中的噪聲會不可避免地對傳輸信息產(chǎn)生不同程度的干擾，從而可能降低通信可靠性。一般地，通信系統(tǒng)的可靠性用誤比特率 (BER)來衡量，其 有效性則用信息傳輸速率 R 比特 /信道符號來衡量。 Shannon 信息和編碼理論的奠基性論文“通信的數(shù)學(xué)理論”發(fā)表之后，改變了這一觀點。根據(jù) Shannon 的信息理論，數(shù)字通信系統(tǒng)的基本組成如圖。比特是一種通用的信息表示形式，它本身并不依賴于信源或信道特征。 Shannon不失最佳性地證明了這種分離性 。對于通信系統(tǒng)設(shè)計者來講，了解系統(tǒng)中信道的特性是必需的。實際應(yīng)用中所涉及到的信道大多都是離散輸入的平穩(wěn)無記憶對稱信道，下面給出幾種常用的編碼信道模型。 在過去的幾十年里，移動通信技術(shù)得到了迅猛的發(fā)展和廣泛的應(yīng)用，至今已發(fā)展了三代。第二代移動通信（ 2G）以數(shù)字傳輸?shù)姆?式進(jìn)行語音通話和數(shù)據(jù)業(yè)務(wù)， 2G 系統(tǒng)采用的是數(shù)字的時分多址（ TDMA）或碼分多址（ CDMA）實現(xiàn)動態(tài)尋址功能，以GSM、 CDMA 系統(tǒng)為代表，實現(xiàn)了從模擬到數(shù)字系統(tǒng)的跨越。 而在移動通信更新?lián)Q代中，信道編碼技術(shù)是其中非常重要的一項。 MATLAB 將高性能的數(shù)值計算和可視化集成在一起，并提供了大量的內(nèi)置函數(shù)，從而被廣泛地應(yīng)用于科學(xué)計算、控制系統(tǒng)、信息處理等領(lǐng)域的 分析、仿真和設(shè)計工作，而且利用 MATLAB 產(chǎn)品的開放式結(jié)構(gòu)，可以非常容易地對 MATLAB 的功能進(jìn)行擴(kuò)充。 3 2 LDPC碼 概述 線性分組碼 因為低密度奇偶校驗碼是一種特殊的線性分組碼，所以本章將首先對 線性分組碼做一個概述，為討論 LDPC 碼作鋪墊。 定義 2：如果一個分組碼 C，包含 N 個由 GF(q)中 的元素構(gòu)成的碼字 ( 0C ， 1C ，?， N1C )，則當(dāng)且僅當(dāng) C 構(gòu)成一個 GF(q)上的矢量子空間時，稱 C 為 q 進(jìn)制線性碼。 定義 3：線性碼的維數(shù)等于對應(yīng)的矢量空間的維數(shù)，一個長度為 N，維數(shù)為K 的線性碼總共包括 k2 個長度為 N 的碼字。此性質(zhì)的一個結(jié)論是線性碼必然包含一個全零碼字。這一性質(zhì)表明確定線性碼的最小距離 (決定檢錯和糾錯能力 )要比一般的分組碼要容易的多。 假設(shè) ( 0g ， 1g ， ， K1g 是組成 (N， K)進(jìn)制碼空閉的一組基底，對任意一個碼字 c∈ C，存在唯一的表達(dá)形式 C= 0a 0g + 1a 1g + + K1a K1g （ 21） 因為所有基元的線性組合仍然是一個碼字，所以存在長度為 K 的碼組 ? ?0 1 K1 a a ...a， ， 和 C 中碼字之間的一一映射。 4 低密度奇偶校驗碼 (LDPC碼 ) LDPC 碼定義 LDPC 碼是線性分組碼中較為特殊的一種，但是目前 LDPC 碼并沒有嚴(yán)格的數(shù)學(xué)定義。 LDPC 碼是一個 m 行 n 列的稀疏矩陣 H 的零空間， H 稱為 LDPC 碼的校驗矩陣，并 且滿足： l、矩陣的行重、列重與碼長的比值遠(yuǎn)小于 1； 任意兩行 (列 )最多只有 1 個相同位置上的 1； 任意線性無關(guān)的列數(shù)盡量的大。 一個規(guī)則 LDPC 碼是指校驗矩陣 H 滿足列重和行重分別等于常數(shù) vd ，和 c d ，因為我們并沒有要求校驗 H 是滿秩矩陣，所以其碼率為： r? 1mn =1 vcdd (22) ()式是一個 n=10， vd =2， cd =4 ， r= 規(guī)則 LDPC 碼的校驗矩陣 。不規(guī)則 LDPC 碼可以用重量分布多項式來方便的描述。類似的， H 的行重分布多項式 ? (x)可以表示為： 5 ? (x)= maxcd i1ii2x? ??? （ 25） i? 是重量為 i 的行所占的比例， ? (x)也滿足 ? (1)=1。 我們得由上面的敘述我們知道， LDPC 碼是由其校驗矩陣 H 定義的。也就是說如果對于線性分組碼的校驗矩陣做行變換，得到的矩陣也是這個碼的校驗矩陣。對于 LDPC 碼的生成矩陣，并沒有其他特殊的限制。圖中的變量節(jié)點ic (i=0， l，．．．， n1)與校驗矩陣的列 (也即碼字中的每一位 )一一對應(yīng)，校驗節(jié)點j(j=0， 1，．．．， m1)與校驗矩陣的行 (也即各個校驗方程 )一一對應(yīng)。這樣，該因子圖是一個偶圖，其鄰接矩陣就是該校驗矩陣。由于 LDPC碼定義中的第 2 條的限制，因子圖中不會存在長度等于 4 的圈 (對任意一個偶圖，圈的最小長度為 4)。非規(guī)則碼的編譯碼方法與規(guī) 則碼相似，而其性能卻優(yōu)于規(guī)則碼，這是因為非規(guī)則碼的“波浪效應(yīng)”，在 LDPC 碼的隨機(jī)雙向圖中，對信息節(jié)點來說，其度數(shù)越高，它從校驗節(jié)點所獲得的信息也就越多，也就能更準(zhǔn)確的判斷其校驗值；反之，從校驗節(jié)點的角度來看，希望度數(shù)低，其度數(shù)越低，那么傳播到相鄰節(jié)點的有用信息也就越多。而所謂的“波浪效應(yīng)”也就是度數(shù)大的信息節(jié)點首先獲得正確值，然后度數(shù)小的信息節(jié)點也可以獲得正確值。在非規(guī)則碼中，度的變化 范圍很大，往往最大度可達(dá)幾十或上百，因此，我們更廣泛地把度的變化很微小的 LDPC 碼都稱之為規(guī)則的。在非規(guī)則碼中，度的變化范圍很大，往往最大度可達(dá)幾十或上百，因此，我們更廣泛地把度的變化很微小的 LDPC 碼都稱之為規(guī)則的。根據(jù)分組碼定義，對于 輸入信源 u， u nmF? ，編碼后得到 的碼字 c， c nF? ，滿足方程： H Tc = 0 為了在接受端易于區(qū)分信息位和校驗位，通常采用系統(tǒng)碼。 3. 2 基于校驗矩陣的編碼算法 (LU 分解法 ) 利用矩陣 B 的系數(shù)特性，對校驗位 p = B1Au 的求解采用以下方法：首先對 B 矩陣進(jìn)行 LU 分解，即 B = LU，其中 L 為下三角矩陣， U 為上三角矩陣，則校驗位滿足 LUp = Au，然后通過以下步驟計算校驗位： 1． z = Au，由于 A 是稀疏矩陣，所以計算復(fù)雜度正比于 m。 3．通過后向遞歸運算，解方程 Up = y 得到校驗位 p。但在實際情況 中，校驗矩陣往往不能化為下三角矩陣。 RU 算法僅僅通過行列置換將一般的低密度奇偶校驗矩陣化為一個近似下三角矩陣，可以使編碼復(fù)雜度從高斯消元法的 o(m2)降為 o(n+92)，其中 g 為近似下三角矩陣與下三角矩陣的差距，并且在最惡劣的情況下，它也只是與碼長行的一小部分成比例。由于原矩陣 J5r 非常稀疏，而且在矩陣變換中只有行列交換，因此變換后的校 驗矩陣仍是稀疏矩陣， A、 B、 C、 D、 E、 T 分別是 （ mg） ?（ nm）、（ mg） ? g、 g ?（ nm）、 g ? g、 g ?（ mg）、（ mg） ?（ mg） 維稀疏矩陣。 H= A B TC D E?????? (32) 長度為 k=nm的信源向量 s 被編碼成一個碼字向量 x=（ s， 1p ， 2p ）， 1 p 、 2p分別定義一個校驗向量， 1p 長為 g， 2p 長為 mg。 計算向量 A2S, O, P????的下校正子 TAB2z =Cs Ep? （ 35） 現(xiàn)在準(zhǔn)備求第一個檢驗向量 1p 。 9 設(shè)第一個校驗向量 1p 為 T 11Bp F z? (36) 這個操作的復(fù)雜度為 o( 2g )。 拋棄臨時檢驗向量西并找出新的上校正子 c A 1z z Bp?? (37) 這也可以在線性時間內(nèi)完成。 計算 T1P , T2P 的復(fù)雜度如表 3,1 和表 所示 。于是最終列的排序為： 1， 2， 3， 4， 10， 6， 7， 5， 11， 12， 8， 9。上述有效編碼方法，利用了校驗矩陣的稀疏性，適用于任何基于稀疏校驗矩陣的編碼。 MP算法集 信息傳遞 (Message Propagation， MP)算法是最主要的一類 LDPC 碼譯碼算法，它具有嚴(yán)格的數(shù)學(xué)結(jié)構(gòu)和良好的性能，使用它能對譯碼性能做定量分析。 信息傳遞算法的主要思想就是通過在變量節(jié)點和校驗節(jié)點之間來回傳遞概率似然值，最終找到正確的碼字。變量節(jié)點接收 12 與它相連接的校驗節(jié)點送來的節(jié)點信息，然后根據(jù)這些信息計算出反饋給各校驗節(jié)點的信息。每次迭代結(jié)束后，對每個變量節(jié)點做判決，得出一個碼字，再通過校驗矩陣驗證碼字正確性。 信息傳遞算法為了保證傳遞信息的獨立性，每個節(jié)點接收的信息都是從除自身之外的其他節(jié)點而來。以一個行重為 cd ，列重為 vd的正則 LDPC 碼為例，當(dāng)前迭代周期中某一變量節(jié)點送來的信息直接來自 vd1? 。因此，在 LDPC 碼譯碼過程中環(huán)對譯碼的影響是不容忽視的。根據(jù)信息迭代過程中傳送消息的不同形式，可以將 LDPC 的譯碼方法分為硬 判決譯碼和軟判決譯碼。但是與軟判決譯碼相比，硬判決譯碼在性能上要損失約 23dB；如果在譯碼過程中傳送的信息是與后驗概率相關(guān)的信息，稱之為軟判決譯碼，如置信傳播譯碼算法。在 AWGN 信道中，它比硬判決譯碼要多 2dB 左右的軟判決增益，而在衰落信道中，軟判決增益超過 5dB。主要的硬判決譯碼算法有比特翻轉(zhuǎn)算法 (BF)、加權(quán)的比特翻轉(zhuǎn)算法 (WBF)等；軟譯碼算法主要有置信傳播算法(BeliefPropagation)、簡化的最小和算法 (Minsum)、歸一化最小和算法 (Normalized Min． Sum)、偏移量最小和算法 (OffsetMin． sum)等。 比特翻轉(zhuǎn)算法 (Bit Flipping Algorithm)可看成是置信傳播算法的簡化形式，而加權(quán)位翻轉(zhuǎn)譯碼算法是在 BF 算法的基礎(chǔ)上加上硬判決譯碼系數(shù)，其性能較比特翻轉(zhuǎn)譯碼算法有一定程度的提高 比特翻轉(zhuǎn)算法 (Bit Flipping Algorithm)是 Gallager在其論文中提出的被命名為 Gallager 硬判決的譯碼算法。再重復(fù)上述的過程，直到譯碼成功后達(dá)到最大迭代次數(shù)。 由于校驗矩陣為稀疏矩陣，而且一般為隨機(jī)構(gòu)成，所以參與每個校驗方程的比特很少，且這些比特在碼字上分布很分散，那么任一校驗方程所含的 比特要么 無錯，要么以很高概率的只有一個比特錯誤， BF 算法就可以有效地進(jìn)行糾錯。但是相對的犧牲的就是譯碼性能，所以下面對于硬判決譯碼算法提出了一種加權(quán)硬判決譯碼算法，它是在 BF 算法基礎(chǔ)上進(jìn)行了一定的改進(jìn)，在性能上有了一定的提高。那么，加權(quán)比特翻轉(zhuǎn)譯碼 (WBF)算法就是在選擇需要翻轉(zhuǎn)的變量節(jié)點的時候，將每一個碼字中不滿足校驗方程個數(shù)最多的碼元的信道輸出信息作為該判決 式的權(quán)重信息。? ?mnH= H ? 為校驗矩陣， ? ? ? ?mnN m n H 1???： 表示與校驗節(jié)點 m 相連的變量節(jié)點， ? ? ? ?mnm n m H 1???： 表示與變量節(jié)點刀相連的校驗節(jié)點。 加權(quán)譯碼算法是通過軟判決譯碼算法和附加信息來計算加權(quán)校驗信息 E，這 種算法雖然比單純的 BF 算法在復(fù)雜度上有了增加，但是卻具有更好的譯碼性能。simulink） MATLAB 軟件 MATLAB 在數(shù)學(xué)類科技應(yīng)用軟件中在 數(shù)值計算 方面首屈一指。 MATLAB 的基本數(shù)據(jù)單位是矩陣，它的指令表達(dá)式與數(shù)學(xué)、工程中常用的形式十分相似，故用 MATLAB 來解算問題要比用 C， FORTRAN 等語言完成相同的事情簡捷得多，并且 mathwork 也吸收了像Maple 等軟件的優(yōu)點 ,使 MATLAB 成為一個強(qiáng)大的數(shù)學(xué)軟件 。工具包又可以分為功能性工具包和學(xué)科工具包。學(xué)科工具包是專業(yè)性比較 強(qiáng)的工具包，控制工具包，信號處理工具包，通信工具包等都屬于此類。除內(nèi)部函數(shù)外，所有 MATLAB 主包文件和各種工具包都是可讀可修改的文件，用戶通過對源程序的修改或加入自己編寫程序構(gòu)造新的專用工具包。 Simulink 仿真 軟件 近年來，由于問題域的擴(kuò)展和仿真支持技術(shù)的發(fā)展，系統(tǒng)仿真方法學(xué)致力與更自然地抽象事物的屬性特征，尋求使模型研究者更自然地參與仿真活動的方法。一般在仿真中要獲得較低的誤比特率需要大量的數(shù)據(jù)幀，而在碼長較長時大量的數(shù)據(jù)幀的計算要花費很多時間，因此只選定了一些碼長相 16 對較短的