歡迎添加微信互相交流學習哦！

項目源碼：https://gitee.com/oklongmm/biye

?

本科畢業設計（論文）

題
目?? ?LDPC碼性能研究

摘 要
?? ?信道編碼是數字通信系統的重要組成部分。LDPC信道編碼技術是編碼界的重要成果之一。1/2碼率的二元LDPC碼在AWGN信道下的性能距信息理論中的Shannon極限僅差0.0045dB，它是目前距Shannon極限最近的糾錯碼。Gallagar在1962年提出LDPC碼，1996年經過Mackey、Spielman和Wiberg等人的再發現后，LDPC碼以其性能優越、全并行迭代譯碼結構、便于硬件實現等優點，在無線通信、存儲工業等領域得到了廣泛應用。
?? ?校驗矩陣的構造是編碼的前提，本文采用了隨機構造法構造，并對矩陣的多種變換方法進行分析，比較了優缺點。譯碼算法是LDPC碼的關鍵，譯碼復雜度的大小直接影響系統的實現。主要分硬判決譯碼、軟判決和復合譯碼。設計中采用的譯碼方式是軟判決譯碼。
?? ?在性能分析方面，利用matlab仿真碼長、列重和迭代次數對LDPC碼性能的影響。仿真結果表明，在一定范圍內，LDPC碼長碼的誤碼性能優于短碼；碼長較小時，列重的增加會使性能變差，而對于長碼，列重在一定范圍內的增大會改善LDPC的誤碼性能；增加迭代次數會使誤碼率降低，但當迭代次數大到一定值時，誤碼率將不會再隨著迭代次數的增加而降低。

關鍵詞 LDPC碼 信道編碼 矩陣變換 性能分析 ?
Abstract
?? ?Channel coding is an important component for digital communication systems. LDPC channel coding technology is one important achievement of the encoding results. The performance of half of the binary bit-rate LDPC codes in AWGN channel only has a tap of 0.0045dB to the Shannon Limit that makes it be the latest error-correcting codes from the Shannon Limit. Gallager proposed LDPC codes in 1962, after Mackey and others re-discovered it in 1996, with best performance, completely decoding algorithm in parallel scheme and easily realized for hardware design, LDPC codes has already been widely used in many practical systems such as wireless communication system and storage system.
?? ?The construction of the Check matrix is a precondition for coding; the randomized method was used in this paper. Several ways to transform the matrix was discussed and being compared about the merits of each method. The decoding algorithm is the key to LDPC code and the complexity of decoding direct impact realization of the system. There are three kinds of decoding algorithms: hard-decision method, soft-decision methods and hybrid decoding. The hard-decision method was used in this design.
Based on studying the basic theory of LDPC codes, the impact of codes length, column weight and iteration times on BER performance of LDPC codes are demonstrated by computer simulation and theoretical analysis. The simulation experiment indicated that: LDPC codes long-code error performance is superior to short-code error performance, but when the code length reaches a certain value, and then increase the code length, BER of LDPC codes lower rate will be small. When the code length is small, increasing the column weight, LDPC codes performance will deteriorate; when code length is large enough, increasing the column weight, LDPC codes performance will be improved, but when the column weight reaches a certain value, as set out priority to increasing the performance of LDPC codes will be worse. To increase the number of decoding iterations, LDPC codes performance will be improved; but when the number of iterations is large enough, then increase the number of iterations, LDPC codes will no longer reduce the error rate.

key words?? ?LDPC codes?? ?channel coding?? ?matrix transformation?? ?performance analysis?? ?
?
目 錄

摘 要?? ?I
ABSTRACT?? ?II
第1章 緒論?? ?1
1.1 數字通信系統?? ?1
1.2 信道編碼理論及其發展?? ?2
1.3 低密度奇偶校驗碼的提出、發展和現狀?? ?4
第2章 預備知識?? ?7
2.1 線性分組碼?? ?7
2.2 信道容量和香農極限?? ?12
第3章 LDPC碼表示及編碼?? ?14
3.1 LDPC碼的定義及其TANNER圖表示?? ?14
3.1.1 LDPC碼的定義及其描述?? ?14
3.1.2 LDPC碼的Tanner圖表示?? ?15
3.2 二進制LDPC碼的編碼原理?? ?16
3.2.1 H矩陣的構造?? ?16
3.2.2 ?LDPC碼的編碼思想?? ?17
第4章 LDPC碼的譯碼思想?? ?22
4.1 軟判決譯碼算法?? ?22
4.1.1 Tanner圖解析法原理?? ?22
4.1.2 SPA算法原理?? ?24
4.1.3 對數域BP譯碼算法?? ?27
4.1.4 最小和（Min-Sum）譯碼算法（改進的對數域BP譯碼算法）?? ?28
4.2硬判決譯碼算法?? ?29
4.2.1 Gallager的比特反轉譯碼算法?? ?29
4.2.2 改進的比特反轉譯碼算法?? ?30
4.3 優化的基于加權錯誤校驗的LDPC比特反轉算法（IWVBF）?? ?31
第5章 程序流程分析?? ?33
5.1 主程序?? ?33
5.2 H矩陣生成?? ?34
5.3 編碼過程?? ?35
5.4 譯碼過程?? ?36
第6章 LDPC碼的性能分析?? ?37
6.1 碼長對LDPC碼性能的影響?? ?37
6.2 列重對LDPC碼性能的影響?? ?37
6.3 迭代次數對LDPC碼性能的影響?? ?38
6.4 H矩陣變換方法對性能的影響?? ?39
總結與展望?? ?43
參考文獻?? ?44
致 謝?? ?45
附 錄?? ?46

?
第1章 緒論
本章簡要介紹了數字通信系統，并對系統中的每一部分進行了功能性說明，介紹了信道編碼理論及其發展歷程，最后概述了低密度奇偶校驗碼的提出、發展和現狀。
1.1 數字通信系統
通信系統的基本目的在于將信息由信源高效、可靠、安全地傳送到信宿。在信息傳輸的過程中，信道中的噪聲會不可避免地對傳輸信息產生干擾，從而導致了可靠性的降低。所以，通信系統設計的核心問題在于如何克服信道中隨機噪聲對信號的干擾，減小信息傳輸產生的差錯，同時在最大程度上保證信息傳輸的效率，即如何解決系統有效性和可靠性的矛盾。一般地，通信系統的可靠性用誤比特率（BER）來衡量，其有效性則用信息傳輸速率R比特/信道符號來衡量。早期的人們普遍認為：通信系統的可靠性與有效性之間存在不可調和的矛盾，一方的改善總是以犧牲另一方為代價，并指出當功率受限時，在有擾通信信道上實現任意小錯誤概率的信息傳輸的唯一途徑就是把信息傳輸速率降低至零。Shannon信息和編碼理論的奠基性論文“通信的數學理論”于1948年發表之后，改變了這一觀點。他首次闡明了在有擾信道上實現可靠通信的方法，指出實現有效而可靠地信息傳輸的途徑就是通過編碼。根據Shannon的信息理論，數字通信系統的基本組成如圖1.1所示：

?
圖1.1 數字通信系統的基本組成

圖中，信源的作用為產生需要傳送的信息，信息可以是模擬信號也可以是數字信號。如果是模擬信號，在進入數字通信系統之前需要進行采樣和量化處理。
信源編碼器的主要作用是將信源發出的信息，例如語音、圖像或者是文字等原始的數據進行轉化，在保證通信質量的前提下，盡可能的通過對信號的壓縮，提高通信系統的有效性。以更少的符號來表示原始信息，使信息能夠更好的在傳輸媒介中進行傳輸。
信道編碼是在發送器和接收器之間實現信號可靠傳輸的必要手段之一。傳輸信道中存在的噪聲必然會對傳輸的信息引入失真和信號判決錯誤，因此需要采用差錯控制碼來檢測和糾正這些比特錯誤。信道編碼器的主要作用是通過對信源編碼后的信息加入冗余信息，使得接收方在收到信號后，可以通過信道編碼中的冗余信息進行前向糾錯，以保證通信系統的可靠性。
數字調制器的作用是使信息變成能夠適應信道傳輸的信號。信號經過調制器后進入物理信道進行傳輸。典型的物理信道包括有線信道、無線信道、光纖信道、衛星信道等，針對不同的信道設計通信系統時要有不同的考慮，如無線信道會收到多徑的影響而產生衰落，而衛星信道會受到信號功率衰減的影響等。
信號到達接收端后，通過數字解調器對接收到的調制信號序列或傳輸碼字進行最優估計，然后輸出數字編碼序列送到信道譯碼器。信道譯碼器對信息進行估計和判決，估計準則是根據編碼準則和信道特性而確定的，目的是最小化信道噪聲的影響。最后信源譯碼器根據信源編碼準則將得到的信道編碼器輸出的編碼信息序列經過相應的信源譯碼后，得到對原始信息序列的估計。
1.2 信道編碼理論及其發展
圖1.1中的信道編譯碼部分是以特定的控制手段，引入適量冗余比特，以克服信息在傳輸過程中受到的噪聲和干擾影響。根據Shannon提出的信道編碼定理，對任意一個平穩離散無記憶有噪聲信源，都有一個固定的量，稱之為信道容量，記做C。只要信息的傳輸速率低于信道容量，就必然存在一種編碼方法，使得信息出現差錯的概率隨碼長的增加趨于任意小；反之，當信息傳輸速率超過信道容量時，則不存在這樣的編碼方法。這就是著名的信道編碼定理，它給出了特定信道上信息傳輸速率的上確界。
信道編碼定理：任意離散輸入無記憶平穩信道存在信道容量，對預期的任一數據速率和任一錯誤概率，有可能設計一對編譯碼器，以保證該信道中速率為R的數據傳輸具有小于p的譯碼錯誤概率。
信道編碼定理指出，在有擾信道中，只要信息傳輸速率小于信道容量，就有可能實現任意可靠的信息傳輸。這個存在性定理提醒我們可以實現以接近信道容量的傳輸速率進行通信。但遺憾的是該定理采用的是非構造性的證明方法，其中并沒有給出逼近信道容量的碼的具體編譯碼方法。
Shannon在信道編碼定理的證明中引用了三個基本條件，即：
(1)、采用隨機的編碼方式；
(2)、碼字長度趨近于無窮大；
(3)、譯碼采用最佳的最大似然譯碼。
一般可將信道編譯碼器所使用的糾錯碼從性能上分為壞碼和好碼。所謂壞碼是指只有將碼率降至零才能使誤碼率為任意小的編碼方式；而好碼又可以分為當誤碼率任意小時，碼率逼近信道容量限的非常好碼和碼率可達到的非零最大值小于信道容量限的一般好碼。雖然Shannon指出一個隨機選擇的碼以很高的概率為好碼，但隨機碼的最大似然譯碼的復雜度往往與碼長呈指數關系，即在誤碼率隨碼長趨于無窮而趨向于零的同時，譯碼復雜度以指數增長，而在實際應用中，只能夠使用以碼長多項式的時間和空間復雜度內完成編譯碼的糾錯碼，因而盡管一般的隨機碼是好碼，但不能看作是實用碼。
自信道編碼定理提出以來，如何構造一個逼近信道容量限的實用好碼成了眾多研究學者竟相研究的課題，并逐漸形成信息論的一個重要分支——信道編碼理論。五十多年來，人們構造實用好碼的探索基本上是按照Shannon所引用的基本條件的后兩條為主線展開的。雖然從理論上講，除了目前已知的碼外，幾乎所有的碼都是好碼，但到目前為止，構造出真正意義上的實用好碼還有較長的距離。雖然如此，通過眾多學者，特別是有關數學和信息論學術界的研究人員五十多年的共同努力，目前已經取得了很多成果。下面對其進行簡要概述。
糾錯碼從構造方法上可分為分組碼（Block Codes）和卷積碼（Convolutional Codes）兩大部分。在分組碼方面，第一個分組碼是1950年發現的能糾正單個錯誤的Hamming碼；在整個50年代，基于代數理論又發現了多個短碼長的分組碼，如1954年Golay發現的Golay碼以及Reed和Muller發現的RM碼，Prange在1957年發現的循環碼等。最有意義的是Bose和Ray-Chaudhuri在1960年及Hocuenghem在1959年分別獨立發現的能糾正多個錯誤的BCH碼，以及Reed和Solomon在1960發現的非二進制RS碼。實際上，BCH碼可以看作是某個RS碼的子域子碼，而RS碼又可以看作是BCH碼的特例。其后發現的分組碼主要有1970年的Goppa碼和1982年發現的代數幾何碼。在所有這些分組碼中，除了Goppa碼和代數幾何碼中存在個別達到GV限的漸進好碼外，其它均不是好碼。分組碼的譯碼主要采用基于代數的硬判決譯碼。
卷積碼最早由Elias提出，早期被稱為樹碼（Tree Codes），現在稱為格圖碼（Trellis Codes）或卷積碼。卷積碼具有動態格圖結構，可用有限狀態機來描述其狀態。由于缺乏有效的理論研究工具，對卷積碼的有效研究成果不是很多，目前性能好的卷積碼的構造方法主要借助于計算機搜索來獲得。卷積碼的譯碼一般采用概率譯碼，由于譯碼算法的簡單、實用和易于實現，卷積碼被廣泛應用于實際中。
1966年，Forney將分組碼和卷積碼結合起來，提出了級聯碼（Concatenated Codes）的概念。級聯碼一般采用RS碼作為外碼，卷積碼作為內碼。Forney的研究表明，級聯碼在性能得到較大改善的情況下，其譯碼復雜度并不顯著增加。
根據對接收信號處理方式的不同，糾錯碼的譯碼可以分為硬判決譯碼和軟判決譯碼。硬判決譯碼是基于傳統糾錯碼觀點的譯碼方法，解調器首先對信道輸出值進行最佳硬判決，再將判決結果送入譯碼器，譯碼器根據解調器的判決結果，利用碼字的代數結構來糾正其中的錯誤。而軟判決譯碼則充分利用了信道輸出的波形信息，解調器將匹配濾波器輸出的一個實數值送入譯碼器，由于實數值包含了比硬判決更多的信道信息，譯碼器能夠通過概率譯碼充分利用這些信息，從而獲得比硬判決譯碼更大的編碼增益。
總之，盡管隨機碼是理論上的好碼，但由于其編碼實現的困難性和無法承受的譯碼復雜度而只被用做理論分析的工具，在信道編碼定理和后來的許多編碼理論成果中，代數編碼理論始終占據了主導地位，使得傳統的信道編碼技術受到臨界速率（Critical Rate），也稱做截止速率（Cutoff Rate）的限制。
1993年Turbo碼的提出被看作是信道編碼理論研究的重要里程碑。Berrou等人將卷積碼和隨機交織器相結合，同時采用軟輸出迭代譯碼來逼近最大似然譯碼，取得了超乎尋常的優異性能，并一舉超越了截止速率，直接逼近Shannon提出的信道容量限。Turbo碼是一種信道編碼理論界夢寐以求的可實用非常好碼，它的出現標志著信道編碼理論研究進入了一個嶄新的階段。Turbo碼成功的根本原因在于其實現方案中長碼構造的偽隨機性是核心，它通過隨機交織器對信息序列的偽隨機置換實現了隨機編碼的思想，從而為Shannon隨機編碼理論的應用研究奠定了基礎。
隨著Turbo碼的深入研究，人們重新發現Gallager早在1962年提出的低密度校驗碼（Low Density Parity-Check Codes，簡稱LDPC碼）也是一種具有漸進特性的非常好碼，它的譯碼性能同樣可以逼近Shannon信道容量限。由于LDPC碼具有在中長碼長時超過Turbo碼的性能，并且具有譯碼復雜度更低，能夠并行譯碼及譯碼錯誤可檢測等特點，成為目前信道編碼理論的研究熱點。研究表明，Turbo碼只是LDPC碼的一個特例，兩者都是基于圖構造的低密度碼，譯碼算法具有等價性，從而使兩者在基于圖模型的編譯碼研究中得到了統一。
1.3 低密度奇偶校驗碼的提出、發展和現狀
1962年，Gallager在他的博士論文中提出了二元正則LDPC碼，也被稱做Gallager碼。Gallager證明了這類碼具有很好的漢明距離特性，是滿足GV限的漸進好碼，在計算樹上進行（N為碼長）次后驗概率迭代譯碼可以獲得依碼字長度指數降低的比特錯誤概率，但限于當時的計算能力，缺少可行的譯碼算法，LDPC碼被認為不是實用碼，在很長一段時間內沒有受到人們的重視。
1981年，Tanner在他的一篇奠基性的文章中正式提出了用圖模型來描述碼字的概念，從而將LDPC碼的校驗矩陣對應到被稱為Tanner圖的雙向二部圖上。采用Tanner圖構造的LDPC碼，通過并行譯碼可以顯著地降低譯碼復雜度。Tanner還仔細分析了最小和算法（Min-Sum Algorithm）與和積算法（Sum-Product Algorithm）兩種信息傳遞算法，證明了基于有限無環Tanner圖的最小和譯碼算法與和積譯碼算法的最優性。但Tanner圖在實際當中是采用隨機圖構造的，其中不可避免地存在小環路現象，這些小的環路會造成譯碼信息的重復傳遞，使譯碼過程中的消息之間不滿足獨立性假設，影響了迭代譯碼算法的收斂性。
Turbo碼的發現重新引發了眾多學者對LDPC碼的研究興趣。MacKay和Neal利用隨機構造的Tanner圖研究了LDPC碼的性能，發現采用和積譯碼算法的正則LDPC碼具有和Turbo碼相似的譯碼性能，在長碼時甚至超過了Turbo碼，這一結果引起了信道編碼界的極大關注。此后，Davey和MacKay從減少Tanner圖上小環路的概念出發提出了基于的LDPC碼，進一步提高了LDPC碼的譯碼性能。
在MacKay和Neal重新發現LDPC碼優異性能的同時，Spielman和Sipser提出了基于二部擴展圖的擴展碼。在對擴展碼的研究中，他們證明了一個隨機構造的Tanner圖以很大的概率為好的擴展圖，而由好的擴展圖構造的線性糾錯碼是漸進好碼，從而證明了采用隨機Tanner圖構造的LDPC碼以很大概率是漸進好碼。Luby等人將采用非正則Tanner圖構造的擴展圖用于刪除信道，稱之為Tornado碼。由于采用了非正則的Tanner圖，Tornado碼具有更大的擴展性和更好的收斂性，糾刪性能更強。此后，采用優化度序列設計的非正則Tanner圖被用于構造LDPC碼，稱為非正則LDPC碼，與正則LDPC碼相比，非正則LDPC碼的性能得到顯著的提高。
同時，Wiberg結合Turbo碼和網格圖的研究，將Tanner 圖推廣到包含隱含狀態變量的因子圖（Factor Graph），對Turbo碼和LDPC碼的研究在因子圖的基礎上得到統一。Wiberg對因子圖的研究發現，對任意給定系統，無環圖的狀態復雜度是最大的，有環圖的狀態復雜度則會大大降低，從而證明了基于有環Tanner圖的LDPC碼具有較低的譯碼復雜度。Wiberg同時還證明了最小和算法和和積算法在本質上的同一性，在格圖譯碼中，最小和算法退化為Viterbi譯碼算法，和積算法退化為BCJR譯碼算法。
近兩年，Richardson等人應用密度進化理論來測度LDPC碼的性能。Richardson等人在對LDPC碼的研究中發現，譯碼信息的迭代傳遞過程中存在著譯碼閾值現象，即當信噪比大于譯碼閾值時，迭代譯碼可使誤碼率趨于零，反之無論采用多長的LDPC碼，經過多少次迭代譯碼，總存在一定的錯誤概率。應用中心極限定理，Richardson等人證明了有限隨機有環圖的譯碼閾值可以逼近無環圖的譯碼閾值。通過建立在無環圖上的密度進化理論，可以精確地計算無環圖上LDPC碼的譯碼閾值，分析其譯碼收斂條件，從而近似估算有環Tanner圖上LDPC碼的性能。研究表明，譯碼閾值的大小與LDPC碼的構造參數密切相關，采用優化度序列設計的非正則LDPC碼可以有效地改善閾值，因此密度進化理論可以用于指導LDPC碼的優化設計。
Chung等通過對密度進化理論的研究，進一步提出了應用高斯逼近原理來簡化譯碼閾值計算和收斂性分析，從而使測度LDPC碼性能的模型由多參數動態系統的密度進化理論模型簡化為單一參數動態系統的高斯逼近模型。
?
第2章 預備知識
本章以漢明碼為例，介紹了線性分組碼的一般原理，并以此為后文中LDPC碼的編碼原理及程序中編碼算法設計打下理論基礎，同時通過對線性分組碼的分析介紹，形象地表現了信道編解碼過程中的糾錯檢錯過程。此外，還對信道容量以及香農極限進行了說明。
2.1 線性分組碼
在第一章中已經提到，信道編碼的目的是提高信號傳輸的可靠性。信道編碼是在經過信源編碼的碼元中增加一些多余的比特，目的在于利用這些特殊的多余比特去發現或糾正傳輸中發現的錯誤。在信道編碼只有發現錯碼能力而無糾錯能力時，必須結合其他的措施來糾正錯碼，否則只能將發現為錯碼的碼元刪除，以求避免錯碼帶來的負面影響。
在線性分組碼中，使用線性代數方程來決定監督位與信息位之間的關系，所謂監督位即在碼元中添加的冗余比特。線性分組碼的構造方式較為簡單、理論較為成熟。本章以漢明碼為例介紹線性分組碼的一般原理。這種編碼方法是由漢明（R. W. Hamming）與1950年提出的。
漢明碼是一種能夠糾正一個錯碼的效率較高的線性分組碼。對于偶數監督碼而言，在接收端解碼時，實際上就是在計算下式：?
?? ??? ?(2-1)
若計算出的S=0，就認為無錯碼；若計算出的S=1，就認為有錯碼。現在將式(2-1)成為監督關系式，S為校正子。由于校正子是一個二進制數字，他只有兩種取值，故只能表示有錯和無錯，而不能進一步的指明錯碼的位置。不難推想，若此碼長增加一位，即有兩個監督位，則能增加一個類似式(2-1)的監督關系式。這樣就能得到兩個校正子。兩個校正子的可能取值有4種組合，即00，01，10，11，故能表示4種不同的信息。若用其中一種組合表示無錯碼，則還有其他3種組合可以用于指明一個錯碼的3個不同位置。因此，若有r個監督關系式，則r個校正子可以指明一個錯碼的()個不同的位置。只有當校正子可以指明的錯碼位置數目等于或大于碼組長度n時，才能夠糾正碼組中任何一個位置上的錯碼，即要求：?
?? ??? ?(2-2)
下面通過一個例子來說明如何具體構造監督關系式。要求設計一個能夠糾正1個錯碼的分組碼(n,k)，給定的碼組中有4個監督位，即k=4.由式(2-2)可知，這時要求監督位數。若取，則。現在用表示這7個碼元，用表示校正子，這三個校正子恰好能夠指明個錯碼的位置。例如，可以按照表2.1所示規定校正子和錯碼位置的關系。當然，也可以做其他的規定，這不影響討論的一般性。
表2.1 校正子和錯碼位置關系
?? ?錯碼位置?? ??? ?錯碼位置
001?? ??? ?101?? ?
010?? ??? ?110?? ?
100?? ??? ?111?? ?
011?? ??? ?000?? ?無錯碼
由此表可見，僅當在位置上有錯碼時，校正子的值才等于1；否則的值等于0。這意味著4個碼元構成偶數監督關系：
?? ??? ?(2-3)
同理，構成如下偶數監督關系：
?? ??? ?(2-4)
以及構成如下偶數監督關系：
?? ??? ?(2-5)
在編碼時，信息位的決定于輸入信號，他們是隨機的。監督位是按照監督關系決定的，應該保證上列3個式子中的校正子等于0，即有：
?? ??? ?(2-6)
上式可改寫為：
?? ??? ?(2-7)
若信息位的值給定，則可以根據上式計算出監督位的值。這樣計算出的結果見表2.2。
表2.2 監督位計算結果
?? ??? ??? ?
0000?? ?000?? ?1000?? ?111
0001?? ?011?? ?1001?? ?100
0010?? ?101?? ?1010?? ?010
0011?? ?110?? ?1011?? ?001
0100?? ?110?? ?1100?? ?001
0101?? ?101?? ?1101?? ?010
0110?? ?011?? ?1110?? ?100
0111?? ?000?? ?1111?? ?111
在接收端解碼時，對于每個接收碼組，先按式(2-3)至式(2-5)計算出校正子，然后按照表2.1判斷錯碼的位置。例如，若接收碼組為0000011，則按式(2-3)至式(2-5)計算得到：。這樣，由表2.1可知，錯碼位置在。
按照上述方法構造的碼成為漢明碼。上面例子中的漢明碼是(7,4)碼，其最小碼距。由式(2-4)和式(2-5)可知，此碼能夠檢測2個錯碼，或糾正1個錯碼。漢明碼的碼率可以由式(2-2)取等號時的值得出：?
?? ? ?? ?(2-8)
當r或n很大時，上式趨近于1.所以漢明碼是一種高效編碼。
在討論上面實例的基礎上，現在介紹線性分組碼的一般原理。前面已經說明，線性分組碼的監督位和信息位的關系是由一組線性代數方程決定的。式(2-6)就是這樣的方程式，將此式改寫成下列形式：
?? ??? ?(2-9)
在上式中已經將簡寫成。代表模2加法。式(2-9)可以改寫成如下的矩陣形式：
?? ??? ?(2-10)
將上式改寫為：
?? ? 或 ?? ?(2-11)
式中
?? ?，， (2-12)
上標“T”表示將矩陣轉置，即將矩陣的第一行變為矩陣的第一列，將矩陣的第二行變為矩陣的第二列……
我們將上式中的H稱為監督矩陣。監督矩陣給定后，碼組中的信息位和監督位的關系就隨之確定了，比較式(2-9)和式(2-10)可以看出，H的行數就是監督關系式的數目，即監督位數r。H的每行中各個“1”的位置表示相應的碼元參與監督關系。例如，H的第一行1110100表示監督位是由之和確定的。式(2-11)中的H可以分為如下兩部分：
?? ??? ?(2-13)
式中，為階矩陣，為階單位方陣。我們將如上式形式所表示的監督矩陣稱為典型監督矩陣。
由代數理論可知，H矩陣的各行應該是線性無關的，否則將得不到r個線性無關的監督關系式，從而也得不到r個獨立的監督位。若一個矩陣能夠寫成典型陣形式，則其各行也一定是線性無關的。因為容易驗證，的各行是線性無關的，故的各行也是線性無關的。
式(2-7)也可以仿照式(2-9)的做法，寫成如下矩陣形式：
?? ??? ?(2-14)
上式兩端分別轉置后，可以變成：
?? ??? ?(2-15)
式中，Q為階矩陣，是P的轉置，即：
?? ??? ?(2-16)
式(1-15)表示，在信息位給定后，用信息位的行矩陣乘以矩陣Q就得出監督位。
我們將Q的左邊加上一個k階單位陣，構成如下矩陣：
?? ??? ?(2-17)
G稱為生成矩陣，因為可以用它產生整個碼組A，即有：
?? ??? ?(2-18)
具有形式的生成矩陣成為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監督位附加于其后。這種形式的碼組稱為系統碼。
比較式(2-13)和式(2-17)可見，典型監督矩陣H和典型生成矩陣G之間通過式(2-16)聯系。
與對矩陣H的要求相似，矩陣G的各行也必須是線性無關的。因為由式(2-18)得知，任意一個碼組A都是G的各行的線性組合。G共有k行，若他們線性無關，則可以組合出種不同的碼組，這恰好是有k位信息位的全部碼組。若G的各行中有線性相關的，則不可能生成種不同的碼組了。實際上，G的各行本身就是一個碼組。因此，如果已有k個線性無關的碼組，則可以將其用作生成矩陣G，并由它產生其余的碼組。
一般來說，式(2-18)中的A是一個n列的列矩陣：
?? ??? ?(2-19)
它的n個元素就是碼組中的n個碼元。所以發送碼組就是A。由于傳輸中的干擾影響，接收碼組可能出現錯碼而有別于A。設接收碼組是一個n列的行矩陣：
?? ??? ?(2-20)
令接收碼組和發送碼組之差為：
?? ? ?(模2)?? ?(2-21)
E就是錯碼的行矩陣，有時還稱其為錯誤圖樣：
?? ??? ?(2-22)
式中，。因此，若，則表示該碼元未錯；若，表示該碼元為錯碼。式(2-21)還可以改寫成：
?? ??? ?(2-23)
上式表示發送碼組A與錯誤碼組E之和等于接收碼組B。例如，若發送碼組，錯碼矩陣，則接收碼組。
?? ?在接收端解碼時，令式(2-11)中的A等于接收碼組B進行計算。若接收碼組B中無錯碼（），由式(2-23)得知，，則式(2-11)仍成立。這時有：
?? ??? ?(2-24)
當接收碼組中有錯碼時，，此時將B代入式(2-11)后，該式不一定成立。此外，在錯碼較多并超出這種編碼的檢錯能力時，B可能變為另一個許用碼組，故式(2-11)仍有可能成立。這時的錯碼將是不可檢測的。所以只有當錯碼未超出檢測能力時，式(2-24)才不成立。假設，這時式(2-24)的右端等于S，即有：
?? ??? ?(2-25)
將式(2-23)代入(2-25)，得到：

由式(2-11)可知，上式右端第一項等于0，所以：
?? ??? ?(2-26)
式中，S就是由式(2-1)中的校正子S構成的矩陣，所以也成為校正子，它同樣可以用來指示錯碼的位置。當H確定后，式(2-26)中，S只與E有關，而與A無關。這意味著S和錯碼E之間有確定的線性變換關系。若S和E有一一對應關系，則S將能代表錯碼位置。
?? ?線性碼有一個重要性質，就是它具有封閉性。封閉性是指一種線性碼中任意兩個碼組之和仍為這種編碼中的一個碼組。下面對此做一簡單證明：
?? ?若和是兩個碼組，則由式(2-11)有：
? ?
將以上兩式相加得：
?? ??? ?(2-27)
所以也是一個碼組。由于線性碼具有封閉性，所以兩個碼組和之間的距離（即對應位不同的數目）必定是另一個碼組的重量（即“1”的數目）。因此，碼的最小距離就是碼的最小重量（除全“0”碼組外）。
2.2 信道容量和香農極限
信道容量表示一個信道下可靠傳輸的最大信息傳輸速率。不同的信道，噪聲的存在形式不同，信道帶寬以及信號的各種限制不同，因而信道容量也不相同。香農在其文章中定義的信道容量為：?
?? ? ?? ?(2-28)
?? ?X和Y分別代表信道的輸入和輸出，是X的概率密度函數；是X和Y的互信息量；H(X)是信源熵；H(Y/X)為信道條件熵，即因為信道噪聲而造成的信息損失熵。
?? ?對于寬帶無限的加性高斯白噪聲(AWGN)信道，信道容量為：?
?? ? ?? ?(2-29)
是傳輸信號的平均功率，為高斯白噪聲的功率譜密度。
?? ?對于帶寬為W，信號平均功率為的帶限AWGN信道，信道容量為：?
?? ? ?? ?(2-30)
式(2-30)即為著名的香農信道容量公式。
?? ?對于低密度碼的研究，需要涉及到輸入離散、輸出連續的AWGN信道。由于只有輸入符號均勻分布時才能使互信息量達到最大，因此假設輸入符號的概率密度函數為：?
?? ? ?? ?(2-31)
即：?
?? ? ?? ?(2-32)
?? ?對于AWGN信道可得：?
?? ? ?? ?(2-33)
?? ? ?? ?(2-34)
將式(2-33)和(2-34)代入式(2-28)有
?? ? ?? ?(2-35)
?? ?R表示碼率，表示傳輸每一個比特所需要的能量，與關系為。因為式(2-35)無法求出解析解，故智能采用數值仿真的方法近似求解。同時需要根據y的特點對其積分區域進行縮減，于是得到：?
?? ? ?? ?(2-36)
其中
當傳輸錯誤概率時，得到的Shannon極限為
?? ? ?? ?(2-37)
可以看出這與理想AWGN信道的Shannon極限是完全一致的。
?? ?我們知道在實際研究中，R是不可能趨近于0的。所以利用式(2-36)，再考慮滿速率傳輸的情況(R=C)，就可以得出不同的R下達到信道容量極限時所需的做小信噪比，如圖2.1所示。
?
圖2.1 二進制AWGN的信道容量
上圖給出了不同編碼速率R下二進制AWGN信道的信道容量。可以看出，當評估某一信道編碼的性能時，不能直接用它的性能和一般意義下的Shannon極限（-1.6dB）進行比較，而應該根據它的碼率在達到實際信道容量時所需的最小信噪比，并用來和其性能做比較，這樣才更合理。下表列舉出了一些常見碼率下所對應的最小信噪比值。
表2.3 不同碼率條件下AWGN信道的最小信噪比
碼率(R)?? ?最低信噪比(dB)
8/9?? ?3.003
4/5?? ?2.040
2/3?? ?1.060
1/2?? ?0.187
1/3?? ?-0.495
0?? ?-1.6
?
第3章 LDPC碼表示及編碼
本章系統地概述了LDPC碼的定義及其Tanner圖表示，以及二進制LDPC碼的編碼原理。
3.1 LDPC碼的定義及其Tanner圖表示
3.1.1 LDPC碼的定義及其描述
一個碼長為n、信息位個數為k的線性分組碼可以由一個生成矩陣來定義，信息序列通過G被映射到碼字。線性分組碼也可以由一個一致校驗矩陣來等效描述，所有碼字均滿足。校驗矩陣每一行表示一個校驗約束，其中所有非零元素對應的碼元變量構成一個校驗集，用一個校驗方程表示；校驗矩陣的每一行表示一個碼元變量參與的校驗約束，當列元素不為零時，表示該碼元變量參與了該行的校驗約束。碼元變量與檢驗方程之間的關系成為結構。下面主要對二元LDPC碼進行討論。
LDPC碼是一種線性分組碼，它的名字來源于其校驗矩陣H的稀疏性，即校驗矩陣中只有數量很少的元素為“1”，大部分都是“0”。Gallager最早給出了正則LDPC碼的定義，具體來講正則LDPC碼的校驗矩陣H滿足下列三個條件：
(1)、H的每行有個“1”；
(2)、H的每列有個“1”，;
(3)、與碼長和H矩陣的行數相比，和都很小。
?
圖3.1 (20,3,4)LDPC碼的校驗矩陣
矩陣H的每列各自包含個“1”，表示每個碼元變量受到相同數目的校驗約束；每行也各自包含個“1”，表示每個校驗方程對相同數目的碼元變量進行校驗約束；由于和都很小，校驗矩陣具有很低的“密度”，因此由校驗矩陣所確定的碼稱為LDPC碼。Gallager證明了當時，這類碼具有很好的漢明距離特性。正則LDPC碼通常用來表示，其中n為碼長,和的含義不變，圖3.1給出了一個(20,3,4)正則LDPC碼的校驗矩陣。
當校驗矩陣H各行（列）中“1”的個數不全相同時，就得到了非正則LDPC碼。
3.1.2 LDPC碼的Tanner圖表示
設一個正則LDPC碼C具有校驗矩陣，其對應的Tanner圖模型可以表示為一個二部圖。其中碼字向量表示為一組比特節點，分別對應于校驗矩陣的各列，而校驗約束則表示為一組校驗節點，對應與校驗矩陣的各行。僅當時，比特節點與校驗節點之間有一條邊相連，節點與之間互稱鄰接節點，其間的連接邊稱為兩個節點的鄰接邊。對于正則LDPC碼，每個比特節點與個個校驗節點相連，稱該比特節點的度為；每個校驗節點與個比特節點相連，稱該校驗節點的度為，度表示與節點相連的邊的數目。圖3.2給出了圖3.1所示校驗矩陣對應的Tanner圖結構。
?圖3.2 (20,3,4)LDPC碼的Tanner圖表示
?? ?根據比特節點與校驗方程之間的約束關系可以得知，Tanner圖中中所有比特節點發出的邊的數目必然等于所有校驗方程所接收的邊的總數。那么對于LDPC碼(n，j，k)，若假設m為校驗方程的個數，即校驗矩陣H的行數，則以下等式必然成立：
?? ??? ?(3-1)
?? ?對于非正則的LDPC碼，每個校驗方程約束的比特節點數目不一樣，同時每個比特節點受約束的校驗方程的數目也不一樣。反映在Tanner圖中就是每個點（比特節點和約束節點）所連接的邊的數目是不完全相同的。這樣一種不規則的LDPC碼在碼長很大的時候性能要比正則的LDPC碼好，這是由于“波浪效應”（Wave Effect）所致。一部分比特節點受到約束的校驗方程數目比較多，即收到的約束度比較高，那么其正確譯碼的速度也相對比較快；以此同時，這些約束度較高的點也為其他約束度較低的點提供了更為準確的譯碼外信息，最終使得所有比特節點正確譯碼的速度更快。又因為校驗矩陣H中每行和每列1的個數不同，所以不能再用(n,j,k)的方式來進行表示。為了準確地表達一個非正則的LDPC碼，我們引入如下表達式：?
?? ? ?? ?(3-2)
?? ?其中表示比特節點的度的分布，表示校驗節點的度的分布；滿足 及 。
?? ?正則LDPC碼可以看成是非正則LDPC碼的特例，對于(n,3,4)形式的正則LDPC碼，相應邊的度分布多項式分別退化為。
3.2 二進制LDPC碼的編碼原理
3.2.1 H矩陣的構造
由于LDPC碼是以校驗矩陣H為特征的，不同的校驗矩陣H對應了不同的碼字集合。因此，LDPC碼的編碼首先要設計校驗矩陣H，同時這也是LDPC碼編碼的關鍵。
對于規則的LDPC碼(n,j,k)，在碼長n一定的情況下，主要的參數選擇則為j和k。目前的研究結果表明，性能最好的規則LDPC碼是(n,3,6)碼。根據式(3-1)可知，參數n,j,k確定后就可以得到校驗方程的數目m，那么H矩陣的大小就可以確定為。LDPC碼校驗矩陣H的一般構造步驟如下：首先生成一個的全0矩陣，然后隨機地將每列中的j個0置換成1，每行當中的k個0置換成1。但是在隨機置1的過程中，有兩種情況是必須要避免的：
(1)、出現長度為4的環
在LDPC碼校驗矩陣H中有一個很重要的概念：H矩陣的最小圍長(girth)，即通常說的環。H矩陣中的4環結構示意圖如下：
?
圖3.3 H矩陣中的4環結構
其對應Tanner圖如下：
?
圖3.4 Tanner圖中的4環結構
當H矩陣中出現長度為4的環時，其結構會導致消息在兩組點之間的反復傳遞，而難以得到更新，與迭代譯碼的思想初衷所違背，是必須清除的一種結構。我們另外做簡單的解釋，例如在圖3.3所示的H矩陣中，存在一個4環結構，于是這個4環對應的校驗方程為：
?? ??? ?(3-3)
?? ??? ?(3-4)
由于4環的存在，我們可以看到，上面兩個校驗方程含有共同的比特節點與，直觀的說，如果這兩個校驗方程均出錯，則我們無法確定與中究竟是哪個出錯。從這個角度可以說明小循環對性能帶來的影響。所以我們在矩陣H矩陣時要避免4環以及短環的存在。理論分析表明，最小環的長度為6的情況下，碼字的最小距離為4。而隨機構造的LDPC碼的最小距離是隨著分組長度，即碼長的增加而線性增加的。
(2)、比特節點所連接的校驗方程過于集中
當比特節點所連接的校驗方程過于集中時，常常導致LDPC碼錯誤地板的發生。例如在圖3.5中，比特節點的度為3，但其中三個帶陰影的比特節點總共只連接了5個校驗方程；除了最右邊的一個校驗方程外，其它4個校驗方程中，每個都連接了兩個陰影的比特節點。因此，如果這三個陰影的比特節點都出錯時，左邊的四個校驗方程都不能檢測到錯誤的存在。而當分組長度增大時，出現這種拓撲結構的可能性會隨之減少。
?
圖3.5比特節點所連接校驗方程過于集中的Tanner圖
對于不規則的LDPC碼其H矩陣的構造也遵循上述兩個原則，不同的是校驗矩陣H每行和每列中1的個數不再相同。在最早提出的不規則LDPC碼中，比特節點和校驗節點的度都是不均勻的，即校驗矩陣H中每列，每行1的個數都不相同，但實際仿真結果表明，這種雙邊不均勻的情況并非最佳方案。實際的應用方案是讓比特節點的度(即校驗矩陣H中每列I的個數)變化比較大，而保持校驗節點的度(即校驗矩陣H中每行1的個數)比較平均．其中約束度比較大的比特節點稱為優先點。在迭代譯碼過程中，優先點首先被正確譯碼的概率是最大的．如何分配這些優先點，讓哪些校驗節點連接更多的優先點，是不規則LDPC碼的一個研究方向。
3.2.2 ?LDPC碼的編碼思想
1、傳統編碼方法
這種編碼方法需要先將H矩陣進行變換得到一個生成矩陣G，然后利用信息序列與生成矩陣相乘進行編碼。下面我們首先給出兩個引理來說明校驗矩陣經過高斯變換不會影響編碼結果。
引理1 設LDPC碼的校驗矩陣為，其中表示的是第k列的列向量，信息序列S編碼后生成的碼字為，如果將H矩陣的第i列和第j列進行交換得到，則，原信息序列經過此新的校驗矩陣編碼后所得的碼字為，即將原碼字的第i個和第j個位置交換后得到新的碼字。
?? ?證明：
?? ?由LDPC碼校驗矩陣和碼字間的正交關系可得，即，所以。所以對校驗矩陣進行列變換，得到的新碼字也是對原碼字進行同樣位置的列變換。在編碼時，只要記錄下校驗矩陣列變換的動作，對新校驗矩陣下得到的碼字進行同樣位置的置換即可以得到原校驗矩陣所對應的碼字。
?? ?引理2 使用高斯消元法對H矩陣進行行變換（即把H矩陣某一行按照模2相加到另一行上）不影響編碼結果，變換所得的矩陣與原矩陣具有等價性。
?? ?證明：
?? ?在Tanner圖中可以看出，把H矩陣的第i行按照模2相加到第j行上，在Tanner圖上即是從節點添加邊到所有與相連的節點上，如果已經與該比特節點相連，則把該連接刪掉。設分別表示原來與校驗節點相連的所有比特節點的集合，表示的交集，表示與變換后的校驗節點相連的比特節點的集合；符號表示按模2進行累加，“+”表示按模2 進行相加，表示第k個比
特節點的值，由LDPC碼的定義可得及，則有：
?? ? ?? ?(3-5)
即，原來的碼字仍可滿足新校驗矩陣的校驗關系，所以，H矩陣進行行行變換不影響編碼結果。
?? ?下面介紹傳統編碼的基本理論和一般過程。
?? ?設信息源為s，則編碼生成的碼字。這種編碼方式是由最基本的原理推得的。當分組長度為n時，編碼復雜度為，在移動通信中這種傳播時延對于語音通信是不能忍受的。計算復雜度也會使得存儲器的數量過多，影響通信成本。為了簡化計算，數學家們設計了很多簡便算法。但是這些算法要求校驗矩陣H具有相應的特殊形式。
?? ?由編碼理論可知，具有系統形式的校驗矩陣H對應的生成矩陣G也具有系統形式，得到的碼字U也是具有系統形式的碼字。現在假設編碼前的信息為s，編碼后的校驗位為c，編碼后信息位s位于碼字U的后部，即；假設校驗矩陣H的大小為，并具有系統形式，其中A是一個的單位矩陣，B是一個的矩陣。運用編碼理論即矩陣運算可以得到下列等式：
?? ??? ?(3-6)
?? ?由此等式可得到：，因為A為單位矩陣，故又可以簡化為：。
?? ?這種編碼方式要求校驗矩陣H具有系統形式，但卻是以犧牲LDPC碼的稀疏性為代價的。因為系統形式的校驗矩陣H要求具有一個的單位矩陣，這必然使得校驗矩陣H中的其余部分必須承擔余下的所有“1”元素，從而使得這部分顯得比較密集，并不能很好的達到LDPC碼原本所要求的稀疏性。這在一定情況下提高了LDPC碼編碼的復雜度。
2、基于下三角形式校驗矩陣的編碼方法
?? ?Mackey等證明，LDPC碼要在線性時間內完成編碼，則其校驗矩陣具有如圖3.6所示的下三角的形式，并建議在構造校驗矩陣時加入某些約束，使得構造出的校驗矩陣具有下三角的形式。但是，如果在構造校驗矩陣時加入某些約束，就違背了Shannon在證明信道編碼時引入的隨機性原則，從而降低了碼的性能。所以，既要保持隨機性原則，又要在線性時間內完成編碼成了LDPC碼發展的一個障礙。
?
圖3.6 校驗矩陣的的下三角形式
基于此T.J.Richardson和R.L.Urbanke提出了Efficient快速編碼方法。Efficient編碼方法的基本思想是利用LDPC碼校驗矩陣稀疏性的性質，對校驗矩陣進行行列置換，使得校驗矩陣具有特定的形式，這中特定的形式使得編碼能夠在先行時間內完成；基于下三角形式校驗矩陣的編碼方法、基于近似下三角校驗矩陣的編碼方法就是其中代表形式。
在基于下三角形式校驗矩陣的編碼方法中，由于僅僅對校驗矩陣進行行列置換，所以校驗矩陣的稀疏性并沒有被破壞，這樣在線性時間內完成編碼是毋庸置疑的。下面討論具體的操作流程：
若LDPC碼的校驗矩陣具有如圖3.6所示的下三角形式，在圖中斜線上全為“1”，而其余的“1”均在斜線的左邊，則可以采用迭代的方式進行編碼。設碼字向量為,將其分為兩部分，即信息位向量和校驗位向量，即，則該編碼的過程可具體描述為：
(1)、直接將信息比特的值賦給信息位向量S；
(2)、采用后向迭代確定所有校驗位的值，即對所有的從小到大依次計算下式：?
?? ? ?? ?(3-7)
其中表示校驗矩陣中第i行，第j列上的元素。
?? ?實際上，該編碼過程就是在從上到下依次利用校驗矩陣的各行校驗約束關系。對于每一個校驗約束關系，其中涉及的變量除斜線上的“1”所對應的校驗位外，其余的變量要么是信息位，要么就是前面已經求出的校驗位，也就是說，該校驗約束關系中只有一個未知變量，因此可以很容易求得相應校驗位的值。
?? ?設校驗矩陣經過變換成為下三角形式后的平均行重為m，則整個編碼約需要m(n-k)次與運算，(m-1)(n-k)次異或運算，當m相對于n可以看作很小的常數時，該編碼方法就具有線性的復雜度。
3、基于近似下三角形式校驗矩陣的編碼方法
?? ?基于近似下三角結構的編碼方法可以看作是基于下三角結構的編碼方法的改進。該方法的編碼處理過程分為兩部：預處理過程和實際編碼過程。預處理過程是一個離線計算，對于一個給定的碼字只需要做一次計算，但實際編碼過程主要是針對傳輸數據的處理部分。
?? ?在變換算法中，假設輸入信息比特部分為s，編碼獲得的校驗比特部分分為和，則碼字，滿足。我們把校驗矩陣進行行列重排，若能直接化為下三角矩陣，則編碼可以線性實現。通過行列變換我們把校驗矩陣化成如下的近似下三角矩陣：
?? ??? ?(3-8)
該矩陣形狀如下：
?
圖3.7 校驗矩陣的近似下三角形式
將校驗矩陣左乘如下矩陣
?? ??? ?(3-9)
得到
?? ??? ?(3-10)
那么可以分解為如下兩個表達式：
?? ??? ?(3-11)
?? ??? ?(3-12)
定義，并且假設非奇異，則求解上面兩式可得：
?? ??? ?(3-13)
?? ??? ?(3-14)
通過如上兩個公式可以計算校驗信息和，從而得到碼字。
?
第4章 LDPC碼的譯碼思想
?? ?LDPC碼的譯碼算法大致分為：軟判決譯碼、硬判決譯碼和混合判決譯碼。他們有著各自不同的糾錯性能和譯碼復雜度。軟判決譯碼算法性能最優，糾錯性能最好，但是運算復雜度也最高，其經典算法就是置信度傳播（Belief Propagation, BP）算法。Gallager提出的比特反轉（Bit-Flipping, BF）譯碼算法是一種硬判決譯碼算法，運算最為簡單 ，復雜度低，但是糾錯性能也較低。混合判決譯碼算法，其糾錯性能和譯碼復雜度都在BF算法和BP算法之間。
?? ?下面將分別介紹三種類型的譯碼算法，分析它們的譯碼原理和性能。
4.1 軟判決譯碼算法
?? ?置信度傳播譯碼算法（BP譯碼算法）是最經典的LDPC碼軟判決譯碼算法之一。核心思想是利用Tanner圖中的比特節點和校驗節點之間的約束關系，在兩種節點之間來回傳遞并且更新置信度信息，最終實現解碼。和積算法（Sum-Product Algorithm, SPA）作為一種通用的消息傳遞算法最早由Gallager提出，具體來說就是針對某一個比特節點進行解碼時，從它所參與的校驗方程那里得到判決信息，再綜合在解碼端接收到的軟判決信息進行最后的判決。而校驗方程的信息又是從參與該校驗方程的其他比特節點得到信息的。
4.1.1 Tanner圖解析法原理
?? ?上面介紹的SPA算法原理可以用Tanner圖來演示。
?
圖3.8 Tanner圖
如圖3.8所示，其中x1~x6為比特節點，f1~f3為校驗節點。設y1~y6為接收到的消息。Tanner圖中比特節點和校驗節點之間的連線看作是信息傳遞的路徑。初始化過程可以表示如下：
?
圖3.9 初始化過程
?? ?(1)、比特節點x1將從它所連接的多個非f3校驗節點那里得到的信息及原始信息的總和傳遞給校驗節點f3，用于修正校驗節點f3的信息。在Tanner圖上示意如下：
?
圖3.10 校驗節點的信息更新(x1?f3)
?? ?(2)、校驗節點f3將從它所連接的多個非x1比特節點那里得到的信息傳遞給比特節點x1，x1得到的是該比特節點的后驗信息，憑此來修正比特節點的判決信息。在Tanner圖上示意如下：
?
圖3.11 比特節點的信息更新(f3?x1)
(3)、比特節點x1綜合從信道直接得到的信息和從與之相連的校驗節點得到的信息做出判決。在Tanner圖上表示如下：
?
圖3.12 比特節點x1的信息判決
4.1.2 SPA算法原理
現在我們對SPA算法的原理進行說明。
令表示與校驗節點j相連的比特節點的集合，記為
表示除i外，與校驗節點j相連的比特節點的集合；
表示與比特節點i相連的校驗矩陣的集合，記為；
表示除j外，與比特節點i相連的校驗節點的集合；
表示包含的第j個校驗方程中的第k個比特；
表示對應于的接收值；
表示接收到后判斷發送比特為的后驗概率；
表示接收到后判斷包含的第j個校驗方程中的第k個比特為的后驗概率；
表示碼字中的比特節點使得包含的所有校驗方程都滿足；
表示第i個比特節點傳遞給第j個比特節點的認為是的外部概率信息，即在得到所有校驗節點和信道信息后，判斷的概率；
，假設，表示校驗節點j傳遞給比特節點i的外部概率信息，即在給定信息位及其它信息位具有獨立概率分布條件下，第j個校驗方程滿足的概率。
如果收到的碼字中某一比特為b，那么定義碼字滿足校驗方程的后驗概率為。
首先我們引入三個結論：
(1)、考慮一個二進制序列，其中。
可以證明，a中含有偶數個1的概率為：
?? ? ?? ?(4-1)
a中含有奇數個1的概率為：
?? ? ?? ?(4-2)
(2)、假設信道為離散無記憶信道，則接收到的信息序列中的各個采樣值獨立，可以計算得到給定接收到的碼字和校驗事件下比特節點的后驗概率：
?? ? ?? ?(4-3)
假設，由結論1可得，該校驗方程滿足的概率是：
?? ? ?? ?(4-4)
對于的情況可類似得到。由于假設之間相互獨立，所有個校驗比特都滿足的概率是：
?? ? ?? ?(4-5)
根據前面對的符號的定義，可以得到如下的計算公式：
?? ? ?? ?(4-6)
?? ? ?? ?(4-7)
根據上面兩個式子以及結論，則有：
?? ? ?? ?(4-8)
同樣地，根據前面對的符號的定義，可以得出下面的公式：
?? ? ?? ?(4-9)
?? ? ?? ?(4-10)
(3)、信道編碼器產生的碼字經過調制然后送入信道，這里采用AWGN信道和BPSK調制，接收端得到的接收序列可以寫成。是0均值且方差為的高斯分布，滿足0，1等概率分布，由此可得AWGN信道下比特節點初始概率信息的計算公式為：
?? ? ?? ?(4-11)
即
?? ? ?? ?(4-12)
SPA算法原理執行過程如下：
(1)、概率信息初始化
根據信道接收信息y，利用公式(4-12)計算每個比特節點的初始概率和。
?? ? ?? ?(4-13)
?? ? ?? ?(4-14)
(2)、校驗節點的概率信息處理
每個比特節點i將自身的概率信息傳遞給它參與的所有校驗節點，計算第j個校驗節點從第i個比特節點處獲得的信息。
?? ? ?? ?(4-15)
?? ? ?? ?(4-16)
(3)、比特節點的概率信息處理
每個校驗節點j將自身的概率信息傳遞給參與它的所有比特節點，計算第i個比特節點從第j個校驗節點處獲得的信息。
?? ? ?? ?(4-17)
?? ? ?? ?(4-18)
其中是常數因子，使得
(4)、判決
?? ? ?? ?(4-19)
?? ? ?? ?(4-20)
是常數因子，使得
根據比特i的概率值可以判決為：若，則，否則。
如果或者達到最大譯碼次數，則終止譯碼，否則跳轉到步驟(2)繼續進行迭代譯碼。
不難看出，在這個算法中有大量的高復雜度的實數操作，并且需要存儲大量的中間過程的數據。由于對數操作可以將實數乘法運算轉換成實數加法運算，所以為了降低解碼復雜度，可以將上面的解碼過程轉化到對數域實現。
4.1.3 對數域BP譯碼算法
首先定義對數似然比LLR(Log-APP-ratio)：
?? ? ?? ?(4-21)
據此定義如下一系列LLR表達式：
?? ??
對數域BP算法譯碼過程如下：
(1)、似然信息初始化
?? ? ?? ?(4-22)
(2)、校驗節點的似然信息處理
將概率域傳遞公式(4-16)重寫為：
?? ??
對它做等式變換，得到：
?? ? ?? ?(4-23)
利用恒等式 的特性 對(4-23)變換得：
?? ??
即
?? ??
令 ， ，則可以得到對數域計算校驗節點似然信息的表達式為：
?? ? ?? ?(4-24)
(3)、比特節點的似然信息處理
?? ??
即對數域計算比特節點似然信息的表達式為：
?? ? ?? ?(4-25)
(4)、判決
利用本次迭代過程中每個比特節點從校驗節點處獲得的似然信息，再加上從信道輸出數據得到的初始似然信息，計算新的似然信息值。
?? ? ?? ?(4-26)
根據比特i的似然值可以判決為：若，則，否則。
如果或者達到最大譯碼迭代次數，則終止譯碼，否則跳轉到步驟(1)繼續執行迭代過程。
4.1.4 最小和（Min-Sum）譯碼算法（改進的對數域BP譯碼算法）
重寫對數域BP譯碼算法的公式(4-24)如下：
?
利用函數 的性質 ，可將上面的表達式簡化為 。
?的函數特性如圖所示：
?
圖3.13 函數 與變量x的關系（x≥0）

根據 的函數特性可以做如下簡化處理：
?
于是可以得到下列公式：
?? ? ?? ?(4-27)
其他操作步驟同前。這就是最小和算法，由J.Chen和M.Fossorier等在1999年提出。在LDPC碼的列重不太大并且碼長不太長的時候，這種算法能夠達到較好的性能。這樣的簡化處理省去了累乘運算，降低了運算復雜度。
4.2硬判決譯碼算法
由Gallager提出的比特反轉（Bit-Flipping，BF）譯碼算法是一種典型的硬判決譯碼算法，它的運算最為簡單，復雜度最低，但是糾錯性能較低。后來的研究人員在其基礎上又提出了一系列改進的BF算法，改進的方向大致可以分成兩個：3利用軟信息對BF算法進行加權優化，第二類是利用校驗矩陣的結構特點對BF算法加以改進。本節我們首先介紹Gallager最初提出的比特反轉譯碼算法，然后闡述一下在此基礎上的改進算法，并提出一種優化的基于加權錯誤校驗的LDPC碼比特反轉算法。
4.2.1 Gallager的比特反轉譯碼算法
Gallager的BF譯碼算法主要通過計算接受序列的伴隨式S來進行解碼。其譯碼原理為：先將從信道得到的譯碼器輸入數據判決為“0”、“1”序列，把該序列代入低密度校驗矩陣計算各個校驗方程的結果，得到相應的錯誤伴隨圖樣。據此可以找出使得校驗方程不成立數目最多的比特節點，然后將比特節點反轉，如果再次進行譯碼校驗沒有錯誤出現，則譯碼終止，否則在達到最大迭代次數前不斷重復譯碼過程，直到所有的校驗方程都成立。
設發送的碼字序列為 ，BPSK調制后序列為 ，其中 ，接收到的硬判決序列為 ，LDPC碼校驗矩陣為 ，其中 。
可以計算碼字的伴隨式為：
?? ? ?? ?(4-28)
其中M=N-K。
若 ，則說明碼字序列滿足第i個校驗方程，若伴隨式S是全零向量，則說明碼字無誤。若伴隨式S不是全零向量，則碼字序列Z中一定有錯誤。按照式(4-29)計算碼字序列中每個比特所參與的不滿足校驗方程數目。

?? ? ?? ?(4-29)
找出F中最大的，反轉對應的比特，然后重復上述過程。
綜上，Gallager的BF譯碼過程如下：
(1)、根據式(4-28)計算碼字序列Z所對應的伴隨式S，若S=0，停止譯碼并輸出Z，否則進入步驟(2)。
(2)、按照式(4-29)計算碼字序列Z中每個比特所參與的不滿足校驗方程數目，并且找出參與錯誤錯誤方程數最多的比特。
(3)、反轉步驟(2)中找到的比特，更新碼字序列Z。
(4)、判斷是否達到最大迭代次數上限，否則重復步驟(1)~(3)。
4.2.2 改進的比特反轉譯碼算法
Gallager的BF譯碼算法非常簡單，但是由于只利用了伴隨式進行解碼，丟失了較多的軟信息，因此性能較差。后來的研究人員在其基礎上又提出了一系列改進的BF譯碼算法。Chan等人借助一個“Taboo”函數來輔助每次迭代過程中反轉比特的選擇，防止同樣的比特被反復反轉；Kou等人提出了一種加權的BF譯碼算法；Zhang等人對此甲醛算法進行優化，進一步提升了性能；Dong等人也對BF算法進行了研究，并提出了基于加權錯誤校驗的比特反轉算法（Weighted Violation based Bit Flipping, WABF）,這種算法較其他算法最大的區別是，它并沒有利用任何軟信息進行算法加權優化，同樣實現了性能的提升，是一種純粹的硬判決譯碼，因此實用性更強，一下做詳細介紹。
假設校驗矩陣 大小為 ，具有統一的列重和行重。 表示接收到的硬判決序列。則z的伴隨式表示為 。令 表示第i個比特節點所參與的校驗錯誤的方程數目； 表示校驗錯誤的方程集合。第m個校驗方程所含有的比特節點的集合表示為 。第n個比特節點所參與的校驗方程的集合為 。
WVBF算法原理如下：
(1)、計算伴隨式s。若s全為0，則停止譯碼。
(2)、計算 ，i=1,2,…,N。
(3)、對m=1,2,…,M，若 ，則計算 。
(4)、對m=1,2,…,M和i=1,2,…,N，若 并且 ，則計算 。
(5)、對i=1,2,…,N，若 ，則計算 。 越大，表示第i個比特節點出錯的概率就越大。若 ，則 。
(6)、找到 最大的比特節點，并反轉它。
重復(1)~(6)，直到伴隨式為全0，或者達到最大迭代次數。
4.3 優化的基于加權錯誤校驗的LDPC比特反轉算法（IWVBF）
在WVBF算法中，一次迭代只能反轉一個比特。而譯碼的收斂所需的平均迭代次數和 有關（N為碼長，p表示接收到的應判決序列的所有比特節點的錯誤概率），因此譯碼速率較低。在此提出一種優化的WVBF算法，它會在一次迭代中反轉一組比特，大大降低了迭代次數，同時提高了譯碼性能。
設定一個判決門限t，t為相對于 恰當選擇的一個大于0的實數。由于 在一次迭代中最多有 種可能的取值，很多比特的 都有可能超過門限，故可以將所有超過此門限的 所對應的比特在一次迭代中全部反轉。因此WVBF算法中步驟(6)可以改進為：
若， ，則反轉所有超過門限的比特節點。
直觀看來，門限值高，很多錯誤的比特不能被反轉，會引起誤判以致性能下降；門限值低，一些正確的比特反被糾錯，性能會更差。所以，恰當選擇門限是關鍵。
改進算法的復雜度主要體現在原先算法的步驟(4)和步驟(6)，在(4)中， 最多有 種可能的取值，我們可以在給定校驗矩陣而譯碼過程未開始時先計算出這些可能的取值，并存儲在查找表中。解碼開始后遇到出發操作只需進行查找表操作即可。令 為每次迭代中錯誤的比特數目（ 的均值為Np），WVBF算法在步驟(6)中，一次迭代中最多有 個比特滿足 。而一次迭代值反轉一個比特，因此需要( )次實數加法操作，IWVBF算法的步驟(6)在一次迭代中反轉一組比特，大大降低了譯碼的迭代次數，因而復雜度較之WVBF算法要低。?
第5章 程序流程分析
為實現對LDPC碼性能的分析，基于MATLAB編寫了LDPC碼的編譯碼程序。程序中主要包括主程序、H矩陣構建、H矩陣變換、LDPC編碼、LDPC譯碼幾個部分。本章主要內容為對程序的流程分析，以及部分函數功能的說明。
5.1 主程序
在本設計中，主程序中實現的功能主要有生成輸入序列、生成H矩陣、編譯碼以及誤碼率計算、仿真結果輸出。其中，生成H矩陣以及與編譯碼相關的功能通過函數調用的形式實現。在程序文件夾中，主程序對應ldpc_demo.m文件。
主程序的流程圖如下：
?
圖5.1 主程序流程圖
下面對主程序中的部分函數加以說明：
1、原始信息序列的生成
主程序中，通過隨機函數生成一個二進制序列作為整個程序中編碼之前的原始信息序列，相關程序代碼如下：
s=round(rand(1,cols-rows));
其中cols與rows分別為主程序中定義的H矩陣的列數和行數，cols-rows為序列的長度，當然序列的長度值可以由自己直接指定。rand()函數為隨機函數，rand(a,b)表示生成a行b列的隨機矩陣，矩陣的所有元素取值在0~1之間。round()函數為取整函數，round(a)表示對數值a中的小數部分按照四舍五入規則進行取整。
整體代碼執行結果為：生成個長度為(cols-rows)的二進制序列。
2、誤碼率的計算（BER統計）
在本設計中，誤碼率的數值是由誤碼比特數除以整體序列長度得到的。在程序中的代碼如下：
errmax=find(s~=uhat);
nerr=length(errmax);
BER=nerr/(cols-rows);
其中s為原始信息序列，uhat為譯碼后序列。?
整體程序段的執行結果為：逐個比特檢索譯碼后序列與原始序列，求出兩個序列中不相同的比特數nerr，最后用誤比特數除以序列長度得出誤碼率。
3、調制與AWGN信道傳輸部分
在本程序中，為有效仿真通信系統模型，將編碼后的序列執行bpsk調制后進行AWGN信道的仿真傳輸，傳輸后的序列再送往解碼模塊。
實現該功能的程序段為：
tx_waveform=bpsk(u,amp);
rx_waveform=awgn(tx_waveform,SNR);
其中u為編碼后序列，amp為幅度，SNR為信噪比。awgn(a,snr)函表示在信號a中加入高斯白噪聲，信噪比SNR以dB為單位。
5.2 H矩陣生成
設計中生成H矩陣采用的是隨機方法，詳細構造過程介紹見3.2.1節。在程序中，H矩陣大小為rowscols，定義列重為bits_per_col，為顯示方便，在流程圖中，我們用n代替列重，用m代替行重。在程序文件中，H矩陣生成對應genH.m文件。
生成H矩陣的程序流程如下：
?
圖5.2 H矩陣的生成
設計中，H矩陣的列重bits_per_col=3，當然也可以設置為其他值，但要注意的一點就是，列重不能取1，列重為1時，對于相應的比特節點只有一個校驗方程，這樣是不能準確完成譯碼的。列重值過大時可能會影響矩陣的稀疏性，這會在一定程度上加大運算復雜度。
5.3 編碼過程
LDPC碼的編碼在主程序中以函數調用的形式實現，編碼算法應用的是傳統編碼方法，編碼原理見2.1節線性分組碼以及3.2.2節LDPC碼的編碼思想。在程序文件中，編碼過程對應ldpc_encode.m、H2P.m、mul_GF2.m文件。
編碼過程中部分程序如下：
[P,rearranged_cols]=H2P(H);
c=mul_GF2(P,s');
u1=[c' s];
u=reorder_bits(u1,rearranged_cols);
設H矩陣大小為rowscols，程序按照以下步驟執行：
(1)、對H進行高斯消元，將其轉換為[I ?P]的形式，其中I為cols階單位陣。
(2)、c=P求得監督位。其中為原信息序列的轉置，c為求出的監督位矩陣；
(3)、將求出的監督位與原始信息序列相連接，設計中將監督位放在了信息序列的前面；
(4)、若H矩陣在高斯消元過程中有列交換，則對編碼后的碼字進行相應的列交換。對碼字進行列交換的原因見第3.2.2節。
其流程圖為：
?
圖5.3 編碼過程整體流程圖
整個編碼過程中的重點為對H矩陣的高斯消元，也是運算量較大的一個部分。，下面我們對程序中高斯消元執行過程進行簡單介紹。
設i=1:1:rows，j=rows-1:-1:1。
首先逐一檢查H的每行H(i,:)，若H(i,i)=0，則尋找該行中的第一個非零元素，并將H的該列與第i列交換，若H(i,i)=1，則不需要進行列交換，然后檢查交換后或者不需要的H(:,i)，自H(i,i)元素以下的第i+1行到第m行是否還有非零元素，若有，則將H的第i行疊加到該行，若無，則繼續檢查下一行。循環整個過程，將H轉化為左下方全為0，H(i,i)全為1的矩陣H1，最后再對H1自第rows行向第j行疊加，最終得到左邊為單位陣的矩陣。即H=[I ?P]。
5.4 譯碼過程
相對編碼過程而言，譯碼過程的運算要相對復雜的多。在本設計中，譯碼采用的是軟判決譯碼算法的SPA算法。譯碼過程相關函數對應程序文件中ldpc_decode.m、mul_GF2.m、extract_mesg.m文件。
譯碼過程流程圖如下：
?
圖5.4 譯碼過程流程圖
譯碼時概率信息初始化步驟中初始化概率p(0)與p(1)的取值是與信道有關的，在不同信道中傳輸信號，其初始化概率值是不相同的。對于AWGN信道，初始化概率值計算公式見式(4-13)、式(4-14)。整個譯碼過程在4.1節有詳細的理論描述，在這里就不再贅述。?
第6章 LDPC碼的性能分析
本章主要內容為，通過利用MATLAB軟件編程仿真來表現碼長、列重和迭代次數對LDPC碼性能的影響。仿真時采用圖5.1所示的LDPC碼編譯碼仿真框圖。
下面我們將就碼長、列重及迭代次數三方面對LDPC碼性能的影響進行分析。
6.1 碼長對LDPC碼性能的影響
應用matlab軟件針對額LDPC碼碼長分別為300、500，列重為3，最大迭代次數設置為25次進行了仿真實驗，分析研究碼長對LDPC碼誤碼性能的影響，仿真結果圖如下：
?
圖6.1 碼長對LDPC碼性能的影響

從圖中的仿真結果可以看出，在同樣的信噪比條件下，隨著碼長的增加，LDPC碼的性能不斷提高。在小信噪比區域，碼長的增加對誤碼率的改進不大，但隨著信噪比的增加，LDPC碼的誤碼率得到的明顯的改善。但隨著碼長的增加，LDPC碼的性能提高是相對的，當達到一定的碼長后，性能將會有很小的提高。這是因為一定碼長下長編碼的性能有一定的極限，隨著碼長的增大，編碼和譯碼的復雜度也增加，編碼性能就會更接近極限，性能隨碼長增加改善的就更少。
6.2 列重對LDPC碼性能的影響
應用matlab軟件針對碼長為256，譯碼的最大迭代次數為30，校驗矩陣的列重分別為2和4的情況下進行了仿真實驗。仿真得出的誤碼性能曲線如圖：

?
圖6.2 列重對LDPC碼性能的影響

從上圖的仿真結果可以看出來，在相同的信噪比下，隨著列重的增加，LDPC碼的誤碼率增大。分析其原因，因為仿真過程中所用的碼長不夠大，校驗矩陣不是足夠稀疏，增加列重，會在一定程度上降低校驗矩陣的稀疏性，在校驗矩陣不足夠稀疏的情況下，稀疏性的一定提高會給編碼對應的Tanner圖帶來大量的短環。而短環，尤其是長度為4的環，會使算法的性能惡化，導致LDPC碼性能的下降。這種LDPC碼性能上的下降會隨著碼長的增加而逐漸減小，當碼長足夠長，列重的增加對校驗矩陣的稀疏性的影響相對較小，而在譯碼時，列重大的LDPC碼比列重小的LDPC碼得到更多的校驗信息，從而得到更可靠的譯碼，所以此時，隨著列重的增加，LDPC碼的性能將會得到改善。但是當列重增加到較大時，因為校驗矩陣不具有稀疏性，性能會隨著列重的增加嚴重下降。
6.3 迭代次數對LDPC碼性能的影響
應用matlab仿真軟件針對碼長500的規則LDPC碼，列重為2，譯碼迭代次數分別為10和100的情況下進行了仿真實驗。下圖給出了上述情況下仿真得到的結果。
?
圖6.3 迭代次數對LDPC碼性能的影響
應用matlab對碼長為500的規則LDPC碼在列重為3、信噪比為4的情況下進行了仿真，得出了LDPC碼誤碼率隨迭代次數變化的曲線，下圖給出了仿真結果：
?
圖6.4 LDPC碼誤碼率隨迭代次數變化曲線
從圖6.3的仿真結果可以看出，在相同的信噪比條件下，LDPC碼的性能隨著迭代次數的增加而逐漸提高。但是通過對圖6.4的觀察發現，誤碼率并不能隨著迭代次數的增加而無限的減少，當迭代次數足夠大時，再增加LDPC碼的迭代次數，只能增加系統的時延和復雜度，其性能不會再有提高。
6.4 H矩陣變換方法對性能的影響
?? ?在設計中，采用了傳統的高斯消元法、基于下三角形式校驗矩陣以及基于近似下三角形式校驗矩陣的編碼方法對LDPC碼誤碼率進行分析和比較。用matlab顯示出的列重為4的校驗矩陣中非零元素（“1”元素）分布如下：
?
圖6.5 H矩陣非零元素分布圖
?? ?在對H進行變換的過程中，首先逐一檢查H的每行H(i,:)，若H(i,i)=0，則尋找該行中的第一個非零元素，并將H的該列與第i列交換，若H(i,i)=1，則不需要進行列交換，然后檢查交換后或者不需要的H(:,i)，自H(i,i)元素以下的第i+1行到第m行是否還有非零元素，若有，則將H的第i行疊加到該行，若無，則繼續檢查下一行。循環整個過程，將H轉化為左下方全為0，H(i,i)全為1的矩陣H1，最后再對H1自第rows行向第j行疊加，最終得到左邊為單位陣的矩陣。即H=[I ?P]。經過高斯消元后的H矩陣非零元素分布圖如下：
?
圖6.6 高斯消元后的校驗矩陣非零元素分布

轉換成下三角形式的校驗矩陣非零元素分布圖如下圖：、

?
圖6.7 下三角形式的校驗矩陣非零元素分布

近似下三角形式的校驗矩陣的非零元素分布圖如下：

?
圖6.8 近似下三角形式校驗矩陣非零元素分布

應用matlab對在碼長為512、列重為4、迭代次數為20的條件下采用圖6.6~圖6.8三種H矩陣變換形式進行編碼的LDPC碼誤碼性能進行分析，得出其性能對比圖如下：
?
圖6.9 三種編碼方式LDPC碼的誤碼性能對比
?? ?由圖6.6~圖6.8可以明顯看出，高斯消元的過程破壞了校驗矩陣原有的稀疏性，在提高了編碼過程中運算量的同時，也會使矩陣中出現較多的短環而影響性能；轉換成下三角形式以及近似下三角形式的校驗矩陣保留了原有的稀疏性，在進行仿真時，其編碼時間明顯的短于傳統編碼所用的時間。通過分析應用matlab進行仿真時所用時間以及觀察圖6.9發現，在列重較小時，除編碼時間上的差別外，三種編碼方式LDPC碼的誤碼率差別并不大，但隨著列重的增大，基于下三角形式以及近似下三角形勢H矩陣的LDPC碼誤碼性能要漸漸優于傳統編碼方式，此外列重值較大時，H矩陣并不一定能夠通過高斯消元轉換成圖6.6所示的形式，這在一個方面也顯示出傳統編碼方式的缺點。此外，通過對基于下三角形式編碼方法以及基于近似下三角形式編碼方法的性能對比可以看出，兩種編碼方式的性能差別并不大，但相比之下，還是后者的性能略好一點。實際上，平時較為常用的LDPC碼編碼方法就是基于近似下三角形式校驗矩陣的編碼方法。
?
總結與展望
?? ?信道編碼理論及技術作為現代通信系統必不可少的關鍵技術，近幾十年在Shannon信道編碼理論的指引下已經經歷了飛速的發展并取得了大量的研究成果。LDPC碼在1996年經過Mackey、Spielman和Wiberg等人的再發現后，在十年左右的時間里，取得了重大研究進展。與已經發展成熟的Turbo相比，LDPC碼擁有更優越的性能，較低的誤碼錯誤平臺，更低的譯碼復雜度。
?? ?本文回顧了信道編碼理論的發展歷史，探討了LDPC碼的基本原理，用matlab軟件對LDPC碼進行了性能仿真，并分析了碼長、列重以及迭代次數的變化會對LDPC碼的性能產生什么影響。
?? ?校驗矩陣的變換對于編碼尤為重要，本文采用隨機法構造校驗矩陣，并分別探討了采用高斯消元法、基于下三角矩陣以及基于近似下三角矩陣三種變換方法的特點及理論。相比之下，高斯消元法破壞了矩陣原有的稀疏性，導致運算量較大，性能上也不如后面二者優越。
?? ?LDPC的譯碼方法有很多，經典的主要有BF、BP、SPA等算法。各有優勢。本文中進行性能仿真時采用的是SPA譯碼算法，在譯碼過程中，比特節點和校驗節點之間傳遞的是置信度信息，即概率值。算法的原理都在文中也做了詳細的介紹。
?? ?任何一項技術的發明都是為了更好的應用，目前LDPC碼的理論發展日趨成熟，我相信：隨著硬件技術不斷發展，加之更加成熟的理論做基礎，LDPC碼作為一種優秀的信道編碼一定會在未來的通信系統中發揮出巨大的作用。
?
參考文獻
[1] ?R.G. Gallager. Low density parity-check codes. IRE Trans. Inf. Theory, 8(1):21-28, Jan. 1962.?
[2] ?Hagiwara, M. & Fossorier, M. P. C. &Imai, 等. Fixed Initialization Decoding of LDPC Codes Over a Binary Symmetric Channel[J]. IEEE Transactions on Information Theory, 2012, 58(4).
[3] ?Sridhara D, Kelley C, Rosenthal A J. Tree-based construction of LDPC codes[C]. Information Theory, Institut fur Mathematik, Zurich Univ. , 4-9 Sept. 2005:845 - 849.?
[4] ?Jin Lu & Jos M. F. Moura. TS-LDPC Codes: Turbo-Structured Codes With Large Girth[J]. IEEE Transactions on Information Theory, March 2007, 53(3): 1080-1094.
[5] ?Moura, JMF, Lu J, etal. Structured low-density parity-check codes[J]. IEEE Signal Processing Magazine, Jan. 2004, 21(1):42-55.
[6]?? ?Mackay D J C. Good error-correcting codes based on very sparse matrices. IEEE Trans. Inform. Theory, 1999; 45(2): 399-431
[7]?? ?Richardson T J, Urbanke R L. Efficient encoding of low-density parity –check code. IEEE Transactions on Information Technology, 2001; 47(2): 638-656
[8] ?戴迎春, 趙忠文, 宋楠. 基于對角線法的LDPC編碼[A]. 全國第五屆信號和智能信息處理與應用學術會議專刊(第一冊)[C], 2011.
[9] ?王鵬. LDPC碼的編譯碼原理及編碼設計[D]. 西安電子科技大學, 2004年1月..
[10] ?唐啟榮. LDPC編碼的研究與硬件實現[D]. 北京郵電大學, 2007年3月.
[11] ?劉英, 張志亮. 基于Matlab平臺的LDPC碼快速仿真研究[J]. 現代電子技術, 2010年(9):121-122,128.
[12] ?王冬梅,王秀芳,浦曉威,路敬偉. 基于Matlab的LDPC碼的研究[J]. 科學技術與工程, 2010年4月, 10(10):2472-2475.
[13] ?岳田, 裴保臣. LDPC 碼的幾種譯碼算法比較[J]. 無線電通信技術, 2006, 32(4):24-26.
[14] ?鄧薇. MATLAB函數速查手冊. 北京：人民郵電出版社, 2008年10月.
[15] ?何樹彬. LDPC碼編譯碼原理及應用. 成都：電子科技大學，2005.
[16] ?徐明遠, 邵玉斌. MATLAB仿真在現代通信中的應用. 西安：西安電子科技大學出版社，2011年4月.
[17] ?韓輝. LDPC碼編譯碼技術研究[D]. 中國科技大學, 2009.
[18] ?馬龍. LDPC碼簡化譯碼算法研究[D]. 重慶郵電大學, 2007.
[19] ?李金根, 鄭紫薇. 低密度奇偶校驗碼的編碼方法研究 [R]. 大連海事大學信息工程學院:, 2009.
[20] ?陳旭燦, 劉冬培. 改進的LDPC譯碼算法研究[N]. 電子科技大學學報, 2010年3月(第39卷第2期).


?

總結

以上是生活随笔為你收集整理的基于Matlab的LDPC码性能研究毕业设计(含源文件)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。