文獻(xiàn)標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.2017.06.009
中文引用格式: 鄧媛媛,卿粼波,王正勇,等. 基于FPGA的極化碼譯碼研究及實現(xiàn)[J].電子技術(shù)應(yīng)用,2017,43(6):37-40,44.
英文引用格式: Deng Yuanyuan,Qing Linbo,Wang Zhengyong,et al. The research and implementation of polarization code decoding based on FPGA[J].Application of Electronic Technique,2017,43(6):37-40,44.
0 引言
最近幾年極化碼在編解碼領(lǐng)域中有突破性的進(jìn)展,從而激起了極化碼理論研究[1]的快速發(fā)展。Arikan Erdal于2008年提出極化碼[1],并在對稱的二進(jìn)制無記憶信道及任意的連續(xù)無記憶信道中證明了極化碼相較于Turbo碼[2]和LDPC碼[3]更能達(dá)到香農(nóng)極限[4],并且用極化碼實現(xiàn)的通信系統(tǒng)能達(dá)到更高的通信帶寬,所以極化碼是目前公認(rèn)的“最好”的碼。
目前,極化碼的譯碼實現(xiàn)方式主要有軟件和硬件兩種方式,軟件的實現(xiàn)方式因CPU串行工作模式限制了譯碼速度的提升,而FPGA因其具有快速并行計算的能力能彌補(bǔ)這一缺陷。此外,極化碼的遞歸結(jié)構(gòu)能夠?qū)崿F(xiàn)資源共享并簡化計算過程,這一特點表明極化碼易于FPGA實現(xiàn)[5-6]。
目前,關(guān)于極化碼的譯碼算法主要有置信度傳播(Brief Propagation,BP)算法[7]、最大似然比(Maximum Likelyhood,ML)算法[8]、連續(xù)消除(Successive Cancellation,SC)算法[9]。這3種算法中,BP和ML算法由于在運算過程中涉及到較多的乘除法運算,因此不利于FPGA實現(xiàn),而SC算法在譯碼過程中主要是通過加減和位運算實現(xiàn),所以SC算法適用于FPGA實現(xiàn)。
基于極化碼、FPGA、SC譯碼算法3方面的優(yōu)點,本文的重點工作是采用極化碼、運用SC譯碼算法設(shè)計一種新型的譯碼器并在Xilinx XC5VFX70T上實現(xiàn)該譯碼器。
1 極化碼的SC譯碼算法
1.1 SC譯碼算法
SC譯碼算法的核心就是連續(xù)地估計每個比特的似然比值,Arikan表示這些似然比值[9]可以通過數(shù)據(jù)流圖采用遞歸的方式被有效地執(zhí)行,這個數(shù)據(jù)流圖類似于快速傅里葉變換結(jié)構(gòu),一般是通過蝶形結(jié)構(gòu)的數(shù)據(jù)流圖來計算似然比值,N=8的蝶形SC譯碼結(jié)構(gòu)圖如圖1所示,y0到y(tǒng)7是信道的輸出值,通過如下結(jié)構(gòu)可得到譯出碼字
2 極化碼譯碼的算法改進(jìn)
2.1 SC譯碼算法結(jié)構(gòu)的改進(jìn)
由圖1可知由于數(shù)據(jù)之間的較強(qiáng)依賴性使得譯碼的效率不高,例如圖1中l(wèi)2階段的所有節(jié)點,當(dāng)輸入數(shù)據(jù)y0到y(tǒng)7準(zhǔn)備完畢時允許節(jié)點執(zhí)行相應(yīng)的操作,而事實上在第一個譯碼時鐘周期內(nèi)只有前4個節(jié)點執(zhí)行了相應(yīng)的操作。為了比較譯碼效率,這里定義α表示使用率,表達(dá)式如式(4)所示:
隨著碼長的增加,使用率逐漸趨近于0,因此有很大的空間提升使用率。為了提升使用率,本文采用了線性的譯碼結(jié)構(gòu)來改進(jìn)蝶形譯碼結(jié)構(gòu)。N=8的SC線性譯碼結(jié)構(gòu)圖如圖3所示。
在線性譯碼結(jié)構(gòu)中,函數(shù)f和g一半碼長的計算量都是在一個時鐘周期完成的,用來存儲部分計算結(jié)果和信道輸出似然比的內(nèi)存單元總共為2N-1個,在整個譯碼過程中的處理單元為N/2個。由式(4)可計算出線性結(jié)構(gòu)譯碼算法的使用率如式(6)所示:
可以看出相比于蝶形譯碼結(jié)構(gòu)而言,采用線性譯碼結(jié)構(gòu)的譯碼算法其使用率有一定的提升,并且這種結(jié)構(gòu)編寫的代碼在硬件實現(xiàn)上更有利于綜合布線。
2.2 SC譯碼算法在FPGA中實現(xiàn)的改進(jìn)
由式(2)可知函數(shù)f和g的計算涉及了乘法和除法,這在FPGA中實現(xiàn)會比較復(fù)雜,因此改進(jìn)了最小和算法,在對數(shù)域中用等價函數(shù)來代替,等價式如式(7)、式(8)所示:
由于信道的輸出和運算過程中的值都是浮點數(shù),這不利于在FPGA中實現(xiàn),所以做了定點量化的改進(jìn),用(C,L,F(xiàn))來表示量化結(jié)果,其中C代表信道輸出的量化比特數(shù),L代表運算過程中對數(shù)似然比的量化比特數(shù),F(xiàn)代表信道輸出和似然比值量化的小數(shù)位數(shù)。量化的位數(shù)不易過長,因為會消耗很多資源,也不易過短,因為會有很大的誤差。本文做了包括(3,4,0)、(3,4,1)、(4,5,0)、(4,5,1)、(5,6,0)、(5,6,1)、(6,7,0)、(6,7,1)這些帶小數(shù)位和不帶小數(shù)位的多種不同位數(shù)的量化,通過實驗結(jié)果的對比,選出了兩種效果較好的量化方式分別是(4,5,0)和(5,6,1),如圖4所示為量化前后的BER曲線圖。
由上圖可知,(4,5,0)和(5,6,1)的量化結(jié)果與量化前相比對譯碼性能的影響都不大。再對比(4,5,0)和(5,6,1)的量化方式,由于選用沒有小數(shù)位的量化方式更有利于硬件實現(xiàn),因此本文選用(4,5,0)的量化方式。
由圖1可知,在譯碼過程中需要的存儲單元總數(shù)為Nlog2N個,隨著編碼塊長度的增加,存儲單元的總數(shù)也在增加,這樣就會占用更多的FPGA的資源,所以采用了資源共享這一方式。本文中編碼塊長度N與階段l的關(guān)系是l=log2N-1,每一個階段l需要的存儲單元是2l,因此實際只需要 N-1個存儲單元即可。采用資源共享的方式并不會對譯碼的性能造成任何影響,并且大大地減少了存儲單元的數(shù)量,節(jié)約了FPGA中的資源。
3 基于FPGA的極化碼譯碼硬件平臺與測試結(jié)果
為了驗證SC譯碼算法在FPGA上實現(xiàn)的正確性,本文首先在MATLAB中仿真對比了蝶形結(jié)構(gòu)、線性結(jié)構(gòu)以及算法改進(jìn)之后的性能;然后用自行設(shè)計的以Xilinx公司的XC5VFX70T為核心處理器的14層電路板作為硬件平臺,該平臺最高運行頻率可達(dá)550 MHz,片內(nèi)時鐘及存儲等資源十分豐富,能夠用來實現(xiàn)極化碼的譯碼;最后給出了modelsim仿真波形和程序運行完成后chipscope抓取波形的對比結(jié)果。
3.1 基于MATLAB的譯碼仿真結(jié)果
如圖5所示為蝶形結(jié)構(gòu)、線性結(jié)構(gòu)和算法改進(jìn)之后的SNR-BER曲線圖。
由圖可知使用蝶形結(jié)構(gòu)的SC譯碼與線性結(jié)構(gòu)的SC譯碼相比在不同信噪比的情況下誤比特率是相同的,這是因為這兩種結(jié)構(gòu)只有在使用率方面有差異。對算法做了最小和、定點量化和資源共享改進(jìn)之后,其性能有所下降,但差別不是很大,為了能夠在硬件上更容易實現(xiàn)極化碼的譯碼,做這些改進(jìn)是值得的。
3.2 基于硬件平臺的譯碼測試結(jié)果
圖6所示為碼長256的仿真波形圖和實際抓取的波形圖。圖中上半部分是model-sim的仿真波形,第一行是源碼字,第二行是譯出的碼字,第三行是源碼字和譯出碼字的異或結(jié)果。圖中下半部分是chipscope波形圖,對其進(jìn)行了局部放大以便于觀察,由于順序不一樣,因此用直線相連接。
圖7所示為碼長1 024的仿真波形和實際抓取的波形圖。圖中上半部分是modelsim仿真圖,第一行是源碼字,第二行是譯出的碼字,第三行是源碼字和譯出碼字的異或結(jié)果,由于碼長太長,所以分成了4段顯示。圖中下半部分是chipscope抓取的波形,在波形中只放大了碼字的開始和結(jié)尾部分,與仿真波形相比較時,其順序是自下往上的。
在工程綜合編譯完成之后會有一個設(shè)計的綜合報告,會給出編譯所使用的LUT、FF、RAM以及最大時鐘頻率,具體值如表1所示,通過式(9)可以計算出運行過程中的吞吐率。
式中fm為最大時鐘頻率,td為譯碼延遲的時鐘周期數(shù),即從譯碼開始至譯碼結(jié)束所使用的時鐘周期數(shù),NA為有效碼長。通過上式可以計算出編碼塊長度為256時吞吐率約為36.4 Mb/s,編碼塊長度為1 024時吞吐率約為34.2 Mb/s。
不同編碼塊長度下的綜合資源結(jié)果比較如表1所示。
相同編碼塊長度下采用蝶形譯碼結(jié)構(gòu)和線性譯碼結(jié)構(gòu)的使用率結(jié)果對比如表2所示。
從表2中可以看出隨著碼長的增加使用率在降低,但是在相同編碼塊長度下線性譯碼結(jié)構(gòu)明顯比蝶形譯碼結(jié)構(gòu)的使用率要高一些。
4 總結(jié)
本文針對當(dāng)前極化碼在整個通信領(lǐng)域的應(yīng)用十分廣泛的現(xiàn)象,主要研究了SC譯碼算法并在Xilinx XC5VFX70T芯片上實現(xiàn),在設(shè)計過程中考慮了FPGA的資源占用情況、譯碼的復(fù)雜度以及譯碼使用率。該譯碼器高達(dá)145 MHz的時鐘頻率和36.4 Mb/s的吞吐率使得該譯碼器具有較強(qiáng)的工程實用性。
參考文獻(xiàn)
[1] 陸婷婷.極化碼的編解碼研究及仿真[D].南京:南京理工大學(xué),2013.
[2] KOVACI M,BALTA H.Turbo codes performance on Rice flat fading environment[C]//Electronics and Telecommunications(ISETC),2014 11th International Symposium on.IEEE,2014:1-4.
[3] KUMAR N,PRAKASH C,SATASHIA S N,et al.Efficient implementation of Low Density Parity Check codes for satellite ground terminals[C]//Adva-nces in Computing,Communications and Informatics(ICACCI),2014 International Conference on.IEEE,2014:689-695.
[4] KORADA S B,URBANKE R.Polar codes:characterization of exponent,bounds,and constructins[J].Information Theory,IEEE Transactions on,2010,56(12):6253-6264.
[5] MISHRA A,RAYMOND A J,AMARU L G,et al.A successive cancellation decoder ASIC for a 1024-bit polar code in 180 nm CMOS[C]//Solid State Circuits Conference(A-SSCC),2012 IEEE Asian.IEEE,2012:205-208.
[6] LEROUX C,TAL I,VARDY A,et al.Hardware archi-tectures for successive cancellation decoding of polar codes[C]//IEEE International Conference on Acoustics.IEEE,2011:1665-1668.
[7] HUSSAMI N,KORADA S B,URBANKE R.Perfor- mance of polar codes for channel and source coding[C]//Information Theory,2009.ISIT 2009.IEEE Intemational Symposium on.IEEE,2009:1488-1492.
[8] KAHRAMAN S,CELEBI M E.Code based efficient maximum-likelihood decoding of short polar codes[C]//Information Theory Proceedings(ISIT),2012 IEEE Intemational Symposium on.IEEE,2012:1967-1971.
[9] ARIKAN E.Channel polarization:A method for costructing capacity-achieving codes for symmetric binary-input memoryless channels[J].IEEE Transactions on Information Theory,2009,55(7):3051-3073.
作者信息:
鄧媛媛,卿粼波,王正勇,高菁汐,徐成強(qiáng)
(四川大學(xué) 電子信息學(xué)院,四川 成都610064)