《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 設(shè)計應(yīng)用 > 基于FPGA的極化碼譯碼研究及實現(xiàn)
基于FPGA的極化碼譯碼研究及實現(xiàn)
2017年電子技術(shù)應(yīng)用第6期
鄧媛媛,卿粼波,,王正勇,,高菁汐,徐成強
四川大學(xué) 電子信息學(xué)院,,四川 成都610064
摘要: 在二進制離散無記憶信道中極化碼可以達到其信道極限容量,,并且實現(xiàn)的復(fù)雜度較低,這在通信領(lǐng)域無疑是一個重大突破,,因此在FPGA中實現(xiàn)極化碼的譯碼有著非常重要的研究意義,。首先介紹了SC(Successive Cancellation)譯碼算法,并將該算法的蝶形結(jié)構(gòu)改進為線形結(jié)構(gòu)從而提高了譯碼效率,;接著對譯碼算法做了包括最小和譯碼,、定點量化和資源共享的改進,以便于在硬件中更容易實現(xiàn),;最后在FPGA中實現(xiàn)了極化碼的譯碼并給出了測試波形以及對不同編碼塊長度的綜合資源進行了對比,。實驗結(jié)果表明,譯碼的最高頻率可達145 MHz,,吞吐率可達36.4 Mbps,。
關(guān)鍵詞: FPGA 極化碼 信道極化 SC譯碼
中圖分類號: TP368
文獻標識碼: 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.
The research and implementation of polarization code decoding based on FPGA
Deng Yuanyuan,Qing Linbo,,Wang Zhengyong,,Gao Jingxi,Xu Chengqiang
School of Electronics and Information Engineering,Sichuan University,,Chengdu 610064,,China
Abstract: In the binary discrete memoryless channel, polarization code can achieve its channel capacity limit and its implementation complexity is relatively low,which is a major breakthrough in communication field,so it is a very important research significance to realize polarization code decoding in FPGA. Firstly,the SC decoding algorithm is introduced and the butterfly structure is converted into liner structure in order to improve the efficiency of decoding. Then the decoding algorithm is improved by minimum decoding, fixed- point quantifying and resources sharing so that it is easier to implement in hardware. Finally,,realizes the polarization code decoding in FPGA and gives the test waveforms, while the comprehensive resource about different coding block length are also compared in this paper. The experimental results show that the decoding can reach the highest frequency 134 MHz and reach the throughput rate 35.6 Mbps.
Key words : FPGA,;polarization code;channel polarization,;SC decoding

0 引言

    最近幾年極化碼在編解碼領(lǐng)域中有突破性的進展,,從而激起了極化碼理論研究[1]的快速發(fā)展。Arikan Erdal于2008年提出極化碼[1],,并在對稱的二進制無記憶信道及任意的連續(xù)無記憶信道中證明了極化碼相較于Turbo碼[2]和LDPC碼[3]更能達到香農(nóng)極限[4],,并且用極化碼實現(xiàn)的通信系統(tǒng)能達到更高的通信帶寬,所以極化碼是目前公認的“最好”的碼,。

    目前,,極化碼的譯碼實現(xiàn)方式主要有軟件和硬件兩種方式,軟件的實現(xiàn)方式因CPU串行工作模式限制了譯碼速度的提升,,而FPGA因其具有快速并行計算的能力能彌補這一缺陷,。此外,極化碼的遞歸結(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)可得到譯出碼字wdz1-t1-s1.gif

wdz1-t1.gif

wdz1-gs1-3.gif

wdz1-t2.gif

2 極化碼譯碼的算法改進

2.1 SC譯碼算法結(jié)構(gòu)的改進

    由圖1可知由于數(shù)據(jù)之間的較強依賴性使得譯碼的效率不高,,例如圖1中l(wèi)2階段的所有節(jié)點,當輸入數(shù)據(jù)y0到y(tǒng)7準備完畢時允許節(jié)點執(zhí)行相應(yīng)的操作,,而事實上在第一個譯碼時鐘周期內(nèi)只有前4個節(jié)點執(zhí)行了相應(yīng)的操作,。為了比較譯碼效率,這里定義α表示使用率,,表達式如式(4)所示:

     wdz1-gs4-5.gif

    隨著碼長的增加,,使用率逐漸趨近于0,因此有很大的空間提升使用率,。為了提升使用率,,本文采用了線性的譯碼結(jié)構(gòu)來改進蝶形譯碼結(jié)構(gòu)。N=8的SC線性譯碼結(jié)構(gòu)圖如圖3所示,。

wdz1-t3.gif

wdz1-t3-x1.gif

    在線性譯碼結(jié)構(gòu)中,,函數(shù)f和g一半碼長的計算量都是在一個時鐘周期完成的,用來存儲部分計算結(jié)果和信道輸出似然比的內(nèi)存單元總共為2N-1個,,在整個譯碼過程中的處理單元為N/2個,。由式(4)可計算出線性結(jié)構(gòu)譯碼算法的使用率如式(6)所示:

    wdz1-gs6.gif

    可以看出相比于蝶形譯碼結(jié)構(gòu)而言,采用線性譯碼結(jié)構(gòu)的譯碼算法其使用率有一定的提升,,并且這種結(jié)構(gòu)編寫的代碼在硬件實現(xiàn)上更有利于綜合布線,。

2.2 SC譯碼算法在FPGA中實現(xiàn)的改進

    由式(2)可知函數(shù)f和g的計算涉及了乘法和除法,這在FPGA中實現(xiàn)會比較復(fù)雜,,因此改進了最小和算法,,在對數(shù)域中用等價函數(shù)來代替,等價式如式(7),、式(8)所示:

wdz1-gs7-8.gif

    由于信道的輸出和運算過程中的值都是浮點數(shù),,這不利于在FPGA中實現(xià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曲線圖。

wdz1-t4.gif

    由上圖可知,,(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)以及算法改進之后的性能,;然后用自行設(shè)計的以Xilinx公司的XC5VFX70T為核心處理器的14層電路板作為硬件平臺,該平臺最高運行頻率可達550 MHz,,片內(nèi)時鐘及存儲等資源十分豐富,,能夠用來實現(xiàn)極化碼的譯碼;最后給出了modelsim仿真波形和程序運行完成后chipscope抓取波形的對比結(jié)果,。

3.1 基于MATLAB的譯碼仿真結(jié)果

    如圖5所示為蝶形結(jié)構(gòu),、線性結(jié)構(gòu)和算法改進之后的SNR-BER曲線圖。

wdz1-t5.gif

    由圖可知使用蝶形結(jié)構(gòu)的SC譯碼與線性結(jié)構(gòu)的SC譯碼相比在不同信噪比的情況下誤比特率是相同的,,這是因為這兩種結(jié)構(gòu)只有在使用率方面有差異,。對算法做了最小和、定點量化和資源共享改進之后,,其性能有所下降,,但差別不是很大,為了能夠在硬件上更容易實現(xiàn)極化碼的譯碼,,做這些改進是值得的,。

3.2 基于硬件平臺的譯碼測試結(jié)果

    圖6所示為碼長256的仿真波形圖和實際抓取的波形圖,。圖中上半部分是model-sim的仿真波形,第一行是源碼字,,第二行是譯出的碼字,,第三行是源碼字和譯出碼字的異或結(jié)果。圖中下半部分是chipscope波形圖,,對其進行了局部放大以便于觀察,,由于順序不一樣,因此用直線相連接,。

wdz1-t6.gif

    圖7所示為碼長1 024的仿真波形和實際抓取的波形圖,。圖中上半部分是modelsim仿真圖,第一行是源碼字,,第二行是譯出的碼字,,第三行是源碼字和譯出碼字的異或結(jié)果,由于碼長太長,,所以分成了4段顯示,。圖中下半部分是chipscope抓取的波形,在波形中只放大了碼字的開始和結(jié)尾部分,,與仿真波形相比較時,,其順序是自下往上的。

wdz1-t7.gif

    在工程綜合編譯完成之后會有一個設(shè)計的綜合報告,,會給出編譯所使用的LUT,、FF、RAM以及最大時鐘頻率,,具體值如表1所示,,通過式(9)可以計算出運行過程中的吞吐率。

    wdz1-gs9.gif

    式中fm為最大時鐘頻率,,td為譯碼延遲的時鐘周期數(shù),,即從譯碼開始至譯碼結(jié)束所使用的時鐘周期數(shù),NA為有效碼長,。通過上式可以計算出編碼塊長度為256時吞吐率約為36.4 Mb/s,,編碼塊長度為1 024時吞吐率約為34.2 Mb/s。

    不同編碼塊長度下的綜合資源結(jié)果比較如表1所示,。

wdz1-b1.gif

    相同編碼塊長度下采用蝶形譯碼結(jié)構(gòu)和線性譯碼結(jié)構(gòu)的使用率結(jié)果對比如表2所示,。

wdz1-b2.gif

    從表2中可以看出隨著碼長的增加使用率在降低,但是在相同編碼塊長度下線性譯碼結(jié)構(gòu)明顯比蝶形譯碼結(jié)構(gòu)的使用率要高一些,。

4 總結(jié)

    本文針對當前極化碼在整個通信領(lǐng)域的應(yīng)用十分廣泛的現(xiàn)象,,主要研究了SC譯碼算法并在Xilinx XC5VFX70T芯片上實現(xiàn),在設(shè)計過程中考慮了FPGA的資源占用情況,、譯碼的復(fù)雜度以及譯碼使用率,。該譯碼器高達145 MHz的時鐘頻率和36.4 Mb/s的吞吐率使得該譯碼器具有較強的工程實用性。

參考文獻

[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.



作者信息:

鄧媛媛,,卿粼波,王正勇,,高菁汐,,徐成強

(四川大學(xué) 電子信息學(xué)院,,四川 成都610064)

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。