1、LDPC編碼原理LDPC碼是一種線性分組碼，它于1962年由Gallager提出，之后很長(zhǎng)一段時(shí)間沒(méi)有收 到人 們的重視。直到1993年Berrou等提出了 turbo碼，人們發(fā)現(xiàn)turbo碼從某種角度上說(shuō) 也是一種 LDPC碼，近幾年人們重新認(rèn)識(shí)到LDPC碼所具有的優(yōu)越性能和巨大的實(shí)用價(jià)值。1996年MacKay 和Neal的研究表明采用LDPC長(zhǎng)碼可以達(dá)到turbo碼的性能，而最近的研究表明，被優(yōu)化了的 非規(guī)則LDPC碼采用可信傳播（Belief Propagation）譯碼算法時(shí)，能得 到比turbo碼更好的性能。和另一種近Shannon限的碼 Turbo碼相比較，DLPC碼主要有以下幾

2、個(gè)優(yōu)勢(shì)：1. LDPC碼的譯碼算法，是一種基于稀疏矩陣的并行迭代譯碼算法，運(yùn)算量要低于Turbo碼 譯碼算法，并且由于結(jié)構(gòu)并行的特點(diǎn)，在硬件實(shí)現(xiàn)上比較容易。因此在大容量通信應(yīng)用中，LDPC 碼更具有優(yōu)勢(shì)。2. LDPC碼的碼率可以任意構(gòu)造，有更大的靈活性。而Turbo碼只能通過(guò)打孔來(lái)達(dá)到高碼 率，這樣打孔圖案的選擇就需要十分慎重的考慮，否則會(huì)造成性能上較大的損失。3. LDPC碼具有更低的錯(cuò)誤平層，可以應(yīng)用于有線通信、深空通信以及磁盤(pán)存儲(chǔ)工業(yè)等對(duì)誤碼 率要求更加苛刻的場(chǎng)合。而Turbo碼的錯(cuò)誤平層在10-6量級(jí)上，應(yīng)用于類似場(chǎng)合中，一般需要和 外碼級(jí)聯(lián)才能達(dá)到要求。LDPC碼的劣勢(shì)在于：硬件資

3、源需求比較大。全并行的譯碼結(jié)構(gòu)對(duì)計(jì)算單元和存儲(chǔ)單元的需求都很大。編碼比較復(fù)雜，更好的編碼算法還有待研究。同時(shí)，由于需要在碼長(zhǎng)比較長(zhǎng)的情況才能充分4. LDPC碼是上個(gè)世紀(jì)六十年代發(fā)明的，現(xiàn)在，在理論和概念上不再有什么秘密，因此 在知識(shí) 產(chǎn)權(quán)和專利上不再有麻煩。這一點(diǎn)給進(jìn)入通信領(lǐng)域較晚的國(guó)家和公司，提供了一個(gè)很好的發(fā)展機(jī) 4 Zx 02.而體現(xiàn)性能上的優(yōu)勢(shì)，所以編碼時(shí)延也比較大。3.相對(duì)而言出現(xiàn)比較晚，工業(yè)界支持還不夠。目前，LDPC碼被認(rèn)為是迄今為止性能最好的碼。LDPC碼是當(dāng)今信道編碼領(lǐng)域的最令 人矚目 的研究熱點(diǎn)，近幾年國(guó)際上對(duì)LDPC碼的理論研究以及工程應(yīng)用和VLSI（超大規(guī)模集成電路）

4、實(shí)現(xiàn) 方面的研究都已取得重要進(jìn)展。基于LDPC碼的上述優(yōu)異性能可廣泛應(yīng)用于光通信、衛(wèi)星通信、深空通信、第四代移動(dòng)通信系統(tǒng)、高速與甚高速率數(shù)字用戶線、光和磁記錄系統(tǒng) 等。LDPC碼可以用非常稀疏的校驗(yàn)矩陣或二分圖來(lái)描述，也就是說(shuō)LDPC碼的校驗(yàn)矩陣的矩陣元 除一小部分不為0外，其它絕大多數(shù)都為Oo通常我們說(shuō)一個(gè)（n,j,k）LDPC碼是指其碼長(zhǎng)為n,其奇偶 校驗(yàn)矩陣每列包含j個(gè)1,其它元素為0 ;每行包含k個(gè)1,其它 元素為0。j和k都遠(yuǎn)遠(yuǎn)小于n,以滿 足校驗(yàn)矩陣的低密度特性。校驗(yàn)矩陣中列和行的個(gè)數(shù)即j和k為固定值的LDPC碼稱為規(guī)則碼，否則 稱為非規(guī)則碼。一般來(lái)說(shuō)非規(guī)則的性能優(yōu)于規(guī)則碼。LDP

5、C碼所面臨的一個(gè)主要問(wèn)題是其較高的編碼復(fù)雜度和編碼時(shí)延。對(duì)其采用普通的編碼方法, LDPC碼具有二次方的編碼復(fù)雜度，在碼長(zhǎng)較長(zhǎng)時(shí)這是難以接受的，幸運(yùn)的是校驗(yàn)矩陣稀疏性使得 LDPC碼的編碼成為可能。目前，好的編碼方法一般有如下幾種情況：1、TJRichardson和R.LUrbanke給出了利用校驗(yàn)矩陣的稀疏性對(duì)校驗(yàn)矩陣進(jìn)行一定的預(yù)處 理后, 再進(jìn)行編碼。2、設(shè)計(jì)LDPC碼時(shí)，同時(shí)考慮編碼的有效性，使H矩陣具有半隨機(jī)矩陣的格式。3、H矩陣具有某種不變特性所采用的其他編碼方法，例如基于刪除譯碼算法 提出的編碼方案。LDPC碼的應(yīng)用所面這幾種編碼方案都是在線性時(shí)間內(nèi)編碼的有效算法，初步解決了臨的一

6、個(gè)主要問(wèn)題。下面對(duì)這幾種編碼方案作一些簡(jiǎn)單的說(shuō)明。Richardson等提出的有效編碼方案：LDPC碼的直接編碼方法就是利用高斯消去法，產(chǎn)生一個(gè)下三角矩陣，然后進(jìn)一步初等變換得到右邊單位陣形式H=P| ,由G= I I P得到生成矩陣，從而由C=M*G直接編碼。這樣的編碼方法是復(fù)雜的，主要原因是由于高斯消去法破壞了原有奇偶校驗(yàn)矩陣的稀疏性。為了保持矩陣的稀疏性，Richards on提出了有效編碼方案，首先可以對(duì)矩陣的列做重排，這樣雖然不能得到一個(gè)完全的下三角形式的矩陣，但可以獲得一個(gè)近似的下三角矩陣。如圖所示，分成六個(gè)分塊的稀疏矩陣，其中g(shù)是一個(gè)相當(dāng)小的數(shù)。如下圖所示:對(duì)于要發(fā)送的信息序列，

7、依然直接作為 LDPC碼字的前NM個(gè)信息位比特輸出，對(duì)于我們將得到以下的兩其生成的校驗(yàn)比特，將其分成兩塊p1,p2, v=u,p1,p2,根據(jù)H?vT = O,個(gè)關(guān)系式Au Bp： Tp；ETA C u：ETBPl 0由(1)式乘以七1再加上(2)式，我們可以得到式(3)如下:ETA C 屮ETBTP1 0通過(guò)(3)式求出p1代入(1)式，就可以得到p2,從而完成編碼過(guò)程。所以編碼復(fù)雜度的分析，因?yàn)檫@六個(gè)分塊陣是通過(guò)對(duì)原有稀疏矩陣的列做重排獲得的，這些分塊陣依然滿足稀疏性，我們可以進(jìn)一步分析出求解P1和P2的運(yùn)算量分別為0 (N + g2 )和ON。由此可以看出，當(dāng)g盡量小的時(shí)候，LDPC碼的

8、編碼運(yùn)算量，就可以控制在線性復(fù)雜度附近。在特殊情況下，設(shè)計(jì)碼字時(shí)，考慮令-ET-1B + D,當(dāng)其為I陣時(shí)，又可以進(jìn)一步降低編碼的復(fù)雜度，此時(shí)編碼步驟可以參考如下：步驟1)計(jì)算AuT和CljT,步驟2）計(jì)算ET 1 AljT步驟3)計(jì)算P：步驟4)計(jì)算P：編碼結(jié)構(gòu)圖如下所示:定義校驗(yàn)矩陣 H已出，Hi是k*(n-k). hk是(n-k)*(n-k)；設(shè)計(jì)碼字時(shí)，令H2矩陣具有如下的形式:將生成的碼字V分成兩部分u,p,由GH T 0,可以得到IH :ihTO : 1 O 1 -1 * U代表信息比特,0,所以P H；p代表生成的校驗(yàn)比特。考慮G=I,P,H2L根據(jù)H2的特性可知，H2T可以由一

9、個(gè)特征多項(xiàng)式為f D 1/1 D的遞歸卷積碼來(lái)表示。此時(shí)編碼結(jié)構(gòu)如下圖所示:Ill1圖3這種編碼算法的缺點(diǎn)在于，H2矩陣存在列重為1的列，這對(duì)迭代譯碼過(guò)程不利，會(huì)產(chǎn)生誤碼平臺(tái)，可以通過(guò)改變這一列重的方法來(lái)優(yōu)化，降低誤碼平臺(tái)。二、編碼部分LDPC碼有很多種譯碼方法，本質(zhì)上大都是基于Tanner圖的消息迭代譯碼算法。根據(jù)消息迭代過(guò)程中傳送消息的不同形式，可以將LDPC的譯碼方法分為硬判決譯碼和軟判決譯碼。如果在 譯碼過(guò)程中傳送的消息是比特值，稱之為硬判決譯碼；如果在譯碼過(guò)程中傳送的消息是與后驗(yàn)概率相關(guān)的消息，稱之為軟判決譯碼，有時(shí)也稱為和積譯碼算法。硬判決譯碼計(jì)算比較簡(jiǎn)單，但性能稍差；軟 判決譯碼

10、計(jì)算比較復(fù)雜，但性能較好。為了平衡性能和計(jì)算復(fù)雜度，可以將兩者結(jié)合使用，稱為混合譯 碼算法。根據(jù)消息迭代過(guò)程中傳送的消息是否進(jìn)行了量化及量化所使用的比特?cái)?shù)，我們可以將譯碼方法 分為無(wú)量化譯碼和量化譯碼。硬判決譯碼可以看成是1比特量化譯碼，軟判決譯碼可以看成無(wú)窮多比特量 化譯碼，而混合譯碼可以看成變比特量化譯碼。從量化譯碼的角度看，硬判決譯碼和軟判決譯碼屬于同 一類譯碼方法，已有的研究表明，可以用3比特量化取得和和積譯碼算法非常接近的性能。目前主要的硬 判譯碼算法有一步大數(shù)邏輯譯碼算法（MLG ） , Gallager提出的比特翻轉(zhuǎn)算法（BF）,加權(quán)的大數(shù)邏輯譯碼算法（WMLG ）,加權(quán)的比特翻

11、轉(zhuǎn)算法（WBF ）以及一些對(duì)以上幾種算法作改進(jìn)的 算法如IWBF等硬判譯碼算法；軟譯碼算法主要有迭代結(jié)構(gòu)的置信傳播算法（BP）（有時(shí)也稱之為和積算 法（SPA）,以及基于標(biāo)準(zhǔn)BP算法，對(duì)信息進(jìn)行部分處理，降低譯碼復(fù)雜度的譯碼算法，如UMP BP-based算法（mirvsum算法），Normlized BP-based算法，還有基于最優(yōu)化理論的譯碼算法如線性 規(guī)化算法（LP ） 下面對(duì)譯碼算法作簡(jiǎn)單的介紹：一、硬判譯碼算法LDPC 碼。一步大數(shù)邏輯譯碼算法，主要原理是根據(jù)通過(guò)一系列的正交方程，比較校驗(yàn)結(jié)果1和0的數(shù)目來(lái)完成 譯碼過(guò)程。這種譯碼算法譯碼結(jié)構(gòu)簡(jiǎn)單，復(fù)雜度較低，但是應(yīng)用場(chǎng)合有限，只適

12、用于某些碼結(jié)構(gòu)比較特殊 的碼字，如有限幾何基于Tanner圖的信息傳遞的比特翻轉(zhuǎn)算法，在每一次迭代過(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)成壞的現(xiàn)象，這些改進(jìn)都進(jìn)一步提高了性能，而沒(méi)有增加復(fù)雜度。二、軟判譯碼算法軟判譯碼算法主要包含BP算法及其簡(jiǎn)化形式，LP算法等。BP算法中消息的傳遞形式是對(duì)數(shù)似然比（LLR）,

13、在迭代過(guò)程中，每次在變量結(jié)點(diǎn)和校驗(yàn)結(jié)點(diǎn)分別按照和規(guī)則與tanh規(guī)則更新節(jié)點(diǎn)的信息。直至譯碼結(jié)束或者校驗(yàn)方程全滿足。BP算法適用于各類信道，具有逼近香農(nóng)限的優(yōu)異性能，但校驗(yàn)節(jié)點(diǎn)的消息計(jì)算復(fù)雜度非常復(fù)雜，為了簡(jiǎn)化 校驗(yàn)節(jié)點(diǎn)的消息計(jì)算，人們提出了很多簡(jiǎn)化算法，女口UMP （mimsum）譯碼算法就是一個(gè)有代表性的簡(jiǎn)化算法，另外為了保證性能上接近與BP算法，以提出了歸一化的BP算法。各種譯碼 簡(jiǎn)化譯碼算法的目的就是在計(jì)算復(fù)雜度、譯碼性能及譯碼時(shí)延等方面取得最 優(yōu)的折中。線性規(guī)化算法（LP ）是基于最優(yōu)化理論提出的一種新的譯碼算法，主要思想是可以把譯碼問(wèn)題看作 一個(gè)整數(shù)優(yōu)化問(wèn)題，通過(guò)對(duì)約束條件的放縮，形

14、成一個(gè)簡(jiǎn)單的線性規(guī)化問(wèn)題，利用最優(yōu)化理論的知識(shí)完成 譯碼。這種譯碼算法的好處在于譯碼復(fù)雜度是線性的，性質(zhì)便于分析，開(kāi)拓了新的譯碼思路。以下分別從性能與譯碼復(fù)雜度兩個(gè)角度分析比較各種譯碼算法，如圖及表所示：3 Um10102*10*210*圖4.TYPE2-D(1023,781 )EG_LDPC碼的在不同譯碼算法下性能曲線圖unasxfed BPSKBPUM P BP baBd mlni-Hini) Normal!?&d BPbasediNoirnak2ed APPGaBAgsZBFweifiMed： BFAlgortihm woiil Imp dMecbon A co-nm 濟(jì)kx) p cjelecticin譯碼算法乘法次數(shù)除法次數(shù)加法次數(shù)標(biāo)準(zhǔn)BP算法11 Nwc 6 N MN Wc 1N 3wc 1NormalizedBP-based 算法0Nwc4N Wc 1 N Iog2 2wc / 2UMP BP-based 算法004N Wc 1 N Iog2 2wc /