LDPC碼性能研究與算法優(yōu)化

1、摘要信道編碼是數(shù)字通信系統(tǒng)的不可或缺的組成部分，其中l(wèi)dpc編碼技術(shù)是編碼界 的重要成果之一。ldpc碼(low-density parity-check codes)是一種采用矩陳構(gòu)造進行 編碼，使用迭代方法進行譯碼的新型信道編碼方案，它的譯碼復雜度很低，并且擁有 逼近香農(nóng)極限的優(yōu)異性能。本文首先介紹信道編碼的發(fā)展歷程、ldpc碼的基本概念和基本原理，然后從h 矩陣(校驗矩陣)的構(gòu)造方法以和性能分析方面對ldpc碼進行了討論，并針對每 種方法提出了自己的結(jié)論和看法。介紹了 ldpc程序的整體框架，分析了程序的運行 過程以及程序中的注意事項。在理論研究方面，本文首先研究了 ldpc碼的碼結(jié)構(gòu)的

2、構(gòu)造方法。然后詳細分析 了傳統(tǒng)的ldpc編碼算法和基于下三角的有效編碼算法。然后利用matlab進行仿真， 將矩陣進行了多次的下三角變換，觀察仿真結(jié)果中信噪比和誤碼率的折線圖，得出結(jié) 論。信噪比不同，分成的最佳下三角個數(shù)不同。同一信噪比下，分割的下三角的個數(shù) 不同，對應的誤碼率也是不相同的。關(guān)鍵詞：ldpc碼矩陣變換信道編碼性能分析abstractchannel coding is an indispensable part of the digital communication system. the ldpc encoding technology is one of the impor

3、tant achievements of the coding community. low-density parity-check(ldpc)code is a class of channel code based on matrix encoding and iterative decoding. it has low decoding complexity as well as capacity approaching performance.this text first introduces the development course of channel coding， th

4、e basic principles and basic concepts of ldpc codes. then from the constructor of the check matrix，and performance analysis of ldpc codes is discussed and put forward their own views and conclusions for each method. introduces the overall framework of ldpc program，analyzed the matters of attention i

5、n the operation process and application of the program.in theory research, this text first studied the method of ldpc code in the code structure. then analyzed in detail of the traditional coding algorithms and efficient coding algorithm based on lower triangle. after that conducted a number of enco

6、ding triangular transformation using the matlab simulation, the simulation results observed snr and ber line graph, draw a conclusion. when the snr is different，the optimal number of triangle divided is different. under the same snr, the number of the triangle is divided into different，the correspon

7、ding bit error rate is not the same.key words: ldpc codes matrix transformation channel coding performance analysis目錄1 11.1數(shù)字通信系統(tǒng)11.2信道模型31.3低密度校驗碼的研究與發(fā)展31.4本文框架結(jié)構(gòu)4第2章ldpc碼的定義和編碼的原理2. 1 2.22.3ldpc碼的基本原理6ldpc碼的表示方法62.2.1矩陣的表示方法6參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參參

8、參參參參參參參參參參參參參ldpc碼的編碼思想8第3章ldpc碼譯碼算法123. 1ldpc碼譯碼算法簡介123.2硬判決譯碼算法原理133. 3bp譯碼算法的原理與優(yōu)勢16第4章ldpg碼的設(shè)計184. ldpc碼的校驗矩陣的設(shè)計19計h矩陣的整體結(jié)構(gòu)19消除四環(huán)20ldpc碼的編和譯碼流程204.4. 1校驗矩陣h的生成214.4.2 ldpc碼的編碼22ijd里）|_第5章研究不同校驗矩陣對ldpc碼性能的影響255. 15.25.3校驗矩陣h的下三角變換25不同的下三角個數(shù)對ldpc碼性能的影響26下三角校驗矩陣對性能的影響分析2633第6章總結(jié)與展望6.1 總、結(jié)

9、-336.2展望33參考文獻34致謝.36附錄37第1章緒論木章主要介紹了數(shù)字通信系統(tǒng)的構(gòu)成和通信系統(tǒng)的工作流程，簡單地介紹了數(shù)字 通信系統(tǒng)的工作原理。同時也介紹了信道編碼技術(shù)的發(fā)展歷程，簡單的闡述了信道編 碼技術(shù)的提出和各個發(fā)展階段中的代表事件，以及取得的成果。1.1數(shù)字通信系統(tǒng)通信系統(tǒng)的基本r的是將所要傳遞的信息由信源高效、可靠、安全地傳遞給信宿。 在信息傳輸時，信道屮的噪聲必然會對傳輸信息產(chǎn)生干擾，從而使可靠性降低。所以, 設(shè)計通信系統(tǒng)的核心問題在于如何減小信道屮隨機噪聲對傳輸信號的干擾，在減小信 息傳輸產(chǎn)生錯誤的同時，還要盡可能地保證信息傳輸?shù)男剩唇鉀Q通信系統(tǒng)屮，有 效性和可靠性之

10、間的矛盾。一般地，用誤碼率（ber）來衡量通信系統(tǒng)的可靠性，用 信息傳輸速率r （比特/信道）符號來衡量系統(tǒng)的有效性。早期，人們普遍認為在通 信系統(tǒng)屮有效性與可靠性之間存在著不可協(xié)調(diào)的矛盾，一方的改善必定會引起另一方 的惡化，并且指出，當功率受限時，在有擾信道上，實現(xiàn)任意小的錯誤概率的信息傳 輸?shù)奈ㄒ环椒ň褪亲屝畔鬏斔俾蕿榱?。這個觀點直到shannon信息編碼理論的奠棊 性論文“通信的數(shù)學理論”于1948年發(fā)表之后才被改變。他第一次闡明了在有擾信 道屮實現(xiàn)可靠通信的方法，并且指出，要想實現(xiàn)可靠而有效地傳輸信息，就要通過編 碼。根據(jù)shamum信息理論，數(shù)字通信系統(tǒng)的棊本組成如圖1.1所示。圖

11、1.1通信系統(tǒng)的簡化模型通信系統(tǒng)一般情況下被分為數(shù)字通信系統(tǒng)和模擬通信系統(tǒng)兩種。模擬通信系統(tǒng)所 發(fā)送的信號一般為電信號的參量連續(xù)值，例如，普通電話機輸出的信號就是模擬信號， 但是，數(shù)字通信系統(tǒng)在發(fā)送信號前，先要將連續(xù)的模擬信號變成數(shù)字信號，經(jīng)由數(shù)字 通信方式傳播之后在接收端通過相反的變換，來還原原始的模擬信號。通常數(shù)字通信系統(tǒng)的構(gòu)成如圖1.2所示。圖1.2數(shù)字通信系統(tǒng)的基本模型如圖1.2所示，信源產(chǎn)生的信號經(jīng)信源編碼器編碼之后，被轉(zhuǎn)換成二進制數(shù)字序 列。為了使序列中的冗余盡可能小，信源編碼器要用盡可能少的二進制數(shù)字來表示信 源輸出，這個過程也被稱為數(shù)據(jù)壓縮。假設(shè)信源編碼器每秒鐘發(fā)送rb比特的信

12、息，那 么，rb就被稱為數(shù)據(jù)率。在數(shù)據(jù)傳輸?shù)倪^程中，信道會引入干擾從而導致信息的接收錯誤，信道編碼器通 過給要發(fā)送的信息序列中加入一定的冗余，從而將信道引入的差錯最小化。假設(shè)信道 編碼器輸入k個信息單元，輸出我們定義1<=1:/11為該信道編碼方式的碼率，并且 稱n為一個碼字。編碼器的任務就是產(chǎn)生差別很大的碼字，因為差別越大，出現(xiàn)錯誤 判決的可能性就越小。因此，經(jīng)信道編碼后產(chǎn)生的傳輸速率為每秒錯誤!未找到引用 源。=錯誤!未找到引用源。/r比特。r是小于1的數(shù)，所以經(jīng)信道編碼之后，數(shù)據(jù)的 傳輸速率變高，也就是占用了更多的帶寬，即引入冗余。信道編碼器的意義就是在發(fā) 射功率，系統(tǒng)帶寬和設(shè)備復

13、雜性的共同約束下提高系統(tǒng)傳輸?shù)目煽啃浴＝?jīng)過信道編碼器編碼產(chǎn)生的數(shù)字信號一般不適合直接在信道中進行傳輸，因此數(shù) 字信號會經(jīng)過調(diào)制器轉(zhuǎn)換為適合在信道中傳輸?shù)哪M信號。此外，還能通過多進制的 調(diào)制方法提來高頻帶利用率。例如一個m進制的調(diào)制器，將l個數(shù)字比特映射到m 個可能的符號上去，則有m=2e，再假設(shè)符號周期為t，則定義rs=l/t為符號率，.錯 誤!未找到引用源。滿足關(guān)系式錯誤!未找到引用源。=錯誤!未找到引用源。/rl。調(diào)制后的信號進入信道進行傳輸，無可避免得要受到外界噪聲的干擾。信道包括 從調(diào)制器到解調(diào)器的所有硬件設(shè)備，存儲媒介，和傳輸媒質(zhì)。在實際的信道中，信道 要受到信道帶寬和熱噪聲的約束

14、，對于無線信道還存在多徑衰落。在接收端，系統(tǒng)采用與發(fā)射端相反的操作來恢復信號。首先，解調(diào)器對接受的信 號進行解調(diào)，如果輸出的是數(shù)字比特，并且直接對數(shù)字比特進行譯碼，那么這種譯碼 方式就被稱為軟譯碼，使用軟譯碼能夠充分利用信道信息，從而提高譯碼準確性，但 計算復雜度則比較高。1.2信道模型圖1.1所示信道部分只是對息傳輸所通過的介的一種抽象，而實際的信道則是 多種多樣的，比如電纜、光纜、存儲設(shè)備、其至連我們所處的空間和宇宙都可以是信 道。對通信系統(tǒng)的設(shè)計者們來說，必需要了解通信系統(tǒng)屮信道的特性。根據(jù)信道的統(tǒng) 計特性是否隨著時間的變化而改變，可以將信道分為平穩(wěn)信道和非平穩(wěn)信道；根據(jù)信 道的輸入和輸

15、出的取值是否是連續(xù)的，可以將信道分為離散信道、連續(xù)信道和離散輸 入/連續(xù)輸出信道；根據(jù)信道的特性對輸入端是否具有對稱性可以將其分為對稱信道 和非對稱信道；根據(jù)信道的輸出之間是否具有相關(guān)性，可將信道分為記憶信道和非記 憶信道。在實際應用中用到的信道，大多都是離散輸入的平穂無記憶對稱信道，下面 給出幾種經(jīng)常用到的信道編碼模型。二進制對稱信道（bsc）:輸入為二進制變量0和1 ,輸出也是二進制變量 0和1 ,而且，傳輸過程中發(fā)生錯誤（輸入為1輸出為0或輸入為0輸出為1） 的概率與輸入沒有夫系。二進制刪除信道（bec）:輸入為進制變量0和1 ,輸出要么是輸入的二進 制變量0和1,要么是刪除e ,而通常

16、情況下傳輸過程中不同的輸入被刪除的 概率是相同的。二進制輸入高斯信道（biawgn）:輸入為二進制變量，輸出為連續(xù)變量， 而且信道中的加性噪聲是服從n（0, <72）的高斯隨機變量。1.3低密度校驗碼的研究與發(fā)展ldpc碼是一種校驗矩陣為稀疏矩陣的線性分組碼，它是由gallager于1962年 提出，1963 年 robert ggallager 發(fā)表的low-density check-parity code一文標志 著ldpc碼的誕生，gallager把ldpc碼校驗矩陣對應到計算樹上，校驗矩陣中每列 對應于閣中的一個變量節(jié)點，每行對應于一個校驗節(jié)點，校驗矩陣中的非零元素所在 的行和

17、列對應的變量節(jié)點和校驗節(jié)點之間有邊相連。gallager證明ldpc碼的最小漢 明距離隨著碼長的增加而線性增加，并且在計算樹上進行后驗概率迭代譯碼可獲得隨 碼字長度增加而降低的比特錯誤概率。雖然gallager己經(jīng)證明了 ldpc碼是具有漸近 特性的好碼，但由于當時計算能力有限，所以ldpc碼一度被認為是一種不實用碼， 在很長的一段時間內(nèi)不被人們所重視。1981年tanner在廣泛研究悶碼的基礎(chǔ)上提出了規(guī)范悶碼的表示方法tanner圖（也稱二分圖），這種方法是把校驗約束建立在局部碼元集合上。從tanner圖上可 以直觀地理解ldpc碼譯的碼過程。直到1996年r.neal和d.mackay彳證

18、明了 ldpc碼是一種好碼，并且，推廣了 gallagcr的概率迭代譯碼算法，論述了和積算法（也稱 bp （置信傳播）算法）的詳細方案，極大地推動了 ldpc碼的發(fā)展，成為ldpc碼 的發(fā)展的里程碑。1997年luby等人首先提出了非規(guī)則ldpc碼，并證明了非規(guī)則 ldpc碼比規(guī)則ldpc碼有更好的性能。實際上在構(gòu)造ldpc碼時，其tanner圖必定存在小環(huán)，這樣就會造成譯碼性能 的下降。要想構(gòu)造好的ldpc碼，可以從兩個方而進行研宂：其一，構(gòu)造綜合性能更 好的碼，其二，尋找構(gòu)造碼的分析方法。a. h. banihashcmi和mao yongyi根據(jù)碼性 能提出根據(jù)圍長（girth）的分布來

19、設(shè)計ldpc碼，hu xiao-yu等人提出丫漸進邊增 長（progressive edge-growth）的構(gòu)造碼算法，適用于隨機構(gòu)造ldpc碼，通過對圍 長進行優(yōu)化，可以消除小環(huán)。tanner等人用循環(huán)矩陣構(gòu)造的ldpc碼校驗矩陣，圍長 很大。shu li和yu kou等人利用有限幾何法構(gòu)造ldpc碼，給出丫 4種基于euclidean 空間的點和線設(shè)計出的碼，但是wiberg通過對因子圖的研宄發(fā)現(xiàn)，對任意給定的系 統(tǒng)，無環(huán)圖的狀態(tài)復雜度是最大的，有環(huán)圖的狀態(tài)復雜度則很小，證明基于有環(huán)tanner 圖的ldpc碼具有較低的譯碼復雜度。mackay等人指出消除4環(huán)對碼的性能將會有 很大的提高

20、，但是，繼續(xù)消環(huán)對于碼的性能提高的影響則越來越不明顯。urbankc和 richardson等人總結(jié)發(fā)展了 luby的分析方法，提出了密度進化（density evolution） 方法，分析了消息快遞譯碼卞的ldpc碼的容量，設(shè)計出非規(guī)則ldpc碼，這種非規(guī) 則碼非常接近香農(nóng)極限，論述了快速ldpc碼的編碼方法，對ldpc碼的研宂和發(fā)展 做出了極大貢獻。在以上工作的棊礎(chǔ)上，ldpc碼的研究在譯碼算法上的簡化，密度進化的改進， 非規(guī)則碼度數(shù)設(shè)計，校驗矩陣的構(gòu)造，距離特性和性能界限的分析，通信和數(shù)據(jù)存儲 的應用，ldpc碼的實現(xiàn)等方而展開，己取得非常多有價值的成果，并在實際系統(tǒng)中 得到應用。1.

21、4本文框架結(jié)構(gòu)本文對ldpc碼進行了深入研宄，通過查閱大量的中外文資料，對ldpc碼的 發(fā)展變化、工作過程以及工作原理等方面進行了詳細的闡述。木論文主要研究了通過 對h矩陣進行不同個數(shù)的下三角變換，對ldpc碼編碼解碼后誤碼率的影響，通過 matlab進行仿真。第一章，緒論。木章主要介紹了 ldpc的基礎(chǔ)知識，介紹了數(shù)字通信系統(tǒng)的構(gòu)成 以及信道編碼技術(shù)的發(fā)展歷程。第二章，ldpc碼的定義和編碼原理。本章主要介紹了 ldpc碼的定義，介紹了 矩陣表示和tanner圖表示這兩種棊本表示方法。同時也詳細講述了 ldpc碼編碼的 思想。第三章，ldpc碼譯碼算法。主要介紹了 ldpc碼的譯碼思想，簡要

22、介紹了軟判 決算法和硬判決算法的發(fā)展歷史。舉例介紹丫 gallager硬判決譯碼算法和ldpc碼的 bp譯碼算法的原理和工作過程。第四章，ldpc碼的設(shè)計。本章主要介紹了校驗矩陣h的生成過程框架，需要注 意的事項以及消除四環(huán)的原因。同時也詳細介紹了 ldpc碼的譯碼流程圖，以及運行 程序的介紹。第五章，就不同校驗矩陣對ldpc碼性能的影響。本章主要是提出了把原矩陣h 變換成不同多個下三角矩陣，對ldpc碼性能的影響問題。然后對此次猜想進行 matlab仿真，探宂h矩陣經(jīng)過不同處理后信息傳輸?shù)恼`碼率之間的關(guān)系，畫出折 線圖以及表格，得出結(jié)論。第六章，簡要概述丫本文介紹的內(nèi)容，對本論文進行了總結(jié)。

23、并且對ldpc碼進 行了闡述，展望了 ldpc碼的發(fā)展前景和發(fā)展方向。在一定時間段里ldpc碼仍然會 是比較熱門的信息傳輸方法。第2章ldpc碼的定義和編碼的原理本章介紹了 ldpc碼的定義，簡單闡述了 ldpc碼元的基本的原理。同時介紹了 矩陣的表示方法和tanner圖表示方法這兩種ldpc碼基本表示方法，舉例描述了這 兩種表示方法。同吋也詳細描述了 ldpc碼的編碼思想，為以后的matlab程序仿 真打下基礎(chǔ)。2.1 ldpc碼的基本原理ldpc(low density parity check)碼又叫做低密度奇偶校驗碼，是一種校驗矩陣非 常稀疏的線性分組碼，也就是說它的校驗矩陣h中非零元

24、素的個數(shù)遠遠要比零元素 的個數(shù)耍小，或者矩陣的行重和列重與碼長相比很小。由于ldpc碼的這些特性，使 其可以構(gòu)造出高性能、低復雜度的編碼。2.2 ldpc碼的表示方法ldpc碼的表示方法一般分為兩種，即矩陣的表示方法和tanner圖表示方法。2.2.1矩陣的表示方法ldpc碼是一種線性分組碼,ldpc碼的碼字由校驗序列和信息序列兩部分組成, 令碼長度為n,信息序列長為k。我們可以使用mxn維的校驗矩陣來唯一地表示一 個碼字。校驗矩陣的每一行可以看成是一個奇偶校驗方程，每一列是該碼字的一位。 每一行非零元素的個數(shù)稱之為行重，我們用么來表示；每一列非零元素的個數(shù)稱為 列重，我們用de來表示。校驗矩

25、陣h的行數(shù)m的值等于碼字要滿足校驗等式的個數(shù), 碼字的每個比特都參與了 dv個校驗等式的校驗，而每個校驗等式包含了碼字中山個 不同比特位。以下面的一個例子來具體說明ldpc碼的矩陣表示：設(shè)一個規(guī)則的ldpc碼的校驗矩陣h如下：（公式2-1）h=110 10 0 0 0 1110 1 0 0 0 1 1 0 110 0 1由式（2-1）知，該規(guī)則ldpc碼的行重山為3,列重錯誤!未找到引用源。為2，設(shè)c=（錯誤!未找到引用源。錯誤!未找到引用源。錯誤!未找到引用源。）滿足該校 驗方程的一個碼字，則有h 錯誤!未找到引用源。=0,即要滿足下面的關(guān)系式。"cl +c2 +c3=oc3 +c

26、4 +c5=0cl +c5 +c6=0（公式 2-2）c2 +c3 +c6=0上式中的加號是二進制加法，經(jīng)過驗證，c=l 00 11 0是符合以上校驗方程的一 個碼字。2.2.2 tanner表示法ldpc碼除了用校驗矩陣h來表示外，還可以用tanner圖表示。tanner圖表示 法是一種非常形象的表示方法，為我們理解和分析ldpc碼的譯碼過程提供了很大的 方便。tanner圖是雙向圖，它將節(jié)點分成兩個不同的集合，任何一個集合的內(nèi)部節(jié)點 沒有連線，只有不同的節(jié)點間才有連線。我們令e表示各邊的集合，v表示各節(jié)點的集合，那么，一個由節(jié)點和節(jié)點之間 的連線所構(gòu)成的tanner圖，就可以表示成g=（v

27、，e）。節(jié)點集合（v） 乂分為兩個 不相交的子集，假設(shè)校驗矩陣h是mxn維的，那么，變量節(jié)點集合就可以表示為 錯誤!未找到引用源。=（錯誤!未找到引用源。，錯誤!未找到引用源。，錯誤!未找到 引用源。），校驗節(jié)點表示為錯誤!未找到引用源。=（bi,b2,-bn）,且滿足關(guān)系v=錯誤! 未找到引用源。u錯誤!未找到引用源。，錯誤!未找到引用源。n錯誤!未找到引用源。 =錯誤!未找到引用源。以上式（2-1）中的校驗矩陣為例，它的tanner圖如圖2.1所示。圖2.1校驗矩陣的tanner圖表示如圖2.1所示，校驗矩陣的每一行對應一個校驗節(jié)點，每一列對應一個變量節(jié)點。 如果校驗矩陣的第i行，第j列是

28、非零元素，則在tanner圖上，第j個變量節(jié)點和第 i個校驗節(jié)點之間有一條邊相連，即節(jié)點錯誤!未找到引用源。與錯誤!未找到引用源。 之間有一條邊相連，邊（錯誤!未找到引用源。，錯誤!未找到引用源。）錯誤!未找到 引用源。e。與節(jié)點相連的邊的數(shù)目為節(jié)點的度（degree）,校驗矩陣的行重,列重與tanner 圖上校驗節(jié)點的度、變量節(jié)點的度是相對應的。我們定義，從某個節(jié)點出發(fā)到再次ih 到該節(jié)點為一個循環(huán)（cycle），所經(jīng)過邊的個數(shù)稱為循環(huán)k:度（girth），在.上面的tanner 圖中，我們可以看到6條粗線構(gòu)成一個有向閉合環(huán)路，它由bl出發(fā)，經(jīng)過6條邊后 乂ihj到了 bl，它的循環(huán)長度為6

29、。我們把tanner圖中最短的循環(huán)長度稱為最小圍長。2.3 ldpc碼的編碼思想ldpc碼的編碼步驟如下：1. 低密度校驗矩陣構(gòu)造ldpc碼，完全由其校驗矩陣來確定，因此，要對ldpc 碼進行編碼，首先要構(gòu)造一個校驗矩陣。如今，低密度校驗矩陣的構(gòu)造方法已經(jīng)有很 多了，假設(shè)已經(jīng)構(gòu)造了一個校驗矩陣h，那么，就可以從碼字空間中選出一組可用碼 字，作為所需構(gòu)造的ldpc碼。2. 為了方便在譯碼的時候確定信息比特的位置，需要用到高斯消元，將非系統(tǒng) 形式的校驗矩陣h,轉(zhuǎn)化為系統(tǒng)形式：h=錯誤!未找到引用源。，i，其中i為單位 矩陣。3. 利用校驗矩陣來得到生成矩陣0=1少。4. 用生成矩陣g與信息序列u相

30、乘，得到編碼輸出碼字：c=u錯誤!未找到引用源。g=u，u錯誤!未找到引用源。p（公式2-3）0前，過長的編碼時延和過高的編碼復雜度，是阻礙ldpc碼的應用的主要因素。 上面介紹的ldpc碼的編碼方法的編碼復雜度為碼長的二次方，碼長很長情況下的編 碼復雜度過高將成為ldpc碼應用的瓶頸。上述ldpc碼的編碼方法的復雜度之所以高，是因為，在構(gòu)造生成矩陣的吋候， 對校驗矩陣進行y高斯消元處理，從而，破壞丫原校驗矩陣的稀疏性，使得生成矩陣 包含人量的“ 1 ”元素。一種改進的法是richardson和urbanke提出的矩陣變換法， 該方法的編碼處理過程分為兩步：即預處理過程和實際編碼過程。預處理過

31、程是一個離線計算過程，針對一個給定的碼字，只需要作一次計算，而實際編碼過程是對傳輸 數(shù)據(jù)的處理。（公式2-4）在urbankc等人的矩陣變換算法中，設(shè)輸入的信息的系統(tǒng)比特部分為s,通過編 碼得到的校驗比特部分為錯誤!未找到引用源。和錯誤!未找到引用源。，則碼字c = （s，錯誤!未找到引用源。，錯誤!未找到引用源。），滿足h錯誤!未找到引用源。=0。 對校驗矩陣進行行和列的變換，如果能夠化成下三角矩陣的形式，則編碼的復雜度是 線性的。一般來說，通過行列變換是能夠?qū)⑿ｒ灳仃嚮扇缦碌慕葡氯蔷仃嚨模篶 d e該矩陣形狀如圖2.2所示。將校驗矩陣左乘如k矩陣t1（公式2-5）i 0-et-1 i

32、可得到：ab t（公式2-6）-et_1/（+c - et'+d 0 那么h錯誤!未找到引用源。=0可以分解成如下的兩個表達式：ast+bpf+tp=0（公式 2-7）（-et、+c）st+（- et !7?+0）?=0（公式 2-8）定義*= -et'+d,并且假設(shè)（b非奇異，則求解上面兩表達式可得：錯誤!未找到引用源。=-（公式2-9）錯誤!未找到引用源。-t'asbpf）（公式2-10）通過以上兩個公式可以計算校驗信息pjup2,從而得到碼字。k面對這種矩陣 變換的編碼方法的復雜度進行了簡單分析，由前面的推導可知，因為系統(tǒng)的信息比特 可以直接獲得，所以復雜度就集屮

33、在了 pl和p2的兩個公式的計算上面。根據(jù)richardson和urbanke對復雜度計算的描述，對于pi和p2計算的復榮度估 計分別如表2-1和表2-2所示。表2.1校驗信息pl的計算復雜度分析操作解釋復雜度as1稀疏矩陣與向量的乘法0(n)t_, (ast)令yf=ast,復雜度同上0(n)-r(t 'ast)令ytls1，復雜度同上0(n)cst稀疏矩陣與向量的乘法0(n)(-er1 ast) + (cst)兩個向;s:的加法運算0(n)(-et 1 as1+ cst)gxg的密集矩陣與叫量的乘法0(g2)表2.2校驗信息pl的計算復雜度分析操作解釋復雜度ast稀疏矩陣與向量的乘

34、法0(n)bpf稀疏矩陣與向量的乘法0(n)(as1 ) + (bp )兩個向量的加法0(n)-r* (ast +bpf)y 3 =（ast+ bpf）,則得-r'y;仍然是稀疏矩陣5向®的乘法0(n)統(tǒng)計兩個計算校驗信息pl和p2的復雜度分析表的數(shù)據(jù)，可以獲得矩陣變換方法 的編碼復雜度o（n+g2）。要想降低編碼的復雜度，應該讓g盡量的小。richardson等人在文章中提出三種greedy算法對矩陣的下三角化變換進行了討論，它們分別是 greedy 算法 a, greedy 算法 b 與 greedy 算法 c,其屮，greedy 算法 ah, greedy 算 法bh與

35、greedy算法ch分別表示直接作用于算法a、b和c的校驗矩陣，而greedy 算法aht, greedy算法bht與greedy算法cht則表示作用于三種算法的校驗矩陣 的轉(zhuǎn)置。三種greedy算法可以讓g盡量減小，從而降低ldpc編碼的復雜度。矩陣變換算法的編碼過程總結(jié)如下：art第一步：預處理過程，輸入非奇異校驗矩陣，輸出形如的等價c d e矩陣，并且保證-etb+d為非奇異矩陣。預處理過程中，包括矩陣的近似下三角轉(zhuǎn)換 art和矩陣的秩校驗。通過行和列的置換將校驗矩陣變換成形如的近似下三角c i） e矩陣形式，并通過運用greedy算法讓g盡量的減小。矩陣的秩校驗是利用高斯消完 成如下矩

36、陣的運算：i0-et'1ib t i a d e |-et-+cb t -et1 腫d 0（公式2-11）關(guān)鍵是檢驗矩陣-et-1b+d是否為奇異矩陣，如果是奇異的，那么需耍再次進行 列置換最終將其變成非奇異形式。第二步:實際編碼過程，當校驗矩陣已經(jīng)化成了形d的非奇異矩陣時，對于給定的輸入信息序列s，只需要通過（公式2-9）和（公式2-10）計算校驗信息pl 和p2就可以得到編碼輸出碼字c=（s，錯誤!未找到引用源。，錯誤!未找到引用源。）。校驗矩陣變換編碼算法雖然可以使編碼復雜度近似呈線性，但是對編碼矩陣的原 始結(jié)構(gòu)耍求比較高，許多矩陣只通過簡單的行列置換滿足不了該方法的諸多限制條

37、件，因此，應用起來也遇到一定的困難。降低編碼復雜度的另外一個有效的方法是設(shè) 計擁有特殊結(jié)構(gòu)的校驗矩陣，比如循環(huán)碼與準循環(huán)碼，只通過信息位或校驗位數(shù)量的 移位寄存器就可以實現(xiàn)此類編碼，復雜度低，沒有大的編碼延遲，與分組長度成線性 關(guān)系，而且硬件實現(xiàn)也很簡單。類循環(huán)碼己經(jīng)成為當前研究的一個熱點。第3章ldpc碼譯碼算法ldpc碼的編碼性能以及應用前景取決于信道編碼的譯碼算法。特別是在碼長較 長的情況下，譯碼算法的復雜度決定了編碼的應用前景。根據(jù)線性分組碼的基本原理 我們知道，譯碼復雜度與碼長呈指數(shù)關(guān)系，隨著碼字的增長，譯碼復雜度將按照指數(shù) 方式增長。當碼長到達一定的長度后，譯碼的復雜程度就趨于無窮

38、大。但是，ldpc 碼的校驗矩陣是稀疏矩陣，所以它的譯碼復雜度大大地降低，譯碼復雜度與碼長近似 于線性的關(guān)系。因此，克服了碼字較長時譯碼算法復雜度高的缺點，使較長碼字的應 用前景更加寬廣。3.1 ldpc碼譯碼算法簡介在差錯控制編碼領(lǐng)域的第一個量化飛躍在于意識到了將譯碼和解調(diào)分離幵來會 帶來損失。為了補償由解調(diào)器引入的差錯，差錯控制編碼理論才被提出。在這個思想 的指引下，調(diào)制解調(diào)器首先要判斷調(diào)制器的輸入是什么，然后，將判決結(jié)果輸入到譯 碼器中；再使用已知的碼字結(jié)構(gòu)來判斷編碼器輸入端的碼字是什么。這個過程稱為 “硬”判決譯碼；但是，它不是最佳的譯碼方法，因為每執(zhí)行一次硬判決，解調(diào)器都 會丟掉一些

39、可能會有用的信息，而且我們知道，不能在執(zhí)行完與這個信息有關(guān)的所有 判決之前，將信息提前丟棄。將編碼和調(diào)制相結(jié)合，解調(diào)器就不會把一些錯誤傳遞給譯碼器。解調(diào)器僅僅對各 種符號進行短暫的估計，通常被稱為“軟”判決，這樣就不會丟掉一些對譯碼器來說 有用的信息了?！白罴选弊g碼器可以采用map（最大后驗概率）算法，將誤碼率（ber） 最小化。軟判決譯碼與硬判決譯碼相比，在性能上，有一定程度的提高。如果采用軟 判決譯碼方法，信號的snr （信噪比）相對于硬判決將具有2db的優(yōu)勢。硬判決譯碼時，采用碼字間的漢明距離最大化原則；而軟判決譯碼，則釆用幾何 距離（歐式距離）最大化的準則。因此，在執(zhí)行軟判決譯碼時，我

40、們常說針對“信 號空間”進行譯碼。gallager在提出ldpc碼的同時，也給出了兩種迭代譯碼算法：硬判決譯碼（bit flipping）算法和軟判決譯碼算法。前者的計算復雜度很低，只需要用到模二運算，侶 是它的譯碼性能不理想，后者雖然譯碼性能更好，侶它的復雜度太高。對硬判決算法 來說，采用信道的軟信息對比特翻轉(zhuǎn)的判據(jù)進行加權(quán)的方法，可以在譯碼復雜度增加 不是很大的情況下，提高譯碼的性能。wbf譯碼算法縮小了與軟判決算法之間的差 距，它的譯碼性能有了很大的提高。1996年，mackay和neal提出了 bp（ belief propagation）算法，也叫做sum.product算法，它的譯

41、碼性能要比硬判決譯碼算法的 性能好很多，但它的運算復雜度卻不大。fossoricr對低復雜度情況下的的bp譯碼算 法作了進一步的研宂，提出bp. based譯碼算法，將bp譯碼算法進行了簡化。為了 改善bp-based譯碼算法對校驗節(jié)點上的簡化處理而造成性能上的損失，j.chen提出了 兩種改進算法，第一種：采用歸一化的，近似最佳bp.bascd算法（也叫做normalized bp. based算法）；男一種：以損失可靠性來換取外附信息精度的offset bp. based 算法。最小和（min-sum ）譯碼算法是根據(jù)對數(shù)域bp算法而提出的一種近似地簡化 算法，它用求最小值的運算的方法簡化

42、了函數(shù)運算，從而，大大降低了運算復雜度， 而不需要對信道噪聲進行估計，但是它的性能也有一定程度上的降低。3.2硬判決譯碼算法原理gallager提出的ldpc碼是一種基于規(guī)則的稀疏二分圖的信道糾錯碼。一個具有 n個變量節(jié)點和r個校驗節(jié)點的二分圖，可以用如下方法，生成對應的維數(shù)k > n 一r的長為n的線性碼：將碼字的比特位和變量節(jié)點一一對應。二進制域上的矢量 x=（xl, x2, x3, x4xn）當滿足方程h*x=0時，為一個碼字，這里的h為二分圖維的關(guān)聯(lián)矩陣，它的列對應于二分圖的變量節(jié)點，行對應于二分圖的校驗節(jié) 點。也可以說，當每一個校驗節(jié)點的相連變量節(jié)點值的異或為0時，其對應的二進

43、 矢量（xl, x2, x3，x4,xn）為一個碼字。下面，只從二分圖的角度來討論，并且，假設(shè)變量節(jié)點產(chǎn)生了某種錯誤。考慮到 變量節(jié)點的度為da,校驗節(jié)點的度為dp的規(guī)則隨機圖，變量節(jié)點，接收到錯誤的 信息比特的概率是p。采用循環(huán)迭代的譯碼算法，每次進行迭代的時候，首先，由變 量節(jié)點發(fā)送一比特的信息到與其和連的校驗節(jié)點，然后，校驗節(jié)點發(fā)送一比特的信息 到與其相連的變量節(jié)點。為了更好地描述譯碼過程，對于變量節(jié)點n與校驗節(jié)點m 相連的邊圖3.1給出了一個描述n的相連節(jié)點的樹。其中，用n表示根節(jié)點， 用n的校驗節(jié)點（除p以外）表示分支節(jié)點。以下的譯碼算法中，我們假設(shè)，對小 于某一最大次數(shù)的迭代來說，

44、n的深度是迭代次數(shù)的兩倍時，其相連節(jié)點可以用一樹 描述。即圖3.1中的循環(huán)的忪度沒有比迭代次數(shù)的兩倍要小的。每一個變量節(jié)點n, 存儲一個接收比特的硬判決信息rn （錯誤概率為p），每一條邊（n，w存儲一比 特節(jié)點n的正確信息的猜測值gn.m。這個猜測信息在譯碼迭代中逐次更新。在每次 迭代循環(huán)過程中，邊（n，h）都要雙向傳遞信息。其迭代過程如下所示：（1）對所有的邊（n，）!）并行地執(zhí)行如下操作：如果是第一次進行這代，令g n.g=rn ,否則，按照如下方法來計算gn# :如果上一次迭代過程中，和節(jié)點n相連（除m以外）的所有的校驗節(jié)點發(fā)送給的信息比特都相同的話，那么，就將 該值賦給gn.p,否則

45、的話gn.g=rn。這兩種情況下，變量節(jié)點n都把值gn +發(fā) 送給校驗節(jié)點（2）對所有邊（n，m）并行地執(zhí)行以下操作校驗節(jié)點將其在本次迭代過程屮從除n之外的其他相連節(jié)點收到的信息的異 或值發(fā)送給變量節(jié)點n。如果圖3.1中沒有循環(huán)，那么，上述算法在所有的校驗都得 到滿足的時候結(jié)束，否則的話，繼續(xù)進行迭代，一直迭代到超過某一預設(shè)的最大迭代 次數(shù)時才停止，各節(jié)點如圖3.1所示。圖3.1變a節(jié)點與校驗節(jié)點局部樹形下面直觀地解釋一下上述算法。節(jié)點n的某個校驗節(jié)點g，將除n之外的所有與 之相連校驗的節(jié)點的異或值發(fā)送給n ,這相當于校驗節(jié)點g，根據(jù)除n節(jié)點之外的相 連節(jié)點提供的參與校驗的信息，向n節(jié)點提出耍

46、求。為了使該校驗約束得到滿足，在 假設(shè)其它節(jié)點所提供的信息是正確的條件下，n節(jié)點應該取它的異或值。但是n節(jié)點 不一定會響應該耍求。如果，除以外所有的校驗節(jié)點都向n節(jié)點提出相同的耍求， 那么，n會響應該要求，并將這個要求的值作為n的猜測信息，發(fā)送給節(jié)點參與 到節(jié)點g的校驗檢查中，節(jié)點將利用這條信息和從其它變量節(jié)點獲得的信息向其 它的校驗節(jié)點提出新耍求。如果，除以外的節(jié)點提出的耍求不完全相同，那么，n 不響應任何耍求，而是將它的初始接收信息r,發(fā)送給校驗節(jié)點fu令pk表示第k次迭代中，節(jié)點n發(fā)送給節(jié)點m錯誤的信息的概率，譯碼迭 代之前，有pn=p。下面將給出遞推形式的方程，來描述概率pk，隨迭代次

47、數(shù)的增加 的演變規(guī)律。在第k次迭代結(jié)束時，對與節(jié)點n除m以外的另一校驗節(jié)點如果， 除n以外的與之相連的變量節(jié)點中，有偶數(shù)個發(fā)送給節(jié)點g的錯誤信息，那么，發(fā)送 給n的要求信息仍然是正確的。由于發(fā)送給g的，每個信息的錯誤率為pk,那么， 易得m接收到偶數(shù)個錯誤的概率為：y _ 0 一巧 + pw1 + 0 一一 w1錯誤!未到引用源。（公式 3-1）上式中，奇數(shù)項相互抵消。在進行第k+l次迭代時，節(jié)點n接收到錯誤的初始信息錯誤!未找到引用源。，發(fā)送出的正確信息的概率為：錯誤!未找到引用源。（公式3-2）同理，第k+l次迭代中，正確地接收到n的初始信息，但發(fā)送錯誤信息的概率 為：錯誤!未找到引用源。

48、（公式3-3）綜上所述：pku=po錯誤!未找到引用源。+錯誤!未找到引用源。（公式3-4）由此，就可以找到所有使pk單調(diào)下降，并且收斂到0的po的值的上界p。上面所說的譯碼規(guī)則，要求n除以外所有的校驗節(jié)點，都對i節(jié)點提出相同的校驗要求時，n節(jié)點才會響應其要求，發(fā)送該信息到p節(jié)點，參與到新一輪的校驗中。 但是，這一要求似乎太過嚴格，可以適當?shù)胤潘桑捍_定一個依賴于迭代次數(shù)的門限值 對于每一對變量節(jié)點n和與其相連的校驗節(jié)點如果n除了 m以外的，所有與之相 連的節(jié)點中，有至少丫k個節(jié)點在上一的次迭代中，對n提出了相同的要求，那么， 在本次迭代中就將該信息發(fā)送給節(jié)點y否則，發(fā)送初始值rn給其它的譯碼算

49、 法保持不變。對于修改過的算法，可利用類似于（公式2-2）的推導方法，來得到獲 得錯誤!未找到引用源。的遞推計算公式。由公式（2-2）,我們可以得出，當pk減少時，只需要很少的校驗節(jié)點提出相同 的要求，就可以推測出n節(jié)點的正確的信息值。該算法在運行時，沿著二分圖中的邊 發(fā)送信息，同時，該算法能夠基于發(fā)送的信息，在運行中動態(tài)地猜測每個變量節(jié)點的 值。當變量節(jié)點的猜測值滿足了所有的校驗節(jié)點時，算法就認為它成功地譯出了原信 息而宣告結(jié)束；如果迭代次數(shù)到達了預設(shè)的最大值而失敗，算法就停止進行。如果不 滿足上述兩個條見，算法將繼續(xù)進行。3.3 bp譯碼算法的原理與優(yōu)勢neal和macka將pearl的譯

50、碼算法和傳播算法相聯(lián)系，通過對beliefpropagation 算法的表述，解釋了由gallager提到的ldpc碼的軟判決算法。bp算法在二分圖中沒有圈的情況下，將和最大似然譯碼mld(macimun likelihood decoding)算法效果相 一致，但是，在編碼長度有限時，尤其是在碼長較短的情況不，二分圖屮存在大量的 短環(huán)。在這種情況下，bp譯碼算法的性能和最大似然譯碼算法的性能還有一定的差 距。盡管如此，bp譯碼算法的性能仍然比硬判決譯碼算法要好的多。ldpc碼采用基于有向二部圖的bp譯碼算法進行譯碼。校驗矩陣h= ( hij) m*n 其中m=n-k。如圖3.2所示。圖3.2

51、 ldpc碼的因子圖碼字x= ( xl，x2，x3，x4xn )表示為一組變量節(jié)點 xj : j=l，2/“n ，如圖3.2 左側(cè)所示。校驗函數(shù)則表示為一組校驗節(jié)點z:i=l,2,3m),如圖3.2右側(cè)所示。 當且僅當hij =1的時候，因子圖從變量節(jié)點xj到校驗節(jié)點zi之間才有一條有向邊。 在h矩陣中，我們將參與第m個校驗約束的信息比特集合定義為r(m)= y : hmy = 1)。同理，我們將參與第y個信息比特校驗的集合定義為m(丫)=m:hmy=l 。其 屮，r(m)/y為r(m)和第y個信息比特的差集，它表示，除了 y之外與m相連的碼 字節(jié)點的個數(shù)。此算法包含兩個互相交替執(zhí)行的部分，和

52、校驗矩陣h中非零元素有 關(guān)的數(shù)值rma和qmx反復迭代更新。在已知其他所有校驗約束信息(m除外)時， x碼字的第人比特取值為x的概率是在已知x第y比特值為x時，其余比特滿 足互相獨立的概率分布。當q<:y er(myy時，第m個校驗約束的概率為錯誤!未 找到引用源。本算法考慮到編碼器輸出的序列經(jīng)bpsk (二相移位鍵控)調(diào)制后，映射為2 2+xo，-xo。令噪聲功率譜密度為n0=2sl其中，噪聲是均值為0,方差為8的高2 2 2斯信號，其密度函數(shù)為n(0, 8-)o單位信噪比為eb/n0=xq/2rs。，其中，r為碼率。如果由校驗矩陣所定義的二部圖屮沒有環(huán)，本算法可以得到所有比特的精確后

53、驗概率，具體譯碼算法如下所示：0 2 1第一步：初始化。令 p:，=p(xy =0)=l/(l+cxp(-2y y /8«),=p(x y=l)分別來表示xy取0和1時各自的先驗概率，并且(3，+p，= l。其屮yy為信道輸出。錯誤!未找到引用源。=錯誤!未找到引用源。（公式3-5）錯誤!未找到引用源。=錯誤!未找到引用源。（公式3-6）第二步：計算錯誤!未找到引用源。和錯誤!未找到引用源。錯誤!未找到引用源。=錯誤!未找到引用源。（公式3-7）錯誤!未找到引用源。=錯誤!未找到引用源。（公式3-8）其屮概率？錯誤!未找到引用源。的和為模2和。假設(shè)錯誤!未找到引用源。的值是否滿足模2

54、決定了條件概率為0或者為1。那么，可以進一步簡化（公式3-7）和（公式3-8）兩式子。令識錯誤!未找到引用源。=錯誤!未找到引用源。_錯誤!未找到引用源。（公式3-9）對每一個m,計算：%錯誤!未找到引用源。=錯誤!未找到引用源。（公式3-10）利用數(shù)學歸納法可得：錯誤!未找到引用源。=錯誤!未找到引用源。（公式3-11）錯誤!未找到引用源。=錯誤!未找到引用源。（公式3-12）第三步：對每一個m和y，利用第二步中計算出的結(jié)果來更新錯誤!未找到引用 源。和錯誤!未找到引用源。：錯誤!未找到引用源。=nmy錯誤!未找到引用源。（公式3-13）錯誤!未找到引用源。=nmy錯誤!未找到引用源。（公式

55、3-14）其中，錯誤!未找到引用源。為歸一化系數(shù)，確保錯誤!未找到引用源。+錯誤!未 找到引用源。=1。令錯誤!未找到引用源。表示碼字乂第信息位取值為x的偽后 驗概率：錯誤!未找到引用源。=ny錯誤!未找到引用源。（公式3-15）錯誤!未找到引用源。=ny錯誤!未找到引用源。（公式3-16）第四步：逐位進行判斷。令錯誤!未找到引用源。=錯誤!未找到引用源。當錯誤!未找到引用源。1時，錯誤!未找到引用源。=1;錯誤!未找到引用 源。1吋，錯誤!未找到引用源。=0.因此，（錯誤!未找到引用源。）。如果入 錯誤!未找到引用源。=0,那么，譯碼成功，否則的話，返冋第二步重復以上步驟。 當?shù)螖?shù)超過規(guī)

56、定的最大值的時候，譯碼失敗。bp譯碼算法的復雜度與碼長呈線性關(guān)系，在硬件中的并行實現(xiàn)，能極大的提高 譯碼的速度，在迭代的過程中，如若試驗譯碼成功，則譯碼過程立即結(jié)束，而不是進 行固定次數(shù)的迭代，這樣，就有效的減少了譯碼算法的迭代次數(shù)；譯碼之后的誤碼率,可以隨著信噪比地增加而任意得減少，并沒有誤碼率下降速度減慢的差錯平臺現(xiàn)象。 ldpc碼的最優(yōu)的譯碼算法是“置信傳播算法”，此算法的核心思想是：利用接收到 的軟信息在校驗節(jié)點之間和比特節(jié)點之間進行迭代運算，從而最大化編碼增益，bp 譯碼算法不管是在理論上，還是在實際中都能夠在awgn （加性高斯白噪聲信道） 環(huán)境下，非常地接近信道容量，因此，bp譯

57、碼算法得到了廣泛地認可。由于校驗矩陣的稀疏特性，ldpc碼的譯碼方法相對來說比較簡單，它的運算量 隨著碼長而線性的增加，但是，不同的譯碼算法要進行的運算卻不一樣，譯碼性能也 隨之不同，硬件實現(xiàn)的難度也不同?？偠灾?，性能較好的譯碼方法所對應的實現(xiàn)復 雜度也較高，而實現(xiàn)復雜度較低的譯碼算法，其性能相對也要差一些。比如，bp算 法能夠充分的利用接收到的軟信息，但是，卻要進行復雜的浮點乘法運算，而比特翻 轉(zhuǎn)譯碼算法僅需要進行簡單的異或、比較大小等運算，卻無法利用接收到的軟信息。 利用了接收到的軟信息的bp譯碼算法的ber（誤碼率）要比比特翻轉(zhuǎn)譯碼算法的低。 bp譯碼算法雖然性能優(yōu)異，但是，它的實現(xiàn)復雜度也較高，因此，對bp譯碼算法 的各種簡化算法成為當前研宄的熱點。降低譯碼算法的復雜度的同時，保證譯碼算法 的性能是未來譯碼算法的發(fā)展方向。在實際的應用中