LDPC譯碼的DSP技術實現

1、 課程名稱： 現代編碼理論 任課教師： 王琳 洪少華 論文題目： LDPC譯碼的BP實現 姓 名： 曹沙沙 學 號： 23320131153243 2014 年 07月06日目錄第一章 LDPC碼的概述31.1、LDPC碼的發(fā)展史31.2、LDPC碼的表示31.3 二進制LDPC碼的編碼方法5校驗矩陣的生成5編碼算法62.1 Gallager概率譯碼基本思路82.2 BP算法研究102.3 用對數似然比表示的BP算法133.1 LDPC譯碼的實現平臺163.1.1硬件實現平臺16 3.1.2 軟件開發(fā)環(huán)境173.2 LDPC譯碼實現系統框架173.4 LDPC的譯碼性能20參考文獻2

2、3 摘要低密度奇偶校驗碼是Gallager提出的一種線性分組碼，其性能可以非常接近香農極限。它是根據低密度稀疏校驗矩陣H和二分圖來構造的，本文詳細的闡述了二進制，規(guī)則的LDPC的BP譯碼算法，其校驗矩陣每一行和每一列的1的個數是相同的，分別為p和q,其Tanner圖中比特節(jié)點的度和校驗節(jié)點的度分別對應著一個固定值，通常用（m，n，p，q）表示。BP譯碼算法是一種迭代的概率譯碼算法，本文著重于BP譯碼算法及其簡化運算。根據實際應用需求，文中提出了基于DSP技術的LDPC譯碼器，降低了硬件成本，通過誤碼率曲線對比，實現了對實驗結果的分析。關鍵詞：二進制LDPC BP算法 迭代概率譯碼 后驗概率23

3、 AbstractLow Density Parity Check(LDPC) codes are a class of linear block codesproposed by Gallager,which perform at a rate extremely closed to the Shannon capacity.It is based on low-density parity check matrix H and sparse bipartite graph is constructed, the paper elaborated binary, LDPC decoding

4、algorithm of BP rule, the number of one of its check matrix each row and each column is the same , respectively, p and q, the Tanner graph of bit nodes and check nodes of degree corresponds to a fixed value, respectively, usually expressed as (m, n, p, q). BP decoding algorithm is the probability of

5、 an iterative decoding algorithm, This paper focuses on its simplified operation. According to the actual application requirements, this paper proposes a LDPC decoder based on DSP technology to reduce the cost of hardware, by contrast BER curves to achieve the analysis of the experimental results.Ke

6、ywords: posterior probability probability decoding algorithm iterative binary LDPC BP 第一章 LDPC碼的概述1.1、LDPC碼的發(fā)展史1、 1963年，Gallager發(fā)現的LDPC碼被稱作古典碼型：規(guī)則LDPC。2、 1998年，MacKay and Spielman發(fā)明了不規(guī)則的LDPC。3、 Richardson and Urbanke開創(chuàng)了用譯碼分析設計碼型的方法。4、針對B-LDPC碼優(yōu)異的糾錯性能，M. Davey和D. Mackay進一步將B-LDPC碼一般化到多進制域上，并且研究結果表明Q-

7、LDPC碼在低碼率（R<1/2），AWGN信道下比B-LDPC碼的糾錯性能還要優(yōu)越，Q-LDPC碼的出現為LDPC碼的研究開拓了一個全新的領域。1.2、LDPC碼的表示LDPC是一種分組碼，但是LDPC碼與其他線性分組碼不同的是，其他線性分組碼由生成矩陣表征，而LDPC碼是由校驗矩陣來表征，其奇偶校驗矩陣具有低密度的1。規(guī)則LDPC碼可以用（n,j,k）的形式表示，其中n表示生成的碼字的碼長，j表示H矩陣的列重，k為行重。也可將j用表示，k用表示。如果用m表示H矩陣中的行數則有。一個規(guī)則的（12，3，4）LDPC碼的H矩陣如下圖所示： 圖11 （12，3，4）LDPC的校驗矩陣我們把H矩

8、陣中的每一行看作一個校驗點(check node)，每一列看作一個變量點(variable node)。則H矩陣反映了變量點與校驗點的連接關系，如在第一行中有，表示模2加，表示第一個校驗點約束、這四個變量點。從而我們可以知道行重k表示一個校驗點約束k個變量點。我們再來看第一列，它表示了第一個變量點受到check2、check5、check7的約束。因此我們又可以推出列重j表示了一個變量點受到j個校驗點的約束。由于LDPC也是一種線性分組碼，因此可以用（n,k）的形式表示。n表示碼長，k表示信息位的個數。為了更形象的表示LDPC碼中變量點與校驗點的關系，九十年代中期科學家們引入雙邊圖（bipar

9、ttie graphs）來表示LDPC碼。雙邊圖是LDPC的一個有用的工具。它將節(jié)點分成兩類，節(jié)點之間用無向的邊進行連接，并且連接只存在于不同類的節(jié)點之間即只存在與校驗點與變量點之間，而兩個校驗點之間或者兩個變量點之間不存在邊的連接。我們把LDPC校驗矩陣H的每一行表示一個校驗點用方框表示，每一列表示一個變量點用圓表示。則由上述可知一個校驗點連接k個變量點，一個變量點連接j個校驗點。當對應H矩陣中時，第i個變量點就與第j個校驗點連接，否則不連接。并且校驗點發(fā)出的邊的總數等于變量點發(fā)出的邊的總數。每個節(jié)點發(fā)出的邊的個數稱為這個點的度。如對于（12，3，4）碼其雙邊圖為：圖12 （12，3，4）L

10、DPC碼的因子圖表示當H矩陣中每列1的個數與（或）每行1的個數不同時稱為不規(guī)則LDPC碼。在雙邊圖中表現為變量點與校驗點的度允許改變。對于不規(guī)則LDPC碼，它更喜歡具有高密度的變量點，因為它將從校驗點接收更多的信息量，從而能更精確的判斷變量點的值。另外，不規(guī)則LDPC碼喜歡具有低密度的校驗點，在這種情況下，校驗點所傳送的信息對于相鄰點而言更有價值。從上分析可知不規(guī)則LDPC碼比規(guī)則LDPC的性能更好的原因在于不規(guī)則LDPC碼中存在波浪效應。高密度的變量點能夠快速的收斂到正確的值，并且它能夠幫助中等的變量點收斂到他們正確的值，從而由于循環(huán)可以幫助低密度的變量點。最終使得所有點的譯碼速度加快。由于

11、不規(guī)則LDPC碼中行重和列重都不是規(guī)則的，因此就不能用（n,j,k）的形式表示。因此不規(guī)則LDPC中采用度的表示方法。 ， （1.1）其中表示變量點的度的分布，表示校驗方程點的度的分布；()表示從度為()的變量點（校驗方程點）所發(fā)出的邊數占總邊數的比例。很顯然。 對于規(guī)則的LDPC碼，也可以用這樣的方式進行表示。例如，對于規(guī)則的LDPC碼(n,3,6)，則，。已知一個度的分布對（）后，可以確定一系列碼字集合，其中校驗方程個數以及碼率如下式所示： （1.2） （1.3）1.3 二進制LDPC碼的編碼方法對于二進制LDPC碼的編碼，其編碼基本步驟為：（1）、按照一定的設置生成校驗矩陣H。（2）、由

12、校驗矩陣H，按照一定的編碼算法生成最后的碼字u。校驗矩陣的生成由于LDPC碼是以校驗矩陣H為特征的，不同的校驗矩陣H對應不同的碼字集合。因此，LDPC碼的編碼首先需要設計校驗矩陣H，同時這也是LDPC碼編碼的關鍵。在H矩陣的設計過程中，必須避免兩種情況，一是出現短周期的環(huán)主要是長為四的環(huán)，二是避免變量點的連接過于集中，即校驗點的度過大。長為4的環(huán)(圖中存在長度為4的圈)會導致信息在兩組點間反復傳遞，難以更新，違背了迭代譯碼的初衷。長為4的環(huán)反映在H矩陣中是存在2×2的子矩陣。當變量點所連接的校驗方程過于集中時，常常導致LDPC碼錯誤地板的發(fā)生。例如在圖23中，變量點的度為3，但其中三

13、個帶陰影的變量點總共只連接了5個校驗方程；除了最右邊的一個校驗方程以外，其它4個校驗方程中，每個都連接了兩個陰影的變量點。因此，如果這三個陰影的變量點都出錯時，左邊4個校驗方程都不能檢測到錯誤的存在。當分組長度增大時，出現這種拓撲結構的可能性也隨之減少。圖23 變量點所連接校驗方程過于集中的因子圖下面以準規(guī)則LDPC碼的H矩陣的生成為例說明校驗矩陣的生成步驟。校驗矩陣的生成步驟如下：（1）、選擇參數（碼長，碼率，列重，行重）。（2）、構造一個全0矩陣。（3）、隨機選擇Wc行加入非0元素。在實際的仿真中采用的是準規(guī)則的H矩陣，既列重相同，行重盡量相同。因此，先在每列選擇Wc行，隨機的插入非0元素

14、。接著再對于低重的行添加非0元素，以避免出現低重的碼字。（4）、對已生成的H矩陣進行消4環(huán)。編碼算法按照上小節(jié)的方法求出校驗矩陣H后，就可以按照一定的編碼方法得到最后生成的碼字。常規(guī)的編碼方法中，當H矩陣被構造出來后，可以得到生成矩陣G，則最后生成的碼字U=S×G。但是實際的編碼過程并不像其表達式這么簡單。我們來看一個例子：一個（10000，5000）線性分組碼，其GI|P矩陣為5000×10000，假設P矩陣中1的密度為0.5，則在P矩陣中將有的1，即有次加法運算。從而所需的寄存器的數目將是很多的。因此我們在編程的過程中采用的是具有系統形式的H矩陣的快速編碼。假設生成的碼

15、字具有系統形式U=C|S，其中C為校驗位，S表示信息位。則我們將校驗矩陣H變換成A|B的形式，其中A為m×m的單位矩陣，B為（n-m）×m的矩陣，則根據,可得AC+BS=0,從而可以得到。在實驗中，是把隨機生成的校驗矩陣經過列變換成系統形式，然后根據H與G的關系，求出生成矩陣G的前面部分，生成矩陣的后面是一個（n-m）×（n-m）的單位矩陣，從而得到校驗位C。由于A是單位陣，從而降低了計算量。這種方法降低了編碼過程的運算量但是同時也降低了其性能。它要求H具有系統形式，就存在一個m×m的單位矩陣，使得剩余部分具有高密度的1。這就使矩陣的稀疏特性被破壞。但是

16、其生成矩陣H較容易。編碼時間與分組長度呈線性關系。 除了上述的兩種方法外，中外學者還研究出了其他更適合硬件實現的編碼算法。主要集中于H矩陣的設計上，如具有類似下三角的H矩陣的設計，具有線性的編碼復雜度，節(jié)省了對寄存器的要求，易于硬件的實現。 第二章 LDPC碼譯碼算法信道編碼的譯碼算法是決定編碼性能和應用前景的一個重要因素，尤其是在長碼的條件下，譯碼算法的復雜度決定了編碼的前途。通常分組碼的譯碼長度與碼長成指數關系，碼長增加到一定的程度后，復雜度的增加將是不可控制的，無法得到實際的應用。LDPC碼則不同，由于其奇偶校驗矩陣的稀疏性，使它存在高效的譯碼算法，其譯碼復雜度與碼長成線性關系，克服了分

17、組碼在碼長比較長時面臨的巨大譯碼計算復雜度問題。Gallager提出LDPC碼時曾給出兩種譯碼算法：硬判決算法和概率譯碼軟判決算法。硬判決不能達到LDPC碼的最佳性能，軟判決則有非常好的性能。BP算法是在Gallager提出的概率譯碼算法的基礎上發(fā)展起來的。2.1 Gallager概率譯碼基本思路 假設發(fā)送端發(fā)送一個碼長為n的二進制序列（）,接收端收到的信號為（），如果發(fā)送的二進制比特是相互獨立的，則可以根據接收信號和信道模型估計出發(fā)送的各比特位0或1的概率。考慮其中的某一比特，如果，則就認為發(fā)送的為1，否則為0。這是對應于沒有信道編碼的情況下。如果經過了信道編碼，此時的二進制序列各比特之間就

18、不是相互獨立的。假設這個二進制序列是一個LDPC碼字，那么這n個比特就要滿足由該碼的校驗矩陣所確定的一系列校驗方程。假設其中一個校驗方程是（模2加法），此時=1的概率，除了接收信號提供的信息外，還要考慮比特間的相關性。假定，滿足校驗方程這一事件記為S，現要計算概率。根據條件概率的貝葉斯公式：當然包含比特的校驗方程可能不止一個，這些校驗方程的某些比特又包含在其他更多的校驗方程中。由于碼字中的各比特的相關性，除了利用對于該比特的接收信號外，還可以利用其他比特的接收信號來修正該比特的后驗概率。為了直觀的表示這種關系，引入校驗集合樹的概念。如下圖所示圖1.1校驗集合樹具體算法Gallager的論文中已

19、有詳細的闡述，這里我們只對結果做下說明。 通過校驗集合樹，在傳送碼字c時，碼字中的各比特滿足包含比特d的j個校驗方程。當接收到相應的符號序列時y時，比特d為1的條件概率可以表示為。同理，比特d為0 的條件概率表示為。令當不考慮發(fā)送比特間的相關性時，d為1的概率表示為，它與信道模型有關。有下面公式：令，表示d的校驗集合樹第一層中包含d的第i個校驗方程的第l個比特位1 的概率，那么有： (2.1)則概率譯碼的步驟可以描述如下：對每一個比特，畫出相應的校驗集合樹，從最高層的節(jié)點開始，應用上式逐層計算出各節(jié)點的后驗概率分布，直至求出根節(jié)點的后驗概率分布。根據后驗概率分布判決該比特是0或者1： 若 其它

20、綜上可見，概率譯碼的算法的運算量是相當大的，因為沒計算一個比特的后驗概率分布，都需要利用所有比特的相關信息，運算量隨碼數的增加呈指數增長。2.2 BP算法研究 校驗集合樹雖然在描述計算單個節(jié)點的后驗概率時非常直觀，但針對不同的節(jié)點有不同的校驗集合樹，因此在描述并行的計算整個碼字各比特的后驗概率時，使用校驗集合樹并不方便，我們這里采用Tanner圖來對應前面提過的校驗集合樹。為了方便該圖只畫出了部分節(jié)點和校驗節(jié)點。Tanner圖的變量節(jié)點對應于校驗集合樹的節(jié)點，校驗節(jié)點對應于校驗集合樹的邊。圖2-2 校驗集合樹的部分anner圖 設表示校驗節(jié)點相連的所有變量節(jié)點的集合，即，表示集合去掉變量節(jié)點。

21、設表示與變量節(jié)點相連的所有校驗節(jié)點的集合，即，表示集合中去掉校驗節(jié)點。 圖 2-3 Tanner圖中關于變量節(jié)點和校驗節(jié)點的局部關系 圖中表示不考慮比特間的相關性，僅僅根據比特的接收信號值以及信道特性而得出的比特取值為x的概率，其中。顯然有?？梢园芽闯勺兞抗?jié)點的固有性質。 設表示基于接收信號并根據校驗節(jié)點集合的信息而得出的比特的概率，其中。同樣有?？梢哉J為是變量節(jié)點向校驗節(jié)點傳遞的信息。 表示當比特，并給定其他比特的一組概率時，校驗節(jié)點m對應的校驗方程成立的概率?？梢钥醋鲂ｒ灩?jié)點向變量節(jié)點傳遞的信息。根據和的定義，考慮到校驗方程都是模2加法，校驗節(jié)點m對應的校驗方程成立的概率即為比特序列中包含

22、偶數個1的概率；校驗節(jié)點m對應的校驗方程成立的概率即為比特序列中包含奇數個1 的概率。在進行簡易的推導易得 （2.2） （2.3）根據式(2.1)以及，以及的定義，可以得到 （2.4）完整的BP算法描述。對滿足的m,l執(zhí)行如下步驟。（1）初始化： ,其中表示信道的先驗概率。（2）校驗節(jié)點更新： ，則有 （2.5）（2.6） （2.7）（3）變量節(jié)點更新： （2.8） （2.9）其中是一個使得的值。（4）似后驗概率更新： （2.10）（2.11）同樣是一個使得的值。（5） 比特判決：如果，則判,(l=1,2,.,N). 若，或者迭代次數達到最大迭代次數，則結束迭代，把作為譯碼輸出，否則轉到步驟（

23、2）繼續(xù)迭代。2.3 用對數似然比表示的BP算法 上述介紹的BP算法比較復雜。一方面該算法需要在每個變量節(jié)點和校驗節(jié)點分別計算各比特為0或者為1 的概率，并且在計算和時，要選擇合適的系數和使之滿足概率和為1 的條件；另一方面，算法的表述太過復雜，采用很多相乘運算，耗費較多的運算時間和硬件資源，不利于硬件實現。采用對數似然比描述的BP算法會有一個非常簡單明了的形式?？紤]一個隨機變量x，它的對數似然比L(x)定義為根據對數似然比的定義，令 那么根據式（2.2）和（2.3）得 因為反曲正切函數在開區(qū)間（-1.1）內單調增加，是關于原點對稱的奇函數。這樣上式變?yōu)楹啙嵭问剑?因為 ，上式右端各項除以 ，

24、右端各項分母再除以 ，可得下式： 再引用的定義得下式：這里為了使形式更簡潔，引用雙曲正切函數：，它是在內單調增加，函數值，以y=+1,-1為漸近線，關于原點對稱的奇函數。最后得到： （2.12）根據式（1.8）和（1.9）有 （2.13）同理有： （2.14）BP算法的步驟整理如下：對于校驗矩陣元素的m,l執(zhí)行如下步驟運算。(1) 初始化：(2) 校驗節(jié)點更新：(3) 變量節(jié)點更新：(4) 似后驗概率更新(5) 比特判決：如果，則判；否則判，（l=1,2,.,N）。若，或者迭代次數達到最大迭代次數，則結束迭代，把作為譯碼輸出，否則轉到步驟（2）繼續(xù)迭代。 上述是完整的的碼譯碼的BP算法，但還沒

25、有說明如何去求得在譯碼的初始化過程中所需要的或，這些值是與信道有關的。下面以信道為例，說明如何計算或的值。表示不考慮比特之間的相關性，僅根據比特的接收信號值以及信道特性而得出的比特取值為的概率，其中的取值為或。假設信道是二進制無記憶對稱信道，其輸入是來自信源的二進制、數字信號，經發(fā)端的二相調制器后變?yōu)?，對極信號。經收端的二相相干解調器又把，對極信號變?yōu)?，數字信號還原輸出。由于高斯白噪聲的存在，相干解調的檢測可能出現錯誤。用信號加噪以后的條件概率密度分布函數來分析誤碼的產生比較清楚。 第三章 基于DSP的LDPC譯碼實現 數字圖像處理是當今最強大的技術之一，它涉及許多學科并在很多科學和工程領域得

26、到了廣泛的應用，例如通信、醫(yī)學成像、雷達、聲吶、高保真音樂在線和石油勘探等，這些領域都發(fā)展成比較成熟的DSP技術，擁有了自己的算法，理論以及專門技術，DSP結合數字信號處理理論，數值分析算法。計算機技術以及微電子技術，并與他們相互交叉相輔相成，相互促進，目前LDPC碼譯碼器的主要實現方法之一便是數字信號處理器等指令串行執(zhí)行系統。3.1 LDPC譯碼的實現平臺LDPC譯碼的DSP實現首先需要在軟件環(huán)境中編譯、調試通過，然后在配置開發(fā)板的相應接口，最終移植到開發(fā)板上運行。本文中LDPC譯碼的環(huán)境選用的是CCS，硬件開發(fā)平臺選用SEED- DEC6713開發(fā)板。3.1.1硬件實現平臺 LDPC譯碼的

27、硬件平臺選用了SEED-DEC6713開發(fā)板，SEED-DTK_FPD實驗箱由以下幾部分構成： 1、 高性能的32-位浮點DSP（TMS320C6713）：主頻可達300MHz，處理性能高達2400MIPS；  SDRAM：2M×32-位（可擴展至4M×32位）  Flash：256K×16-位（可擴展至1M×16位） 2、 提供看門狗電路、電源監(jiān)視、上電復位、手動復位  2路編程可選的RS232/RS422/RS485  3、

28、0;處理器為 TMS320C5402 DSP 4、 SRAM：64K×16-位（可擴展至256K×16位） 5、 Flash：256K×16-位（用于存放二級標準漢字庫及駐留實驗程序）  提供看門狗電路、電源監(jiān)視、上電復位、手動復位  1路RS232接口 6、 1路12位10S建立時間±10V輸出D/A，可擴充至17路 7、 19鍵薄膜鍵盤 8、 240*128大屏幕液晶顯示 SEED-DTK_I

29、O 實驗箱輸入/輸出模塊 9、 64個宏單元可編程CPLD，完成交通燈和I/O實驗  音頻驅動電路，直接驅動8無源音箱  MIC接口，Line In接口  電源工作指示  D/A輸出測試端 10、步進和直流伺服電機  立體聲耳麥，音頻線 11、 SEED-DTK_CPLD   實驗箱CPLD實驗模塊 12、64個宏單元可編程CPLD 13、  6位7段LED顯示，完成

30、計數實驗  CPLD編程JTAG接口  8個LED指示燈。 3.1.2 軟件開發(fā)環(huán)境SSC是由TI公司提供的集成開發(fā)環(huán)境，也是目前使用的最廣泛的DSP開發(fā)環(huán)境之一。CCS提供最基本的代碼生成工具，它具有一系列的調試和分析能力，它支持設計、編程和編譯、調試和分析等開發(fā)周期的所有階段。CCS具有以下功能：1、 集成可視化的編輯界面，可以直接編寫C語言、匯編語言、·H文件、·cmd文件等。2、 集成代碼生成工具。包含連接器、匯編器和優(yōu)化C編輯器。3、 包含基本調試工具：查看寄存器、變量的窗口、存儲器、裝入執(zhí)行代碼等，并支持C源代碼調試。4、

31、 支持多個DSP調試。5、 支持斷點調試，包括條件斷點、硬件斷點、數據空間讀和寫等。6、 數據圖形顯示功能，可以繪制時域和頻域波形、星座圖、圖像等，并可以自動刷新。3.2 LDPC譯碼實現系統框架LDPC碼在SEED-DEC6713開發(fā)板上實現，將產生的輸入碼字存儲在SDRAM中，由EDMA控制TMS320C6713芯片通過外部存儲器接口（EMIFA）訪問外部SDRAM。LDPC的譯碼實現框圖如下所示，用rand()函數產生的隨機二進制序列作為編碼輸出，具體實現方式為，首先根據碼長和碼率產生一組信息位并存儲在外部存儲器中，通過EDMA把信息位從外部存儲器傳輸到片內緩存進行編碼，編碼后的數據再通過EDMA把編碼后的數據輸送到片外存儲器中。其中兩次EDMA的數據傳輸中使用連接傳輸。 圖3.1 LDPC編譯碼的系統框圖LDPC譯碼模塊的接口參數如下圖所示。 圖3.2 譯碼模塊的接口LDPC譯碼的實現流程如下所示，LDPC譯碼實現系統按功能分可以分為兩大塊：系統配置模塊和譯碼執(zhí)行模塊。其中系統配置模塊包括外部存儲器接口、增強型的直接存儲器訪問的配置和中斷向量表的初始化。 圖3.3 LDPC實現系統流程圖 其中第二章詳細介紹了LDPC碼的譯碼算法，可知LDPC譯碼一般包括以下5個步驟：1、初始化2、校驗節(jié)點更新3、變量節(jié)點更新4