LDPC碼實現(xiàn)及性能研究

1、信息系統(tǒng)工程設(shè)計課程報告LDPC碼實現(xiàn)及性能研究前言里斯本時間，2016年10月14號凌晨，3GPP RAN1會議確定5G將使用LDPC碼作為移動寬帶（eMBB）業(yè)務(wù)數(shù)據(jù)信息的長碼塊編碼方案。在問世53年之后，LDPC終于被主流移動通信系統(tǒng)接納。故而我們對LDPC碼的編碼理論進行了研究整理。本報告主要對LDPC碼的整體實現(xiàn)進行仿真，包括校驗矩陣生成、信道編碼、譯碼各個部分，并在不同的碼長、碼率條件下分析驗證了其實際誤碼性能。一 課題背景1 信道編碼在移動通信中，由于存在干擾和衰落，信號在傳輸過程中會出現(xiàn)差錯，所以需要對數(shù)字信號采用糾、檢錯技術(shù)，即糾、檢錯編碼技術(shù)，以增強數(shù)據(jù)在信道中傳輸時抵御各

2、種干擾的能力，提高系統(tǒng)的可靠性。對要在信道中傳送的數(shù)字信號進行的糾、檢錯編碼就是信道編碼。 信道編碼是為了降低誤碼率和提高數(shù)字通信的可靠性而采取的編碼。信道編碼之所以能夠檢出和校正接收比特流中的差錯，是因為加入一些冗余比特，把幾個比特上攜帶的信息擴散到更多的比特上。為此付出的代價是必須傳送比該信息所需要的更多的比特。 傳統(tǒng)的信號編碼有漢明碼、BCH碼、RS碼和卷積碼。目前應(yīng)用較廣的有Turbo碼，以及5G即將使用的LDPC碼，還有具有應(yīng)用潛力的Polar碼等。不同的信道編碼，其編譯碼方法也有所不同，性能也有所差異。2 LDPC碼從1964年Gallager發(fā)表的Low-Density Chec

3、k-Parity Code一文標志著LDPC碼的誕生，在文章中，他證明了LDPC碼性能接近于香農(nóng)極限，同時在文章中也提出了構(gòu)建H矩陣的一種方法，以及兩種解碼方法和示意性的硬件電路原理圖，但是由于當時科技水平有限，硬件條件的限制，LDPC碼并沒有得到重視和推廣。直到1996年D.Mac Kay 和R.Neal證明了LDPC碼性能和成本都優(yōu)于Turbo碼，LDPC碼才有進入人們的視野，掀起了一番研究的熱潮。隨后學(xué)術(shù)界對LDPC投入了大量的關(guān)注，對編碼矩陣構(gòu)造、譯碼算法優(yōu)化等關(guān)鍵技術(shù)展開研究。其中比較關(guān)鍵的研究突破包括：高通的Thomas J. Richardson提出的Multi-Edge構(gòu)造方法

4、可以靈活的得到不同速率LDPC碼，非常適合通信系統(tǒng)的遞增冗余（IR-HARQ）技術(shù)；再加上LDPC的并行譯碼可以大幅度降低LDPC碼的解碼時間和復(fù)雜度，LDPC從理論進入通信系統(tǒng)的障礙被全部掃清了?，F(xiàn)在，LDPC碼被公認為是性能最接近香農(nóng)極限的信道編碼之一。方法描述LDPC碼實際是一種線性分組碼，即分為固定長度的碼組，每一組內(nèi)k個信息位被編為n位碼組長度，而（m = n-k）個監(jiān)督位被加到信息位之后形成新碼以實現(xiàn)檢錯與糾錯，記為(n , k)碼。當分組碼的信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系時，這種分組碼就稱為線性分組碼。因此LDPC的編碼關(guān)鍵就在于從k比特的信息到長度為n比特的碼組上的映射

5、關(guān)系，通常由一個對應(yīng)的校驗矩陣H來表示。LDPC碼的主要特點在于其校驗矩陣H的稀疏性，此種特性使得LDPC碼具有更好的易實現(xiàn)性。LDPC碼的具體實現(xiàn)首先需要校驗矩陣H的設(shè)計，隨后根據(jù)H陣即可相應(yīng)地生成編碼序列完成編碼過程；通過信道傳輸之后對接收到的信號進行相應(yīng)地譯碼，判決出原有信息位。每一部分的具體原理與過程在下文詳細闡述。1 校驗矩陣生成1.1 基本校驗矩陣的生成LDPC碼作為一種線性分組碼，可由其校驗矩陣H陣唯一確定。而由于LDPC碼H矩陣的稀疏特性，矩陣中非零元素很少，因此每一LDPC碼所對應(yīng)的H陣又可由相應(yīng)的二分圖表示，稱為該碼的Tanner圖。Tanner圖中的變量（比特）節(jié)點對應(yīng)至

6、H矩陣中的每一列，也即對應(yīng)LDPC碼的每一碼比特；Tanner圖中的校驗節(jié)點分別對應(yīng)到H矩陣的每一行，也即對應(yīng)LDPC碼中的校驗比特。兩類節(jié)點之間的連接情況對應(yīng)H矩陣中元素的取值：若第i個校驗節(jié)點與第j個變量節(jié)點之間存在連接，則代表H矩陣的(i,j)個元素取值為1；若無連接則對應(yīng)元素為零。圖二.1與圖二.2分別是一個(16,8)LDPC碼的H陣與 Tanner圖。圖 Error! No text of specified style in document.1 (16,8)LDPC碼H陣圖 Error! No text of specified style in document.2 (16,

7、8)LDPC碼Tanner圖在碼長較長的情況下，LDPC碼的H矩陣會十分龐大。因此通常將H矩陣分塊表示：完整的H矩陣視作由多個Z*Z的子矩陣生成，原始的H矩陣即可由一個mb×nb的基本矩陣Hb表示（mb=mz, nb=nz），Hb中每一元素對應(yīng)一個Z*Z子矩陣，Z被稱為擴展因子。其中準循環(huán)LDPC碼（QC-LDPC）較為常用，其特點在于每一子矩陣為全零方陣或單位陣向右循環(huán)移位得到的置換矩陣，因此各子矩陣都可由循環(huán)移位的位數(shù)表示，H陣所需存儲空間極大減小。另外子矩陣可由循環(huán)移位得到，也更易于硬件實現(xiàn)。1.2 可變速率的校驗矩陣設(shè)計傳統(tǒng)的LDPC碼中，每一H陣都分別對應(yīng)一個碼率

8、與碼長。而在對不同的碼率、碼長的要求越來越多的情況下，這種對需要對不同要求分別設(shè)計不同H陣的方法較為繁瑣。因此1中提出了一種可兼容不同碼率與碼長的H陣設(shè)計方案，這種兼容性主要通過嵌套的基本矩陣（圖）與可變的擴展因子Z實現(xiàn)。嵌套的基本圖基本矩陣（圖）由是嵌套的子圖的集合，即可從該集合中最大的基本圖中截取部分形成新的基本圖以應(yīng)對不同碼長、碼率要求。其中每一子圖由一相對高碼率的核心圖與IR-HARQ擴展構(gòu)成：核心圖由包括2個打孔節(jié)點的信息位與校驗位構(gòu)成，其中校驗位結(jié)構(gòu)與802.11n標準中類似；IR-HARQ擴展由核心圖中比特進一步校驗生成。子圖構(gòu)成的集合設(shè)定最大/最小信息比特數(shù)與最大/最小校驗比特

9、數(shù)，即并由此可計算出該基本矩陣可實現(xiàn)的碼長與碼率范圍。1.2.2可變的擴展因子擴展因子Z可由不同碼長、碼率要求取不同的值，取值集合被分為不同的群組，相同群組內(nèi)的Z取值對應(yīng)的擴展子矩陣移位情況相同。因此，由可變的基本矩陣與擴展因子Z的不同取值，可實現(xiàn)不同碼長與碼率的LDPC校驗矩陣。2 LDPC碼編碼算法2.1 直接編碼算法直接編碼方法的大致思路是：利用高斯消去法將M*N的校驗矩陣H變換成H'=P I，因為校驗矩陣H的不確定，所以在變換過程中可能會涉及到初等行列變換。如果進行了初等行列變換，則同時要記錄下這些行列變換信息。如果校驗矩陣 H 滿足線性相關(guān)的，將會刪去相關(guān)的行，那么這種情況下

10、，LDPC 碼的碼率由該校驗矩陣確定，其值將大于 1 K/ N；然后，根據(jù)系統(tǒng)形式的校驗矩陣H'=P I，得到其對應(yīng)的生成矩陣G = I PT。如果在生成系統(tǒng)形式的校驗矩陣的過程中沒有進行初等行列變換，則有 HGT = 0，否則HGT 0，而對于將校驗矩陣H進行行列變換的依據(jù)則是根據(jù)記錄之前記錄下的行列變換信息。最后，m為信息序列，則編碼后的序列為 c = mG。需要說明的是，如果在生成系統(tǒng)形式的校驗矩陣的過程中進行了初等行列變換，則需要使用進行過相應(yīng)的初等行列變換的校驗矩陣 H 進行譯碼。 上面思路基本適用于對任意結(jié)構(gòu)的LDPC碼進行編碼，得到的編碼復(fù)雜度往往與碼長成正比。由于這種編

11、碼算法的計算復(fù)雜度過于龐大，且會占用過大的存儲空間。因此，不適合于硬件實現(xiàn)，這也是早期阻礙 LDPC 碼發(fā)展的原因之一2。由于LDPC 碼的碼長n很大，同時很多性能優(yōu)良的LDPC碼都是采用隨機方式構(gòu)造的，這就導(dǎo)致使用上述方法得到生成矩陣 G 的運算量很大。為降低編碼復(fù)雜度，現(xiàn)在已發(fā)展出多種已經(jīng)簡化的編碼方法，而下面將討論的這種編碼算法就被視為一種高效的LDPC碼編碼算法，而且應(yīng)用廣泛。2.2 基于校驗矩陣的編碼算法傳統(tǒng)的直接編碼適用于任意結(jié)構(gòu)的LDPC碼，但缺點在于編碼過于復(fù)雜。RU算法是一種可解決該問題的有效算法，主要思想是利用校驗形矩陣具有的稀疏性來盡量減輕編碼的運算量3。這種算法為了能得

12、到一個近似下三角矩陣，會依靠行列置換來改變校驗矩陣H，這么變換的好處就在于原來矩陣所具有的稀疏性會被保留。如圖二.3所示：通過某種方法將原來矩陣分成六個分塊的稀疏矩陣，圖中顯示的G盡可能小。M - GGN - MNG M - GMACBDTE0圖 Error! No text of specified style in document.3校驗矩陣分解示意圖現(xiàn)在假設(shè)信源s的長度是K = N-M，并且x =(s,P1 ,P2 )被編碼成碼字向量，其中P1 、P2都定義成校驗向量，長度分別是：G和M-G。具體編碼步驟如下：首先對M*N維矩陣H做行、列變換，得到H矩陣的形式為：(1)計算信源向量的上

13、校正子(2)找出第二個校驗向量的臨時值，使得上校正子為零(3)接著計算向量的下校正子(4)首先要做的就是準備求第一個檢驗向量P1。由矩陣（該矩陣必須可逆） F = -ET-1B+D來求逆矩陣，該計算完成一次的復(fù)雜度O(G2 )，這個逆矩陣是一個G*G維高密度矩陣?，F(xiàn)在假設(shè)第一個校驗向量 (5)接著放棄臨時檢驗性向量，但是要找出新的有效地且符合條件的上校正子（可以在線性時間完成）：(6)接著求解出上面提到的P2的值，同樣必須使上校正子滿足全為零（利用回代算法在線性時間內(nèi)求出）。 上述RU算法，利用了校驗矩陣的稀疏性，適用于任何基于稀疏校驗矩陣的編碼。整個編碼流程的示意圖如下：開始編碼接受二進制待

14、編碼序列校驗比特編碼器P1校驗比特編碼器P2將信息源比特和生成的校驗比特合成碼字并且最終輸出編碼結(jié)束圖 Error! No text of specified style in document.4 RU編碼算法流程圖3 LDPC碼譯碼算法3.1 BP算法BP算法（Belief Propagation Algorithm）是一類較重要的消息傳遞算法，該算法經(jīng)常用在人工智能等領(lǐng)域中。算法中各個節(jié)點之間傳遞的信息是概率或置信信息，例如由變量節(jié)點vi傳遞給校驗節(jié)點cj的信息是vi取某些特定值的概率信息，該信息的具體取值依賴于vi的觀測值和其他所有與vi相連的校驗節(jié)點（cj除外）在上一輪迭代中傳遞給v

15、i的置信信息，同樣的，由cj傳遞給vi的信息也是cj取某些特定值的概率信息，該信息的取值依賴于其他所有與cj相連的變量節(jié)點（vi除外）在上一輪迭代中傳遞給的置信信息4。3.1.1概率域上的BP算法現(xiàn)在給出信道為高斯白噪聲信道（AWGN, Additive Whiten Gaussian Noise），噪聲方差表示為2，調(diào)制方式為BPSK、概率域上的LDPC碼的和積譯碼算法。其中，碼元cj0,1，調(diào)制符號xj=1-2cj，輸出yj=xj+nj(-,+)。在接收到y(tǒng)n情況下, 的先驗概率記為在概率域上，我們用表示第k次迭代某個變量節(jié)點的可信度，即第k次迭代時的概率；表示的第k次迭代時，由傳遞給的信

16、息；表示的第k次迭代時，由傳遞給的信息；表示變量節(jié)點所對應(yīng)的校驗式集合；表示校驗式所對應(yīng)的變量節(jié)點集合。概率域的算法如下：初始化：迭代次數(shù)若假定發(fā)送序列先驗等概，則同時變量節(jié)點向校驗節(jié)點傳遞初始信息，第一步，檢驗k是否大于最大迭代次數(shù)Max，如果是，結(jié)束這幀的譯碼，否則繼續(xù)；第二步，更新變量節(jié)點信息：第個校驗節(jié)點收集除了第j個以外的變量節(jié)點傳遞來的信息，然后再傳遞給與其相連的第j個變量節(jié)點，更新變量節(jié)點為0或1的概率。由校驗節(jié)點傳遞給變量節(jié)點的概率信息為：第三步，每個變量節(jié)點收集與它相連的校驗節(jié)點的概率信息，更新對校驗節(jié)點的可信度。計算每個變量節(jié)點上的；其中為概率歸一化因子，保證。在獲得第k次

17、迭代每個變量節(jié)點的概率域上的可信度后，可以做硬判決得到一個嘗試性的譯碼輸出序列。第四步，更新校驗節(jié)點信息：計算每一個變量節(jié)點的后驗概率；其中為概率歸一化因子，保證。第五步，對每個變量節(jié)點，根據(jù)做硬判決，得到一個輸出序列，若>0.5則輸出為1，否則為0；如果使得所有校驗式滿足，則將作為譯碼輸出，并結(jié)束譯碼，否則，跳轉(zhuǎn)到第一步。對數(shù)域上的BP算法用表示第k次迭代的對數(shù)似然比，表示第k次迭代的對數(shù)似然比，表示第k次迭代的對數(shù)似然比。定義：其中，；定義：對數(shù)域的BP算法如下：初始化：迭代次數(shù)；對賦初值，；第一步，檢驗k是否大于最大迭代次數(shù)，如果是，結(jié)束這幀的譯碼，否則繼續(xù)；第二步，更新變量節(jié)點的

18、對數(shù)似然比信息：計算每一個；第三步，計算每個變量節(jié)點上的；第四步，更近校驗節(jié)點的對數(shù)似然比信息：計算每一個；第五步，對每個變量節(jié)點，根據(jù)做硬判決，得到一個輸出序列；若大于0，則輸出為1，否則為0；如果使得所有校驗式滿足，則將作為譯碼輸出，并結(jié)束譯碼，否則，跳轉(zhuǎn)到第一步。無論是概率域的BP算法還是對數(shù)域的BP算法，它們所需要的存儲量基本是相同的，因為LDPC碼校驗矩陣的稀疏性，兩種算法所要的存儲量都和碼長成線性關(guān)系。在運算復(fù)雜度方面，概率域的BP算法需要做大量的乘法運算，而對數(shù)域上BP算法只需要做加法運算，對于對數(shù)運算，在定點化實現(xiàn)的時候，可以通過查表獲得。由此可見，對數(shù)域的算法利于硬件實現(xiàn)，而

19、概率域的算法適合于浮點仿真的計算。 3.2 最小和（Min-Sum）算法 在對數(shù)域的BP譯碼算法中，對數(shù)似然比沿著變量節(jié)點和校驗節(jié)點之間的連線進行傳遞，從而在每次譯碼迭代中提供了關(guān)于變量節(jié)點的判決信息。但該譯碼算法存在以下問題：(1)在每次迭代過程中，大量使用了浮點型運算，由其是采用了很多的浮點型對數(shù)和指數(shù)運算；(2)由于在每一次迭代過程中，都要對全部比特和校驗信息進行計算，因此，導(dǎo)致該譯碼算法的復(fù)雜度較高5。為了降低LDPC碼的譯碼算法，我們使用最小和算法實現(xiàn)LDPC碼的譯碼工作。最小和算法和BP算法相類似，在對數(shù)域的BP算法中，定義了。該函數(shù)滿足，即，因此對于，可以通過某種近似簡化計算，通

20、過的曲線可以知道，當在趨向于0的充分小的去建立，的上升速度很快，所以，幾乎完全由中最小的一個值決定最終取值。在計算和的時候，因為后面的計算只需要對這些數(shù)據(jù)做求最小值的計算，所以對于高斯白噪聲信道的方差也可以簡化掉。另外和這兩個變量的更新算法，和對數(shù)域BP算法中的更新基本相同。Min-Sum算法迭代的流程圖如圖二.5所示。其結(jié)構(gòu)基本和BP算法相似，只是在迭代譯碼的過程中只有加法和比較大小的運算，運算量和存儲量都要比BP算法小得多，很適合硬件實現(xiàn)。圖 Error! No text of specified style in document.5 Min-Sum譯碼算法流程圖三 仿真實驗1 仿真場景

21、本實驗考慮AWGN信道、BPSK調(diào)制方式，對LDPC碼編譯碼進行仿真，驗證不同碼長與碼率下的誤碼性能，并與Turbo碼進行比較。考慮編碼部分，由于可變碼率的校驗矩陣設(shè)計在應(yīng)對不同碼長、碼率要求時，除確定擴展因子Z值與截取適當?shù)幕緢D之外，還需進行靈活地打孔與速率匹配，過程較為復(fù)雜，因此本實驗中我們依然采用了802.11n標準中的校驗矩陣6，即支持碼長為648,1296,1944；支持的碼率為1/2,2/3,3/4,5/6.根據(jù)標準給出的基本矩陣Hb及相應(yīng)的擴展因子Z得出校驗矩陣H，進而得出生成矩陣G并完成編碼。譯碼部分，采用Min-Sum算法迭代實現(xiàn)，復(fù)雜度相較其余BP算法更低。本次仿真首先在

22、固定碼率為1/2的條件下，對648、1296、1944三種碼長的LDPC碼的誤碼性能分析；其次在固定碼長為1296與1944的條件下，對四種不同碼率的LDPC碼的誤碼性能進行分析。2 仿真結(jié)果與分析2.1 比較不同碼長的誤碼性能圖 Error! No text of specified style in document.6 碼率為1/2，不同碼長下的誤碼率由圖三.1所示，誤碼率整體隨信噪比增加而降低。而碼長越長，誤碼性能越好。另外，在信噪比較低時，不同碼長的誤碼性能差異不大，當信噪比提升到一定程度時不同碼長的誤碼率差距越來越大，碼長的影響更明顯。2.2 比較不同碼率的誤碼性能圖 Error! No text of specified style in document.7 碼長為1296，不同碼率下的誤碼率圖 Error! No text of specified style in document.8 碼長為1944，不同碼率下的誤碼率由圖中可以明顯看出，在兩種固定碼長情況下，碼率的增加均使得誤碼率顯著升高，也即相同碼長下誤碼性能的提高需要通過降低碼率來實現(xiàn)，尤其在信噪比較低的情況下。這也反映了傳輸有效性與可靠性的折中關(guān)系