,，

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

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

1 LDPC碼簡(jiǎn)介

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

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

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

(1)

(2)

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

2 LLR BP譯碼算法原理

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

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

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

(8)

硬判決步驟：后驗(yàn)似然比率的計(jì)算，即

(9)

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

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

3.1 輸入信號(hào)的量化

由于QC-LDPC碼的生成矩陣和校驗(yàn)矩陣都是準(zhǔn)循環(huán)矩陣，因此相比于隨機(jī)構(gòu)造的LDPC碼來(lái)說(shuō)，具有較低的編譯碼復(fù)雜度[13]，所以采用基于802.16e標(biāo)準(zhǔn)，并經(jīng)過(guò)編碼的準(zhǔn)循環(huán)奇偶校驗(yàn)碼(QC-LDPC)，其碼率為1/2，碼長(zhǎng)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)奇偶校驗(yàn)碼

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

(10)

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

(11)

又因?yàn)閤i和ni相互獨(dú)立，根據(jù)特征函數(shù)的性質(zhì)，兩個(gè)相互獨(dú)立的隨機(jī)變量之和的特征函數(shù)等于它們的特征函數(shù)之積，故yi的特征函數(shù)為

(12)

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

(13)

(14)

圖3 接收信號(hào)概率密度曲線

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

圖4 接收信號(hào)累積分布曲線

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

圖5 輸入信號(hào)不同比特?cái)?shù)量化

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

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

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

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

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

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

4 結(jié) 論

基于LDPC碼的LLR BP譯碼算法，對(duì)其輸入信號(hào)，中間變量等參數(shù)進(jìn)行了量化分析.著重討論了在高斯白噪聲信道下，量化方式，量化范圍以及量化比特?cái)?shù)對(duì)LDPC碼的影響.仿真結(jié)果表明:對(duì)于輸入信號(hào)，在范圍均取為[-4,4]的條件下，采用6比特均勻量化時(shí)已經(jīng)可以達(dá)到一個(gè)很好的性能，隨著比特?cái)?shù)的增加沒(méi)有明顯區(qū)別.在對(duì)輸入變量和中間變量均采用相同比特均勻量化時(shí)，選擇量化比特為10，變量L(rij)量化范圍取為[-7.5,7.5]，L(qij)量化范圍取為[-20,20]，可以在盡量減少運(yùn)算復(fù)雜度的同時(shí)也得到一個(gè)比較良好的譯碼性能.采用上述方案，可以比較有效的消除錯(cuò)誤平層，更大程度的獲取譯碼性能，同時(shí)也對(duì)LDPC譯碼的硬件實(shí)現(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].遙測(cè)遙控,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] 李秋玲.基于動(dòng)態(tài)消息調(diào)度的LDPC碼及數(shù)字噴泉碼改進(jìn)譯碼算法研究[D].成都:西南交通大學(xué),2012.

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

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

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

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

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

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

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

[16] 劉藝美,吳康.基于2PSK無(wú)線載波通信系統(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è)計(jì)與實(shí)現(xiàn)[J].通信技術(shù),2010,43(5):84-86.

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