基于BP譯碼算法的準(zhǔn)循環(huán)低密度奇偶校驗碼量化問題研究

,，

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

低密度奇偶校驗碼是一種校驗矩陣稀疏的線性分組碼，由Gallarger在60年代提出[1-2].1995年前后，LDPC碼又被人們所重新重視，有MacKay和Neal[3]提出的可行性迭代譯碼算法——置信算法(BP algorithm)[4]，對LDPC碼的發(fā)展具有很大的推動作用.LDPC碼具有并行的譯碼結(jié)構(gòu)，更適于高速硬件實現(xiàn)，每比特譯碼所需的計算量更少，錯誤平層更低[5]，但由于BP譯碼算法在硬件實現(xiàn)太過復(fù)雜，所以經(jīng)過改進，得到了對數(shù)似然比譯碼算法(LLR BP).這種改進的BP譯碼算法可以大大降低硬件實現(xiàn)的復(fù)雜度，同時減小性能的損失.與此同時數(shù)據(jù)量化的合理性對譯碼算法硬件的實現(xiàn)以及準(zhǔn)確性方面也有很大的影響.筆者著重研究低密度奇偶校驗碼LLR BP譯碼算法的量化問題，對量化范圍、量化比特數(shù)、量化方式[6-7]這三方面進行了討論和比較，最終得到一個比較合理的量化方案，從而保持了較低的譯碼誤碼率，減少譯碼算法的錯誤平層，達(dá)到更高的譯碼性能.

1 LDPC碼簡介

低密度奇偶校驗碼是一種線性碼,通?？梢杂眯ｒ灳仃噷ζ溥M行表示，并且其校驗矩陣H中‘1’的密度很低[8].LDPC碼可以分為規(guī)則和非規(guī)則兩種.規(guī)則的LDPC碼可以用(N,j,k)來表示，其中：N為碼長；k為校驗矩陣每行中1的個數(shù)；j為校驗矩陣每列中1的個數(shù)，規(guī)則的LDPC碼每行具有相同的行重和每列具有相同的列重.且每兩行(列)最多只有一個相同的位置上的1.j，k相對于行數(shù)與列數(shù)來說都非常小，且j小于k.相對于規(guī)則碼，非規(guī)則LDPC碼指的是其每行(列)的行(列)重并不相同.我們可以用度數(shù)分布(λ，ρ)來表示.這里先介紹二分圖的概念，非規(guī)則LDPC碼的二分(Tanner)圖如圖1所示.

圖1 一種非規(guī)則LDPC碼的Tanner圖

上排校驗節(jié)點代表校驗矩陣中的每一行，即校驗方程，下排的變量節(jié)點代表每一列.其中變量節(jié)點(Variable nodes)用圓點表示，校驗節(jié)點(Check nodes)用方框表示[9].每個校驗節(jié)點和變量節(jié)點之間的連線表示這一行這一列位置上的元素值為1.每一個校驗節(jié)點都會向相連接的變量節(jié)點傳輸消息的同時進行求和計算，同樣的每個變量節(jié)點也進行相同的步驟.對于非規(guī)則LDPC碼來說，我們可以通過其度分布進行多項式的構(gòu)造，即

(1)

(2)

式中：dv為變量節(jié)點中最大度數(shù)；λi為變量節(jié)點中i的度數(shù)占總度數(shù)的比率；dc為校驗節(jié)點中最大度數(shù)；ρi為變量節(jié)點中i的度數(shù)占總度數(shù)的比率[10].

2 LLR BP譯碼算法原理

這部分簡單介紹一下LLR BP譯碼算法原理[11].首先定義初始消息.假設(shè)信道中初始化消息似然比為

(3)

校驗節(jié)點傳輸?shù)乃迫槐认?/p>

(4)

變量節(jié)點傳輸?shù)乃迫槐认?/p>

(5)

判決譯碼時變量節(jié)點接收的全信息[12]為

(6)

1) 初始化.傳遞消息之前，要首先計算信道傳輸給所有變量節(jié)點的初始似然比消息L(Pi)，這里i=1,2,…,n.對每一個變量節(jié)點i和與其相鄰的校驗節(jié)點j∈C(i)，設(shè)定變量節(jié)點i傳遞給校驗節(jié)點j∈C(i)的初始消息為:L(0)(qij)=L(Pi).

2) 迭代處理過程.水平方向步驟：由校驗節(jié)點向變量節(jié)點傳輸消息.對所有校驗節(jié)點j和與其相鄰的變量節(jié)點i∈R(j),第l次迭代時，計算第j個校驗節(jié)點傳遞給第i∈R(j)個變量節(jié)點的消息，即

(7)

垂直方向步驟：由變量節(jié)點向校驗節(jié)點傳輸消息.對所有變量節(jié)點i和與其相鄰的校驗節(jié)點j∈C(i),第l次迭代時，計算第i個變量節(jié)點傳遞給第j∈C(i)個校驗節(jié)點的消息[13-15]，即

(8)

硬判決步驟：后驗似然比率的計算，即

(9)

3 LLR BP譯碼算法的量化性能分析與仿真

因為數(shù)據(jù)的量化對硬件的實現(xiàn)與性能有很大影響，所以這里我們將對LLR BP譯碼算法中的輸入信號以及兩個中間變量L(rij)和L(qij)分別進行量化處理.量化是對抽樣后的信號取值，將抽樣值的范圍分為M個區(qū)間，每個區(qū)間用一個電平表示，這種方法稱為量化[16].量化又分為均勻量化和非均勻量化.M個抽樣值區(qū)間是等間隔劃分的就是均勻量化，M個抽樣值區(qū)間不是等間隔劃分的就是非均勻量化.信號在進行量化的過程中會引入量化噪聲，我們要盡量減小這個量化噪聲，提高信號量噪比.通過量化方式，量化范圍以及量化比特的對比和選擇，可以盡量得到一個比較好的量化方案，從而減小量化誤差.

3.1 輸入信號的量化

由于QC-LDPC碼的生成矩陣和校驗矩陣都是準(zhǔn)循環(huán)矩陣，因此相比于隨機構(gòu)造的LDPC碼來說，具有較低的編譯碼復(fù)雜度[13]，所以采用基于802.16e標(biāo)準(zhǔn)，并經(jīng)過編碼的準(zhǔn)循環(huán)奇偶校驗碼(QC-LDPC)，其碼率為1/2，碼長1 056[17-18].圖2為該碼H矩陣的示意圖，矩陣維度528×1 056，橫坐標(biāo)為矩陣中的行，縱坐標(biāo)為矩陣中的列.從圖2中看出：碼的結(jié)構(gòu)近似于上三角結(jié)構(gòu)，有利于減小譯碼復(fù)雜度.

圖2 基于802.16e標(biāo)準(zhǔn)的循環(huán)奇偶校驗碼

這里對發(fā)射信號采用的是BPSK調(diào)制[19].設(shè)信號為{ci|i=1,2,…,n,ci∈{0,1}}，經(jīng)過調(diào)制，0→+1，1→-1產(chǎn)生已調(diào)信號{xi|i=1,2,…,n,xi∈{-1,1}}，信號源為等概發(fā)送.假設(shè)接收信號為yi=xi+ni，這里xi為已調(diào)信號，是一個離散型隨機變量，故而xi的特征函數(shù)為

(10)

ni為噪聲，服從高斯分布N(0,σ2)，故其特征函數(shù)為

(11)

又因為xi和ni相互獨立，根據(jù)特征函數(shù)的性質(zhì)，兩個相互獨立的隨機變量之和的特征函數(shù)等于它們的特征函數(shù)之積，故yi的特征函數(shù)為

(12)

經(jīng)過傅里葉變換，yi對應(yīng)的概率密度函數(shù)f(x)和累積分布函數(shù)F(x)為

(13)

(14)

圖3 接收信號概率密度曲線

圖3是碼率為1/2，信噪比從1～3 dB，間隔1 dB的接收信號的概率密度圖.圖4為該接收信號的累積分布圖.從圖4可以看出：在σ=1時，接近于99%的接收信號基本都落在了范圍[-4,4]上.因此我們可以將量化范圍取為[-4,4].

圖4 接收信號累積分布曲線

非線性量化隨信號的變化取不同的量化間隔，實現(xiàn)起來比較復(fù)雜，考慮到運算復(fù)雜度和硬件消耗，文中均采用均勻量化方式.對輸入信號分別進行6,8,10,12比特數(shù)的量化，量化范圍均取為[-4,4].如圖5所示，與未量化相比，6比特均勻量化已經(jīng)能夠達(dá)到很好的譯碼性能，隨著量化比特數(shù)的增加，其效果幾乎無區(qū)別.

圖5 輸入信號不同比特數(shù)量化

3.2 中間變量L(rij)和L(qij)量化處理

在譯碼過程中，還會涉及到中間變量的問題.對于中間變量來說，其數(shù)目比較多，且容易發(fā)生數(shù)據(jù)溢出，我們要保證譯碼過程中不出現(xiàn)因溢出導(dǎo)致的譯碼性能惡化.在LLR-BP譯碼算法中，有兩個中間變量L(rij)和L(qij).

圖6為兩個中間變量的概率密度圖，分別給出了一次迭代，五次迭代和最后一次迭代結(jié)束后統(tǒng)計的所有變量的概率密度曲線.其信噪比從1～3 dB，間隔為1 dB.從圖6中可以看出：隨著迭代次數(shù)的增加，中間變量的范圍逐漸增大，在最后一次迭代結(jié)束后，中間變量L(rij)大部分落在區(qū)間[-7.5,7.5]中，L(qij)信號大部分都落于區(qū)間[-20,20]中.故而我們將L(rij)量化范圍取為[-7.5,7.5]，L(qij)量化范圍取為[-20,20].

對于中間變量，我們同樣采用均勻量化.這里，對譯碼算法的中間變量做量化處理的同時，也對其對應(yīng)的輸入信號做相同比特的處理.分別對輸入信號和中間變量做未量化,6比特均勻量化,8比特均勻量化,10比特均勻量化和12比特均勻量化處理.輸入信號的量化范圍均取為[-4,4],中間變量L(rij)的量化范圍取為[-7.5,7.5],L(qij)的量化范圍取為[-20,20].從圖7中可以看出：隨著量化比特數(shù)的增加，性能也越來越好，10比特均勻量化已經(jīng)達(dá)到一個不錯的譯碼性能，而12 bit均勻量化比之更優(yōu).考慮到運算復(fù)雜度和硬件資源的消耗，最終選取10比特均勻量化作為中間變量的最終量化方案.

圖6 中間變量的概率密度曲線

圖7 中間變量不同比特量化仿真

4 結(jié) 論

基于LDPC碼的LLR BP譯碼算法，對其輸入信號，中間變量等參數(shù)進行了量化分析.著重討論了在高斯白噪聲信道下，量化方式，量化范圍以及量化比特數(shù)對LDPC碼的影響.仿真結(jié)果表明:對于輸入信號，在范圍均取為[-4,4]的條件下，采用6比特均勻量化時已經(jīng)可以達(dá)到一個很好的性能，隨著比特數(shù)的增加沒有明顯區(qū)別.在對輸入變量和中間變量均采用相同比特均勻量化時，選擇量化比特為10，變量L(rij)量化范圍取為[-7.5,7.5]，L(qij)量化范圍取為[-20,20]，可以在盡量減少運算復(fù)雜度的同時也得到一個比較良好的譯碼性能.采用上述方案，可以比較有效的消除錯誤平層，更大程度的獲取譯碼性能，同時也對LDPC譯碼的硬件實現(xiàn)有著重大意義.

參考文獻(xiàn)：

[1] GALLAGER R G. Low-density parity-check codes[J]. IRE Transactions on Information Theory,1962,8(1):21-28.

[2] GALLAGER R G. Low-density parity-check codes[D]. Cambridge：Cambridge University,1963.

[3] MACKAY D, NEAL R. Near Shannon limit performance of low density parity check codes[J]. Electronic Letters,1996,32(18):1645-1646.

[4] KSCHISCHANG F R, Frey B J. Iterative decoding of compound codes by probability propagation in graphical models[J]. Selected Areas in Communications, IEEE Journal on,1998,16(2):219-230.

[5] 竇金芳,王楠,周宇昌,等.LDPC碼在深空通信中的應(yīng)用[J].遙測遙控,2009,30(1):30-35.

[6] PING L, LEUNG W K. Decoding low density parity check codes with finite quantization bits[J]. Communications Letters, IEEE,2000,4(2):62-64.

[7] HE Yu-cheng, SUN Shao-hui, WANG Xin-mei. Fast decoding of LDPC codes using quantization[J]. IEEE Electronics Letters,2002,38(4):189-190.

[8] 李秋玲.基于動態(tài)消息調(diào)度的LDPC碼及數(shù)字噴泉碼改進譯碼算法研究[D].成都:西南交通大學(xué),2012.

[9] 辛勇.基于快速擁阻密度估計的布局優(yōu)化[D].上海：上海交通大學(xué),2006.

[10] 高冰.串行級聯(lián)生成陣碼編譯碼算法研究[D].北京：北京郵電大學(xué),2011.

[11] 魏瑞剛,陳暉,邱金蕙,等.高速數(shù)據(jù)傳輸中的LDPC碼譯碼算法研究[J].無線電工程,2011,41(3):20-22.

[12] 王博.低信噪比衛(wèi)星通信中的編碼與解調(diào)技術(shù)研究[D].杭州：杭州電子科技大學(xué)，2012.

[13] 徐藝萍.多標(biāo)準(zhǔn)DTV中LDPC譯碼算法的研究與設(shè)計[D].武漢：武漢理工大學(xué),2012.

[14] 劉帆洨.LDGM碼及其在協(xié)作編碼中的應(yīng)用研究[D].成都：西南交通大學(xué),2010.

[15] 王巽冬.卷積LDPC碼編譯碼研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2011.

[16] 劉藝美,吳康.基于2PSK無線載波通信系統(tǒng)的研究[J].信息通信,2013(7):27-28.

[17] 胡潘,李珊珊,趙宏宇.基于WIMAX的LDPC碼性能研究[J].通信技術(shù),2011,44(4):28-30.

[18] 楊建平,陳慶春.IEEE802.16e標(biāo)準(zhǔn)LDPC譯碼器設(shè)計與實現(xiàn)[J].通信技術(shù),2010,43(5):84-86.

[19] 應(yīng)亞萍，許建鳳，陳婉君.2FSK調(diào)制解調(diào)系統(tǒng)的FPGA設(shè)計與實現(xiàn)[J].浙江工業(yè)大學(xué)學(xué)報，2010,38(3):282-285.