《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 設計應用 > 基于FPGA的SCL譯碼算法優(yōu)化與設計
基于FPGA的SCL譯碼算法優(yōu)化與設計
2018年電子技術應用第12期
廖海鵬,卿粼波,滕奇志,何小海,鄧媛媛
四川大學 電子信息學院,四川 成都610065
摘要: 由于極化碼被指出在二進制離散無記憶信道中具有實現(xiàn)其極限容量的理論性能,近年來極化碼在通信領域的貢獻日漸凸顯。極化碼的譯碼系統(tǒng)可采用軟件或者硬件方式實現(xiàn),其中使用軟件方式時譯碼效率受限于CPU的串行處理模式,因此在具有并行工作模式的FPGA上進行極化碼的譯碼實現(xiàn)對于通信系統(tǒng)來說具有非常大的意義。首先介紹了極化碼的SCL譯碼算法;然后針對該算法進行優(yōu)化從而提高譯碼效率,以及針對該算法在FPGA上的實現(xiàn)進行了定點量化的改進;最后對譯碼器進行硬件仿真,以及在FPGA上進行了實現(xiàn)與性能分析。實驗結果表明該譯碼器在碼長為512時譯碼最高頻率為143.988 MHz,吞吐率為28.79 Mb/s。
中圖分類號: TN911.2
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.181295
中文引用格式: 廖海鵬,卿粼波,滕奇志,等. 基于FPGA的SCL譯碼算法優(yōu)化與設計[J].電子技術應用,2018,44(12):1-4,8.
英文引用格式: Liao Haipeng,Qing Linbo,Teng Qizhi,et al. The optimization and design of SCL decoding algorithm based on FPGA[J]. Application of Electronic Technique,2018,44(12):1-4,8.
The optimization and design of SCL decoding algorithm based on FPGA
Liao Haipeng,Qing Linbo,Teng Qizhi,He Xiaohai,Deng Yuanyuan
School of Electronics and Information Engineering,Sichuan University,Chengdu 610065,China
Abstract: In recent years, the contribution of polarization code to communication field is becoming more and more prominent, because the theory of polarization code is proved to be able to achieve the channel limit capacity in BDMC. The decoding system of polarization codes can be realized by software or hardware, and the software decoding speed is limited by the CPU serial working mode. So it is of great value for the communication filed to implement the decoder of polarization code on FPGA with parallel working mode. Firstly the SCL decoding algorithm is introduced in this paper. Then the algorithm is optimized to improve the decoding efficiency, and the quantization improvement is carried out on FPGA. Finally, the hardware emulation of the decoder and the performance analysis are carried out on FPGA. The experimental results show that the maximum frequency of the decoder is up to 143.988 MHz, and the throughput is up to 28.79 Mb/s when the code length is 512.
Key words : polarization code;FPGA;SCL decoding;fixed-point quantitative

0 引言

    2008年ARIKAN E提出了信道極化的概念并對信道極化現(xiàn)象進行了詳細的描述[1]極化碼的主要過程是在編碼系統(tǒng)中通過對信道進行結合與拆分,然后在其中選擇好的部分信道來進行有效數(shù)據(jù)的傳輸。極化碼被嚴格證明有以下兩個特性:一是基于信道極化現(xiàn)象存在;二是在碼長為無限長時,其信道容量可達香農(nóng)極限。相比于經(jīng)典的Turbo碼與LDPC碼,極化碼具有更低的誤碼率和復雜度以及更高的吞吐率[2-3]。

    極化碼的譯碼算法研究近年來發(fā)展迅速,其中成為研究熱點的連續(xù)刪除(Successive Cancellation,SC)譯碼算法的基本思想是通過對信息位的比特似然概率值的判斷來進行譯碼。但由于在譯碼時前一個譯碼值會對之后的譯碼值造成影響,因此導致譯碼性能較差[4]。在此基礎上改進的序列連續(xù)刪除(Successive Cancellation List,SCL)算法能在計算復雜度與空間復雜度之間實現(xiàn)更好的平衡[5],相比于在軟件上實現(xiàn)該算法,在FPGA上進行SCL譯碼可以使譯碼速度進一步加快[6]。目前極化碼各方面都已經(jīng)取得了碩果,但是在FPGA上的譯碼實現(xiàn)仍然存在著譯碼效率和吞吐率不夠高等問題[6]。因此本文針對極化碼的SCL譯碼算法進行了研究和優(yōu)化,減少資源消耗同時提高譯碼效率;針對FPGA上的譯碼器設計進行了定點量化的改進;最后在Xilinx的VC707開發(fā)板上進行了譯碼器的實現(xiàn)與性能分析。實驗結果表明譯碼器在碼長為512時譯碼效率為143.988 MHz,吞吐率達到了28.79 Mb/s,具有較強的工程使用價值。

1 極化碼的SCL譯碼算法

    SCL譯碼算法實質(zhì)是對SC譯碼算法的推廣,SC譯碼算法的基本思想是通過對每個傳輸碼字的LLR(對數(shù)似然比值)進行判斷譯出碼字,LLR的定義如式(1)所示。

wdz1-gs1-2.gif

    圖1所示為SC譯碼路徑示意圖,由示意圖和LLR計算公式可以看出SC譯碼在譯碼過程中前一個譯碼值與之后的譯碼值相互關聯(lián),這將對其譯碼算法的性能造成影響。

wdz1-t1.gif

wdz1-gs3.gif

其中函數(shù)δ(x)=(1-sgn(δ))/2,符號函數(shù)sgn(x)表示在x>0時值為1,x<0時值為-1,x=0時值為0。l代表相應路徑且初始值wdz1-gs3-x1.gif

    如圖2所示的SCL譯碼過程中,傳輸?shù)拇a字為1010,其中前兩位為固定比特,后兩位為信息比特。傳輸碼字從根節(jié)點出發(fā)向下擴展,可以得到相應的PM值,一直擴展到4條路徑,此時取出PM值較小的兩條路徑繼續(xù)擴展,其余路徑刪除,因此最終只有4條路徑,其中最后算出的PM值最小的相應路徑即為譯碼結果。圖2中曲線代表此次PM值最小路徑為1010,譯碼結果正確。

wdz1-t2.gif

2 SCL譯碼的優(yōu)化與設計

    SCL譯碼算法的核心依然是SC譯碼算法,但其性能優(yōu)于SC譯碼算法。在FPGA上進行SCL譯碼算法的實現(xiàn)會遇到如何提高譯碼效率和吞吐率以及如何合理利用FPGA片上資源等挑戰(zhàn)。針對SCL譯碼算法的優(yōu)化可以在基于其具有的遞歸結構下對譯碼計算過程進行簡化,針對FPGA上的譯碼器設計可在運算過程中對浮點數(shù)進行量化,更有利于硬件實現(xiàn)。

2.1 SCL譯碼算法系統(tǒng)設計

    圖3所示為本文所設計的SCL譯碼系統(tǒng)圖,針對在SCL譯碼的過程中有可能出現(xiàn)最小PM值路徑譯碼不是正確譯碼的情況,可以通過采用文獻[8]中的增加循環(huán)冗余校驗(Cyclic Redundancy Check,CRC)輔助的方法來進行解決。在編碼系統(tǒng)中先對源碼進行校驗碼的添加,然后進行極化碼的編碼生成相應的碼字進行傳輸。解碼系統(tǒng)在FPGA上使用設計的譯碼器對傳輸過來的碼字進行極化碼譯碼以及校驗碼校驗,在譯碼最后階段的路徑選擇時從最小PM值逐條校驗,一旦出現(xiàn)校驗通過的路徑即為譯碼結果。

wdz1-t3.gif

2.2 SCL譯碼算法優(yōu)化

    SCL譯碼過程實質(zhì)是L個SC譯碼算法同時進行,圖4所示為碼長為8時的SC譯碼算法遞歸流程圖,圖中傳遞的信息wdz1-2.2-x1.gif均為LLR,其中S代表計算層數(shù),i代表相應碼字標號。

wdz1-t4.gif

    在SC譯碼算法中,LLR的計算公式如下:

wdz1-gs4-5.gif

2.3 FPGA中實現(xiàn)算法的改進

    在圖4所示的SC譯碼算法流程圖中實線部分代表執(zhí)行的f函數(shù),虛線部分代表執(zhí)行的g函數(shù)。分別定義如下:

wdz1-gs6-8.gif

    在SCL譯碼過程中的LLR計算值均為浮點數(shù),直接在FPGA中計算會使得譯碼復雜度較高,因此將浮點數(shù)進行定點量化轉(zhuǎn)變成定點數(shù),定點量化的結果通過(O,R,D)來表示,定義如表1所示。

wdz1-b1.gif

    對f函數(shù)進行改進之后,譯碼過程中的計算不再涉及乘除法,因此信道輸出和LLR的小數(shù)位數(shù)可以一致。由于采用定點量化用量化值代替了原始值,必定會對譯碼結果造成一定影響,因此選擇合適的量化比特數(shù)和小數(shù)位數(shù)尤為重要。通過對信道輸出值以及運算過程中的對數(shù)似然比值進行詳細的分析以及對比實驗,選出了三種如下較好的量化方式。圖5所示為量化前后的BER曲線圖。

wdz1-t5.gif

    如圖5所示的三種量化方式相比,(4,4,0)由于LLR量化的比特數(shù)過小,導致效果不是很理想。(4,5,0)和(5,6,1)的量化選擇基本沒有降低SCL的譯碼性能,而(4,5,0)這種沒有小數(shù)位的量化選擇更有利于在FPGA上進行計算,因此譯碼器的設計選用(4,5,0)的量化方式。

3 譯碼硬件平臺與譯碼測試結果

3.1 硬件平臺選擇

    本文選擇在Xilinx的VC707開發(fā)板上對譯碼器進行實現(xiàn)。該開發(fā)板的主芯片為XC7VX485T,包含有485 760個邏輯單元、2 800個DSP Slice、37 080 KB內(nèi)存以及700個I/O引腳等資源。其最高運行頻率可以達到741 MHz,可以用來實現(xiàn)極化碼的譯碼。圖6為該評估板實物圖。

wdz1-t6.gif

3.2 譯碼的仿真與測試

    為了對SCL和SC算法進行對比以及選擇一個合適的路徑刪減值L,在譯碼器編寫前對各L值下的SCL算法進行了MATLAB仿真,仿真結果如圖7所示。

wdz1-t7.gif

    由圖7可知當L=1和L=2時誤比特率差別較大,再繼續(xù)加大L值時雖然可以使誤比特率進一步降低,但是差別已經(jīng)沒有那么明顯,為了在FPGA上能夠更容易實現(xiàn)SCL算法,選擇L=2來進行路徑刪減實現(xiàn)算法。

    接著對譯碼器的正確性進行驗證,先通過ModelSim仿真軟件對譯碼器進行硬件仿真。然后使用ISE軟件帶有的Chipscope在線邏輯分析儀去抓取在FPGA上的譯碼結果,通過硬件仿真結果與FPGA上的譯碼結果對比來驗證譯碼的正確性。

    如圖8所示上半部分為在ModelSim上碼長為64時的仿真結果,data_u_out和data_uhat_out分別為輸入源碼字和譯碼仿真結果。下半部分為使用Chipscope抓取的FPGA中運行結果波形圖,data_u和data_uhat分別為輸入源碼字和實際譯碼結果。輸入源碼中有一半碼字為固定比特,因此有效碼字只有32位。由圖8可以看出源碼字和仿真結果以及FPGA譯碼結果均為69ab4d68,因此本次譯碼結果正確。

wdz1-t8.gif

    圖9和圖10所示分別為碼長為128和512時的仿真結果和譯碼結果波形圖。在抓取512碼長的波形時,由于碼長太長,因此在Chipscope中分成了四段進行顯示,由于Chipscope與ModelSim顯示順序不同,因此用相應數(shù)字表示了相應的結果順序,可以看出譯碼結果均正確。

wdz1-t9.gif

wdz1-t10.gif

3.3 譯碼性能分析

    下面對算法的性能以及工程占用資源等進行綜合分析,在ISE軟件上的綜合報告中可以查看譯碼器在FPGA上的資源使用結果,如表2所示。

wdz1-b2.gif

    通過綜合資源結果可以對譯碼器的吞吐率進行計算,公式如下:

    wdz1-gs9.gif

式中N為有效碼長,fmax為最大時鐘頻率,td為譯碼延遲的時鐘周期數(shù)。吞吐率計算結果如表3所示。

wdz1-b3.gif

4 結論

    如今極化碼正越來越受到研究者們的重視,而國內(nèi)在極化碼譯碼算法研究方面有待深入,尤其是在硬件平臺中實現(xiàn)的較少?;诖吮疚闹饕槍O化碼的SCL譯碼算法進行了研究與優(yōu)化,并在FPGA上設計了譯碼器,最后在Xilinx的VC707開發(fā)板上進行譯碼器的實現(xiàn)。該譯碼器的設計降低了譯碼復雜度以及FPGA上的資源消耗,在碼長為512時譯碼最高頻率為143.988 MHz,吞吐率為28.79 Mb/s,有較強的工程實用性。

參考文獻

[1] ARIKAN E.Channel polarization:a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J].IEEE Transactions on Information Theory,2009,55(7):3051-3073.

[2] SASOGLU E,TELATAR I E,ARIKAN E.Polarization for arbitrary discrete memoryless channels[C].Information Theory Workshop,2009 ITW.IEEE,2009:144-148.

[3] ZHANG T,PARHI K K.A 54 Mbps (3,6)-regular FPGA LDPC decoder[C].Signal Processing Systems.IEEE,2002:127-132.

[4] 李廷墅.極化碼譯碼算法的研究和分析[D].廣州:華南理工大學,2013.

[5] LI B,SHEN H,TSE D.An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check[J].IEEE Communications Letters,2012,16(12):2044-2047.

[6] 魏一鳴.極化碼性能研究及其SCL譯碼算法的FPGA實現(xiàn)[D].南京:南京航空航天大學,2017.

[7] BALATSOUKAS-STIMMING A,RAYMOND A J,GROSS W J,et al.Hardware architecture for list successive cancellation decoding of polar codes[J].IEEE Transactions on Circuits & Systems II Express Briefs,2014,61(8):609-613.

[8] 江濤,王濤,屈代明,等.極化碼與奇偶校驗碼的級聯(lián)編碼:面向5G及未來移動通信的編碼方案[J].數(shù)據(jù)采集與處理,2017,32(3):463-468.



作者信息:

廖海鵬,卿粼波,滕奇志,何小海,鄧媛媛

(四川大學 電子信息學院,四川 成都610065)

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