基于FPGA的極化碼的SC譯碼算法結構的改進方法 - 全文

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

0 引言

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

目前，極化碼的譯碼實現方式主要有軟件和硬件兩種方式，軟件的實現方式因CPU串行工作模式限制了譯碼速度的提升，而FPGA因其具有快速并行計算的能力能彌補這一缺陷。此外，極化碼的遞歸結構能夠實現資源共享并簡化計算過程，這一特點表明極化碼易于FPGA實現[5-6]。

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

基于極化碼、FPGA、SC譯碼算法3方面的優點，本文的重點工作是采用極化碼、運用SC譯碼算法設計一種新型的譯碼器并在Xilinx XC5VFX70T上實現該譯碼器。

1 極化碼的SC譯碼算法

1.1 SC譯碼算法

SC譯碼算法的核心就是連續地估計每個比特的似然比值，Arikan表示這些似然比值[9]可以通過數據流圖采用遞歸的方式被有效地執行，這個數據流圖類似于快速傅里葉變換結構，一般是通過蝶形結構的數據流圖來計算似然比值，N=8的蝶形SC譯碼結構圖如圖1所示，y0到y7是信道的輸出值，通過如下結構可得到譯出碼字

基于FPGA的極化碼的SC譯碼算法結構的改進方法

2 極化碼譯碼的算法改進

2.1 SC譯碼算法結構的改進

由圖1可知由于數據之間的較強依賴性使得譯碼的效率不高，例如圖1中l2階段的所有節點，當輸入數據y0到y7準備完畢時允許節點執行相應的操作，而事實上在第一個譯碼時鐘周期內只有前4個節點執行了相應的操作。為了比較譯碼效率，這里定義α表示使用率，表達式如式(4)所示：

基于FPGA的極化碼的SC譯碼算法結構的改進方法

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

基于FPGA的極化碼的SC譯碼算法結構的改進方法

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

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

2.2 SC譯碼算法在FPGA中實現的改進

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

基于FPGA的極化碼的SC譯碼算法結構的改進方法

由于信道的輸出和運算過程中的值都是浮點數，這不利于在FPGA中實現，所以做了定點量化的改進，用(C，L，F)來表示量化結果，其中C代表信道輸出的量化比特數，L代表運算過程中對數似然比的量化比特數，F代表信道輸出和似然比值量化的小數位數。量化的位數不易過長，因為會消耗很多資源，也不易過短，因為會有很大的誤差。本文做了包括(3，4，0)、(3，4，1)、(4，5，0)、(4，5，1)、(5，6，0)、(5，6，1)、(6，7，0)、(6，7，1)這些帶小數位和不帶小數位的多種不同位數的量化，通過實驗結果的對比，選出了兩種效果較好的量化方式分別是(4，5，0)和(5，6，1)，如圖4所示為量化前后的BER曲線圖。

基于FPGA的極化碼的SC譯碼算法結構的改進方法

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

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

3 基于FPGA的極化碼譯碼硬件平臺與測試結果

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

3.1 基于MATLAB的譯碼仿真結果

如圖5所示為蝶形結構、線性結構和算法改進之后的SNR-BER曲線圖。

基于FPGA的極化碼的SC譯碼算法結構的改進方法

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

3.2 基于硬件平臺的譯碼測試結果

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

基于FPGA的極化碼的SC譯碼算法結構的改進方法

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

基于FPGA的極化碼的SC譯碼算法結構的改進方法