LDPC編碼算法分析和研究

湖南大學畢業(yè)設計(論文)第頁論文題目LDPC編碼算法實現(xiàn)與分析學生姓名學生學號專業(yè)班級學院名稱信息科學與工程學院指導老師學院院長2014年5月19日LDPC編碼算法實現(xiàn)與分析摘要低密度奇偶校驗碼（LowDensityParityCheckCodes）由Gallager在20世紀60年代首次提出，經(jīng)過30多年的沉寂，最終因為具有逼近Shannon極限以及譯碼復雜度低等明顯優(yōu)勢得到研究者的重視[[]BernhardM.J.LDPCCodes[]BernhardM.J.LDPCCodes–abriefTutorial.TechniqueReport,2005論文旨在研究基于MATLAB的LDPC碼的編譯性能仿真。主要的環(huán)節(jié)有：=1\*GB3①LDPC碼的構造；=2\*GB3②LDPC碼的相關編碼實現(xiàn)；=3\*GB3③LDPC碼的譯碼實現(xiàn)。在整個設計及過程中，基于以上主要環(huán)節(jié)，實現(xiàn)對LDPC碼的性能分析，并得出相關結論。在實現(xiàn)編碼方面，主要采用的是基于奇偶校驗矩陣的編碼算法，而譯碼過程用到的是比特翻轉（BitFlipping）譯碼算法。 關鍵詞：LDPC碼；校驗矩陣；編譯碼；MATLABImplementationandanalysisofLDPCencodingalgorithmAbstractLDPC(LowDensityParityCheckCodes)wasfirstproposedbyGallagerinthe1960s,after30yearsofsilence,becauseofeventuallyapproachingtheShannonlimitwithdecodingcomplexityandlowobviousadvantages,researcherspaidmoreattention.[1]Withthedevelopmentofcommunicationstechnologies,withflexibleLDPCcodestructure,LDPCcodehasbeenwidelyusedindeepspacecommunications,opticalcommunications,satellitedigitalvideoandaudiobroadcastingandotherfields.LDPCcodehasbecomethefourth-generationcommunicationssystemstrongcompetitor.ThePaperaimstostudytheperformanceofthesimulationbasedonMATLABaboutLDPCcodes.Themainareashavebeenidentified:①LDPCcodesconstruction;②LDPCcodesencoding;③LDPCcodedecoderimplementations.Throughoutthedesignandprocess,achievetheperformanceofLDPCcodeanalysisanddrawrelevantconclusions.Intherealizationofencoding,themainencodingalgorithmusedisbasedontheparitycheckmatrix,andthedecodingprocessusedisbitflip(BitFlipping)decodingalgorithm.Keyword:LDPCcodesParitycheckmatrixEncodinganddecodingMATLAB第Ⅱ頁目錄1緒論 11.1課題背景及目的 11.2國內(nèi)外研究現(xiàn)狀 11.3論文的組織結構及研究內(nèi)容 32LDPC碼的相關背景知識 52.1線性分組碼 52.1.1線性分組碼的相關概念 52.1.2線性分組碼的性質 52.2糾錯碼簡介 62.3LDPC碼的表示 72.4LDPC碼的構造 83LDPC碼的編碼 113.1直接編碼算法 113.2基于校驗矩陣的編碼算法 123.3小結 154LDPC碼的譯碼 174.1主要譯碼算法 174.1.1比特翻轉譯碼算法 174.1.2加權比特翻轉譯碼算法 204.1.3置信傳播譯碼算法 214.2小結 215LDPC編譯碼算法仿真平臺的實現(xiàn) 225.1LDPC編譯碼過程 225.2仿真結果展示分析 22總結和展望 26致謝 28參考文獻 29 1緒論1.1課題背景及目的自從信道編碼理論被提出以來，研究者們就在各個方面做了很多的努力。包括尋找接近香農(nóng)極限的性能碼；包括通過各種手段降低編碼和譯碼的復雜度；也包括提出更具實踐意義的信道方案。正因為有了這些成就，才使得后來的研究者有了完善和改進的基礎，把信道編碼更加廣泛地運用到信息領域的各個角落。隨著通信領域相關技術的發(fā)展，早期的碼，例如：BCH碼，Turbo碼，已經(jīng)無法完全適應當今的要求。而且信息系統(tǒng)越來越要求有更高的數(shù)據(jù)速率，加上計算機硬件的不斷發(fā)展以及相關理論的更新，使得LDPC碼在一段時間的停滯不前之后，有了新的發(fā)展和突破。不得不說明的是，LDPC碼在某些條件下?lián)碛泻芏嘁呀?jīng)得到實際應用的良好性能，相對的他的復雜度并不算太高，而且結構又靈活，所以成為了時下第四代移動通信的熱門研究點。同時LDPC碼在很多領域都得到了良好地應用，比如：在探測未知的深空領域時。這些都給社會的發(fā)展帶來了深遠的影響。所以有理由相信LDPC碼在未來的信息領域有巨大的前景。1.2國內(nèi)外研究現(xiàn)狀LDPC碼能夠取得現(xiàn)在的成就，自然少不了信道編碼研究者們的不懈努力。BehairyH和ChangS.C提出了具有并行級聯(lián)特點的Gallager碼（PCGC），就是在Turbo碼的編碼中用到LDPC碼。其方法就是在不適用交織機的情況下實現(xiàn)信息碼元的輸出，并且經(jīng)實踐得到了良好的效果[[][]BehairyH,ChangSC.ParallelconcatenatedGallagercodes[J].Electronicsletters,2000,36(24):2025-2026.YuKou，ShuLin等利用有線集合的代數(shù)方法，構造成功LDPC碼，借此生成的循環(huán)碼字可以用相對簡單的具有線性反饋位移性質的寄存器進行編碼，這一舉措極大的簡化了復雜性，從而使得到的糾錯方面的能力更靠攏香農(nóng)極限。根據(jù)查閱相關資料，當前在最好的情況下，LDPC碼字性能與香農(nóng)極限相比，僅僅相差0.0045dB[[]Yu[]YuKou，ShuLin,FossorierM.LowDensityCheckCodes:ConstructionBasedonFiniteGeometries.ProcGlobecomConf[C].2001,2(1):825-829M.G.Luby等提出，在非二元有限域中這個情況下，定義碼有性能的改進，同樣有這種可能的還包括校驗矩陣。同時相比基于正則圖定義的碼，基于非正則定義的碼性能更加好。他還提出某種雙向圖的LDPC碼在可擦除信道中有較多的運用，而且可以實現(xiàn)時間復雜度是線性規(guī)律的編碼和譯碼。同時D.J.C.Mackay通過對超泊松分布結構的相關性能的驗證，發(fā)現(xiàn)當相關的矩陣的結構呈現(xiàn)具的是三角形結構時，更能實現(xiàn)快速編碼[[]M[]M.GLuby,M.Mitzenmacher,M.A.Shokrollahi.ImprovedLow-DensityParity-CheckCodesUsingIrregularGraphs.IEEETransactiononInformationTheory.2001,47(2):619-632T.J.Richardson和R.L.Burbanke研究了如何通過確定校驗矩陣的稀疏性來得到更高效的編碼器，如何是編碼時間和碼長度更加貼合線性關系增長。T.J.Richardson通過研究非正則圖的復雜性來發(fā)現(xiàn)更優(yōu)的非正則碼LDPC碼。劉水平等將編碼器分子若干個子相互串聯(lián)級聯(lián)的編碼器，從而實現(xiàn)非正則LDPC碼的設計。這樣做不僅能夠保證低密度校驗碼的特點，實驗還表明：這樣一來簡化了編碼算法，而且碼結構得到固定，從而實現(xiàn)更好的性能[[][]劉水平，劉玉君.串行級聯(lián)LDPC碼[J].信息工程大學學報，2004,5（2）:76-79賀玉成等經(jīng)過研究提出了一種迭代譯碼量算法，該算法是基于置信傳播。其優(yōu)勢在于：首先，極大降低存儲要求；其次，計算復雜度得到改善；最后，算法是呈現(xiàn)對稱性特點的，這些優(yōu)勢使得改進后的LDPC碼在實際通信中成為現(xiàn)實。由于攤就分析的不斷深入，極大地優(yōu)化了LDPC碼的編碼復雜性。因此，LDPC碼在多個領域得到廣泛應用[[][]賀玉成，孫韶輝，慕建軍，王新梅。快速低密度校驗碼迭代譯碼量化算法[J].西安電子科技大學學報（自然科學版），2002,29（3）：338-342葉芳等人研究出一種填充算法，該算法是通過構造稀疏的校驗形矩陣來實現(xiàn)的。這種算法的優(yōu)勢在于當需要構造高圈長的校驗矩陣時，實現(xiàn)起來的復雜度會比較低[[][]葉芳，劉鈞雷，朱琦。擴展比特填充算法與LDPC碼的構造[J].重啟有點學院學報，2004,16（3）：21-24彭立等人介紹了一種以某一矩陣為子矩陣，通過對這類矩陣進行合適的排列組合，進而構造出低密度校驗矩陣的一種LDPC碼編碼器的設計方案。Chiani、Myhre和Wadayama等人的主要研究工作是LDPC碼在衰落信道中的應用。其中Chiani的主要工作是對有記憶塊衰落的信道進行性能估評。Myhre提出了一種編碼調制方案，主要是針對慢變化衰落信道的一種LDPC調制方案。Wadayama主要針對可能突發(fā)信道的LDPC碼進行了研究，并且提出一種模型適用于隱馬爾可夫噪聲信道[[][]LivaG,ChianiM.ProtographLDPCcodesdesignbasedonEXITanalysis[C]//GlobalTelecommunicationsConference,2007.GLOBECOM'07.IEEE.IEEE,2007:3250-3254.現(xiàn)今研究中，關于LDPC碼的改進優(yōu)化工作，主要往矩陣構造、編碼算法改進優(yōu)化等方面進行。隨著LDPC嗎的研究深入，其出色的性能，已經(jīng)得到廣泛的關注，并被用于衛(wèi)星通信，光纖通信，移動通信以及壓縮圖像輸出等總所數(shù)字通信領域。1.3論文的組織結構及研究內(nèi)容本文共分為六章：第一章為緒論，主要介紹“LDPC編碼算法實現(xiàn)和分析”的課題的背景、選取該課題的目的以及國內(nèi)外對于LDPC碼的一些相關研究，最后介紹了論文的結構。第二章主要是講述系統(tǒng)LDPC碼的相關背景知識，主要研究內(nèi)容集中在線性分組碼的簡單介紹、糾錯碼的介紹、LDPC碼的闡發(fā)分析，這中間就包括LDPC碼的構造。第三章是LDPC碼的編碼算法，本章節(jié)主要介紹幾種使用廣泛的編碼算法，有直接編碼算法和基于校驗矩陣的編碼算法。第四章是LDPC碼的譯碼算法實現(xiàn)，介紹了三種相關算法，主要集中在對于翻轉譯碼算法的研究和分析，并且對相關內(nèi)容進行了小結。第五章主要是對LDPC編譯碼算法基于MATLAB進行實際仿真實現(xiàn)。主要是對實驗結果繪制出的曲線圖截圖進行展示，分析這些因素對于誤碼率的影響，并得出相關的結論。本課題的名稱為“LDPC編碼算法實現(xiàn)與分析”，研究的主要方向包含了下面幾個內(nèi)容：研究LDPC碼在通信編碼領域的產(chǎn)生以及發(fā)展道路，論敘LDPC碼的發(fā)展狀況，討論LDPC碼對于整個通信編碼領域發(fā)展的重要意義。具體技術點具體分析，拆分為小的重點難點進行重點剖析，在不同的編碼條件中以具體的不同的形式和內(nèi)容表現(xiàn)出來。本文介紹了與LDPC碼背景相關的知識，包括其表現(xiàn)形式，結合相關的研究探究LDPC碼的碼構造常用方法：基于校驗形矩陣H的構造。研究探討LDPC碼的編碼和譯碼算法的實現(xiàn)，總結其相對傳統(tǒng)的BCH碼的優(yōu)缺點。從對比的角度分析LDPC碼的使用場景以及現(xiàn)階段面臨的困難、需要解決的問題，并且歸納其使用場景?？偨Y了LDPC碼相關研究的曲線圖，通過分析聯(lián)系實際總結LDPC碼的優(yōu)點。通過分析現(xiàn)在已有的研究成果，提出針對性的解決方案，研究在實際應用中的深遠意義和價值。并對“LDPC編碼算法的實現(xiàn)和分析”中研究的問題以及實際中遇到的問題進行解決。2LDPC碼的相關背景知識2.1線性分組碼考慮到LDPC碼的本質是線性分組碼，因此十分有必要在本章節(jié)首先對線性分組碼的相關知識做一個簡單概述。線性分組碼的本質其實是奇偶校驗碼，它的描述方式通常為（n，k）。2.1.1線性分組碼的相關概念如果碼字序列的表示是(cn-1，cn-2,，…，c1，c0)，那么分組碼會對每段長度為k的信息組，通過增加r=n–k數(shù)目的檢驗元的規(guī)則來完成。一般來說，通過編碼器以后，二進制情形下數(shù)目為2k的信息組會產(chǎn)生2k個對應的碼字。那么這些產(chǎn)生的碼字集合就是（n，k）的分組碼，長度為n的序列會有2n種排列方式。 而長度是n的分組碼可以用作前向糾錯。在分組碼中，形成新碼的一般方式是監(jiān)督位加上信息位；在編碼中，被編成長度是n位，個數(shù)是（n-k）個的監(jiān)督碼是由k個信息位而來，這些形成的監(jiān)督碼起到檢錯和糾錯的作用[[][]單亦先.循環(huán)碼的實現(xiàn)方法及其在前向糾錯中的應用[J].石油大學學報:自然科學版,2001,25(5):98-99. k比特序列又稱作k元組，其實質是k位比特信息構成的序列，該序列包含有2k個信息，以此類推，n元組的概念是：n位比特構成的序列，當中包含有2n個元素。由于分組碼的編碼是遵循一一對應的原則，所以在編碼過程中，每個k元組會相應地映射到2n個數(shù)中的某一個n元組中。通過一個查詢表可以順利實現(xiàn)這樣的映射。介紹完基本的知識，現(xiàn)在從兩個方面來分析線性分組碼： （1）分組特點：對于線性分組碼而言，碼長會是恒定的，同樣消息長度也是恒定的。另外，如果存在碼長是n時，若其中消息位顯示為k，而且每次輸出n位僅僅與當前的k位輸入有關； （2）線性特點：在線性分組中，碼字c相對應的各位碼元與消息的關系是線性組合關系。2.1.2線性分組碼的性質對于一個線性分組碼，能夠用c=mG來實現(xiàn)碼字c的可能表示，當中字母m有兩種意思，第一是表示k長度的消息；第二就是表示k維度的向量。特別注意的是：矩陣運算采用模二加和模二乘。下面還有一些關于線性分組碼不得不列出的有用性質，如下：性質1：零向量一定會是一個碼字，可以記做θ=（0，0，…，0）。推而廣之，在線性組合碼中，任意碼字的線性組合仍然是一個碼字[[]宮曉妍[]宮曉妍,劉建偉.LDPC碼編碼方案研究與發(fā)展[J].通信技術,2008,15(10):276-280性質2：任意兩碼字的和仍然會是一個碼字。性質3：可以用G來表示碼字c。具體的表示是對G的行向量進行線性組合。行向量是碼集里面的碼字，因此要擁有的特點是呈現(xiàn)線性無關。假設(g0，g1，g2，…，gk-1)是線性組合（n，k）基底，那么對于任意屬于G的碼字c，其表現(xiàn)方式是唯一的，如下：C=a0g0+a1g1+…+ak-1gk-12.2糾錯碼簡介當出傳輸過程發(fā)生錯誤后，糾錯碼(ErrorCorrectingCode)最大的好處就是能夠在接受端發(fā)現(xiàn)并糾正錯誤[[]新梅[]新梅,國鎮(zhèn).糾錯碼:原理與方法[M].西安電子科技大學出版社,1991.檢錯碼：一類用來發(fā)現(xiàn)錯誤的碼；編碼：碼字之間建立關系。依據(jù)是否滿足編碼規(guī)則來判斷接收端的碼字是不是正確的。如果根據(jù)判斷得到的反饋信息是碼字錯誤，那就按照一定的規(guī)則將錯誤所在位置的碼字糾正。這一個過程就是譯碼。當然，檢錯碼結合其他檢測手段，可以進行錯誤糾正。存在某種關系的糾錯編碼和信源編碼是信息傳輸?shù)膬蓚€方面，具體來說這種關系是一種對偶的關系。所謂對偶關系就是按照某些規(guī)則將原有碼字改變成另一種碼字，改變之后的碼字要有一定的剩余度。而且要滿足碼字對應的碼元之間保持某種的關系。而線性碼就是指碼元之間存在線性的關系；否則就是非線性碼。 糾錯碼是憑借較大的碼字之間的差距來實現(xiàn)和完成檢錯和糾錯。譯碼環(huán)節(jié)是糾錯碼順利實現(xiàn)難度最大的部分，也是糾錯碼最終是否可以應用的關鍵。已有的研究表明：當碼長越大時，最終的誤碼率越小。但是加大碼長帶來的后果就會導致編譯碼設備更加復雜，而且會產(chǎn)生較大的延時。所以現(xiàn)有的研究主要是集中在尋找到一種當碼長增加時，誤碼率會呈現(xiàn)指數(shù)下降的譯碼方法；隨著碼長的增加，譯碼的復雜程度會以線性增長，而且滿足其計算量基本與碼長無關。2.3LDPC碼的表示首先需要說明，有關LDPC碼的研究到目前為止并沒有對其給出一個非常嚴格的定義。普遍認同的的LDPC碼的表示方式有兩種：第一種表示方法是像所有線性分組碼一樣它們能夠通過矩陣被描述。第二種是通過圖形被表示。矩陣表示的例子如下：（1）上面方程式（1）定義的矩陣是不完全符合條件奇偶校驗矩陣，其大小是n*m，表示形成（8，4）的矩陣?，F(xiàn)在定義兩個數(shù)字來表示矩陣：Wr表示1所在的行，Wc表示其所在的列。對于一個可以被稱作低密度矩陣的矩陣要滿足的兩個條件是：Wc《n而且Wr《m。為了滿足這些條件，奇偶校驗矩陣應該很大。所以上面例子里面的矩陣嚴格意義上說不是真正的低密度奇偶校驗矩陣。Tanner圖被認為是LDPC碼的另一種有效圖形表示。Tanner圖是二分圖，這就意味著圖的節(jié)點被分成兩個獨特的部分，而邊僅僅是用來聯(lián)系兩個不同類型的節(jié)點。CC1C0C35C6C7C2C3C4f1f2f3f0c_nodesv_nodes（2）以上Tanner圖中有兩類型的節(jié)點：變量節(jié)點（v_nodes）和校驗節(jié)點（c_nodes）。結合奇偶校驗矩陣，Tanner圖可以理解成包含m個校驗節(jié)點，校驗節(jié)點就相當于奇偶校驗位的數(shù)目，n個變量節(jié)點，其含義相當于在碼字中的比特數(shù)。如果（1）中H矩陣中的某一元素hij是1，那么校驗節(jié)點fi和變量節(jié)點Cj就要連接起來。2.4LDPC碼的構造通常情況下，LDPC碼的構造思路是：（1）先隨機生成列為c和行為r的H矩陣，并且該矩陣要滿足任意兩列重疊為1的數(shù)目要盡可能少； （2）產(chǎn)生的H矩陣要滿足滿秩矩陣。經(jīng)過高斯消元法，使之前的H矩陣進行變換，滿足H=[PT|I]，再有校驗矩陣和生成矩陣的關系得到G=[I|P]。 （3）然后可以由vT=GxT得到編碼后的碼字。 構造LDPC碼H矩陣的部分代碼如下：3LDPC碼的編碼 目前，直接編碼算法和基于校驗矩陣的編碼算法是LDPC碼的主流編碼算法之一，而其中直接編碼算法用到了高斯消元法[[]黃煒,張建秋[]黃煒,張建秋.構造準循環(huán)LDPC碼生成矩陣的塊高斯消元法[J].復旦學報:自然科學版,2009(6).3.1直接編碼算法直接編碼方法的大致思路是：利用高斯消去法將m*n的校驗矩陣H變換成H’=[PI]，因為校驗矩陣H的不確定，所以在變換過程中可能會涉及到初等行列變換。如果進行了初等行列變換，則同時要記錄下這些行列變換信息。如果校驗矩陣H滿足線性相關的，將會刪去相關的行，那么這種情況下，LDPC碼的碼率由該校驗矩陣確定，其值將大于1–k/n；然后，根據(jù)系統(tǒng)形式的校驗矩陣H’=[PI]，得到其對應的生成矩陣G=[IPT]。如果在生成系統(tǒng)形式的校驗矩陣的過程中沒有進行初等行列變換，則有H?GT=0，否則H?GT≠0，而對于將校驗矩陣H進行行列變換的依據(jù)則是根據(jù)記錄之前記錄下的行列變換信息。最后，m為信息序列，則編碼后的序列為c=m?G。需要說明的是，如果在生成系統(tǒng)形式的校驗矩陣的過程中進行了初等行列變換，則需要使用進行過相應的初等行列變換的校驗矩陣H進行譯碼。上面思路基本適用于對任意結構的LDPC碼進行編碼，得到的編碼復雜度往往與碼長成正比。由于這種編碼算法的計算復雜度過于龐大，且會占用過大的存儲空間。因此，不適合于硬件實現(xiàn)，這也是早期阻礙LDPC碼發(fā)展的原因之一[[]張晨[]張晨.高吞吐量LDPC碼編碼構造及其FPGA實現(xiàn)[D][D].上海交通大學,2008.由于LDPC碼的碼長n很大，同時很多性能優(yōu)良的LDPC碼都是采用隨機方式構造的，這就導致使用上述方法得到生成矩陣G的運算量很大。為降低編碼復雜度，現(xiàn)在已發(fā)展出多種已經(jīng)簡化的編碼方法，而下面將討論的這種編碼算法就被視為一種高效的LDPC碼編碼算法，而且應用廣泛。3.2基于校驗矩陣的編碼算法與傳統(tǒng)的BCH碼相比，LDPC碼具備良好的性能以及更低的解碼復雜度，但是其最大的缺點就是編碼過于復雜。Richardson和Urbanke二人經(jīng)過研究找到一種可以解決LDPC碼編碼過于復雜的方法，其主要思想就是要利用校驗形矩陣具有的稀疏性來盡量減輕編碼的運算量[[]UrbankeT[]UrbankeTRR,RichardsonT.Efficientencodingoflow-densityparitycheckcodes[J].IEEETrans.onInform.Theory,2001,47(2):638-656.這種算法為了能得到一個近似下三角矩陣，會依靠行列置換來改變校驗矩陣H，這么變換的好處就在于原來矩陣所具有的稀疏性會被保留。比如下圖（3）：通過某種方法將原來矩陣分成六個分塊的稀疏矩陣，圖中顯示的G竟可能小。M-GM-GGN-MNGM-GMABCDTE0（3）首先，奇偶校驗矩陣可以通過行變換和列變換實現(xiàn)重新排列，得到如上圖（3）：是一個經(jīng)過了行列變換得到的近似下三角形矩陣。因為原有的矩陣是非常稀疏的，在進行完行列變換以后，得到的矩陣仍然是具備稀疏性的奇偶校驗矩陣。圖中的A、B、C、D、E、T，由前面的分析可知：這六個部分都是維稀疏矩陣；另一種表示是（M-G）*（N-M）、（M-G）*G、G*（N-M）、G*G、G*（M-G）、（M-G）*（M-G）。值得注意的是：T矩陣必須滿足某些元素全是零，也就是指對角線上的元素。由此矩陣H可以表示成另外一種形式：，現(xiàn)在假設信源s的長度是k=n-m，并且x=（s，p1，p2）被編碼成碼字向量，其中p1、p2都定義成校驗向量，長度分別是：G和M-G。得到的編碼步驟如下：（1）計算信源向量的上校正子ZA=AsT（4）（2）找出第二個校驗向量的臨時值，使得上校正子為零=T-1ZA(5)該向量能夠通過回頭代入計算的算法，并且在呈現(xiàn)線性關系的時間內(nèi)得出結果，也就是運算的第一個比特，接著是運算第二個比特，接下來是第三個，以此類推。（3）接著計算向量的下校正子ZB=CsT-EpA（6）（4）首先要做的就是準備求第一個檢驗向量p1。由矩陣F=-ET-1B+D來求逆矩陣，該計算完成一次的復雜度O(G2)，這個逆矩陣是一個G*G維高密度矩陣。現(xiàn)在假設第一個校驗向量p1是(7)（5）接著放棄臨時檢驗性向量，但是要找出新的有效地且符合條件的上校正子（可以在線性時間完成）：Zc=ZA+Bp1(8)（6）接著求解出上面提到的p2的值，同樣必須使上校正子滿足全為零（利用回代算法在線性時間內(nèi)求出）。=-T-1zc(9)最后計算、的復雜度如表3.1和表3.2所示。表3．1計算的復雜度操作復雜度說明AO（N）稀疏矩陣和向量相乘O（N）稀疏矩陣和向量相乘O（N）稀疏矩陣和向量相乘向量的減法運算O（N）矩陣的求逆運算高密度矩陣和向量相乘表3．2計算的復雜度操作復雜度說明AO（N）稀疏矩陣和向量相乘O（N）稀疏矩陣和向量相乘A+O（N）稀疏矩陣和向量相乘向量的加法運算-(A+)O（N）稀疏矩陣和向量相乘上述RU算法，利用了校驗矩陣的稀疏性，適用于任何基于稀疏校驗矩陣的編碼。整個編碼流程的示意圖如下：開始編碼開始編碼接受二進制待編碼序列校驗比特編碼器p1校驗比特編碼器p2將信息源比特和生成的校驗比特合成碼字并且最終輸出編碼結束由上面兩個表格可知，基于校驗矩陣的編碼算法的復雜度與N+G2有關，具體的關系式成正比，換一句話說，編碼復雜度隨著G值的減小而降低。由此可以得出結論：如果想要達到降低編碼復雜度的目的，可以在進行行列變化時，盡量減小G值。LDPC碼編碼算法實現(xiàn)部分代碼如下：3.3小結傳統(tǒng)的LDPC碼并不利于推廣，原因是編碼復雜度高，所以在構造LDPC碼的H矩陣時，不能只單方面地想到如何去優(yōu)化碼字的性能，同時也要把編碼的復雜度納入考慮范疇。本章節(jié)里面所提到的編碼算法，在降低編碼復雜度方面都是利用H矩陣自身的某些特點對其進行處理，這樣做可以使編碼復雜度降低到線性復雜度。Richardson和Urbanke首先提出的基于校驗矩陣的編碼方案通過對原有矩陣的處理完成編碼，這個方法基本是適用于一般的H的矩陣。雖然對于LDPC碼的研究已經(jīng)取得很多的成果，但是目前并沒有一套完善的、系統(tǒng)的LDPC編碼理論。為了使編碼復雜度隨著碼長呈現(xiàn)線性增長，現(xiàn)有的研究主要是利用稀疏性，也就是說保持校驗矩陣的稀疏性來編碼。我相信只有綜合考慮運算的復雜度和存儲量，才能設計出符合要求的低復雜度編碼方法。因此，如何降低LDPC編碼復雜度，成為研究者們爭相研究的熱點問題。4LDPC碼的譯碼4.1主要譯碼算法在討論LDPC碼的譯碼算法時，不得不涉及兩個概念：硬判決譯碼和軟判決譯碼。比特翻轉算法屬于一種典型的硬判決算法。主要的優(yōu)點在于較低的復雜度。考慮實際設計，本文主要對比特翻轉譯碼進行實現(xiàn)和分析。4.1.1比特翻轉譯碼算法 硬判決譯碼算法是由Gallager突出的一種簡單易懂的算法，并且經(jīng)過研究表明：這類算法運算量不高而且沒有嚴格的存儲量要求。比特翻轉（Bit-Flipping）譯碼算法是由Gallager在1963年提出，后續(xù)研究表明，當某有線幾何碼的列重和行重盡可能大時，BF譯碼算法十分有效[[]郭強.基于可靠率的改進的LDPC[]郭強.基于可靠率的改進的LDPC碼BF譯碼算法[J].南京理工大學學報:自然科學版,2009(2):165-167. 現(xiàn)在我們設置c=（c0，c1，…，cN-1）為發(fā)送序列，經(jīng)BPSK調制為序列x=(c0，c1，…，cN-1)，負責接收的序列表示成xi=(2ci-1)，，而經(jīng)過這一個過程得到的硬判決向量序列z=（z0，z1，…，zN-1）表示是：11，當ri>0；Zi=0，當ri<0。通過這樣的過程得到的伴隨式s=（s0，s1，s2，…，sJ-1）=z=HT如果能夠滿足sj=0，就表明接收到的序列能夠滿足第j個校驗方程式；若s=0，則表示接收向量滿足所有校驗方程，接收碼字z正確，那么就表示譯碼成功；若s集合存在非零元素的向量，那就表示接受序列有錯誤存在，如果出現(xiàn)這種情況，就必須計算對應碼字不滿足校驗方程式的個數(shù)，且要尋找其中的最大值，然后翻轉對應位置的碼元。不斷重復上面的過程，當所有的的碼字都譯碼成功或者達到設定的迭代次數(shù)時，才停止。歸納比特翻轉譯碼算法的步驟如下：（1）利用相關公式計算校驗和，判斷s是不是滿足全部是零，若滿足這個條件，那么就表示譯碼成功，如果不滿足就轉到步驟（2）；(2)需要計算碼字中的比特的可靠度量值；(3)由步驟（2）中計算出的度量值將接收序列中最不可靠的比特對應的碼元zj翻轉，然后重新計算校驗和；(4)重復步驟（1）至步驟（3），直到所有的校驗方程都被滿足或者迭代次數(shù)達到設置的最大值。由于校驗矩陣是一種稀疏矩陣，通常情況下是隨機的，這就導致校驗方程式的比特數(shù)目較少，而且這些比特比較分散，這么一來，任意校驗方程式中的比特會存在兩種情況：一是沒有錯；另外就是極有可能只包含一個比特錯誤。這樣一來，比特翻轉譯碼算法就可以有效地進行錯誤糾正。哪怕方程式中不只一個比特錯誤，也可以順利進行糾錯，不過這么做就是以犧牲譯碼性能為代價?？紤]到這一方面，于是在翻轉譯碼算法的基礎上提出一種加權硬判決譯碼算法，對比而言該算法性能得到了提高，下一節(jié)會有介紹。LDPC碼比特翻轉譯碼算法實現(xiàn)主要代碼如下：4.1.2加權比特翻轉譯碼算法加權比特翻轉譯碼算法的思路是：當某個變量節(jié)點需要翻轉時，必須要記錄某些輸出信息，而這些信息指得就是碼元的信道信息，嚴格意義上說是指無法滿足校驗方程的碼元。并以此信息來作為判決式的權重信息[[]謝東覺[]謝東覺,張興敢,唐嵐.一種改進的LDPC碼多比特翻轉譯碼算法[J].現(xiàn)代電子技術,2011,34(003):11-13.加入令為接收端的信息，而調制信息則是，又有高斯白噪聲為。其中有校驗矩陣，相關聯(lián)的變量節(jié)點由來表示，同樣，相關聯(lián)的校驗節(jié)點由表示。于是，當有m=0，1，?，M－1；n=0，1，…，N－1加權BF譯碼算法的步驟如下表示：(1)利用相關知識，分析集合s中的元素是否全為零，如果滿足這個條件，就表示譯碼成功，如果存在非零元素，就進行步驟（2）；(2)計算0<i<N－1，n∈N(m)；(3)當n=0，1，?，N－1，代入運算：，并且尋找其中的最大值，進行對用的翻轉；(4)將得到的新的向量序列代替原向量，實施步驟（1），如滿足伴隨式全為“0”，那么就表示譯碼成功，停止譯碼；否則反復執(zhí)行上述步驟（1）至（4），當達到設置的迭代次數(shù)極限時，停止譯碼。通過軟判決算法和附加信息來計算加權校驗信息的思路是加權譯碼算法的核心，雖然與的單純的比特翻轉譯碼算法相比，這種算法的復雜度會增加；不過相應地，其譯碼性能會更好。4.1.3置信傳播譯碼算法使用置信傳播算法進行相關的譯碼操作時，表示LDPC碼的二分圖中環(huán)路的長度決定了性能的好壞。如果一個環(huán)路的周長很小，那么就會存在高度相關的譯碼信息，尤其是當環(huán)路的周長是4的時候，而這些高度相關的譯碼信息會使譯碼性能受到局限。所以若要使置信傳播譯碼算法盡可能地發(fā)揮優(yōu)良性能，那么就必須避免周長很小的環(huán)路，特別是周長是4的環(huán)路[[]郭銳[]郭銳,劉濟林.LDPC碼的一種低復雜度BP譯碼算法[J].浙江大學學報:工學版,2008,42(3):450-455.置信傳播算法包括兩個交替的部分，在這一過程中，每一個位于奇偶校驗矩陣H中的非零元素，都會有兩個對應的變量，而這兩個變量進行迭代并且會更新，直到因為譯碼成功而停止或者因為達到最大迭代而終止。特別要說明的是：就存儲需求量方面，有關對數(shù)域和一般的置信傳播這兩種譯碼算法的要求是基本相同的[[]賀玉成[]賀玉成,楊莉,王新梅,等.置信傳播譯碼算法的性能測度[J].電子學報,2002,30(4):576-580.4.2小結研究表明：有多種譯碼算法適用于LDPC碼的譯碼，對于那些性能較好的譯碼算法，相應的復雜度也越高，而那些復雜度較低的譯碼算法，其性能也會相對較差。[20]LDPC碼譯碼方法相對其他信道編碼較為簡單，其間一個重要的原因是校驗性矩陣的擁有稀疏性的特點，所以在一定條件下，運算量會呈現(xiàn)線性增長。當然，譯碼性能的差異是一定存在的，原因可能很多，比如：不同的譯碼方法要進行的運算有所差別。比特翻轉譯碼算法（BF譯碼算法）在很多情況下相對復雜度低，在一些特殊場合也具有重要的應用前景。然而在實際情況中，必須綜合考慮性能要求、硬件本身的條件等多個因素，從而在性能與復雜度之間找到一個合理點，以此來選擇合適的譯碼算法。5LDPC編譯碼算法仿真平臺的實現(xiàn)5.1LDPC編譯碼過程由前面的章節(jié)繪制得出LDPC編譯碼流程如下：開始開始構造近似下三角形H矩陣輸入信息比特流編碼與調制信道中傳輸接收端BF譯碼統(tǒng)計誤碼個數(shù)計算BER結束5.2仿真結果展示分析 這次的所有編譯碼的實現(xiàn)都是基于MATLAB，因為MATLAB能夠集成可視化和數(shù)值計算，在操作過程中極大地提供了便捷。MATLAB本身提供了大量的函數(shù)，這些函數(shù)覆蓋了與科學有關的計算、關于系統(tǒng)的控制、信息處理等領域，能夠完成的工作包括從分析到仿真再到工作設計。由于MATLAB的開放式結構使得在擴充功能方面變得相對容易。MATLAB另一個優(yōu)點就是分析和處理數(shù)據(jù)的能力十分強大，而且對于矩陣的處理運算有十分高效，因此可以運用MATLAB完成對