LDPC碼的編譯碼原理及編碼設(shè)計

代號學(xué)號

分類號密級

題（中、英文）目LDPC碼的編譯碼原理及編碼設(shè)計

_______PrinciplesandCode-DesignofLDPCCodes

作者姓名...........指導(dǎo)教師姓名'職務(wù).................

學(xué)科門類..........學(xué)科'專業(yè)..............................

提交論文日期

LDPC碼的編譯碼原理及編碼設(shè)計

作者:

導(dǎo)師:

學(xué)科:

摘要

低密度校驗碼以其低復(fù)雜度的迭代譯碼算法和可逼近信道容量限而成為目前最佳的

編碼技術(shù)之一，越來越受到眾多編碼研究學(xué)者的關(guān)注。本文在對低密度校驗碼現(xiàn)有理論

的研究基礎(chǔ)上，系統(tǒng)地分析了低密度校驗碼在刪除信道下的糾錯性能和度序列設(shè)計、低

密度校驗碼的圍長設(shè)計和快速編碼設(shè)計等編碼設(shè)計問題，獲得了一些研究成果，主要概

括為：

1.系統(tǒng)地闡述了低密度校驗碼基于圖模型的編譯碼思想，介紹了密度進(jìn)化理論，

對影響低密度校驗碼糾錯性能的兩個主要因素一一度序列設(shè)計和圍長設(shè)計進(jìn)行

了深入分析；

2.闡述了應(yīng)用于刪除信道下的糾刪碼基本原理，介紹了兩類標(biāo)準(zhǔn)的RS碼類糾刪

碼，重點(diǎn)分析了具有線性時間編碼和恢復(fù)算法的漸近好碼一級聯(lián)型低密度糾刪

碼，分析了正則度分布的閾值，對正則低密度校驗碼在刪除信道下的糾錯性能

進(jìn)行了仿真，從理論上證明了基于（乩2d）-正則度序列的低密度糾刪碼都不是

漸近最優(yōu)碼"23）,同時還分析了非正則低密度校驗碼的度序列設(shè)計，基于右

邊正則序列提出了一種改進(jìn)型右邊正則序列，證明了此序列為漸近擬最優(yōu)的，

對基于幾類現(xiàn)有典型度分布序列的級聯(lián)型低密度糾刪碼進(jìn)行了模擬仿真及性能

分析；

3.研究了現(xiàn)有的具有較大圍長的低密度校驗碼設(shè)計方法，提出了一種新的構(gòu)造具

有較大圍長的正則低密度校驗碼方法并對其在高斯信道下的糾錯性能進(jìn)行了仿

真，提出了漸進(jìn)邊增長算法的改進(jìn)算法，使采用改進(jìn)后的算法構(gòu)造的低密度校

驗碼能夠嚴(yán)格滿足給定的度序列分布；

4.對低密度校驗碼的快速編碼問題進(jìn)行了深入研究，指出了旋風(fēng)碼和重復(fù)累積碼

能夠達(dá)到線性編碼的原因及其與可快速編碼的低密度校驗碼之間的關(guān)系，提出

了兩種可線性編碼的低密度校驗碼的構(gòu)造方法并對其在高斯信道下的糾錯性能

進(jìn)行了仿真。

關(guān)鍵詞：低密度校驗碼刪除信道圖模型度分布序列圍長高斯信

道快速編碼

ABSTRACT

Low-densityparity-checkcodescometobeoneofthebestcodingtechnologiesbecause

oftheirlow-complicityiterativedecodingalgorithmandcapacityapproachingperformance,

andtheyattractmoreandmoreresearchers9eyesinrecentyears.Inthisdissertation,thebasic

principlesofthecodinganddecodingofLDPCcodesarestudiedsystematically,andsome

code-designproblemssuchasthedesignofdegreedistributionsequences,thedesignofgirths

andthedesignofefficientencode-ableLDPCcodesareanalyzedindetail.Basedonallthese

efforts,somepositiveresultsareobtainedandsummarizedasfollow:

1.Thecodinganddecodingideasoflow-densityparity-checkcodesongraphsare

systematicallysummarized,andthedensityevolutiontheoryisintroduced.Thetwoleading

factorsontheperformanceofLDPCcodes,i.e.thedegreedistributionsequencesandthe

girthsofthesecodes,areanalyzedindetail;

2.TheprinciplesofErasurecodesusedunderBinaryErasureChannelsaresummarized

andErasurecodeswhichbelongtostandardclassesofRScodesareintroducedwithemphasis

oncascadedlow-densityerasurecodeswithlineartimeencodinganderasurerecover

algorithms.Thresholdsofregulardegreedistributionsareanalyzed.Itisshownthatlow-density

erasurecodesbasedon(d,2d)-regularsequencesofdegreedistributionarenotcloseto

optimal(d>3).Twoparesofirregulardegreedistributionsequencesareintroducedandapare

ofimprovedrightregularsequencesoflow-densityerasurecodesarepresented,Itistestified

thatthenewsequencesareasymptoticallyquasi-optimal.Inthemeantime,simulationsof

cascadedlow-densityerasurecodesbasedonafewtypesofspecialsequencesofdegree

distributionavailablearegiven,togetherwithperformanceanalysesonthesecodes.

3.TheavailabledesignmethodsofLDPCcodeswithlargegirthareintroducedanda

newconstructionofregularLDPCcodeswithlargegirthisbroughtalongwithitsrealization

algorithm,andtheperformancesoftheLDPCcodesgeneratedbythismethodareanalyzed

andsimulatedunderAWGNchannels.ImprovedProgressiveEdge-Growthalgorithmis

presentedbywhichtheLDPCcodesgeneratedcansatisfythegivendegreedistribution

strictly.

4.TheefficientencodingproblemofLDPCcodesisdiscussedindetail,andthereasons

thatTornadocodesandrepeataccumulatecodesarelinearencode-ableandtherelationships

betweenthemandefficientencode-ableLDPCcodesarepresented.Twoconstructionsof

linearencode-ableLDPCcodesarebroughtupandtheirperformancesunderAWGN

channelsaresimulated.

in

Keywords:lowdensityparity-checkcodeserasurechannelgraphmodel

degreedistributionsequencesgirthAWGNchannel

efficientencoding

IV

目錄

第一章緒論............................................................1

1.1數(shù)字通信系統(tǒng)與信道模型...........................................1

1.1.1數(shù)字通信系統(tǒng)...............................................1

1.1.2信道模型...................................................2

1.2糾錯編碼理論及其發(fā)展.............................................3

1.3低密度校驗碼的提出、發(fā)展和現(xiàn)狀....................................5

1.4本文主要研究工作及內(nèi)容安排.......................................6

第二章LDPC碼的編譯碼原理...........................................7

2.1LDPC碼的定義及其Tanner圖表示...................................7

2.1.1LDPC碼的定義及其描述......................................7

2.1.2LDPC碼的Tanner圖表示及非正則LDPC碼......................8

2.2LDPC碼的譯碼....................................................9

2.2.1LDPC碼的譯碼思想..........................................9

2.2.2BIAWGN信道下的算法描述...................................12

2.2.3BSC信道下的算法描述.......................................13

2.2.4BEC信道下的算法描述.......................................14

2.3LDPC碼的性能分析..............................................15

2.3.1LDPC碼的度序列設(shè)計及密度進(jìn)化理論.........................15

2.3.2LDPC碼的圍長設(shè)計..........................................17

2.4本章小結(jié)........................................................18

第三章刪除信道下的LDPC碼.........................................19

3.1糾刪碼及其發(fā)展..................................................19

3.1.1刪除信道和糾刪碼...........................................19

3.1.2RS碼類糾刪碼..............................................21

3.1.3低密度糾刪碼...............................................21

3.2刪除信道下的密度進(jìn)化理論........................................23

3.2.1密度進(jìn)化理論的直接描述.....................................23

3.2.2密度進(jìn)化理論的微分方程描述.................................25

3.3正則LDPC碼在刪除信道下的性能..................................27

3.3.1正則LDPC碼閾值的唯一存在性分析...........................25

v

3.3.2一類正則LDPC碼的性能分析...............................25

3.4非正則LDPC碼在刪除信道下的性能...............................31

3.4.1Heavy-Tail/Poisson度序列分布................................31

3.4.2右邊正則度序列分布.........................................32

3.5基于改進(jìn)型的右邊正則度序列設(shè)計..................................34

3.5.1改進(jìn)型右邊正則度序列設(shè)計...................................34

3.5.2改進(jìn)型右邊正則度序列的性能分析.............................35

3.6本章小結(jié)........................................................38

第四章LDPC碼的圍長研究............................................39

4.1現(xiàn)有的幾種圍長設(shè)計方法..........................................39

4.1.1一種基于RS碼的代數(shù)構(gòu)造方法................................39

4.1.2一種基于矩陣分裂的代數(shù)構(gòu)造方法.............................40

4.1.3一種啟發(fā)式搜索方法一PEG構(gòu)造方法..........................41

4.2一種具有較大圍長的正則LDPC碼構(gòu)造方法..........................42

4.3PEG算法研究....................................................47

4.4本章小結(jié)........................................................48

第五章LDPC碼的快速編碼研究.......................................49

5.1LDPC碼的快速編碼..............................................49

5.2兩類可快速編碼的碼類............................................51

5.2.1Tornado碼及其編碼..........................................51

5.2.2重復(fù)累積碼及其編碼.........................................52

5.3可線性編碼的LDPC碼構(gòu)造.........................................52

5.3.1直接構(gòu)造法.................................................52

5.3.2刪除構(gòu)造法.................................................53

5.4關(guān)于線性編碼的幾點(diǎn)設(shè)想...........................................55

5.5本章小結(jié)........................................................56

結(jié)束語..................................................................57

致謝....................................................................59

參考文獻(xiàn)................................................................61

碩士期間完成的論文和科研工作........................................65

VI

_____________________________________第一章緒論_________________________________1

第一章緒論

本章首先簡要介紹了數(shù)字通信系統(tǒng)及信道模型，回顧了信道編碼理論與技術(shù)的發(fā)展

歷程，然后概述了低密度校驗碼的提出、發(fā)展和研究現(xiàn)狀，最后總結(jié)了作者在攻讀碩士

學(xué)位期間的研究工作，給出了全文的內(nèi)容安排。

1.1數(shù)字通信系統(tǒng)與信道模型

1.1.1數(shù)字通信系統(tǒng)

通信系統(tǒng)的基本目的在于將信息由信源高效、可靠、有時還需安全地傳送到信宿。

有擾通信信道中的噪聲會不可避免地對傳輸信息產(chǎn)生不同程度的干擾，從而可能降低通

信可靠性。所以通信系統(tǒng)設(shè)計的核心問題就是在存在隨機(jī)噪聲的信道中如何克服干擾，

減小信息傳輸?shù)牟铄e，同時又不降低信息傳輸?shù)男?，即如何解決系統(tǒng)的有效性與可靠

性之間的矛盾。一般地，通信系統(tǒng)的可靠性用誤比特率（BER）來衡量，其有效性則用

信息傳輸速率R比特/信道符號來衡量。早期的人們普遍認(rèn)為山：通信系統(tǒng)的可靠性與有

效性之間是一對不可調(diào)和的矛盾，一方的改善總是以犧牲另一方為代價，并指出當(dāng)功率

受限時，在有擾通信信道上實現(xiàn)任意小錯誤概率的信息傳輸?shù)奈ㄒ煌緩骄褪前研畔鬏?/p>

速率降低至零。Shannon信息和編碼理論的奠基性論文“通信的數(shù)學(xué)理論”于1948年發(fā)

表之后⑵，改變了這一觀點(diǎn)。他首次闡明了在有擾信道上實現(xiàn)可靠通信的方法，指出實

現(xiàn)有效而可靠地信息傳輸?shù)耐緩骄褪峭ㄟ^編碼。根據(jù)Shannon的信息理論，數(shù)字通信系

統(tǒng)的基本組成如圖1.1所示⑶⑷⑸。

圖1.1數(shù)字通信系統(tǒng)模型

Shannon的信息理論從通信系統(tǒng)的整體最佳化來研究信息的傳輸和處理。比特是一

種通用的信息表示形式，它本身并不依賴于信源或信道特征。這就允許我們分別設(shè)計圖

1」所示的兩個階段的信息處理，即信源編碼和信道編碼。Shannon不失最佳性地證明了

這種分離性⑵⑶。

2LDPC碼的編譯碼研究及編碼設(shè)計

1.1.2信道模型

圖1」中的信道部分只是信息傳輸所通過媒介的一種抽象，實際的信道是多種多樣

的，如電纜、光纜、存儲設(shè)備、甚至我們所處的實際空間及外太空等等。對于通信系統(tǒng)

設(shè)計者來講，了解系統(tǒng)中信道的特性是必需的。根據(jù)信道的輸入輸出的取值連續(xù)與否可

以將其分為離散信道、連續(xù)信道和離散輸入/連續(xù)輸出信道；根據(jù)信道統(tǒng)計特性是否隨時

間改變可以將其分為平穩(wěn)信道和非平穩(wěn)信道；根據(jù)信道的輸出之間是否具有相關(guān)性可將

其分為記憶信道和無記憶信道；根據(jù)信道的特性對輸入端是否具有對稱性可以將其分為

對稱信道和非對稱信道。實際應(yīng)用中所涉及到的信道大多都是離散輸入的平穩(wěn)無記憶對

稱信道，下面給出幾種常用的編碼信道模型⑷⑸⑹［久

二進(jìn)制對稱信道（BSC）：輸入為二值變量0、1,輸出也為二值變量0、1,且傳

輸過程中發(fā)生錯誤（輸入為0輸出為1或輸入為1輸出為0）的概率與輸入無關(guān)；

二進(jìn)制刪除信道（BEC）：輸入為二值變量0、1,輸出或為輸入的二值變量0、1,

或為刪除E,且通常傳輸過程中不同輸入被刪除的概率相同；

二進(jìn)制輸入高斯信道（BIAWGN）：輸入為二值變量，輸出為連續(xù)變量，且信道中

的加性噪聲為服從N（0,02）的高斯隨機(jī)變量。

圖1.2至圖1.4給出了以上三種信道的模型圖。

圖1.2二進(jìn)制對稱信道（BSC）圖1,3二進(jìn)制刪除信道（BEC）

圖1.4二進(jìn)制輸入高斯信道（BIAWGN）

第一章緒論3

1.2信道編碼理論及其發(fā)展

圖1.1中的信道編譯碼部分是以特定的控制手段，引入適量冗余比特，以克服信息

在傳輸過程中受到的噪聲和干擾影響。根據(jù)Shannon提出的信道編碼定理，對任意一個

平穩(wěn)離散無記憶有噪聲信源，都有一個固定的量，稱之為信道容量，記做C。只要信息

的傳輸速率低于信道容量，就必然存在一種編碼方法，使得信息出現(xiàn)差錯的概率隨碼長

的增加趨于任意?。环粗?，當(dāng)信息傳輸速率超過信道容量時，則不存在這樣的編碼方法。

這就是著名的信道編碼定理，它給出了特定信道上信息傳輸速率的上確界。

定理1.1(信道編碼定理)：任意離散輸入無記憶平穩(wěn)信道存在信道容量。，對預(yù)

期的任一數(shù)據(jù)速率R<C和任一錯誤概率p>0,有可能設(shè)計一對編譯碼器，以保證該

信道中速率為R的數(shù)據(jù)傳輸具有小于p的譯碼錯誤概率。

信道編碼定理指出，在有擾信道中，只要信息傳輸速率小于信道容量，就有可能實

現(xiàn)任意可靠的信息傳輸。這個存在性定理提醒我們可以實現(xiàn)以接近信道容量的傳輸速率

進(jìn)行通信。但遺憾的是該定理采用的是非構(gòu)造性的證明方法，其中并沒有給出逼近信道

容量的碼的具體編譯碼方法。

Shannon在信道編碼定理的證明中引用了三個基本條件，即：

(1)、采用隨機(jī)的編碼方式；

(2)、碼字長度趨近于無窮大；

(3)、譯碼采用最佳的最大似然譯碼。

一般可將信道編譯碼器所使用的糾錯碼從性能上分為壞碼和好碼。所謂壞碼是指只

有將碼率降至零才能使誤碼率為任意小的編碼方式；而好碼又可以分為當(dāng)誤碼率任意小

時，碼率逼近信道容量限的非常好碼和碼率可達(dá)到的非零最大值小于信道容量限的一般

好碼。雖然Shannon指出一個隨機(jī)選擇的碼以很高的概率為好碼，但隨機(jī)碼的最大似然

譯碼的復(fù)雜度往往與碼長呈指數(shù)關(guān)系，即在誤碼率隨碼長趨于無窮而趨向于零的同時，

譯碼復(fù)雜度以指數(shù)增長，而在實際應(yīng)用中，只能夠使用以碼長多項式的時間和空間復(fù)雜

度內(nèi)完成編譯碼的糾錯碼，因而盡管一般的隨機(jī)碼是好碼，但不能看作是實用碼。

自信道編碼定理提出以來，如何構(gòu)造一個逼近信道容量限的實用好碼成了眾多研究

學(xué)者竟相研究的課題，并逐漸形成信息論的一個重要分支一一信道編碼理論。五十多年

來，人們構(gòu)造實用好碼的探索基本上是按照Shannon所引用的基本條件的后兩條為主線

展開的。雖然從理論上講，除了目前已知的碼外，幾乎所有的碼都是好碼，但到目前為

止，構(gòu)造出真正意義上的實用好碼還有較長的距離。雖然如此，通過眾多學(xué)者，特別是

有關(guān)數(shù)學(xué)和信息論學(xué)術(shù)界的研究人員五十多年的共同努力，目前已經(jīng)取得了很多成果。

下面對其進(jìn)行簡要概述。

糾錯碼⑸⑻從構(gòu)造方法上可分為分組碼(BlockCodes)和卷積碼(Convolutional

Codes)兩大部分。在分組碼方面，第一個分組碼是1950年發(fā)現(xiàn)的能糾正單個錯誤的

4LDPC碼的編譯碼研究及編碼設(shè)計

Hamming碼；在整個50年代，基于代數(shù)理論又發(fā)現(xiàn)了多個短碼長的分組碼，如1954年

Golay發(fā)現(xiàn)的Golay碼以及Reed和Muller發(fā)現(xiàn)的RM碼，Prange在1957年發(fā)現(xiàn)的循環(huán)碼

等。最有意義的是Bose和Ray-Chaudhuri在1960年及Hocuenghem在1959年分別獨(dú)立發(fā)

現(xiàn)的能糾正多個錯誤的BCH碼，以及Reed和Solomon在1960發(fā)現(xiàn)的非二進(jìn)制RS碼。實

際上，BCH碼可以看作是某個RS碼的子域子碼，而RS碼又可以看作是BCH碼的特例。

其后發(fā)現(xiàn)的分組碼主要有1970年的Goppa碼和1982年發(fā)現(xiàn)的代數(shù)幾何碼。在所有這些

分組碼中，除了Goppa碼和代數(shù)幾何碼中存在個別達(dá)到GV限的漸進(jìn)好碼外，其它均不是

好碼。分組碼的譯碼主要采用基于代數(shù)的硬判決譯碼。

卷積碼最早由Elias提出，早期被稱為樹碼(TreeCodes),現(xiàn)在稱為格圖碼

(TrellisCodes)或卷積碼。卷積碼具有動態(tài)格圖結(jié)構(gòu)，可用有限狀態(tài)機(jī)來描述其狀態(tài)。

由于缺乏有效的理論研究工具，對卷積碼的有效研究成果不是很多，目前性能好的卷積

碼的構(gòu)造方法主要借助于計算機(jī)搜索來獲得。卷積碼的譯碼一般采用概率譯碼，由于譯

碼算法的簡單、實用和易于實現(xiàn)，卷積碼被廣泛應(yīng)用于實際中。

1966年，F(xiàn)orney將分組碼和卷積碼結(jié)合起來，提出了級聯(lián)碼(Concatenated

Codes)的概念。級聯(lián)碼一般采用RS碼作為外碼，卷積碼作為內(nèi)碼。Forney的研究表

明，級聯(lián)碼在性能得到較大改善的情況下，其譯碼復(fù)雜度并不顯著增加。

根據(jù)對接收信號處理方式的不同，糾錯碼的譯碼可以分為硬判決譯碼和軟判決譯碼。

硬判決譯碼是基于傳統(tǒng)糾錯碼觀點(diǎn)的譯碼方法，解調(diào)器首先對信道輸出值進(jìn)行最佳硬判

決，再將判決結(jié)果送入譯碼器，譯碼器根據(jù)解調(diào)器的判決結(jié)果，利用碼字的代數(shù)結(jié)構(gòu)來

糾正其中的錯誤。而軟判決譯碼則充分利用了信道輸出的波形信息，解調(diào)器將匹配濾波

器輸出的一個實數(shù)值送入譯碼器，由于實數(shù)值包含了比硬判決更多的信道信息，譯碼器

能夠通過概率譯碼充分利用這些信息，從而獲得比硬判決譯碼更大的編碼增益。

總之，盡管隨機(jī)碼是理論上的好碼，但由于其編碼實現(xiàn)的困難性和無法承受的譯碼

復(fù)雜度而只被用做理論分析的工具，在信道編碼定理和后來的許多編碼理論成果中，代

數(shù)編碼理論始終占據(jù)了主導(dǎo)地位，使得傳統(tǒng)的信道編碼技術(shù)受到臨界速率(Critical

Rate),也稱做截止速率(CutoffRate)凡的限制⑷。

1993年Turbo碼⑼皿的提出被看作是信道編碼理論研究的重要里程碑。Berrou等人將

卷積碼和隨機(jī)交織器相結(jié)合，同時采用軟輸出迭代譯碼來逼近最大似然譯碼，取得了超

乎尋常的優(yōu)異性能，并一舉超越了截止速率，直接逼近Shannon提出的信道容量限。

Turbo碼是一種信道編碼理論界夢寐以求的可實用非常好碼，它的出現(xiàn)標(biāo)志著信道編碼

理論研究進(jìn)入了一個嶄新的階段。Turbo碼成功的根本原因在于其實現(xiàn)方案中長碼構(gòu)造

的偽隨機(jī)性是核心，它通過隨機(jī)交織器對信息序列的偽隨機(jī)置換實現(xiàn)了隨機(jī)編碼的思想,

從而為Shannon隨機(jī)編碼理論的應(yīng)用研究奠定了基礎(chǔ)。

隨著Turbo碼的深入研究，人們重新發(fā)現(xiàn)Gallager早在1962年提出的低密度校驗碼

11111121(LowDensityParity-CheckCodes,簡稱LDPC碼)也是一種具有漸進(jìn)特性的非常好

第一章緒論5

碼，它的譯碼性能同樣可以逼近Shannon信道容量限口31口4］口5山6］。由于LDPC碼具有在中

長碼長時超過Turbo碼的性能，并且具有譯碼復(fù)雜度更低，能夠并行譯碼及譯碼錯誤可

檢測等特點(diǎn)，成為目前信道編碼理論的研究熱點(diǎn)。研究表明，Turbo碼只是LDPC碼的一

個特例H7)［網(wǎng)說，兩者都是基于圖構(gòu)造的低密度碼，譯碼算法具有等價性，從而使兩者在

基于圖模型的編譯碼研究中得到了統(tǒng)一。

1.3低密度校驗碼的提出、發(fā)展和現(xiàn)狀

1962年，Gallager在他的博士論文中提出了二元正則LDPC碼，也被稱做Gallager碼

|n,oGallager證明了這類碼具有很好的漢明距離特性，是滿足GV限的漸進(jìn)好碼，在計算

樹上進(jìn)行/(xlog(log(N))(N為碼長)次后驗概率迭代譯碼可以獲得依碼字長度指數(shù)降

低的比特錯誤概率，但限于當(dāng)時的計算能力，LDPC碼被認(rèn)為不是實用碼，在很長一段

時間內(nèi)沒有受到人們的重視。

1981年，Tanner在他的一篇奠基性的文章中正式提出了用圖模型來描述碼字的概念,

從而將LDPC碼的校驗矩陣對應(yīng)到被稱為Tanner圖12?！车碾p向二部圖上。采用Tanner圖構(gòu)造

的LDPC碼，通過并行譯碼可以顯著地降低譯碼復(fù)雜度。Tanner還仔細(xì)分析了最小和算法

(Min-SumAlgorithm)與和積算法(Sum-ProductAlgorithm)兩種信息傳遞算法，證明

了基于有限無環(huán)Tanner圖的最小和譯碼算法與和積譯碼算法的最優(yōu)性。但

Tanner圖在實際當(dāng)中是采用隨機(jī)圖構(gòu)造的，其中不可避免地存在小環(huán)路現(xiàn)象，這些小的

環(huán)路會造成譯碼信息的重復(fù)傳遞，使譯碼過程中的消息之間不滿足獨(dú)立性假設(shè)，影響了

迭代譯碼算法的收斂性。

Turbo碼的發(fā)現(xiàn)重新引發(fā)了眾多學(xué)者對LDPC碼的研究興趣。MacKay和Neal利用隨機(jī)

構(gòu)造的Tanner圖研究了LDPC碼的性能，發(fā)現(xiàn)采用和積譯碼算法的正則LDPC碼具有和

Turbo碼相似的譯碼性能，在長碼時甚至超過了Turbo碼1⑹⑵1,這一結(jié)果引起了信道編碼

界的極大關(guān)注。此后，Davey和MacKay從減少Tanner圖上小環(huán)路的概念出發(fā)提出了基于

GF(q),q>2的LDPC碼122M23］,進(jìn)一步提高了LDPC碼的譯碼性能。

在MacKay和Neal重新發(fā)現(xiàn)LDPC碼優(yōu)異性能的同時，Spielman和Sipser提出了基于二

部擴(kuò)展圖的擴(kuò)展碼3H25H26M27］。在對擴(kuò)展碼的研究中，他們證明了一個隨機(jī)構(gòu)造的Tanner

圖以很大的概率為好的擴(kuò)展圖，而由好的擴(kuò)展圖構(gòu)造的線性糾錯碼是漸進(jìn)好碼，從而證

明了采用隨機(jī)Tanner圖構(gòu)造的LDPC碼以很大概率是漸進(jìn)好碼。Luby等人將采用非正則

Tanner圖構(gòu)造的擴(kuò)展圖用于刪除信道，稱之為Tornado碼網(wǎng)網(wǎng)。由于采用了非正則的

Tanner圖，Tornado碼具有更大的擴(kuò)展性和更好的收斂性，糾刪性能更強(qiáng)。此后，采用優(yōu)

化度序列設(shè)計的非正則Tanner圖被用于構(gòu)造LDPC碼，稱為非正則LDPC碼，與正則

LDPC碼相比,非正則LDPC碼的性能得到顯著的提高阿31］網(wǎng)33］［33

6LDPC碼的編譯碼研究及編碼設(shè)計

同時，Wiberg結(jié)合Turbo碼和網(wǎng)格圖的研究，將Tanner圖推廣到包含隱含狀態(tài)變量

的因子圖（FactorGraph）口利那叫對Turbo碼和LDPC碼的研究在因子圖的基礎(chǔ)上得到

統(tǒng)一。Wiberg對因子圖的研究發(fā)現(xiàn)，對任意給定系統(tǒng)，無環(huán)圖的狀態(tài)復(fù)雜度是最大的，

有環(huán)圖的狀態(tài)復(fù)雜度則會大大降低，從而證明了基于有環(huán)Tanner圖的LDPC碼具有較低

的譯碼復(fù)雜度。Wiberg同時還證明了最小和算法和和積算法在本質(zhì)上的同一性，在格圖

譯碼中，最小和算法退化為Viterbi譯碼算法，和積算法退化為BCJR譯碼算法。

近兩年，Richardson等人應(yīng)用密度進(jìn)化理論來測度LDPC碼的性能同361。Richardson

等人在對LDPC碼的研究中發(fā)現(xiàn)，譯碼信息的迭代傳遞過程中存在著譯碼閾值現(xiàn)象，即

當(dāng)信噪比大于譯碼閾值時，迭代譯碼可使誤碼率趨于零，反之無論采用多長的LDPC碼,

經(jīng)過多少次迭代譯碼，總存在一定的錯誤概率。應(yīng)用中心極限定理，Richardson等人證

明了有限隨機(jī)有環(huán)圖的譯碼閾值可以逼近無環(huán)圖的譯碼閾值。通過建立在無環(huán)圖上的密

度進(jìn)化理論，可以精確地計算無環(huán)圖上LDPC碼的譯碼閾值，分析其譯碼收斂條件，從

而近似估算有環(huán)Tanner圖上LDPC碼的性能。研究表明，譯碼閾值的大小與LDPC碼的構(gòu)

造參數(shù)密切相關(guān)，采用優(yōu)化度序列設(shè)計的非正則LDPC碼可以有效地改善閾值，因此密

度進(jìn)化理論可以用于指導(dǎo)LDPC碼的優(yōu)化設(shè)計。

Chung等通過對密度進(jìn)化理論的研究，進(jìn)一步提出了應(yīng)用高斯逼近原理來簡化譯碼

閾值計算和收斂性分析，從而使測度LDPC碼性能的模型由多參數(shù)動態(tài)系統(tǒng)的密度進(jìn)化

理論模型簡化為單一參數(shù)動態(tài)系統(tǒng)的高斯逼近模型網(wǎng)1133】。

1.4本文主要研究工作和內(nèi)容安排

作者結(jié)合國家和陜西省自然科學(xué)基金、“適合中國的4G及后3G中關(guān)鍵技術(shù)研究”

（與三星公司合作）及國家自然基金委和香港科技局聯(lián)合資助項目等科研課題，采用理

論分析和仿真相結(jié)合的方法，對LDPC碼的理論進(jìn)行了深入研究，取得了一些成果。全

文共六章，其余章節(jié)安排如下。

第二章系統(tǒng)地闡述了LDPC碼基于Tanner圖的編譯碼原理，分析了LDPC碼的各項

參數(shù)指標(biāo)對其性能的影響，給出了合理的解釋；第三章分析了正則LDPC碼在刪除信道

下的理論性能，證明了3,2d）正則碼都不是漸進(jìn)最優(yōu)碼，介紹了幾種非正則的度序列分

布函數(shù)，提出了一種改進(jìn)型的右邊正則度序列分布函數(shù)并對相應(yīng)LDPC碼在刪除信道下

的性能進(jìn)行了仿真；第四章介紹了圍長對LDPC碼性能的影響，提出了一種構(gòu)造具有較

大圍長的正則LDPC碼設(shè)計方法；第五章對LDPC碼的快速編碼實現(xiàn)進(jìn)行了分析，構(gòu)造

了兩種可實現(xiàn)線性編碼的LDPC碼并對它們在高斯信道下的性能進(jìn)行了仿真；最后對全

文的主要內(nèi)容和成果進(jìn)行了總結(jié)，并指出了進(jìn)一步研究的問題和需要做的工作。

第二章LDPC碼的編譯碼原理7

第二章LDPC碼的編譯碼原理

本章系統(tǒng)地概述了LDPC碼的定義及其Tanner圖表示，基于圖結(jié)構(gòu)闡述了LDPC碼

的譯碼思想，并給出了LDPC碼在幾種常見信道下的譯碼算法，隨后介紹了密度進(jìn)化理

論并對影響LDPC碼性能的幾個因素進(jìn)行了分析，指出了優(yōu)化方向，最后對本章進(jìn)行了

總結(jié)。

2.1LDPC碼的定義及其Tanner圖表示

2.1.1LDPC碼的定義及其描述

一個碼長為〃、信息位個數(shù)為左的線性分組碼可以由一個生成矩陣Gk〃來定義，信

息序列s.通過G被映射到碼字x=sGo線性分組碼也可以由一個一致校驗矩陣

來等效描述，所有碼字均滿足X-HT=0。校驗矩陣的每一行表示一個校驗約束

z,,其中所有非零元素對應(yīng)的碼元變量尤/構(gòu)成一個校驗集，用一個校驗方程表示；校驗

矩陣的每一列表示一個碼元變量參與的校驗約束，當(dāng)列元素不為零時，表示該碼元變量

參與了該行的校驗約束。碼元變量與校驗方程之間的關(guān)系稱為結(jié)構(gòu)。下面主要對二元

LDPC碼進(jìn)行討論。

LDPC碼是一種線性分組碼，它的名字來源于其校驗矩陣的稀疏性，即校驗矩陣中

只有數(shù)量很少的元素為“1”,大部分都是“0"。Gallager最早給出了正則LDPC碼的定義,

具體來講正則LDPC碼的校驗矩陣H滿足下面三個條件：

(1)、H的每行有0個“1”；

(2)、H的每列有2個“1”，2>3；

(3)、與碼長和H矩陣的行數(shù)相比，夕和4都很小。

T11110000000000000000/

,00001111000000000000CD

00

:0000000011110000000000

.0000000000001111000000

；00000000000000001111co

r1000100010001000000000

:0100010001000000100000

00

(0010001000000100010000

:0001000000I0001000i000

00

'00000001000100