《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 業(yè)界動態(tài) > 基于FPGA的規(guī)則(3,6)LDPC碼譯碼器

基于FPGA的規(guī)則(3,6)LDPC碼譯碼器

2008-07-29
作者:李智明 王 琳 范 雷

??? 摘?要: 基于軟判決譯碼規(guī)則,采用完全并行的解碼結(jié)構(gòu),使用Verilog硬件描述語言,在Xilinx公司的FPGA(Virtex-2 xcv1000)上實(shí)現(xiàn)了碼率為1/2、幀長為20bit的規(guī)則(3,6)LDPC碼的譯碼器" title="譯碼器">譯碼器,最大" title="最大">最大傳輸速率" title="傳輸速率">傳輸速率可達(dá)20Mbps。對LDPC碼的實(shí)際應(yīng)用具有重要的推動作用。
??? 關(guān)鍵詞: LDPC碼? 變量節(jié)點(diǎn)? 校驗(yàn)檢點(diǎn)? 因子圖? 譯碼

?

??? 在通信系統(tǒng)中糾錯碼" title="糾錯碼">糾錯碼被用來提高信道傳輸?shù)目煽啃院凸β世寐?,低密度奇偶校?yàn)碼(LDPC碼)是目前最逼近香農(nóng)限的一類糾錯碼。1962年,Gallager[1]首次提出了LDPC碼的古典模型,即規(guī)則(regular)的LDPC碼:(n,j,k),校驗(yàn)矩陣H具有恒定的列重量和行重量。LDPC碼由于比Turbo碼更接近香農(nóng)限的誤碼率性能[2]和完全并行的迭代譯碼算法使其比Turbo碼在部分場合具有更廣泛的應(yīng)用前景,從而使LDPC碼成為當(dāng)前糾錯編碼的一個研究熱點(diǎn)。基于良好的譯碼性能,LDPC碼被認(rèn)為是通信系統(tǒng)的下一代糾錯碼。
1 規(guī)則LDPC碼
1.1 因子圖描述

??? 因子圖[2]有兩類頂點(diǎn),分別為變量節(jié)點(diǎn)(variable nodes,用空的圓點(diǎn)表示)和校驗(yàn)節(jié)點(diǎn)(check nodes,用方框表示)。Tanner圖就是這兩類頂點(diǎn)之間的二部圖,即每條邊的一端與變量節(jié)點(diǎn)相連,另一端與校驗(yàn)節(jié)點(diǎn)相連。變量節(jié)點(diǎn)代表實(shí)際的變量,校驗(yàn)節(jié)點(diǎn)代表這些變量節(jié)點(diǎn)之間的約束。對于(j,k)-LDPC碼的每個變量(bit)都受j個校驗(yàn)(check)的約束,因此每個變量節(jié)點(diǎn)應(yīng)該連接j個校驗(yàn)節(jié)點(diǎn)。每個校驗(yàn)方程有k個變量,因此每個校驗(yàn)節(jié)點(diǎn)應(yīng)與k個變量節(jié)點(diǎn)相連。由于LDPC是一種線性碼,使得它的因子圖一邊為變量節(jié)點(diǎn),一邊為校驗(yàn)節(jié)點(diǎn),故LDPC碼的因子圖表示有專用的定義:二部圖(bipartite graphs)。
??? 圖1表示了校驗(yàn)矩陣為H的規(guī)則(3,6)LDPC碼的因子圖,它是由10個變量定點(diǎn)和5個校驗(yàn)定點(diǎn)組成的二部圖,邊剛好對應(yīng)于矩陣中1的位置,這種因子圖是LDPC迭代譯碼算法的基礎(chǔ)。

?


1.2 LDPC碼的譯碼算法
??? LDPC碼的譯碼采用信度傳播(belief-propagation或BP)算法[1],它與因子圖相對應(yīng),如圖1所示,利用BP算法獲得好的譯碼性能,LDPC碼的因子圖中環(huán)的長度必須盡可能地長,長度為4的環(huán)會降低BP算法的性能,H矩陣設(shè)計時應(yīng)避免出現(xiàn)。如果直接使用BP算法,由于在迭代過程中存在大量的乘運(yùn)算,將使硬件的復(fù)雜度大幅度上升,本論文采用改進(jìn)的Log-BP算法[1][4],把大量的乘運(yùn)算轉(zhuǎn)換成加運(yùn)算,從而降低硬件復(fù)雜度及生產(chǎn)成本。
??? 首先定義可能用到的幾個變量及符號的意義:H表示一個M×N的LDPC校驗(yàn)矩陣,Hi,j表示矩陣H中第i行第j列的元素。定義校驗(yàn)節(jié)點(diǎn)m上的第n個變量節(jié)點(diǎn)為N(m)={n:Hm,n=1},關(guān)聯(lián)在變量節(jié)點(diǎn)n上的第m個校驗(yàn)節(jié)點(diǎn)為M(n)={m:Hmn=1}。定義校驗(yàn)節(jié)點(diǎn)m上關(guān)聯(lián)的除了第n個變量節(jié)點(diǎn)以外的所有變量節(jié)點(diǎn)為N(M)n,變量節(jié)點(diǎn)n上關(guān)聯(lián)的除了第m個校驗(yàn)節(jié)點(diǎn)外的所有校驗(yàn)節(jié)點(diǎn)為M(n)m。
??? Log-BP算法的譯碼過程:

??? 輸入數(shù)據(jù):初始概率n=1, …, N;

??? 輸出數(shù)據(jù)" title="輸出數(shù)據(jù)">輸出數(shù)據(jù):硬判決結(jié)果

??? 譯碼過程:
??? 初始化:對于接收到的每個變量節(jié)點(diǎn)n計算初始信道信息并對每個點(diǎn)計算初始信息,其中(m,n)∈{(i,j)|Hi j=1}。

???

??? 迭代譯碼:
??? (1)校驗(yàn)節(jié)點(diǎn)計算

???

???

???? 對于每個變量節(jié)點(diǎn)n,在完成變量節(jié)點(diǎn)計算后,對

??? (3)判決條件

???

??? 否則跳到第2步迭代譯碼部分,直至校驗(yàn)成功或者達(dá)到最大迭代次數(shù)。
??? 上面算法中的αm,n和βm,n都被稱為外部信息,其中αm,n是從變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的信息,βm,n是從變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳遞的信息。通過log-BP算法和BP算法的比較可以發(fā)現(xiàn),log-BP算法中除了f(x)=log剩下的都是加法運(yùn)算,從而避免了BP算法中乘運(yùn)算過多的弊病。在本文中函數(shù)f(x)利用FPGA中的查找表(Look-up Table, LUT)實(shí)現(xiàn)。
2 H矩陣的生成
??? Gallager提出的LDPC碼的H矩陣[1]必須滿足以下兩點(diǎn):
??? (1)H矩陣的每一列有j個1,j>=3;
??? (2)H矩陣的每一行有k個1,k>j;
??? 本文中選擇j=3,k=6,通過編程用matalab軟件生成若干滿足條件的H矩陣,選擇其中一個性能最好的H矩陣進(jìn)行LDPC碼的fpga譯碼實(shí)現(xiàn)。當(dāng)n=20時,最終選擇H矩陣如圖2所示。

?

?

3 LDPC碼完全平行譯碼結(jié)構(gòu)
??? 由二部圖可以直觀地看出,變量節(jié)點(diǎn)計算需要的信息只需由校驗(yàn)節(jié)點(diǎn)來提供,校驗(yàn)節(jié)點(diǎn)計算需要的信息只需要由變量節(jié)點(diǎn)來提供,譯碼器在設(shè)計時可以給每個變量節(jié)點(diǎn)分配一個變量節(jié)點(diǎn)處理單元(Variable Node processing Unit,VNU),給每個校驗(yàn)節(jié)點(diǎn)分配一個校驗(yàn)節(jié)點(diǎn)處理單元(Check Node processing Unit,CNU),從而實(shí)現(xiàn)譯碼器的完全并行結(jié)構(gòu)。
??? 譯碼器的核心模塊是迭代譯碼部分,迭代譯碼的結(jié)構(gòu)與算法是緊密相連的,譯碼結(jié)構(gòu)的確定必須在仔細(xì)分析算法的基礎(chǔ)上,迭代譯碼的過程是CNU和VNU模塊計算結(jié)果的相互傳遞和更新。如果直接將CNU和VNU連接,不但不容易控制迭代的過程并且可能出現(xiàn)不穩(wěn)定狀態(tài),所以需要在CNU和VNU之間安插RAM以起到數(shù)據(jù)的緩沖和控制作用。輸入、輸出模塊分別控制數(shù)據(jù)的輸入和輸出,當(dāng)條件滿足或者是迭代完成時,讀入數(shù)據(jù)并把迭代結(jié)果輸出。
3.1 迭代譯碼結(jié)構(gòu)
??? 圖3表示平行迭代譯碼結(jié)構(gòu)[5][6]。其中只畫出兩個節(jié)點(diǎn)之間一條數(shù)據(jù)通路的連接方式,因?yàn)槭峭耆叫械g碼結(jié)構(gòu),其他節(jié)點(diǎn)之間數(shù)據(jù)通路的連接方式與此相同。信道初始化數(shù)據(jù)送入VNU模塊進(jìn)行數(shù)據(jù)處理后,送入RAM模塊,數(shù)據(jù)經(jīng)過CNU模塊,最后再送入VNU模塊,這樣就完成一次迭代。數(shù)據(jù)信息從VNU到CNU與數(shù)據(jù)信息從CNU到VNU分別在不同的數(shù)據(jù)線上傳輸(圖1)。

?


3.2 變量節(jié)點(diǎn)結(jié)構(gòu)(VNU)
??? 變量節(jié)點(diǎn)的結(jié)構(gòu)如圖4所示。從中可以看出每個變量節(jié)點(diǎn)的度為3(j=3),四個5 bit輸入信息包含一個信道信息和三個與之相連的校驗(yàn)節(jié)點(diǎn)的信息。由log-BP算法可以看到α進(jìn)行的是量化值的計算,沒有牽扯到符號位,而γm,n和λn的計算都有包含符號位的相加,實(shí)際上其中還包含了減法運(yùn)算,而本文采用的符號信息位的格式不能用于減法運(yùn)算,需要將其轉(zhuǎn)換為其他格式。在本文進(jìn)行和運(yùn)算時,首先將其轉(zhuǎn)換為二進(jìn)制補(bǔ)碼形式,運(yùn)算結(jié)束后再轉(zhuǎn)換回符號量化位格式,查表(FX_LUT)進(jìn)行f(x)運(yùn)算。可由FPGA中的邏輯單元LUT來實(shí)現(xiàn)。Comb模塊把1bit的判決結(jié)果x、4bit的查找表運(yùn)算結(jié)果與符號位合在一起作為外部信息送入校驗(yàn)節(jié)點(diǎn)(CNU)。圖4上半部分為輸出譯碼的結(jié)果,下半部分為三個數(shù)據(jù)輸出通道中的一個,其余兩個的結(jié)構(gòu)與此完全相同,唯一不同的是加法器的輸入, 根據(jù)log-BP算法,其中初始化數(shù)據(jù)經(jīng)過S-to-T轉(zhuǎn)換后的數(shù)據(jù)輸入固定,另外兩個輸入數(shù)據(jù)為其他兩個數(shù)據(jù)通道的輸入經(jīng)過S-to-T轉(zhuǎn)換后的數(shù)據(jù)。

?

?

3.3 校驗(yàn)節(jié)點(diǎn)結(jié)構(gòu)(CNU)
??? 校驗(yàn)節(jié)點(diǎn)(CNU)結(jié)構(gòu)如圖5所示,每個檢驗(yàn)節(jié)點(diǎn)的度數(shù)為6(k=6),圖5只畫出數(shù)據(jù)的一個輸出通道,其余5個輸出通道的結(jié)構(gòu)與此完全相同,加法器為檢驗(yàn)節(jié)點(diǎn)首先對外部信息中的判決結(jié)果進(jìn)行驗(yàn)證,看是否滿足H·xT=0,滿足則結(jié)束迭代。CNU模塊中f(x)的x計算是只計算量化值而不管正負(fù)的,而本譯碼器采用的符號量化位格式只需將符號位屏蔽即可得到相當(dāng)于絕對值效果的量化位運(yùn)算,也就是CNU模塊中不需要將符號量化位轉(zhuǎn)化為二進(jìn)制補(bǔ)碼形式。

?


3.4? 數(shù)據(jù)輸入與輸出
??? 完全平行譯碼結(jié)構(gòu)可以分為三部分:迭代譯碼模塊、數(shù)據(jù)輸入模塊和數(shù)據(jù)輸出模塊。因?yàn)槭峭耆叫凶g碼方式,輸入數(shù)據(jù)經(jīng)過串并轉(zhuǎn)換后,同時讀入VNU進(jìn)行迭代計算。在數(shù)據(jù)輸出模塊,每一次迭代完成要進(jìn)行條件判別,如果CNU所有的校驗(yàn)結(jié)果都為零,則輸出數(shù)據(jù)?;蛘咭呀?jīng)完成17次迭代,此時強(qiáng)制輸出數(shù)據(jù)。數(shù)據(jù)的輸入與輸出分別用不同的時鐘進(jìn)行控制。圖6為譯碼器其中一幀數(shù)據(jù)的測試結(jié)果,編碼之前的信息為01010101,圖6中OutData為編碼后數(shù)據(jù)的輸出。

?


4? FPGA實(shí)現(xiàn)
??? 根據(jù)規(guī)則(3,6)LDPC碼的完全平行譯碼結(jié)構(gòu),選擇在Xilinx Virtex2 XC2V1000-fg256上對其進(jìn)行物理實(shí)現(xiàn),譯碼器采用Verilog硬件描述語言編寫,用Xilinx的開發(fā)工具ISE6.1在XC2V1000上對譯碼器進(jìn)行布局布線。硬件資源的占有率如表1所示。通過時序分析可以看出,譯碼器的最大時鐘頻率為20MHz,以輸入時鐘為基準(zhǔn),完成17次迭代最多需要20個時鐘,完成一幀數(shù)據(jù)的輸入需要20個時鐘,可以得出譯碼器的最大譯碼速率為:V=20×20/20=20Mbps。圖7為幀長為20bit的LDPC碼的譯碼性能,因?yàn)榇a長較短,性能沒有達(dá)到最好。這為更高速 LDPC碼譯碼器的設(shè)計打下堅(jiān)實(shí)的基礎(chǔ),碼長為1024bit,傳輸速率可進(jìn)一步提高,甚至達(dá)到1Gbps,譯碼性能會更好[6][7]。

?

?


??? 本文基于軟判決譯碼規(guī)則,采用完全平行譯碼結(jié)構(gòu),設(shè)計出幀長為20bit,碼率為1/2的規(guī)則(3,6)LDPC碼的譯碼器,在Xilinx virtex2 XC2V1000-fg256上對其進(jìn)行物理實(shí)現(xiàn),最大迭代次數(shù)為17次,傳輸速率達(dá)到20Mbps。LDPC碼具有良好譯碼性能,與Turbo碼相比更易于硬件實(shí)現(xiàn),并能得到更高的譯碼速度。下一步將設(shè)計出碼長為1024bit或碼長更長的LDPC譯碼器,進(jìn)一步提高傳輸速率,降低誤碼率,為加速該技術(shù)在中國的商用奠定基礎(chǔ)。
參考文獻(xiàn)
1 R.G. Gallager.Low density parity check codes.IRE Trans. Inform. Theory,1962; IT-8(Jan):21~28
2 R. M. Tanner. A recursive approach to low complexity?codes.IEEE Trans. Inform. Theory,1981; IT-42:533~547
3 M. Chiani, A. Conti, and A. Ventura.Evaluation of lowdensity parity-check codes over block fading channels. in??2000 IEEE International Conference on Communications.?2000:1183~1187
4 S. Kim, G. E. Sobelman, J. Moon.Parallel VLSI Architectures for a Class of LDPC Codes. Circuits and Systems.IEEE International Symposium on, 2002;Volume:2
5 C. J. Howland and A. J. Blanksby.Parallel decoding architectures for lowdensity parity check codes. in Proc. IEEE?ISCAS,2001;4(5):742~745
6 A. J. Blanksby and C. J. Howland. A 690-mW 1-Gb/s?1024-b, rate-1/2 low-density parity-check code decoder.?IEEE Journal of Solid-State Circuits,2002;37(3):404~412
7 T. Zhang and K.K. Parhi.VLSI implementation-oriented(3,k)egular low-density parity-check codes. IEEE Workshop on Signal Processing Systems (SiPS), 2001;9

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點(diǎn)。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問題,請及時通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。