一種低硬件復雜度極化碼譯碼器的FPGA實現

丁響

（西南電子技術研究所 四川省成都市 610036）

信道編碼用于對抗信息傳輸過程中的干擾，將因干擾導致的錯誤信息進行糾正，提高通信的可靠性。經過幾十年的發展演變，Turbo碼和LDPC從眾多信道編碼方案中展現出優勢，是當前應用最多的兩種編碼方案，其性能優越，但是復雜度較高，且不能完全達到香濃極限。由E.Arikan[1]提出的極化碼(Polar Code)作為第一種理論上可以使信道容量達到香農極限的編譯碼方法，成為編譯碼領域的的研究熱點。華為公司對極化碼做了大量研究，取得了較多專利成果，并成功將極化碼推舉為5G控制信道的編碼方案，使得我國在通信領域走上了世界舞臺。

出于知識產權的原因，越來越多的項目要求使用極化碼編譯碼方案。當前，極化碼的研究主要集中在如何提高譯碼性能、降低計算復雜度、減少譯碼延遲、節省硬件資源等問題上，使其能應用于實際系統。

在算法研究方面，E.Arikan在提出極化碼構造理論的同時，給出了一種極化碼SC譯碼算法，該算法與置信度傳播（Brief Propagation，BP）算 法 和最大似 然 比（MaximumLikelyhood，ML）算法相比，譯碼復雜度最低。Vardy[2]等學者提出的連續刪除列表（SCL）算法和Niu.K[3]等學者提出的連續刪除堆棧（SCS）算法是基于SC 算法的改進，都是通過增加SC算法中的候選路徑來提高譯碼性能，降低誤碼率，但同時也增加了譯碼的復雜度。

在硬件實現方面，最早Leroux 等人提出了幾種SC譯碼器的硬件實現結構[4-5]，其中經典結構有樹形以及線性結構等。后來，Leroux等人對其進一步優化，提出了SC譯碼的半平行譯碼結構[6]，該結構通過犧牲較小的吞吐率來大幅度降低系統復雜度，但內存復雜度沒有改善。隨后，諸多學者先后提出了SCL[7-8]、CA-SCL[9]等算法的硬件實現方法，這些算法的系統復雜度相對SC算法也顯著提高。

圖1：譯碼器整體結構

圖2：LLR計算單元

圖3：部分和更新矩陣

面向某項目物聯網超低功耗的實際應用，本文設計了（1024，512）的polar碼，基于譯碼性能和硬件實現復雜度的綜合考慮，選取SC算法，采用半平行的硬件實現結構，研究其性能和復雜度的改善。通過對半平行結構的SC譯碼器的研究，給出了完整硬件架構，詳細的分析和介紹硬件設計中各子模塊，優化了論文中[6]部分和更新模塊，在僅增加極小的譯碼時延的情況下大大降低了硬件資源。

1 極化碼編譯碼原理

1.1 極化碼編碼原理

極化碼為一種線性分組碼，通過編碼使碼字產生極化現象，即部分信道（碼字的位）的信道容量趨于0，即純噪聲信道，另外一些則趨近于1，即完美信道。因此，編碼時將待編碼的比特放置在信道容量高的位上，冗余位放在信道容量低的位上，一般將冗余位設置為0。

極化碼碼長為N，對于信息位長為K的編碼，首先需要知道N個信道的信道容量大小排序。將K個信息比特放在K個信道容量最大的信道位置上，其余為0，稱為凍結比特，排序后的序列記為根據線性分組碼的編碼方式進行編碼初始信息為生成的碼字。根據信道組合方法可以迭代得到生成矩陣其中F為核矩陣為F的n階Kronecker積，n=log2(N)。BN為比特翻轉操作，其目的是將輸入序列的位置進行置換，如xi的下標i的二進制表示為〈i〉2= (in-1in-2…i0)，其中ij∈{0,1}，經過比特翻轉操作后的二進制表示為〈i〉2= (i0i1…in-1)。

1.2 極化碼SC譯碼算法

SC譯碼是通過對每個傳輸碼字的LLR（對數似然比）進行計算，進而譯出碼字。定義第i個比特的對數似然比為其中為條件轉移概率為接收序列為前i-1個已知信息的估計值，其判決準則為：

其中λ=n,n-1,…,1，f和g分別為：

為了便于硬件實現，使用最小和算法計算f(α,β)≈f(α,β)?sign(α)sign(β)min(|α|,|β|)，其可以直接由比較器和加法器實現，避免了使用乘法器和除法器等比較復雜的電路。

1.3 半平行SC算法

線性SC算法在l=n-λ 層被激活時，有2l個計算單元（PE）在同時計算，且只有其中一種函數（f或g）被激活，在一個碼字向量譯碼過程中共被激活2λ次。所以，總的譯碼時長為：

圖4：硬件資源

當SC譯碼算法采用半平行結構時[6]，提高了PE使用率，大幅減少了PE的數量，僅增加了少量時延，是一種降低SC譯碼器復雜度的有效方法。不失一般性，設置PE結構數量為P=2p，當2l≤P時，對時延沒有影響，當2l>P時需要個時鐘周期完成l層的更新。故半平行譯碼結構的時長為：

2 改進的SC譯碼器硬件結構設計

本文根據項目需求，設計碼長為1024，碼率為1/2的極化碼。經仿真論證，對于碼長大于1024的碼塊，當PE的并行度為64時，可達到90%以上的吞吐率，故選取P=64。定點化譯碼器中的數據，并對譯碼器數據溢出采用飽和處理，保證譯碼器的位寬不變，極大地降低硬件復雜度，同時譯碼器性能幾乎無損耗。譯碼器的整體硬件結構主要包括以下模塊: 信道LLR緩存、中間計算結果LLR緩存 、LLR計算單元PE、信息比特估算單元、部分和更新以及存儲單元，如圖1 所示。

2.1 LLR計算單元

為了便于硬件實現，本文將f函數和g函數兩者融合為一個節點，亦即一個計算單元PE，通過復用器可以實現二者的功能轉換。f函數的進一步簡化為：

其中|X|代表變量X的幅值，ψ(X)為他的符號，在verilog語言中，

g函數符號項的輸出將由λa，λb的幅值大小以及的大小決定，計算公式如下：

PE最終輸出結果由B(l,i)決定，即

B(l,i) 由計算層數l和碼字序列的標號i決定，為B(l,i)=il。

2.2 LLR存儲

LLR存儲分為兩個部分：一是接收信道信息的LLR存儲，另一個則為PE計算結果LLR存儲。為了提高吞吐率，信道接收LLR的存儲采用乒乓操作。定點化后LLR的數據位寬為Q-bit。在l層，函數f和g的計算交替進行，且計算的次數相等，都是2n-l?2次。采用時分多路技術，l層LLR的存儲個數為N?2n-l，故LLR的存儲空間只需要(3N-1)Q比特，其中2NQ比特用來存儲接收信道LLR，(N-1)Q比特則用來存儲由PE計算得到的內部LLR。由于碼長僅為1024，為了避免添加多余的延遲，使得在一個時鐘周期內可以同時讀取PE的輸入數據和存儲PE計算的輸出結果，本文采取寄存器的存儲方式，使得控制簡單，并且有效地利用了硬件資源。在l≤p層時，存儲寄存器的位寬為比特，深度為1；在l>p層時，存儲寄存器的位寬為比特，深度為2n-1-p。

以N=8，P=2的半平行結構設計為例。首先從l=3層開始讀數，分兩個時鐘周期完成，第一個時鐘周期讀取的4個LLR數據并計算出l=2層的2個LLR數據，并存儲到的低PQ位中，第二個時鐘周期讀取的4個LLR數據并計算出l=2層的2個LLR數據，并存儲到的高PQ位中；接著讀取l=2層的數據，只需一個時鐘周期即可計算出l=1層的內部LLR，并將其存儲到的PQ位中；第四個時鐘周期讀取l=1層的LLR，且只需要一個時鐘周期即可計算出l=0層的內部LLR，此時PE的并行度Puse少于P，僅需存儲Puse個PE的計算結果，即存儲到的Q位中。

2.3 部分和的存儲和更新優化

在整個譯碼過程中，當PE進行g函數的操作時，應指定具體部分和項，即一旦被估計出來，部分和項就需同步更新。由論文[2]可知，部分和存儲為Cλ[β][i mod 2]，其中β為分支，0≤β<2n-λ，λ為層數，0≤λ

圖5：算法仿真結果（N=1024）

論文[6]中部分和更新較為復雜，本文對部分和更新方法進行了優化，具體實現如下：部分和更新是在信息比特估算完成的時候同步進行，即在層數l為0時進行更新，而每層的更新策略如下：在l層時，當[in-l-1,in-l-2),…,i0]所有位均為1， l層部分和的更新公式為：

2.4 控制模塊

譯碼器控制單元是譯碼器正常工作的關鍵，用于控制和協調各階段的譯碼過程。這部分主要包括LLR輸入數據的寫入和讀取，譯碼進程計數器，硬判決比特的RAM的讀寫地址和控制信號，凍結比特存儲單元ROM的讀地址和控制信號。

信道緩存需要將累計接收的2P個數據依次寫入reg寄存器中，直至一幀數據接收完畢，才開始譯碼。

譯碼進程計數器主要包括輸出當前譯碼比特的序列號i（i∈{0,1,…,N-1}），當前計算的層數l，以及當前層內部計算所需的時鐘數?，i的計算比較簡單，即當層數l=0時，i加1。層數l的計數依賴于當前譯碼比特的序列號i和當前層數內部計算的時鐘數?。譯碼開始時，即i=0時，層數l=n-1，當時，l=l-1，當層數l減少到0時，將l更新為layerini，layerini是從低位查找二進制表示的i中第一個為1的比特位置索引號，例如以N=1024為例，i=0,1,2,3,4,5,6,7,8,9,……，則當前譯碼比特i對應的層數l的起始層數為layerini=9,0,1,0,2,0,1,0,3,0,……。由于l層需要2l次計算，則需要個時鐘，因此?的計數從0到時復位。

ROM塊用于存儲凍結比特的信息，提供信道信息給譯碼器進行譯碼，ROM的地址索引與當前比特的序列號一一對應。

3 仿真結果與性能分析

本文實現譯碼器的硬件平臺為Xilinx公司的V7系列型號xc7vx485tあg1157-2的FPGA芯片，使用2017.4版本的Vivado進行綜合，得到的資源占用情況如圖4所示，資源使用率僅為4%左右。

仿真結果表明，在碼長1024，工作頻率100M，譯碼器的時延為0.02081ms，即譯出一個碼塊需要2081個時鐘周期。

根據吞吐率計算公式：

得到譯碼器吞吐率為49.2Mbps，與全平行結構相比，吞吐率降低了2%，而硬件資源節約了大概67%。

硬件譯碼算法的另一個評判標準為誤碼率，本文中8bit量化與未量化的誤碼率BER（bit error rate）和誤幀率FER（frame error rate）如圖5所示，統計幀數為106。從圖中可以看出，量化之后BER、FER與理論未量化之間相差不超過0.05dB，表明了該譯碼器算法硬件實現可以獲得與浮點計算同等的優異性能。

4 結語

對碼長為1024，碼率為1?2的極化碼，選取硬件復雜度最低的SC 譯碼算法，采用半平行的硬件架構，詳細論述了LLR計算單元、LLR存儲、控制模塊的實現，并新設計了一種易于實現的部分和更新模塊。相較于平行結構，該設計減少了67%的系統硬件資源占用，顯著降低了FPGA實現的復雜度，同時吞吐量達到了49.2Mbps，僅降低2%，體現出較高的工程應用價值。