【文章內容簡介】 TC s E? 1 T（ T As ） O（ n） 稀疏矩陣和向量相乘 向量的減法運算 1TC s EF ? ?????? 1 T（ T A s ） O（ n） 矩陣的求逆運 算 高密度矩陣和向量相乘 表 3． 2 計算 2Tp 的復雜度 操 作 復 雜 度 備 注 A Ts O（ n） 稀疏矩陣和向量相乘 1TBP O（ n） 稀疏矩陣和向量相乘 A Ts + 1TBP O（ n） 稀疏矩陣和向量相乘 向量的加法運算 1T? (A Ts + 1TBP ) O（ n） 稀疏矩陣和向量相乘 10 例 一個 (12,3,6)LDPC 碼的校驗矩陣如下： 將列重新按下序排列： 1， 2， 3， 4， 5， 6， 7， 10， 11， 12， 8， 9 得到一個g =2 的近似下三角矩陣為 用高斯消元法消去矩陣 E ，得到 可以看到 1 11U E T B + D = 11???? ???? 矩陣 U 是奇異矩陣 ，這種奇異性可以通過交換列 5， 8 來消除。于是最終列的排序為： 1， 2， 3， 4， 10， 6， 7， 5， 11， 12， 8， 9。對應的等價矩陣為 11 假設待編碼的信息比特為 s = (1 0 0 0 0 0)，按照上述步驟計算： ? ?TTA s 1 1 0 1? ? ?T1 TT A s 1 1 0 0?? ??? ? ?T1 TT A s 0 0????? ? ?TTCs 0 0? ? ? T 1 T T E T A s C s 0 1? ? ? ???? ? ? ? ? ? T 1 1 T T T1U E T A s + C s 0 1 = P?? ??? 根據(jù)得到的 1p 計算 2p ? ?TT1B p = 0 1 0 0 ? ?TTT 1A s B p 1 0 0 1? ? ? ???? ? ? ? ? ? T1 T T T12T A s B p 1 0 1 0 = p? ?????? 因此編碼得到的碼字為 ? ? ? ?12s p p 1 0 0 0 0 0 0 1 1 0 1 0? 將上述碼字代入式（ ）進行檢驗，得到 HcT = 0，因此滿足校驗方程。上述有效編碼方法，利用了校驗矩陣的稀疏性，適用于任何基于稀疏校驗矩陣的編碼。 4 LDPC碼的譯碼 概述 LDPC碼具有良好性能的重要原因之一是 LDPC碼采用了基于置信傳播的迭 代譯碼算法，這是一種迭代概率譯碼算法，是 LDPC 碼與傳統(tǒng)糾錯碼的重要區(qū)別。 MP算法集 信息傳遞 (Message Propagation， MP)算法是最主要的一類 LDPC 碼譯碼算法，它具有嚴格的數(shù)學結構和良好的性能，使用它能對譯碼性能做定量分析。LDPC 碼譯碼算法中很多種都可以被歸結到信息傳遞 算法集中。 信息傳遞算法的主要思想就是通過在變量節(jié)點和校驗節(jié)點之間來回傳遞概率似然值，最終找到正確的碼字。這一過程在 Tanner 圖上可以直觀的表示出來，信息在 Tanner 圖中沿著連接變量節(jié)點和校驗節(jié)點的邊雙向傳遞。變量節(jié)點接收 12 與它相連接的校驗節(jié)點送來的節(jié)點信息，然后根據(jù)這些信息計算出反饋給各校驗節(jié)點的信息。校驗節(jié)點開始接收與它相連接的變量節(jié)點送來的節(jié)點信息，然后根據(jù)這些信息計算出反饋給各變量節(jié)點的信息，如此往復形成迭代。每次迭代結束后，對每個變量節(jié)點做判決，得出一個碼字，再通過校驗矩陣驗證碼字正確性。如果譯 碼成功，則譯碼結束；否則繼續(xù)迭代，直到達到預先設定的最大迭代次數(shù)。 信息傳遞算法為了保證傳遞信息的獨立性，每個節(jié)點接收的信息都是從除自身之外的其他節(jié)點而來。但是由于現(xiàn)實中所使用的碼長都是有限的，使得節(jié)點不可能永遠收到與自身無關的信息，即存在環(huán)的影響。以一個行重為 cd ，列重為 vd的正則 LDPC 碼為例，當前迭代周期中某一變量節(jié)點送來的信息直接來自 vd1? 。個校驗節(jié)點， 而這些校驗節(jié)點所送來的信息又來自與各自相連的以 cd 一 1個變量節(jié)點在上一迭代周期中送出的值，如下圖所示的樹狀圖表示它們之間的關系。因此，在 LDPC 碼譯碼過程中環(huán)對譯碼的影響是不容忽視的。 圖 節(jié)點樹 LDPC 碼有很多種譯碼方法，本質上大都是基于 Tanner 圖的信息傳遞譯碼算 法。根據(jù)信息迭代過程中傳送消息的不同形式，可以將 LDPC 的譯碼方法分為硬 判決譯碼和軟判決譯碼。如果在譯碼過程中傳送的信息是比特值，稱之 為硬判決 譯碼，如 BF 算法，它具有較低的譯碼復雜度，易于工程實現(xiàn)。但是與軟判決譯碼相比，硬判決譯碼在性能上要損失約 23dB；如果在譯碼過程中傳送的信息是與后驗概率相關的信息，稱之為軟判決譯碼，如置信傳播譯碼算法。雖然軟判決算法譯碼復雜度較高，但可以獲得更好的譯碼準確性，比硬判決譯碼具有更大的編碼增益。在 AWGN 信道中，它比硬判決譯碼要多 2dB 左右的軟判決增益，而在衰落信道中，軟判決增益超過 5dB。硬判決譯碼可以看成是 l 比特量化譯碼， 13 而軟判決譯碼可以看成無窮多比特量化譯碼。主要的硬判決譯碼算法有比特翻轉算法 (BF)、加權的比特翻轉算法 (WBF)等；軟譯碼算法主要有置信傳播算法(BeliefPropagation)、簡化的最小和算法 (Minsum)、歸一化最小和算法 (Normalized Min． Sum)、偏移量最小和算法 (OffsetMin． sum)等。 硬判決譯碼算法 比特翻轉算法 Gallager 在其論文中提出了硬判決譯碼算法，該算法是一種比較簡單而且容易理解的譯碼算法，它對運算量和存儲量的要求都很低，但是其性能相對比較差。 比特翻轉算法 (Bit Flipping Algorithm)可看成是置信傳播算法的簡化形式，而加權位翻轉譯碼算法是在 BF 算法的基礎上加上硬判決譯碼系數(shù)，其性能較比特翻轉譯碼算法有一定程度的提高 比特翻轉算法 (Bit Flipping Algorithm)是 Gallager在其論文中提出的被命名為 Gallager 硬判決的譯碼算法。設碼字 c=? ?0 1 N1c c ... c， ， ， 為發(fā)送序列，經(jīng) BPSK 調制為序 列 x=? ?0 1 N1c c ... c， ， ， ， ? ?iix 2c 1??， 0 i N1?? ， ? ?0 1 N1r r r ... r? ， ， ， 為接收的實數(shù)向量序列，由實數(shù)序列可以得到硬判決二元向量序列z=( 0 1 N 1z z z， ， ... ， )： iii1 r 0z 0 r 0??? ? ??， 當 時， 當 時 （ 41） 由此得到碼字伴隨式 s=（ 0 1 2 J 1s s s s， ， ， ... ，） = TzH? ，若 js0? ，則說明接收向量 滿足第 j 個校驗方程；若 s=0，則表示接收向量滿足所有校驗方程，接收碼字 z 正 確，譯碼成功；若伴隨式為非全“ 0”向量時，接收序列 z 有錯誤，此時則需計算出每個碼元不滿足校驗方程的個數(shù) f=? ?0 1 N1f f f， ， ... ， =sH，搜索 f中的最大值，翻轉對應位置的碼元 jz 。再重復上述的過程，直到譯碼成功后達到最大迭代次數(shù)。 BF 譯碼算法步驟如下： (1)根據(jù)硬判決二元向量序列得到碼字 的伴隨式 s，判斷 s 是否為全“ 0”，如果為全“ 0”，則譯碼成功，否則轉 (2)； (2)計算 f，并找出其最大值 jf =max{f}，翻轉對應位置的碼元 jz ； 14 (3)將得到的新的向量序列代替原向量，轉 (1)，如滿足伴隨式全為“ 0”，譯碼成功，跳出，否則重復上述步驟，直到達到最大迭代次數(shù)。 由于校驗矩陣為稀疏矩陣，而且一般為隨機構成，所以參與每個校驗方程的比特很少，且這些比特在碼字上分布很分散，那么任一校驗方程所含的 比特要么 無錯，要么以很高概率的只有一個比特錯誤， BF 算法就可以有效地進行糾錯。即使某一校驗方程發(fā)生多于一個錯誤，糾錯仍可以進行。但是相對的犧牲的就是譯碼性能，所以下面對于硬判決譯碼算法提出了一種加權硬判決譯碼算法，它是在 BF 算法基礎上進行了一定的改進，在性能上有了一定的提高。 加權比特翻轉譯碼算法 在譯碼接收端通過添加一些可信信息將可以提高 BF 算法的糾錯性能。那么，加權比特翻轉譯碼 (WBF)算法就是在選擇需要翻轉的變量節(jié)點的時候，將每一個碼字中不滿足校驗方程個數(shù)最多的碼元的信道輸出信息作為該判決 式的權重信息。 設譯碼器接收端的輸入信息為 ? ?0 1 1, , . . . ,Ny y y y x w?? ? ?，其中? ?0 1 1, , ...,Nx x x x?? 是經(jīng)過調制后的信息， ? ?0 1 1w , ,..., Nw w w ?? 為加性高斯白噪聲。? ?mnH= H ? 為校驗矩陣， ? ? ? ?mnN m n H 1???： 表示與校驗節(jié)點 m 相連的變量節(jié)點， ? ? ? ?mnm n m H 1???： 表示與變量節(jié)點刀相連的校驗節(jié)點。因此， WBF 算法的一般步驟如 下，其中 m=0， 1， ?， M－ 1， n=0， 1， ?， N－ 1： (1)根據(jù)硬判決二元向量序列 z 得到碼字的伴隨式為 s，判斷 s 是否為全“ 0”， 如果為全“ 0”，則譯碼成功，否則轉 (2)； (2)計算 iminy {min y }? ： 0iN－ 1， n∈ N(m)； (3)對于 n=0， 1， ?， N－ 1，計算 n m M ( ) m inE = (2 1)nmsy? ?? ，并找出其中最大的值 max{ }jnEE? ，翻轉對應位置的 jz ； (4)將得到的新的向量序列代替原向量，轉 (1)，如滿足伴隨式全為“ 0”，譯碼成功，跳出，否則重復上述步驟，直到達到最大迭代次數(shù)。 加權譯碼算法是通過軟判決譯碼算法和附加信息來計算加權校驗信息 E，這 種算法雖然比單純的 BF 算法在復雜度上有了增加，但是卻具有更好的譯碼性能。 15 5 AWGN 信道下 LDPC碼的性能仿真 仿真軟件簡介（ matlabamp。simulink） MATLAB 軟件 MATLAB 在數(shù)學類科技應用軟件中在 數(shù)值計算 方面首屈一指。 MATLAB 可以進行 矩陣 運算、繪制函數(shù)和數(shù)據(jù)、實現(xiàn)算法、創(chuàng)建用戶界面、連 接其他編程語言的程序等，主要應用于工程計算、控制設計、信號處理與通訊、 圖像處理 、 信號檢測 、金融建模設計與分析等領域 。 MATLAB 的基本數(shù)據(jù)單位是矩陣，它的指令表達式與數(shù)學、工程中常用的形式十分相似，故用 MATLAB 來解算問題要比用 C， FORTRAN 等語言完成相同的事情簡捷得多，并且 mathwork 也吸收了像Maple 等軟件的優(yōu)點 ,使 MATLAB 成為一個強大的數(shù)學軟件 。 MATLAB 包括擁有數(shù)百個內部函數(shù)的主包和三十幾種工具包。工具包又可以分為功能性工具包和學科工具包。功能 工具包用來擴充 MATLAB 的符號計算，可視化建模仿真，文字處理及實時控制等功能。學科工具包是專業(yè)性比較 強的工具包，控制工具包，信號處理工具包，通信工具包等都屬于此類。 開放性使MATLAB 廣受用戶歡迎。除內部函數(shù)外，所有 MATLAB 主包文件和各種工具包都是可讀可修改的文件，用戶通過對源程序的修改或加入自己編寫程序構造新的專用工具包。 其中的 Communication Toolbox—— 通訊工具 箱與 Signal Processing Toolbox—— 信號處理工具箱 等在通信方面得到很多應用。 Simulink 仿真 軟件 近年來，由于問題域的擴展和仿真支持技術的發(fā)展，系統(tǒng)仿真方法學致力與更自然地抽象事物的屬性特征，尋求使模型研究者更自然地參與仿真活動的方法。在這些探索的推動下， MATHWORKS 公司推出的 Simulink 提供了一個系統(tǒng)級的建模與動態(tài)仿真的圖形用戶環(huán)境，并且利用 MATLAB 在科學計算上的天然優(yōu)勢，建立起了一個從設計構思到最終要求的可視化橋梁，它的模塊化，可以很方便的創(chuàng)建和維護一個完整的模型評估不同的算法和結構并驗證系統(tǒng)性能 仿真與結果分析 仿真中采用的信道都是二進制輸入的加性高斯白噪聲信道，采用的 調制方式都是基帶 BPSK調制。一般在仿真中要獲得較低的誤比特率需要大量的數(shù)據(jù)幀，而在碼長較長時大量的數(shù)據(jù)幀的計算要花費很多時間，因此只選定了一些碼長相 16 對較短的規(guī)則 LDPC碼進行了仿真。而由于受碼長和仿真數(shù)據(jù)量的限制使得仿真得到的性能結果較 LDPC碼所能夠達到的性能指標有一定的差距。仿真中所用的是規(guī)則的 LDPC碼，其校驗矩陣使用 Gallager的隨機構造的方法生成，具有固定的列重和行重。由于在編碼二分圖中長度為 4的圈的存在會導致 LDPC碼的誤碼率性能變得很差，因此構造的校驗矩陣在編程上考慮了消除長度為 4的圈。 仿真中選用了碼率為 1/2和 2/3，碼長分別為 4 9 20 408和 816五種碼長的 LDPC碼娜l。