文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.181295
中文引用格式： 廖海鵬，卿粼波，滕奇志，等. 基于FPGA的SCL譯碼算法優化與設計[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.
0 引言
2008年ARIKAN E提出了信道極化的概念并對信道極化現象進行了詳細的描述[1]。極化碼的主要過程是在編碼系統中通過對信道進行結合與拆分，然后在其中選擇好的部分信道來進行有效數據的傳輸。極化碼被嚴格證明有以下兩個特性：一是基于信道極化現象存在；二是在碼長為無限長時，其信道容量可達香農極限。相比于經典的Turbo碼與LDPC碼，極化碼具有更低的誤碼率和復雜度以及更高的吞吐率[2-3]。
極化碼的譯碼算法研究近年來發展迅速，其中成為研究熱點的連續刪除（Successive Cancellation，SC）譯碼算法的基本思想是通過對信息位的比特似然概率值的判斷來進行譯碼。但由于在譯碼時前一個譯碼值會對之后的譯碼值造成影響，因此導致譯碼性能較差[4]。在此基礎上改進的序列連續刪除（Successive Cancellation List，SCL）算法能在計算復雜度與空間復雜度之間實現更好的平衡[5]，相比于在軟件上實現該算法，在FPGA上進行SCL譯碼可以使譯碼速度進一步加快[6]。目前極化碼各方面都已經取得了碩果，但是在FPGA上的譯碼實現仍然存在著譯碼效率和吞吐率不夠高等問題[6]。因此本文針對極化碼的SCL譯碼算法進行了研究和優化，減少資源消耗同時提高譯碼效率；針對FPGA上的譯碼器設計進行了定點量化的改進；最后在Xilinx的VC707開發板上進行了譯碼器的實現與性能分析。實驗結果表明譯碼器在碼長為512時譯碼效率為143.988 MHz，吞吐率達到了28.79 Mb/s，具有較強的工程使用價值。
1 極化碼的SCL譯碼算法
SCL譯碼算法實質是對SC譯碼算法的推廣，SC譯碼算法的基本思想是通過對每個傳輸碼字的LLR(對數似然比值)進行判斷譯出碼字，LLR的定義如式(1)所示。
圖1所示為SC譯碼路徑示意圖，由示意圖和LLR計算公式可以看出SC譯碼在譯碼過程中前一個譯碼值與之后的譯碼值相互關聯，這將對其譯碼算法的性能造成影響。
其中函數δ(x)=(1-sgn(δ))/2，符號函數sgn(x)表示在x>0時值為1，x<0時值為-1，x=0時值為0。l代表相應路徑且初始值
如圖2所示的SCL譯碼過程中，傳輸的碼字為1010，其中前兩位為固定比特，后兩位為信息比特。傳輸碼字從根節點出發向下擴展，可以得到相應的PM值，一直擴展到4條路徑，此時取出PM值較小的兩條路徑繼續擴展，其余路徑刪除，因此最終只有4條路徑，其中最后算出的PM值最小的相應路徑即為譯碼結果。圖2中曲線代表此次PM值最小路徑為1010，譯碼結果正確。
2 SCL譯碼的優化與設計
SCL譯碼算法的核心依然是SC譯碼算法，但其性能優于SC譯碼算法。在FPGA上進行SCL譯碼算法的實現會遇到如何提高譯碼效率和吞吐率以及如何合理利用FPGA片上資源等挑戰。針對SCL譯碼算法的優化可以在基于其具有的遞歸結構下對譯碼計算過程進行簡化，針對FPGA上的譯碼器設計可在運算過程中對浮點數進行量化，更有利于硬件實現。
2.1 SCL譯碼算法系統設計
圖3所示為本文所設計的SCL譯碼系統圖，針對在SCL譯碼的過程中有可能出現最小PM值路徑譯碼不是正確譯碼的情況，可以通過采用文獻[8]中的增加循環冗余校驗（Cyclic Redundancy Check，CRC）輔助的方法來進行解決。在編碼系統中先對源碼進行校驗碼的添加，然后進行極化碼的編碼生成相應的碼字進行傳輸。解碼系統在FPGA上使用設計的譯碼器對傳輸過來的碼字進行極化碼譯碼以及校驗碼校驗，在譯碼最后階段的路徑選擇時從最小PM值逐條校驗，一旦出現校驗通過的路徑即為譯碼結果。
2.2 SCL譯碼算法優化
SCL譯碼過程實質是L個SC譯碼算法同時進行，圖4所示為碼長為8時的SC譯碼算法遞歸流程圖，圖中傳遞的信息
均為LLR，其中S代表計算層數，i代表相應碼字標號。
在SC譯碼算法中，LLR的計算公式如下：
2.3 FPGA中實現算法的改進
在圖4所示的SC譯碼算法流程圖中實線部分代表執行的f函數，虛線部分代表執行的g函數。分別定義如下：
在SCL譯碼過程中的LLR計算值均為浮點數，直接在FPGA中計算會使得譯碼復雜度較高，因此將浮點數進行定點量化轉變成定點數，定點量化的結果通過（O，R，D）來表示，定義如表1所示。
對f函數進行改進之后，譯碼過程中的計算不再涉及乘除法，因此信道輸出和LLR的小數位數可以一致。由于采用定點量化用量化值代替了原始值，必定會對譯碼結果造成一定影響，因此選擇合適的量化比特數和小數位數尤為重要。通過對信道輸出值以及運算過程中的對數似然比值進行詳細的分析以及對比實驗，選出了三種如下較好的量化方式。圖5所示為量化前后的BER曲線圖。
如圖5所示的三種量化方式相比，(4，4，0)由于LLR量化的比特數過小，導致效果不是很理想。(4，5，0)和(5，6，1)的量化選擇基本沒有降低SCL的譯碼性能，而(4，5，0)這種沒有小數位的量化選擇更有利于在FPGA上進行計算，因此譯碼器的設計選用(4，5，0)的量化方式。
3 譯碼硬件平臺與譯碼測試結果
3.1 硬件平臺選擇
本文選擇在Xilinx的VC707開發板上對譯碼器進行實現。該開發板的主芯片為XC7VX485T，包含有485 760個邏輯單元、2 800個DSP Slice、37 080 KB內存以及700個I/O引腳等資源。其最高運行頻率可以達到741 MHz，可以用來實現極化碼的譯碼。圖6為該評估板實物圖。
3.2 譯碼的仿真與測試
為了對SCL和SC算法進行對比以及選擇一個合適的路徑刪減值L，在譯碼器編寫前對各L值下的SCL算法進行了MATLAB仿真，仿真結果如圖7所示。
由圖7可知當L=1和L=2時誤比特率差別較大，再繼續加大L值時雖然可以使誤比特率進一步降低，但是差別已經沒有那么明顯，為了在FPGA上能夠更容易實現SCL算法，選擇L=2來進行路徑刪減實現算法。
接著對譯碼器的正確性進行驗證，先通過ModelSim仿真軟件對譯碼器進行硬件仿真。然后使用ISE軟件帶有的Chipscope在線邏輯分析儀去抓取在FPGA上的譯碼結果，通過硬件仿真結果與FPGA上的譯碼結果對比來驗證譯碼的正確性。
如圖8所示上半部分為在ModelSim上碼長為64時的仿真結果，data_u_out和data_uhat_out分別為輸入源碼字和譯碼仿真結果。下半部分為使用Chipscope抓取的FPGA中運行結果波形圖，data_u和data_uhat分別為輸入源碼字和實際譯碼結果。輸入源碼中有一半碼字為固定比特，因此有效碼字只有32位。由圖8可以看出源碼字和仿真結果以及FPGA譯碼結果均為69ab4d68，因此本次譯碼結果正確。
圖9和圖10所示分別為碼長為128和512時的仿真結果和譯碼結果波形圖。在抓取512碼長的波形時，由于碼長太長，因此在Chipscope中分成了四段進行顯示，由于Chipscope與ModelSim顯示順序不同，因此用相應數字表示了相應的結果順序，可以看出譯碼結果均正確。
3.3 譯碼性能分析
下面對算法的性能以及工程占用資源等進行綜合分析，在ISE軟件上的綜合報告中可以查看譯碼器在FPGA上的資源使用結果，如表2所示。
通過綜合資源結果可以對譯碼器的吞吐率進行計算，公式如下：
式中N為有效碼長，fmax為最大時鐘頻率，td為譯碼延遲的時鐘周期數。吞吐率計算結果如表3所示。
4 結論
如今極化碼正越來越受到研究者們的重視，而國內在極化碼譯碼算法研究方面有待深入，尤其是在硬件平臺中實現的較少。基于此本文主要針對極化碼的SCL譯碼算法進行了研究與優化，并在FPGA上設計了譯碼器，最后在Xilinx的VC707開發板上進行譯碼器的實現。該譯碼器的設計降低了譯碼復雜度以及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實現[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] 江濤，王濤，屈代明，等.極化碼與奇偶校驗碼的級聯編碼：面向5G及未來移動通信的編碼方案[J].數據采集與處理，2017，32(3)：463-468.
作者信息:
廖海鵬，卿粼波，滕奇志，何小海，鄧媛媛
（四川大學 電子信息學院，四川 成都610065）