一種低硬件復(fù)雜度極化碼譯碼器的FPGA實現(xiàn)

丁響

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

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

出于知識產(chǎn)權(quán)的原因，越來越多的項目要求使用極化碼編譯碼方案。當(dāng)前，極化碼的研究主要集中在如何提高譯碼性能、降低計算復(fù)雜度、減少譯碼延遲、節(jié)省硬件資源等問題上，使其能應(yīng)用于實際系統(tǒng)。

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

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

圖1：譯碼器整體結(jié)構(gòu)

圖2：LLR計算單元

圖3：部分和更新矩陣

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

1 極化碼編譯碼原理

1.1 極化碼編碼原理

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

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

1.2 極化碼SC譯碼算法

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

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

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

1.3 半平行SC算法

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

圖4：硬件資源

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

2 改進(jìn)的SC譯碼器硬件結(jié)構(gòu)設(shè)計

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

2.1 LLR計算單元

為了便于硬件實現(xiàn)，本文將f函數(shù)和g函數(shù)兩者融合為一個節(jié)點，亦即一個計算單元PE，通過復(fù)用器可以實現(xiàn)二者的功能轉(zhuǎn)換。f函數(shù)的進(jìn)一步簡化為：

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

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

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

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

2.2 LLR存儲

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

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

2.3 部分和的存儲和更新優(yōu)化

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

圖5：算法仿真結(jié)果（N=1024）

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

2.4 控制模塊

譯碼器控制單元是譯碼器正常工作的關(guān)鍵，用于控制和協(xié)調(diào)各階段的譯碼過程。這部分主要包括LLR輸入數(shù)據(jù)的寫入和讀取，譯碼進(jìn)程計數(shù)器，硬判決比特的RAM的讀寫地址和控制信號，凍結(jié)比特存儲單元ROM的讀地址和控制信號。

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

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

ROM塊用于存儲凍結(jié)比特的信息，提供信道信息給譯碼器進(jìn)行譯碼，ROM的地址索引與當(dāng)前比特的序列號一一對應(yīng)。

3 仿真結(jié)果與性能分析

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

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

根據(jù)吞吐率計算公式：

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

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

4 結(jié)語

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