現(xiàn)代編碼理論期末報(bào)告LDPC

1、廈門(mén)大學(xué)不同仿真平臺(tái)下LDPC編譯碼效率對(duì)比課程名稱： 現(xiàn)代編碼理論 任課教師： 洪少華 王琳 院 系： 通信工程系 姓 名： 張琳 林治 學(xué) 號(hào)： 23320131153234 23320131153224 摘要現(xiàn)代編碼理論通過(guò)軟判決譯碼、和積算法、因子圖這三個(gè)核心概念在指導(dǎo)著眾多“好碼”的仿真和實(shí)現(xiàn)。本文分別在C語(yǔ)言環(huán)境和MATLAB環(huán)境下對(duì)比低密度奇偶校驗(yàn)碼的編譯碼效率，并分析對(duì)比了兩種仿真平臺(tái)的優(yōu)缺點(diǎn)。關(guān)鍵詞： 現(xiàn)代編碼理論 軟判決譯碼 低密度奇偶校驗(yàn)碼AbstractModern encoding theories through the soft decoding and enco

2、ding ,product algorithm and factor diagram three core concepts in guiding many simulation and implementation of the good code. This paper respectively contrast of low density parity check code decoding efficiency in C language environment and MATLAB environment, and then analyze the advantages and d

3、isadvantages of the two kinds of simulation platform.Key Words: Modern encoding theories the soft decoding and encoding LDPC(low-density parity-check) codes目錄摘要1Abstract2緒 論41.1研究背景41.2通信系統(tǒng)模型41.3 因子圖51.4 軟判決譯碼51.4.1逐位軟判決譯碼51.4.2.逐組軟判決譯碼61.5 基于網(wǎng)格圖上分組碼的Viterbi譯碼71.5.1、分組碼與網(wǎng)格圖的關(guān)系71.5.2基于Shannon乘積的最小網(wǎng)格圖

4、設(shè)計(jì)81.5.3.軟輸入/軟輸出的譯碼算法8第二章 LDPC原理與BP譯碼原理102.1LDPC原理102.2和積算法原理13第三章 仿真分析183.1仿真結(jié)果分析：183.2 C語(yǔ)言和MATLAB語(yǔ)言的仿真對(duì)比：19第四章 總結(jié)與展望20參考文獻(xiàn)21緒 論1.1研究背景 編碼是信息從一種形式或格式轉(zhuǎn)換為另一種形式的過(guò)程。用預(yù)先規(guī)定的方法將文字、數(shù)字或其他對(duì)象編成數(shù)碼，或?qū)⑿畔ⅰ?shù)據(jù)轉(zhuǎn)換成規(guī)定的電脈沖信號(hào)?，F(xiàn)代編碼，是編碼的一個(gè)新分支，基于一些理論基礎(chǔ)來(lái)指導(dǎo)較好的編碼方向。現(xiàn)代編碼中常用的經(jīng)典理論，如因子圖，和積算法等，已經(jīng)得到廣泛應(yīng)用，并指導(dǎo)編碼出很好的編譯碼方法，如ldpc碼，原木圖ldp

5、c碼等，用不同的方法在各種信道下會(huì)得到不同的結(jié)果，基于它們的性能比較也必然成為一個(gè)很重要的因素。1.2通信系統(tǒng)模型主要包括：信源，編碼器，信道，譯碼器，信宿這五部分，如如1.1所示： 圖1.1 數(shù)字通信模型信源：產(chǎn)生消息和消息序列的源編碼器信源編碼器，信道編碼起，保密編碼器信道信號(hào)的傳輸通道譯碼器信源譯碼器，信道譯碼起，保密譯碼器，和編碼器的功能相反信宿消息傳送的歸宿 實(shí)際的通信還需要，同步，調(diào)制，解調(diào)等多個(gè)步驟，才能保障通信的準(zhǔn)確到達(dá)，根據(jù)實(shí)際的要求和需要，可適當(dāng)?shù)卦黾右恍┚獾燃夹g(shù)。1.3 因子圖將一個(gè)具有多個(gè)變量的全局函數(shù)因子分解成幾個(gè)局部函數(shù)的積而形成的一個(gè)雙向圖叫因子圖。如g（x1,

6、x2,x3,x4,x5）是具有5個(gè)變量的實(shí)質(zhì)函數(shù)，將其分解成5個(gè)局部函數(shù)之積，即： 則對(duì)應(yīng)的因子圖如圖 所示。在該圖中，每個(gè)變量對(duì)應(yīng)于一個(gè)變量節(jié)點(diǎn)，每個(gè)局部因子對(duì)應(yīng)于一個(gè)函數(shù)節(jié)點(diǎn)，這兩類(lèi)節(jié)點(diǎn)構(gòu)成因子圖的頂點(diǎn)集。圖1.2 因子圖因子圖的定義與聯(lián)合概率密度函數(shù)之間，提取-乘積算法與邊緣密度求取之間有極大的相似性，因此，可在概率個(gè)隨機(jī)過(guò)程領(lǐng)域，因子圖分析法有極大的應(yīng)用。1.4 軟判決譯碼在尋找較為實(shí)用的次最佳軟判決譯碼方法或準(zhǔn)最佳軟判決MLD算法中，一般可分為使碼字的每個(gè)碼元譯碼錯(cuò)誤概率最小的逐位軟判決譯碼方法，和使碼字錯(cuò)誤概率最小的逐組軟判決譯碼方法.雖然這二類(lèi)軟判決譯碼方法都是準(zhǔn)最佳或最佳的，但

7、其譯碼的基本思想并不完全相同.1.4.1逐位軟判決譯碼Massey提出了適用于大數(shù)邏輯可譯碼的APP譯碼算法12，這是一種門(mén)限譯碼，用于硬判決時(shí)就是大數(shù)邏輯譯碼.而后，F(xiàn)orney等人提出了漸近APP算法13，但僅適用于正交碼.1976年Hartman和Rudolph對(duì)這種算法進(jìn)行了推廣，提出了HR算法14.這種算法利用有限域上的FFT變換，能適用于任何線性分組碼，而Massey的算法，僅僅是HR算法的一種特例.HR算法對(duì)每位碼元的判決，是基于計(jì)算它的對(duì)偶碼的碼字的后驗(yàn)概率基礎(chǔ)上，因此它的譯碼復(fù)雜性是O(2n(1-R).Weldon提出的重量刪除譯碼(WED)算法，使逐位軟判決譯碼開(kāi)始走向?qū)嵱?/p>

8、，因?yàn)樗挠?jì)算復(fù)雜性并不是n的指數(shù)函數(shù)而是多項(xiàng)式函數(shù)，當(dāng)然性能比APP差.如何減少譯碼復(fù)雜性而性能又接近APP，是這類(lèi)算法的研究方向.有關(guān)這類(lèi)算法的發(fā)展過(guò)程，請(qǐng)參考文獻(xiàn)16.在逐位軟判決譯碼算法中，特別值得提出的是由Bahl等人提出的，用迭代方法計(jì)算每位碼元最大后驗(yàn)概率的BCJR算法，這種算法適用于任何線性分組碼和卷積碼.由于在計(jì)算每個(gè)碼元的最大后驗(yàn)概率時(shí)采用迭代方法，因此計(jì)算速度很快.這種算法剛剛提出時(shí)，并沒(méi)有引起有關(guān)理論和工程界的多大注意.直到1993年Berrou等人提出Turbo碼后，這種算法才引起了人們的廣泛注意，并且對(duì)它作了各種改進(jìn).有關(guān)這種算法的最近進(jìn)展情況，將在后面的Turbo

9、碼一節(jié)中作進(jìn)一步介紹.以碼字為單位的最大似然譯碼，一直是理論上討論得最多，實(shí)際中也用得最為廣泛的一類(lèi)譯碼方法.1.4.2.逐組軟判決譯碼最早的逐字軟判決譯碼是1954年Wagner提出的僅適用于n,n-1,2碼的譯碼算法，這也可以說(shuō)是軟判決譯碼思想的萌芽.系統(tǒng)開(kāi)始研究逐字軟判決譯碼始于Forney的工作，F(xiàn)orney在他的博士論文中首次提出了廣義最小距離譯碼(GMD)3，19.GMD譯碼是一種迭代糾錯(cuò)譯碼.算法需要d/2次硬譯碼，得到d/2個(gè)候選碼字，然后挑出一個(gè)最好的作為譯碼器輸出.在1993年的國(guó)際信息論會(huì)議上，有四位學(xué)者分別提出用Berlekamp-Massey算法，能夠一次得到所有GM

10、D的候選碼字20.GMD譯碼的基本思想可以說(shuō)是以后幾乎所有各種逐字軟判決譯碼的基礎(chǔ)，Chase21在GMD譯碼思想基礎(chǔ)上提出了Chase算法.Chase算法是一種伴隨式譯碼，利用可信信息尋找最可能的錯(cuò)誤圖樣，根據(jù)試探錯(cuò)誤圖樣數(shù)目的不同，分為三種算法：Chase1,2和3.其譯碼復(fù)雜性能以Chase1最高，Chase3最低；當(dāng)然譯碼性能以Chase1最好，Chase3最差.在中等碼長(zhǎng)和中等糾錯(cuò)能力情況下，Chase2算法的復(fù)雜性可以為人們所接受且譯碼性能很接近MLD，因此在實(shí)際中用得最多.正因如此，自八十年代至今各國(guó)有關(guān)學(xué)者，在改進(jìn)Chase2算法方面做了大量工作.其中心思想是加快它的譯碼速度并

11、改善譯碼性能.因此主要圍繞以下二個(gè)問(wèn)題研究：(1)引入結(jié)束試探的門(mén)限標(biāo)準(zhǔn)，以減低譯碼的平均時(shí)間提高譯碼速度，其關(guān)鍵是盡早找到重量最輕的錯(cuò)誤圖樣，或最似然的碼字.(2)在(1)的基礎(chǔ)上，擴(kuò)大Chase2的試探集合，使盡量包含最似然信的碼字，以提高譯碼性能.我們?cè)?986年首先引入了結(jié)束譯碼的門(mén)限標(biāo)準(zhǔn)，從而使譯碼的平均時(shí)間得到大幅度減少，以后范平志等作了進(jìn)一步改進(jìn)23，最近我們又提出了根據(jù)信噪比變化，從固定門(mén)限變?yōu)榭勺冮T(mén)限的思想，使譯碼時(shí)間得到進(jìn)一步縮短.國(guó)外學(xué)者如Forney、Lous、Fossorier、Snyder、Beery、Vardy、Kaneko、Lin、Taipale等，在此方向上也

12、提出了許多性能達(dá)到或接近MLD、譯碼平均時(shí)間比Chase2更少的改進(jìn)算法.如1994年和1997年Kaneko、Nishijima等提出的KN算法，為了使試探圖樣中能包含最似然的碼組，其試探圖樣的數(shù)目和結(jié)束試探的標(biāo)準(zhǔn)也隨信噪比變化25.又如Fossorier和Lin提出的FL算法，也是一種性能能達(dá)到預(yù)先指定要求或接近MLD的改進(jìn)Chase算法26，27.它的基本思想也是根據(jù)每個(gè)碼元可信度的大小，對(duì)其重新排序，根據(jù)對(duì)譯碼性能要求，計(jì)算為了達(dá)到該性能所需的試探次數(shù)，然后再進(jìn)行多次信息集譯碼.所有這些算法，都是Chase2算法的改進(jìn)，其中心思想都是利用接收碼元的可信信息的硬判決譯碼器進(jìn)行多次譯碼，以

13、找到與發(fā)送碼字最似然的碼字，并在給定的判決門(mén)限或標(biāo)準(zhǔn)下結(jié)束譯碼.1.5 基于網(wǎng)格圖上分組碼的Viterbi譯碼1.5.1、分組碼與網(wǎng)格圖的關(guān)系1974年，Bahl等首次將分組碼用網(wǎng)格圖表示,從而揭示了分組碼與卷積碼之間的聯(lián)系,1978年Wolf又系統(tǒng)地提出了分組碼的網(wǎng)格圖表示,并將卷積碼的Viterbi譯碼算法用于分組碼的譯碼,Forney進(jìn)一步分析了分組碼的網(wǎng)格圖結(jié)構(gòu),并為一些分組碼設(shè)計(jì)了有效的軟判決譯碼算法，而Muder基于圖論的方法將分組碼的網(wǎng)格圖的設(shè)計(jì)形式化，為分組碼網(wǎng)格圖結(jié)構(gòu)的研究奠定了基礎(chǔ).一個(gè)分組碼的網(wǎng)格圖可按段表示和構(gòu)造.設(shè)C是GF(q)上的一個(gè)(n,k)線性碼，則C的網(wǎng)格圖有

14、n+1層，每一層的狀態(tài)集為Vi,i=0,1，n，網(wǎng)格圖的分支由0，1，q-1標(biāo)識(shí)，每條路徑對(duì)應(yīng)一個(gè)碼字.如果V0只有一個(gè)狀態(tài)S0，每個(gè)狀態(tài)都出現(xiàn)在某條長(zhǎng)為n的路徑上，并且從S0出發(fā)的任意兩條長(zhǎng)為i的路徑表示不同的i元組(或i維矢量)，則將這樣的網(wǎng)格稱為真正的網(wǎng)格圖.線性碼與真正網(wǎng)格圖之間存在一一對(duì)應(yīng)關(guān)系，但非線性碼不一定存在真正的網(wǎng)格圖表示.對(duì)于給定時(shí)間軸，Wolf、Forney和Muder構(gòu)造的網(wǎng)格圖是唯一真正的最小網(wǎng)格圖，即|Vi|是最小的,i=0,1,，n.定義網(wǎng)格圖指標(biāo)為，則min(k,n-k-2)smin(n,n-k)其中=n-k-d+1，d為碼C的最小距離如果C為完備碼，則smin

15、(n,n-k-3)30,31顯然，最小網(wǎng)格圖指標(biāo)s與碼的坐標(biāo)次序有關(guān)11,31，即與生成(校驗(yàn))矩陣中列的百列方式有關(guān)，對(duì)生成(校驗(yàn))矩陣列的重排運(yùn)算稱為置換將碼C在置換意義下能夠達(dá)到的最小指標(biāo)s稱為絕對(duì)最小網(wǎng)絡(luò)圖尺寸s(C),s=s(C)的網(wǎng)格圖稱為絕對(duì)最小網(wǎng)格圖，s(C)可以刻劃碼的Viterbi譯碼算法的時(shí)間復(fù)雜性.由于一般分組碼的網(wǎng)格圖比較復(fù)雜，不便于譯碼實(shí)現(xiàn)，所以，F(xiàn)orney提出了結(jié)構(gòu)化的網(wǎng)格圖構(gòu)造方法.利用Forney的方法，一個(gè)網(wǎng)格圖可由許多結(jié)構(gòu)相同的子網(wǎng)格圖組成，從而便于譯碼的并行處理，但這樣的網(wǎng)格圖與碼的結(jié)構(gòu)有關(guān)，目前只知道RM碼和Golay碼等幾種碼存在這種規(guī)則網(wǎng)格圖.F

16、orney最小規(guī)則網(wǎng)格圖的構(gòu)造方法的關(guān)鍵也在于碼元坐標(biāo)的次序，由于譯碼問(wèn)題的難處理性，可以設(shè)想，對(duì)于一般分組碼很難找到一個(gè)有效的方法求具有最小網(wǎng)格圖的最佳置換.實(shí)際上，最近已經(jīng)證明了某種求置換問(wèn)題是NPC問(wèn)題，正因?yàn)檫@樣，對(duì)于給定碼利用其組合(或代數(shù))特性求其網(wǎng)格圖結(jié)構(gòu)就具有重要的理論和應(yīng)用價(jià)值.但是，對(duì)于即使是很特殊的碼要求其最小網(wǎng)格圖也是很困難的.因此，對(duì)于實(shí)際應(yīng)用，我們可基于近似最小網(wǎng)格圖設(shè)計(jì)有效的譯碼算法，實(shí)際上，許多譯碼思想都是這樣的。1.5.2基于Shannon乘積的最小網(wǎng)格圖設(shè)計(jì)Forney等人提出的網(wǎng)格圖構(gòu)造方法只對(duì)某些特殊的碼找到了對(duì)應(yīng)的最小網(wǎng)格圖，而對(duì)于絕大多數(shù)碼尚不清楚其

17、最小網(wǎng)格圖指標(biāo)s(C)和最小網(wǎng)格圖的結(jié)構(gòu).但是，由一些碼的代數(shù)結(jié)構(gòu)可知，這些碼可由一些“小”的線性碼構(gòu)成，如果已知這些小線性碼的網(wǎng)格圖結(jié)構(gòu)，則有可能由這些網(wǎng)格圖構(gòu)造給定碼的最小網(wǎng)格圖35,36.設(shè)T，是兩個(gè)n+1層網(wǎng)格圖，第t層的狀態(tài)分別為,i=1,，Nt,，網(wǎng)格圖的每條分支代表h個(gè)字符，則T與的Shannon乘積T也具有n+1層，第t層的狀態(tài)由表示，i=1,，Ni,.當(dāng)且僅當(dāng)T中有一條連接狀態(tài)的分支,中有一條連接狀態(tài)的分支時(shí)，T中有一條連接狀態(tài)和狀態(tài)的分支，該分支的標(biāo)號(hào)為,其中的加法為GF(q)中的矢量加法，分別為分支的標(biāo)號(hào)，例如，由四個(gè)子碼的最小網(wǎng)格圖可構(gòu)造出(8，4，4)RM碼的最小網(wǎng)格

18、圖.這里給出的網(wǎng)格構(gòu)造方法對(duì)于比較小的線性碼是非常有效的，但是，如果線性碼空間比較大，則這種構(gòu)造方法也是比較復(fù)雜的.1.5.3.軟輸入/軟輸出的譯碼算法軟輸入/軟輸出的譯碼算法是Turbo碼譯碼必需的算法.自Turbo碼出現(xiàn)以來(lái)，這方面的研究也引起了關(guān)注.最優(yōu)的算法是BCJR算法17及軟輸入/軟輸出Viterbi算法46.人們?cè)诖嘶A(chǔ)上，提出一些次優(yōu)的譯碼算法，以降低復(fù)雜度，提高譯碼速度.S.S.Pietrobon68注意到函數(shù)f(z)=ln(1+ez)(z0)的如下性質(zhì)：z=0時(shí)，f(z)取最大值f(0)=ln2=0.693，隨著z的增大，f(z)迅速下降，當(dāng)z7時(shí)，f(z)接近0.利用這一

19、性質(zhì)，可以由MAP算法得到次優(yōu)的logMAP算法.V.Franz59提出了M-BCJR算法和T-BCJR算法.BCJR算法有兩個(gè)遞推公式.考慮一個(gè)網(wǎng)格圖，設(shè)其有L級(jí)，則前向遞推公式(t是行向量)t=t-1.t,t=1,，L后身遞推公式(t是列向量)t=t+1.t+1,t=L-1,，1轉(zhuǎn)換矩陣t(i,j)=PrSt=j,Yt|St-1=i,t=1,，LM-BCJR算法與T-BCJR算法基于這樣一個(gè)事實(shí)，在與中，有些分量接近于0，可以忽略M-BCJR算法：每次遞推時(shí)，只保留t與t中M個(gè)量大的分量T-BCJR算法：每次遞增推時(shí)，忽略t與t中小于某門(mén)限T的分量模擬結(jié)果表明，T-BCJR算法優(yōu)于M-BC

20、JR算法，與BCJR算法性能接近，但計(jì)算量減少50%90%第二章 LDPC原理與BP譯碼原理2.1LDPC原理LDPC 碼可以由它的校驗(yàn)矩陣 H 來(lái)定義， H 是一稀疏矩陣，矩陣中除很少一部分元素為非零元素外，其它大部分的元素都是零即所謂的“低密度”。LDPC 碼也可以用二分圖(也稱 Tanner 圖)來(lái)表示。二分圖和校驗(yàn)矩陣 H 是直接對(duì)應(yīng)的，由比特節(jié)點(diǎn)(也可稱為變量節(jié)點(diǎn))、校驗(yàn)節(jié)點(diǎn)和連接它們的邊組成。每個(gè)校驗(yàn)節(jié)點(diǎn)對(duì)應(yīng)于 H 的一行，每個(gè)比特節(jié)點(diǎn)對(duì)應(yīng)于 H 的一列。當(dāng)碼字中某一比特包含在某一校驗(yàn)方程中，即校驗(yàn)矩陣中相應(yīng)位為 1 時(shí)，校驗(yàn)節(jié)點(diǎn)和比特節(jié)點(diǎn)間存在連線，我們將這條邊稱為相鄰邊，相鄰邊

21、兩端的節(jié)點(diǎn)稱為相鄰點(diǎn)。每個(gè)節(jié)點(diǎn)的相鄰邊條數(shù)稱為該節(jié)點(diǎn)的度數(shù)(degree)。LDPC碼的校驗(yàn)矩陣的構(gòu)造方法是一個(gè)值得注意的問(wèn)題。對(duì)于信道編碼，影響編碼性能的一個(gè)重要因素是最小碼距。對(duì)于LDPC碼，由于譯碼算法的限制，Tanner圖中度的分布、圈的分布以及girth的大小也會(huì)影響譯碼性能。通常我們希望LDPC 碼具有最小碼重即最小碼距，又希望避免Tanner圖中短圈的出現(xiàn)。但這些因素之間是相互矛盾的。增加LDPC 碼的最小碼重，必然要增加校驗(yàn)矩陣H的行重和列重，隨之而來(lái)的就是Tanner圖中短圈出現(xiàn)的可能性有所增加。因此對(duì)于已經(jīng)確定了度分布多項(xiàng)式的LDPC碼，如何構(gòu)造校驗(yàn)矩陣H，既然增加最小碼重

22、同時(shí)又能避免短圈的存在，并且要具有較低的硬件實(shí)現(xiàn)復(fù)雜度，一只是LDPC 碼研究領(lǐng)域中的一個(gè)焦點(diǎn)。一般說(shuō)來(lái)，構(gòu)造LDPC碼的奇偶校驗(yàn)矩陣有兩種方法：一種是隨機(jī)或偽隨機(jī)結(jié)構(gòu)的，即在對(duì)度分布和最小全場(chǎng)等因素做一定限制的條件下，利用計(jì)算機(jī)搜索方法進(jìn)行隨機(jī)貨這類(lèi)隨機(jī)生成奇偶校驗(yàn)矩陣；另一種是利用代數(shù)學(xué)或者組合理論構(gòu)造LDPC碼的奇偶校驗(yàn)矩陣，使之具有規(guī)律的結(jié)構(gòu)，易于理論分析。下面我們分別介紹一下。Gallager隨機(jī)構(gòu)造法。Gallager的做法是用稀疏校驗(yàn)矩陣的隨機(jī)置換和級(jí)聯(lián)來(lái)模擬隨機(jī)碼。具體矩陣如下：其他方法如MacKay的隨機(jī)構(gòu)造法。還有高斯消去法、類(lèi)上三角矩陣的編碼等等。4MacKay的方法為：

23、保證列重固定，而行進(jìn)行均勻化的處理，并且要求交疊不超過(guò)1。高斯消元法是利用代數(shù)的方法。校驗(yàn)矩陣H給定后，H為MxN的矩陣，然后假設(shè)其滿秩。編碼后的碼字x需要滿足。根據(jù)這個(gè)屬性，一種常用的LDPC碼的直接編碼方法就是高斯消元法。利用高斯消元法將校驗(yàn)矩陣化為下圖的形式。x可以分為兩部分，s和p，分別表示系統(tǒng)位和信息位。編碼步驟如下：系統(tǒng)位s為要發(fā)送的N-M個(gè)信息比特；由于變換后的矩陣具有上三角矩陣的形式，所以校驗(yàn)比特p通過(guò)向后遞推的公式如下類(lèi)上三角矩陣的編碼是為了降低復(fù)雜度的。高斯消元法編碼復(fù)雜度很高，考慮利用校驗(yàn)矩陣的稀疏性來(lái)降低復(fù)雜度。為了保持校驗(yàn)矩陣的稀疏特性，只對(duì)校驗(yàn)矩陣進(jìn)行行列變換，得到

24、圖2.4形式的類(lèi)上三角矩陣。設(shè)變換后的校驗(yàn)矩陣為：所有的子矩陣均可看做系數(shù)矩陣。為了得到遞推的公式，將校驗(yàn)矩陣做線性變換，左乘一個(gè)矩陣，變換后的矩陣為利用變換后的矩陣可以進(jìn)行校驗(yàn)位的遞推。將x分為三部分，s表示系統(tǒng)比特，表示校驗(yàn)比特。兩部分校驗(yàn)比特的遞推公式如下：上式中所有的矩陣仍為稀疏矩陣，進(jìn)一步分析可以得出的計(jì)算復(fù)雜度分別為.在g很小的時(shí)候，運(yùn)算復(fù)雜度和碼長(zhǎng)成線性關(guān)系。2.2和積算法原理LDPC碼的譯碼方法有硬判決譯碼和軟判決譯碼方法。對(duì)于LDPC碼來(lái)說(shuō)，主要的硬判決譯碼算法有比特翻轉(zhuǎn)（Bit-Flipping,BF）算法以及在此基礎(chǔ)上進(jìn)行改進(jìn)的算法。比特翻轉(zhuǎn)算法屬于硬判決譯碼，是通過(guò)基于

25、Tanner圖的信息傳遞來(lái)進(jìn)行譯碼，最先有Gallager提出?；赥anner圖的信息傳遞的比特翻轉(zhuǎn)算法的基本過(guò)程是：在每一次迭代過(guò)程中根據(jù)某一種準(zhǔn)則決定將其中的某一個(gè)比特進(jìn)行翻轉(zhuǎn)，直至迭代過(guò)程結(jié)束或者校驗(yàn)方程全部滿足。這種譯碼算法的核心在于確定比特翻轉(zhuǎn)的準(zhǔn)則，如Gallager最初提出的BF算法，準(zhǔn)則是不滿足校驗(yàn)方程個(gè)數(shù)最多的比特進(jìn)行翻轉(zhuǎn)，后來(lái)提出的加權(quán)算法主要是在翻轉(zhuǎn)準(zhǔn)則加入變量節(jié)點(diǎn)可靠性度量，改進(jìn)算法主要是在檢測(cè)翻轉(zhuǎn)過(guò)程中防止出現(xiàn)翻轉(zhuǎn)成環(huán)的現(xiàn)象，這些改進(jìn)都進(jìn)一步提高了性能，而沒(méi)有增加復(fù)雜度。下面具體介紹比特翻轉(zhuǎn)算法。本文采用的是和積算法3。原理如下：首先介紹因子圖。因子圖是一種用于描述

26、多變量函數(shù)的方法。一般來(lái)說(shuō)，在因子圖中存在兩種節(jié)點(diǎn)，一種是變量節(jié)點(diǎn)，一種是函數(shù)節(jié)點(diǎn)。如下所示：一個(gè)函數(shù)g（x），通?？梢詫?xiě)為如下形式：寫(xiě)成和積算法的形式就是：下面介紹具體算法步驟：這是一種迭代算法，所以通常需要好幾輪迭代才能完成。調(diào)制后每一個(gè)碼字c=（c1，c2，.）映射為傳輸序列s，然后s通過(guò)信道，接收到的序列為y，根據(jù)y， 首先介紹所用到的有關(guān)符號(hào)的含義：1、 初始化計(jì)算信道傳遞給比特借點(diǎn)的初始概率。然后對(duì)每一個(gè)比特借點(diǎn)i和與其相鄰的校驗(yàn)借點(diǎn)，設(shè)定比特借點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的初始消息為當(dāng)在AWGN信道中采用BPSK調(diào)制時(shí)，碼字 映射為傳輸序列,接收端碼字為信源等概率分布,此時(shí)概率BP譯碼的初始消

27、息為2、 迭代處理步驟1：校驗(yàn)節(jié)點(diǎn)消息處理對(duì)所有的校驗(yàn)節(jié)點(diǎn)j和與其相鄰的比特節(jié)點(diǎn)i，第L次迭代時(shí)，計(jì)算第j個(gè)校驗(yàn)節(jié)點(diǎn)傳向第i個(gè)比特節(jié)點(diǎn)的消息步驟2：比特節(jié)點(diǎn)消息處理對(duì)所有的比特節(jié)點(diǎn)i和與其相鄰的校驗(yàn)節(jié)點(diǎn)j，計(jì)算第i個(gè)消息其中是校正因子，使步驟3：譯碼判決對(duì)所有比特節(jié)點(diǎn)計(jì)算硬判決消息其中是校正因子，使若3、停止若或者達(dá)到最大迭代次數(shù)，則結(jié)束運(yùn)算，否則從步驟1繼續(xù)迭代。第三章 仿真分析3.1仿真結(jié)果分析：我們采用的是C語(yǔ)言平臺(tái)和MATLAB平臺(tái)，SNR為0到5dB，第一幅圖為BER曲線，第二幅圖為FER曲線，采用的是置信度傳播算法。通過(guò)在MATLAB中調(diào)用C語(yǔ)言的譯碼程序完成。由于MATLAB要先

28、轉(zhuǎn)化為C語(yǔ)言才進(jìn)一步編譯，所以理論上MATLAB的編譯碼效率更低。仿真的結(jié)果確實(shí)驗(yàn)證了這個(gè)結(jié)論。我們從最后一個(gè)圖可以看到，C語(yǔ)言的仿真要比MATLAB快了一倍。 圖3.1 BER 曲線圖3.2 幀差錯(cuò)率曲線3.2 C語(yǔ)言和MATLAB語(yǔ)言的仿真對(duì)比：同時(shí)，我們還對(duì)比了C語(yǔ)言和MATLAB語(yǔ)言下的編譯碼速度（低SNR情況下）:SNR0123BER0.121220.0712140.019210.00242C20 sFER0.967740.769230.352940.06237BER0.121220.0712140.019210.00242Matlab 56 sFER0.967740.769230.

29、352940.06237 并且，我們還發(fā)現(xiàn)，隨著SNR的提高，譯碼的時(shí)間不是線性增長(zhǎng)的，例如，為5dB時(shí)，譯碼完成時(shí)間為448.5972秒。第四章 總結(jié)與展望本文對(duì)C語(yǔ)言和MATLAB語(yǔ)言下的LDPC編碼效率有了一個(gè)新的認(rèn)識(shí)，發(fā)現(xiàn)基于C語(yǔ)言的LDPC碼編碼效率有明顯的優(yōu)勢(shì)，對(duì)以后的工作做了一些鋪墊。參考文獻(xiàn)1C.E.Shannon.A mathematical theory of communication.BSTJ,27:379423,July and:623656,Dct.19482S.Lin and D.J.Costello.(王育民，王新梅譯).差錯(cuò)控制編碼：基礎(chǔ)與應(yīng)用.北京：人民郵電

30、出版社，19863G.D.Forney,Jr.Concatenated codes.Sc.D.Thesis,M.I.T.,Cambridge,Mass,1965,also MIT Press Research Monograph 37,19664王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼：原理與應(yīng)用.西安：西安電子科技大學(xué)出版社，19915F.J.Mac Williams and N.J.A.Sloane.The Theory of Error-Correcting Codes.New York,North-Holland,19776M.A.Tsfasman,S.G.Vladut and T.Zink.Modul