基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法 - 全文

在二進(jìn)制離散無(wú)記憶信道中極化碼可以達(dá)到其信道極限容量，并且實(shí)現(xiàn)的復(fù)雜度較低，這在通信領(lǐng)域無(wú)疑是一個(gè)重大突破，因此在FPGA中實(shí)現(xiàn)極化碼的譯碼有著非常重要的研究意義。首先介紹了SC（Successive Cancellation）譯碼算法，并將該算法的蝶形結(jié)構(gòu)改進(jìn)為線形結(jié)構(gòu)從而提高了譯碼效率；接著對(duì)譯碼算法做了包括最小和譯碼、定點(diǎn)量化和資源共享的改進(jìn)，以便于在硬件中更容易實(shí)現(xiàn)；最后在FPGA中實(shí)現(xiàn)了極化碼的譯碼并給出了測(cè)試波形以及對(duì)不同編碼塊長(zhǎng)度的綜合資源進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，譯碼的最高頻率可達(dá)145 MHz，吞吐率可達(dá)36.4 Mbps。

0 引言

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

目前，極化碼的譯碼實(shí)現(xiàn)方式主要有軟件和硬件兩種方式，軟件的實(shí)現(xiàn)方式因CPU串行工作模式限制了譯碼速度的提升，而FPGA因其具有快速并行計(jì)算的能力能彌補(bǔ)這一缺陷。此外，極化碼的遞歸結(jié)構(gòu)能夠?qū)崿F(xiàn)資源共享并簡(jiǎn)化計(jì)算過(guò)程，這一特點(diǎn)表明極化碼易于FPGA實(shí)現(xiàn)[5-6]。

目前，關(guān)于極化碼的譯碼算法主要有置信度傳播(Brief Propagation，BP)算法[7]、最大似然比(Maximum Likelyhood，ML)算法[8]、連續(xù)消除(Successive Cancellation，SC)算法[9]。這3種算法中，BP和ML算法由于在運(yùn)算過(guò)程中涉及到較多的乘除法運(yùn)算，因此不利于FPGA實(shí)現(xiàn)，而SC算法在譯碼過(guò)程中主要是通過(guò)加減和位運(yùn)算實(shí)現(xiàn)，所以SC算法適用于FPGA實(shí)現(xiàn)。

基于極化碼、FPGA、SC譯碼算法3方面的優(yōu)點(diǎn)，本文的重點(diǎn)工作是采用極化碼、運(yùn)用SC譯碼算法設(shè)計(jì)一種新型的譯碼器并在Xilinx XC5VFX70T上實(shí)現(xiàn)該譯碼器。

1 極化碼的SC譯碼算法

1.1 SC譯碼算法

SC譯碼算法的核心就是連續(xù)地估計(jì)每個(gè)比特的似然比值，Arikan表示這些似然比值[9]可以通過(guò)數(shù)據(jù)流圖采用遞歸的方式被有效地執(zhí)行，這個(gè)數(shù)據(jù)流圖類似于快速傅里葉變換結(jié)構(gòu)，一般是通過(guò)蝶形結(jié)構(gòu)的數(shù)據(jù)流圖來(lái)計(jì)算似然比值，N=8的蝶形SC譯碼結(jié)構(gòu)圖如圖1所示，y0到y(tǒng)7是信道的輸出值，通過(guò)如下結(jié)構(gòu)可得到譯出碼字

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

2 極化碼譯碼的算法改進(jìn)

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

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

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

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

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

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

由于信道的輸出和運(yùn)算過(guò)程中的值都是浮點(diǎn)數(shù)，這不利于在FPGA中實(shí)現(xiàn)，所以做了定點(diǎn)量化的改進(jìn)，用(C，L，F(xiàn))來(lái)表示量化結(jié)果，其中C代表信道輸出的量化比特?cái)?shù)，L代表運(yùn)算過(guò)程中對(duì)數(shù)似然比的量化比特?cái)?shù)，F(xiàn)代表信道輸出和似然比值量化的小數(shù)位數(shù)。量化的位數(shù)不易過(guò)長(zhǎng)，因?yàn)闀?huì)消耗很多資源，也不易過(guò)短，因?yàn)闀?huì)有很大的誤差。本文做了包括(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ù)的量化，通過(guò)實(shí)驗(yàn)結(jié)果的對(duì)比，選出了兩種效果較好的量化方式分別是(4，5，0)和(5，6，1)，如圖4所示為量化前后的BER曲線圖。

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

由上圖可知，(4，5，0)和(5，6，1)的量化結(jié)果與量化前相比對(duì)譯碼性能的影響都不大。再對(duì)比(4，5，0)和(5，6，1)的量化方式，由于選用沒(méi)有小數(shù)位的量化方式更有利于硬件實(shí)現(xiàn)，因此本文選用(4，5，0)的量化方式。

由圖1可知，在譯碼過(guò)程中需要的存儲(chǔ)單元總數(shù)為Nlog2N個(gè)，隨著編碼塊長(zhǎng)度的增加，存儲(chǔ)單元的總數(shù)也在增加，這樣就會(huì)占用更多的FPGA的資源，所以采用了資源共享這一方式。本文中編碼塊長(zhǎng)度N與階段l的關(guān)系是l=log2N-1，每一個(gè)階段l需要的存儲(chǔ)單元是2l，因此實(shí)際只需要 N-1個(gè)存儲(chǔ)單元即可。采用資源共享的方式并不會(huì)對(duì)譯碼的性能造成任何影響，并且大大地減少了存儲(chǔ)單元的數(shù)量，節(jié)約了FPGA中的資源。

3 基于FPGA的極化碼譯碼硬件平臺(tái)與測(cè)試結(jié)果

為了驗(yàn)證SC譯碼算法在FPGA上實(shí)現(xiàn)的正確性，本文首先在MATLAB中仿真對(duì)比了蝶形結(jié)構(gòu)、線性結(jié)構(gòu)以及算法改進(jìn)之后的性能；然后用自行設(shè)計(jì)的以Xilinx公司的XC5VFX70T為核心處理器的14層電路板作為硬件平臺(tái)，該平臺(tái)最高運(yùn)行頻率可達(dá)550 MHz，片內(nèi)時(shí)鐘及存儲(chǔ)等資源十分豐富，能夠用來(lái)實(shí)現(xiàn)極化碼的譯碼；最后給出了modelsim仿真波形和程序運(yùn)行完成后chipscope抓取波形的對(duì)比結(jié)果。

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

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

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

3.2 基于硬件平臺(tái)的譯碼測(cè)試結(jié)果

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

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

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

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

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

基于FPGA的極化碼的SC譯碼算法結(jié)構(gòu)的改進(jìn)方法

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

4 總結(jié)

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

閱讀全文

上一頁(yè)1 2 3全文