ldpc碼的編譯碼算法研究本科畢業(yè)論文(編輯修改稿)

　

【文章內(nèi)容簡介】 碼算法，是 LDPC 碼與傳統(tǒng)糾錯碼的重要區(qū)別。 MP 算法集信息傳遞(Message Propagation，MP)算法是最主要的一類 LDPC 碼譯碼算法，它具有嚴(yán)格的數(shù)學(xué)結(jié)構(gòu)和良好的性能，使用它能對譯碼性能做定量分析。LDPC 碼譯碼算法中很多種都可以被歸結(jié)到信息傳遞算法集中。信息傳遞算法的主要思想就是通過在變量節(jié)點和校驗節(jié)點之間來回傳遞概率似然值，最終找到正確的碼字。這一過程在 Tanner 圖上可以直觀的表示出來，信息在 Tanner 圖中沿著連接變量節(jié)點和校驗節(jié)點的邊雙向傳遞。變量節(jié)點接收與它相連接的校驗節(jié)點送來的節(jié)點信息，然后根據(jù)這些信息計算出反饋給各校驗節(jié)點的信息。校驗節(jié)點開始接收與它相連接的變量節(jié)點送來的節(jié)點信息，然后根據(jù)這些信息計算出反饋給各變量節(jié)點的信息，如此往復(fù)形成迭代。每次迭代結(jié)束后，對每個變量節(jié)點做判決，得出一個碼字，再通過校驗矩陣驗證碼字正確性。如果譯碼成功，則譯碼結(jié)束；否則繼續(xù)迭代，直到達到預(yù)先設(shè)定的最大迭代次數(shù)。信息傳遞算法為了保證傳遞信息的獨立性，每個節(jié)點接收的信息都是從除自身之外的其他節(jié)點而來。但是由于現(xiàn)實中所使用的碼長都是有限的，使得節(jié)點不可能永遠收到與自身無關(guān)的信息，即存在環(huán)的影響。以一個行重為 ，列cd重為 的正則 LDPC 碼為例，當(dāng)前迭代周期中某一變量節(jié)點送來的信息直接來vd自 。個校驗節(jié)點，而這些校驗節(jié)點所送來的信息又來自與各自相連的以1?一1個變量節(jié)點在上一迭代周期中送出的值，如下圖所示的樹狀圖表示它們之c間的關(guān)系。因此，在 LDPC 碼譯碼過程中環(huán)對譯碼的影響是不容忽視的。13 圖 節(jié)點樹LDPC 碼有很多種譯碼方法，本質(zhì)上大都是基于 Tanner 圖的信息傳遞譯碼算法。根據(jù)信息迭代過程中傳送消息的不同形式，可以將 LDPC 的譯碼方法分為硬判決譯碼和軟判決譯碼。如果在譯碼過程中傳送的信息是比特值，稱之為硬判決譯碼，如 BF 算法，它具有較低的譯碼復(fù)雜度，易于工程實現(xiàn)。但是與軟判決譯碼相比，硬判決譯碼在性能上要損失約23dB；如果在譯碼過程中傳送的信息是與后驗概率相關(guān)的信息，稱之為軟判決譯碼，如置信傳播譯碼算法。雖然軟判決算法譯碼復(fù)雜度較高，但可以獲得更好的譯碼準(zhǔn)確性，比硬判決譯碼具有更大的編碼增益。在 AWGN 信道中，它比硬判決譯碼要多2dB 左右的軟判決增益，而在衰落信道中，軟判決增益超過5dB。硬判決譯碼可以看成是 l 比特量化譯碼，而軟判決譯碼可以看成無窮多比特量化譯碼。主要的硬判決譯碼算法有比特翻轉(zhuǎn)算法(BF)、加權(quán)的比特翻轉(zhuǎn)算法(WBF)等；軟譯碼算法主要有置信傳播算法(BeliefPropagation) 、簡化的最小和算法(Minsum) 、歸一化最小和算法(Normalized Min．Sum) 、偏移量最小和算法(OffsetMin．sum)等。 硬判決譯碼算法 比特翻轉(zhuǎn)算法Gallager 在其論文中提出了硬判決譯碼算法，該算法是一種比較簡單而且容易理解的譯碼算法，它對運算量和存儲量的要求都很低，但是其性能相對比較差。14比特翻轉(zhuǎn)算法(Bit Flipping Algorithm)可看成是置信傳播算法的簡化形式，而加權(quán)位翻轉(zhuǎn)譯碼算法是在 BF 算法的基礎(chǔ)上加上硬判決譯碼系數(shù)，其性能較比特翻轉(zhuǎn)譯碼算法有一定程度的提高比特翻轉(zhuǎn)算法(Bit Flipping Algorithm)是 Gallager 在其論文中提出的被命名為Gallager 硬判決的譯碼算法。設(shè)碼字 c= 為發(fā)送序列，經(jīng) BPSK??01N1c.， ， ，調(diào)制為序列 x= ， ， ， 為??01N1c.， ， ， iix2??i????， ， ，接收的實數(shù)向量序列，由實數(shù)序列可以得到硬判決二元向量序列 z=()：01N1zz， ， .， （41）ii1r0z??????， 當(dāng) 時， 當(dāng) 時由此得到碼字伴隨式 s=（ ）= ，若 ，則說012J1ss， ， ， .， TzH?js0明接收向量滿足第 j 個校驗方程；若 s=0，則表示接收向量滿足所有校驗方程，接收碼字 z 正確，譯碼成功；若伴隨式為非全“0”向量時，接收序列 z 有錯誤，此時則需計算出每個碼元不滿足校驗方程的個數(shù) f= = ，搜索 f??01N1ff， ， .， sHA中的最大值，翻轉(zhuǎn)對應(yīng)位置的碼元 。再重復(fù)上述的過程，直到譯碼成功后達jz到最大迭代次數(shù)。BF 譯碼算法步驟如下：(1)根據(jù)硬判決二元向量序列得到碼字的伴隨式 s，判斷 s 是否為全“0” ，如果為全“0” ，則譯碼成功，否則轉(zhuǎn)(2)；(2)計算 f，并找出其最大值 =max{f}，翻轉(zhuǎn)對應(yīng)位置的碼元 ；jf jz(3)將得到的新的向量序列代替原向量，轉(zhuǎn)(1) ，如滿足伴隨式全為“0” ，譯碼成功，跳出，否則重復(fù)上述步驟，直到達到最大迭代次數(shù)。由于校驗矩陣為稀疏矩陣，而且一般為隨機構(gòu)成，所以參與每個校驗方程的比特很少，且這些比特在碼字上分布很分散，那么任一校驗方程所含的比特要么無錯，要么以很高概率的只有一個比特錯誤，BF 算法就可以有效地進行糾錯。即使某一校驗方程發(fā)生多于一個錯誤，糾錯仍可以進行。但是相對的犧牲的就15是譯碼性能，所以下面對于硬判決譯碼算法提出了一種加權(quán)硬判決譯碼算法，它是在 BF 算法基礎(chǔ)上進行了一定的改進，在性能上有了一定的提高。 加權(quán)比特翻轉(zhuǎn)譯碼算法在譯碼接收端通過添加一些可信信息將可以提高 BF 算法的糾錯性能。那么，加權(quán)比特翻轉(zhuǎn)譯碼(WBF)算法就是在選擇需要翻轉(zhuǎn)的變量節(jié)點的時候，將每一個碼字中不滿足校驗方程個數(shù)最多的碼元的信道輸出信息作為該判決式的權(quán)重信息。設(shè)譯碼器接收端的輸入信息為 ，其中??011,.Nyyxw????是經(jīng)過調(diào)制后的信息， 為加性高斯白噪聲。??01,.Nxx?? 1,.為校驗矩陣， 表示與校驗節(jié)點 m 相連的變量節(jié)??mnH=???mnH?：點， 表示與變量節(jié)點刀相連的校驗節(jié)點。因此，WBF 算mn1??：法的一般步驟如下，其中 m=0，1，?，M－1，n=0，1，?，N－1：(1)根據(jù)硬判決二元向量序列 z 得到碼字的伴隨式為 s，判斷 s 是否為全“0”，如果為全“0” ，則譯碼成功，否則轉(zhuǎn)(2)；(2)計算 0iN－1，n∈N(m)；iminy{}?：(3)對于 n=0， 1，?，N－1，計算 ，并找出其中最mM()minE=21nsy???大的值 ，翻轉(zhuǎn)對應(yīng)位置的 ；axjnEjz(4)將得到的新的向量序列代替原向量，轉(zhuǎn)(1) ，如滿足伴隨式全為“0” ，譯碼成功，跳出，否則重復(fù)上述步驟，直到達到最大迭代次數(shù)。加權(quán)譯碼算法是通過軟判決譯碼算法和附加信息來計算加權(quán)校驗信息 E，這種算法雖然比單純的 BF 算法在復(fù)雜度上有了增加，但是卻具有更好的譯碼性能。5 AWGN 信道下 LDPC 碼的性能仿真 仿真軟件簡介（matlabamp。simulink）MATLAB 軟件MATLAB 在數(shù)學(xué)類科技應(yīng)用軟件中在數(shù)值計算方面首屈一指。 MATLAB 可16以進行矩陣運算、繪制函數(shù)和數(shù)據(jù)、實現(xiàn)算法、創(chuàng)建用戶界面、連 接其他編程語言的程序等，主要應(yīng)用于工程計算、控制設(shè)計、信號處理與通訊、圖像處理、信號檢測、金融建模設(shè)計與分析等領(lǐng)域。MATLAB 的基本數(shù)據(jù)單位是矩陣，它的指令表達式與數(shù)學(xué)、工程中常用的形式十分相似，故用 MATLAB 來解算問題要比用 C，F(xiàn)ORTRAN 等語言完成相同的事情簡捷得多，并且 mathwork 也吸收了像 Maple 等軟件的優(yōu)點,使 MATLAB 成為一個強大的數(shù)學(xué)軟件。MATLAB 包括擁有數(shù)百個內(nèi)部函數(shù)的主包和三十幾種工具包。工具包又可以分為功能性工具包和學(xué)科工具包。功能工具包用來擴充 MATLAB 的符號計算，可視化建模仿真，文字處理及實時控制等功能。學(xué)科工具包是專業(yè)性比較強的工具包，控制工具包，信號處理工具包，通信工具包等都屬于此類。開放性使 MATLAB 廣受用戶歡迎。除內(nèi)部函數(shù)外，所有 MATLAB 主包文件和各種工具包都是可讀可修改的文件，用戶通過對源程序的修改或加入自己編寫程序構(gòu)造新的專用工具包。其中的 Communication Toolbox——通訊工具箱與 Signal Processing Toolbox——信號處理工具箱等在通信方面得到很多應(yīng)用。Simulink 仿真軟件近年來，由于問題域的擴展和仿真支持技術(shù)的發(fā)展，系統(tǒng)仿真方法學(xué)致力與更自然地抽象事物的屬性特征，尋求使模型研究者更自然地參與仿真活動的方法。在這些探索的推動下，MATHWORKS 公司推出的 Simulink 提供了一個系統(tǒng)級的建模與動態(tài)仿真的圖形用戶環(huán)境，并且利用 MATLAB 在科學(xué)計算上的天然優(yōu)勢，建立起了一個從設(shè)計構(gòu)思到最終要求的可視化橋梁，它的模塊化，可以很方便的創(chuàng)建和維護一個完整的模型評估不同的算法和結(jié)構(gòu)并驗證系統(tǒng)性能 仿真與結(jié)果分析仿真中采用的信道都是二進制輸入的加性高斯白噪聲信道，采用的調(diào)制方式都是基帶BPSK調(diào)制。一般在仿真中要獲得較低的誤比特率需要大量的數(shù)據(jù)幀，而在碼長較長時大量的數(shù)據(jù)幀的計算要花費很多時間，因此只選定了一些碼長相對較短的規(guī)則LDPC碼進行了仿真。而由于受碼長和仿真數(shù)據(jù)量的限制使得仿真得到的性能結(jié)果較LDPC 碼所能夠達到的性能指標(biāo)有一定的差距。仿真中所用的是規(guī)則的LDPC碼，其校驗矩陣使用Gallager 的隨機構(gòu)造的方法生成，具有固定的列重和行重。由于在編碼二分圖中長度為4的圈的存在會導(dǎo)致LDPC碼的誤17碼率性能變得很差，因此構(gòu)造的校驗矩陣在編程上考慮了消除長度為4的圈。仿真中選用了碼率為1/2和2/3，碼長分別為4920408和816五種碼長的LDPC碼娜l。主要針對碼長為81碼率為1/2的LDPC碼，對基于BF算法的各種硬判決譯碼算法和基于BP算法的各種軟譯碼算法及其改進算法的進行仿真，并比較了不同算法的誤碼率性能，同時得到了一些算法性能最好時的參數(shù)配置。然后對碼長為20408和816，碼率都為1/2的三種碼型進行了仿真，分析碼長與誤碼性能的關(guān)系。對于碼長為%和 816，碼率分別為 1/2和2/3兩種碼型進行仿真，并比較其性能。然后對碼長為816，碼率都為1/2的迭代次數(shù)分別取40和50四種情況進行了仿真，分析迭代次數(shù)與誤碼性能的關(guān)系。從而確定了各種改進算法的性能及其碼長、碼率和迭代數(shù)對譯碼性能的影響。 譯碼仿真系統(tǒng)框圖及系統(tǒng)總流程圖為了仿真LDPC 碼的譯碼性能要搭建一個從發(fā)送到接收的簡單系統(tǒng)，系統(tǒng)框圖如圖5一1所示 圖51 LDPC譯碼仿真系統(tǒng)框圖針對LDPC譯碼仿真系統(tǒng)框圖做了其對應(yīng)的流程圖，如圖5一2所示。18 圖52 譯碼仿真系統(tǒng)總流程圖 BF 算法及其改進算法仿真圖 53 為比特翻轉(zhuǎn)算法和改進的加權(quán)比特翻轉(zhuǎn)算法的誤碼率性能仿真結(jié)果。選用的碼型為 LDPC(8l6，3，6)，最大迭代次數(shù)為 50。19 圖 53 BF 算法及其 3 種改進算法在 LDPC(816,3,6)中的性能由圖 53 可以看出，比特翻轉(zhuǎn)算法及其另外的三種改進算法的誤碼率性能總體比較差，在信噪比達到 6dB 以上時，它們的誤碼率才可以達到 數(shù)量級的510?水平。從每個算法性能看，單純的硬判決比特翻轉(zhuǎn)的 BF 算法性能最差，當(dāng)信噪比小于 5dB 時，誤碼率一直處于 之上，即使信噪比達到 6dB，它的誤碼率210?剛接近 了。KLF 算法的性能比 BF 算法相對要好一些，在信噪比小于 6dB410?時，KLF 算法的性能比 BF 算法好很多，在誤碼率為 處和 處，KLF 算10?2?法比 BF 算法的大約有 的改善，在信噪比接近 6dB 時，兩種算法的性能差距大幅縮小，達到了同一數(shù)量級。而改進的兩種加權(quán)的比特翻轉(zhuǎn)算法 IMMBF 和 RRWBF 的性能較前兩種算法相比，性能有了明顯的改善，尤其是在信噪比小于 4dB 的范圍內(nèi)，但信噪比大于 4dB 時，它們的性能與 KLF 性能變得很接近，IMMBF 算法的性能最佳，總體講，改進的算法與原始的 BF 算法相比，誤碼率性能有了一定的提高，但效果有限在實際信號的信道譯碼中，這些算法雖然復(fù)雜度較小，然而實用性較差。20結(jié) 論信道編碼理論及技術(shù)作為現(xiàn)代通信系統(tǒng)必不可少的關(guān)鍵技術(shù)，在香農(nóng)的信道編碼定理的指引下， LDPC 碼作為一種新的編碼方式，由于其校驗矩陣具有稀疏的特點，使得它的譯碼復(fù)雜度與碼長呈線性的關(guān)系，而性能卻很接近Shannon 的極限，因此得到了人們更多的注意。本文在對 LDPC 碼進行研究的時候，主要完成了以下幾個方面（1）介紹 LDPC 碼的基本原理和分類，分別從基于生成矩陣和基于校驗矩陣詳細討論了 LDPC 碼編碼算法，簡單介紹了線性分組碼編碼，LU 分解法，RU 分解法。并用簡明例子對 RU 算法做了清晰的解釋。（2）對譯碼大致做了解釋：分為軟判決譯碼（MP 算法）和硬判決譯碼（比特翻轉(zhuǎn)算法和加權(quán)比特翻轉(zhuǎn)算法） 。（3）在本文的最后用 AWGN 信道下 LDPC 碼的性能仿真，主要是針對比特翻轉(zhuǎn)算法進行仿真。作者在理解 LDPC 碼基本編譯碼理論的基礎(chǔ)之上，認(rèn)為有待于對如下問題將 LDPC 碼做進一步的研究LDPC 碼的校驗矩陣結(jié)構(gòu)及其優(yōu)化已經(jīng)證明了非規(guī)則碼比規(guī)則碼具有更好的性能，采用具有非均勻行、列重量的非規(guī)則碼均可改善碼的性能，因此校驗矩陣的結(jié)構(gòu)及其優(yōu)化還有待進一步的研究。LDPC