《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > 基于FPGA的SCL譯碼算法優(yōu)化與設(shè)計(jì)
基于FPGA的SCL譯碼算法優(yōu)化與設(shè)計(jì)
2018年電子技術(shù)應(yīng)用第12期
廖海鵬，卿粼波,，滕奇志,，何小海,，鄧媛媛
四川大學(xué) 電子信息學(xué)院,，四川 成都610065
摘要： 由于極化碼被指出在二進(jìn)制離散無記憶信道中具有實(shí)現(xiàn)其極限容量的理論性能,，近年來極化碼在通信領(lǐng)域的貢獻(xiàn)日漸凸顯,。極化碼的譯碼系統(tǒng)可采用軟件或者硬件方式實(shí)現(xiàn),，其中使用軟件方式時(shí)譯碼效率受限于CPU的串行處理模式,，因此在具有并行工作模式的FPGA上進(jìn)行極化碼的譯碼實(shí)現(xiàn)對(duì)于通信系統(tǒng)來說具有非常大的意義。首先介紹了極化碼的SCL譯碼算法,；然后針對(duì)該算法進(jìn)行優(yōu)化從而提高譯碼效率,，以及針對(duì)該算法在FPGA上的實(shí)現(xiàn)進(jìn)行了定點(diǎn)量化的改進(jìn)；最后對(duì)譯碼器進(jìn)行硬件仿真,，以及在FPGA上進(jìn)行了實(shí)現(xiàn)與性能分析,。實(shí)驗(yàn)結(jié)果表明該譯碼器在碼長(zhǎng)為512時(shí)譯碼最高頻率為143.988 MHz，吞吐率為28.79 Mb/s,。
中圖分類號(hào)： TN911.2
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.181295
中文引用格式： 廖海鵬,，卿粼波，滕奇志,，等. 基于FPGA的SCL譯碼算法優(yōu)化與設(shè)計(jì)[J].電子技術(shù)應(yīng)用,，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提出了信道極化的概念并對(duì)信道極化現(xiàn)象進(jìn)行了詳細(xì)的描述[1]。極化碼的主要過程是在編碼系統(tǒng)中通過對(duì)信道進(jìn)行結(jié)合與拆分,，然后在其中選擇好的部分信道來進(jìn)行有效數(shù)據(jù)的傳輸,。極化碼被嚴(yán)格證明有以下兩個(gè)特性：一是基于信道極化現(xiàn)象存在,；二是在碼長(zhǎng)為無限長(zhǎng)時(shí)，其信道容量可達(dá)香農(nóng)極限,。相比于經(jīng)典的Turbo碼與LDPC碼,，極化碼具有更低的誤碼率和復(fù)雜度以及更高的吞吐率[2-3]。

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

1 極化碼的SCL譯碼算法

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

wdz1-gs1-2.gif

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

wdz1-t1.gif

wdz1-gs3.gif

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

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

wdz1-t2.gif

2 SCL譯碼的優(yōu)化與設(shè)計(jì)

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

2.1 SCL譯碼算法系統(tǒng)設(shè)計(jì)

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

wdz1-t3.gif

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

    SCL譯碼過程實(shí)質(zhì)是L個(gè)SC譯碼算法同時(shí)進(jìn)行，圖4所示為碼長(zhǎng)為8時(shí)的SC譯碼算法遞歸流程圖,，圖中傳遞的信息wdz1-2.2-x1.gif均為L(zhǎng)LR,，其中S代表計(jì)算層數(shù)，i代表相應(yīng)碼字標(biāo)號(hào),。

wdz1-t4.gif

    在SC譯碼算法中,，LLR的計(jì)算公式如下：

wdz1-gs4-5.gif

2.3 FPGA中實(shí)現(xiàn)算法的改進(jìn)

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

wdz1-gs6-8.gif

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

wdz1-b1.gif

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

wdz1-t5.gif

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

3 譯碼硬件平臺(tái)與譯碼測(cè)試結(jié)果

3.1 硬件平臺(tái)選擇

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

wdz1-t6.gif

3.2 譯碼的仿真與測(cè)試

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

wdz1-t7.gif

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

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

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

wdz1-t8.gif

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

wdz1-t9.gif

wdz1-t10.gif

3.3 譯碼性能分析

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

wdz1-b2.gif

    通過綜合資源結(jié)果可以對(duì)譯碼器的吞吐率進(jìn)行計(jì)算,，公式如下：

    wdz1-gs9.gif

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

wdz1-b3.gif

4 結(jié)論

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

參考文獻(xiàn)

[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].廣州：華南理工大學(xué),，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實(shí)現(xiàn)[D].南京：南京航空航天大學(xué)，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] 江濤，王濤,，屈代明,，等.極化碼與奇偶校驗(yàn)碼的級(jí)聯(lián)編碼：面向5G及未來移動(dòng)通信的編碼方案[J].數(shù)據(jù)采集與處理，2017,，32(3)：463-468.



作者信息:

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

（四川大學(xué) 電子信息學(xué)院，四川 成都610065）

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