一種高性能極化碼SC譯碼器設計

王曉蕾，戴吳駿，杜高明，李楨旻，張多利

(合肥工業(yè)大學 微電子設計研究所，安徽 合肥 230601)

信道極化[1]的概念及極化碼[2](Polar Code)分別于2008年和2009年被提出。極化碼是目前唯一被證明可達信道容量的編碼[3]方式，吸引了廣泛的關注。2016年，極化碼成為了5G移動增強寬帶場景下控制信道編碼方案。部分學者將極化碼引入神經(jīng)網(wǎng)絡[4-6]加速器，促進了5G的發(fā)展。5G網(wǎng)絡要求信息傳輸具有低延時[7]和大容量的特點，同時使用的芯片資源越少越好。因此設計低延時、高吞吐率[8]和高資源效率[9]的極化碼譯碼器已成為趨勢。

文獻[2]提出的串行抵消(Successive Cancellation，SC)譯碼算法采用串行譯碼方式造成高延時。根據(jù)該算法設計的SC譯碼器采用蝶形譯碼架構(gòu)，造成了資源浪費。簡化串行抵消[10](Simplify SC，SSC)譯碼算法對已知是凍結(jié)比特的結(jié)點不再譯碼，直接判定譯碼結(jié)果為0。預計算簡化串行抵消[11](Precomputation SSC)譯碼算法將SSC譯碼算法的周期進一步減少，通過減少譯碼周期，降低了延時，提高了吞吐率。相比于傳統(tǒng)蝶形SC譯碼器，研究人員根據(jù)降階串行抵消(2b-SC)譯碼算法設計的譯碼器[12]在延時、吞吐率以及資源消耗方面均有所改進。流水線架構(gòu)的SC譯碼器[13-14]通過復用對數(shù)似然比計算單元(Process Element，PE)減少了資源浪費。

上述算法都是從單個角度解決問題，沒有充分壓縮譯碼周期和發(fā)掘電路性能，因此無法滿足5G通訊的要求。本文從算法和電路兩個層面減少譯碼周期，實現(xiàn)低延時和高吞吐率，并從PE單元復用角度設計電路，實現(xiàn)高資源效率。本文的研究主要集中在以下3個方面：

(1)通過剪枝凍結(jié)比特結(jié)點的方式化簡SC譯碼二叉樹，減少譯碼凍結(jié)比特消耗的周期。設計PE單元存儲模塊，存儲對數(shù)似然比(Log Likelihood Ratio，LLR)，后續(xù)階段可以直接調(diào)用該模塊存儲的計算結(jié)果，減少再次計算LLR需要的譯碼周期。在譯碼最終階段采用2b-SC算法，該算法采用組合電路，因此不消耗譯碼周期，可進一步減少總的譯碼周期；

(2)設計資源復用的硬件電路結(jié)構(gòu)，假設碼長為N，該譯碼器所需要的PE單元為N/2個，將PE單元組合成PE陣列。譯碼到某個階段時，如果子碼的長度為Nv，那么只需激活前Nv/2個PE單元參與計算，提高了資源效率；

(3)本文設計了碼長為1 024，信息位為512的SC譯碼器，采用專用集成電路(Application Specific Integrated Circuit，ASIC)方式實現(xiàn)。在華潤上華(CSMC)180 nm和中芯國際(SMIC)40 nm標準工藝下完成電路測試。結(jié)果表明譯碼周期僅為330，吞吐率達到388.85 Mbit·s-1和343.60 Mbit·s-1，資源效率為2.204 Mbit·s-1·kGE-1(kGE=1 000個與非門)和1.949 Mbit·s-1·kGE-1，譯碼器性能得到了顯著提升。

1 SC與SSC譯碼算法分析

1.1 SC譯碼算法

利用碼長為N，信息位為K的極化碼可以構(gòu)建深度log2N的譯碼二叉樹。如圖1所示，圖中白色葉子結(jié)點表示單個凍結(jié)比特，黑色葉子結(jié)點表示單個信息比特。從葉子結(jié)點向上遞歸，對于任何一個結(jié)點，如果左右孩子結(jié)點都是凍結(jié)比特結(jié)點，則父結(jié)點也是凍結(jié)比特結(jié)點；如果左右孩子結(jié)點都是信息比特結(jié)點，則父結(jié)點也是信息比特結(jié)點，否則就是混合比特結(jié)點，即圖中灰色結(jié)點。定義譯碼二叉樹的葉子結(jié)點深度為0，根結(jié)點的深度為log2N。

圖1 (8，4)譯碼二叉樹Figure 1. (8，4) decoding binary tree

SC算法譯碼過程是一個滿二叉樹深度優(yōu)先遍歷的過程，譯碼所有葉子結(jié)點得到的結(jié)果就是最終的譯碼序列。遍歷二叉樹的串行特點導致譯碼周期消耗多，延時大，吞吐率低。如圖2所示，SC譯碼流程按照圖中虛線箭頭所示路徑進行遍歷，總的譯碼周期為τd=2×(N-1)。

圖2 SC譯碼算法流程Figure 2. The process of SC decoding algorithm

1.2 SSC譯碼算法

文獻[10]提出了SSC譯碼算法。此算法對凍結(jié)比特不進行譯碼，直接判決譯碼比特為0，減少了譯碼凍結(jié)比特消耗的周期，使得總譯碼周期減少。具體譯碼遍歷流程描述為以下步驟：

步驟1確定譯碼二叉樹深度；

步驟2二叉樹進行深度優(yōu)先遍歷，確定譯碼結(jié)點在二叉樹上的深度dv，每層結(jié)點LLR數(shù)目為Nv=2dv，如果孩子結(jié)點是凍結(jié)比特結(jié)點，則直接返回碼長為Nv/2的凍結(jié)比特序列(Nv≥2)，否則繼續(xù)進行深度優(yōu)先遍歷；

步驟3完成最后一個結(jié)點遍歷，譯碼結(jié)束。

圖3 SSC譯碼算法流程 Figure 3. The process of SSC decoding algorithm

為了更加清晰地了解SSC譯碼算法譯碼流程，以圖3譯碼二叉樹進行說明：

步驟1確定譯碼二叉樹深度為3；

步驟2二叉樹進行深度優(yōu)先遍歷，從根結(jié)點到葉子結(jié)點的深度分別為3、2、1、0；對應碼長分別為8、4、2、1；根結(jié)點的左右孩子結(jié)點都是混合比特結(jié)點，所以根據(jù)路徑①遍歷到達左孩子結(jié)點。由于此結(jié)點的左孩子結(jié)點是凍結(jié)比特結(jié)點，所以根據(jù)路徑②遍歷右孩子結(jié)點，以此類推，根據(jù)路徑③～⑨遍歷剩余二叉樹結(jié)點；

步驟3完成最后一個結(jié)點遍歷，譯碼結(jié)束。

2 譯碼算法優(yōu)化

2.1 2b-SC譯碼算法

文獻[12]提出了2b-SC算法。該算法根據(jù)輸入LLR(a)和LLR(b)的不同分成4種情況：

(1)當譯碼比特序列都屬于凍結(jié)比特集時，譯碼結(jié)果都為0；

(2)當譯碼比特序列只有2i-1屬于凍結(jié)比特集時，如果輸入的LLR之和大于等于0，則譯碼結(jié)果都為0，否則2i-1對應的譯碼比特為0，2i對應的譯碼比特為1；

(3)當譯碼比特序列只有2i屬于凍結(jié)比特集時，如果輸入的LLR符號位乘積大于等于0，則譯碼結(jié)果都為0，否則2i-1對應的譯碼比特為1，2i對應的譯碼比特為0；

(4)當譯碼比特序列都不屬于凍結(jié)比特集時，如果輸入的LLR符號位乘積大于等于0，則2i-1對應的譯碼比特為0，否則2i-1對應的譯碼比特為1，2i對應的譯碼比特一直為LLR(a)的符號位。

2b-SC算法Inputs: (LLR(a) && LLR(b) from (n-1)th decoding stage)Description:(get^u2i-1 && ^u2i)Case 1:2i-1 && 2i belong to froze bits set^u2i-1=0, ^u2i=0Case 2:only 2i-1 belong to froze bits set if LLR(a) + LLR(b)≥0^u2i-1=0, ^u2i=0 else^u2i-1=0, ^u2i=1Case 3:only 2i belong to froze bits set if sign(LLR(a))sign(LLR(b))≥0^u2i-1=0, ^u2i=0 else^u2i-1=1, ^u2i=0Case 4: none of them belong to froze bits set if sign(LLR(a))sign(LLR(b))≥0^u2i-1=0, ^u2i=sign(LLR(a)) else^u2i-1=1, ^u2i=sign(LLR(a))Outputs: ^u2i-1,^u2i

如圖4所示，當譯碼二叉樹遍歷深度為1時，該深度結(jié)點存在兩個LLR，采用2b-SC算法可以同時得到兩個譯碼比特。

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

本文對SC譯碼算法進行優(yōu)化，具體的譯碼算法步驟如下：

步驟1確定碼長N、信息位K以及構(gòu)造方法，所需PE數(shù)目為N/2，輸入來自信道的{LLR1，LLR2，…，

LLRN}；

步驟2深度優(yōu)先遍歷譯碼二叉樹，當譯碼深度為log2N～1時，對每層譯碼結(jié)點進行遍歷，確定譯碼結(jié)點在二叉樹上的深度dv。如果深度在log2N與2之間，則對應該結(jié)點的對數(shù)似然比數(shù)目為Nv=2dv，需要激活前N(PE)=(N/2)×2dv個PE單元。如果該譯碼結(jié)點的孩子結(jié)點為凍結(jié)比特結(jié)點，則直接返回碼長為Nv/2的凍結(jié)比特序列，否則繼續(xù)進行深度優(yōu)先遍歷。遍歷到深度為1的結(jié)點時，直接利用2b-SC譯碼算法進行譯碼，得到兩個譯碼比特；

步驟3遍歷完最后一個深度為1的結(jié)點，譯碼結(jié)束。

圖4 優(yōu)化的SC譯碼算法流程Figure 4. The process of optimized SC decoding algorithm

為了更加清晰地了解譯碼過程，以圖4所示的二叉樹進行說明。輸入LLR后，需要4個PE單元，遍歷路徑①時，消耗1個周期，計算得到的LLR輸入存儲陣列，供路徑②和根結(jié)點的右孩子結(jié)點使用。遍歷路徑②也消耗1個周期，然后直接利用2b-SC譯碼算法得到譯碼比特。遍歷根結(jié)點的右孩子結(jié)點不消耗周期。遍歷路徑③時，消耗1個周期，得到的LLR可以供5、6、7、8號譯碼比特使用。因此，總的譯碼周期為3。

3 優(yōu)化的SC譯碼算法硬件實現(xiàn)

3.1 整體架構(gòu)

本文提出的SC優(yōu)化譯碼算法的硬件架構(gòu)如圖5所示，為了方便說明，本文設定N=8。

該硬件電路主要有6個模塊：對數(shù)似然比計算模塊、數(shù)據(jù)存儲模塊、數(shù)據(jù)選擇模塊、部分和模塊、控制器模塊以及P結(jié)點模塊。本文采用對數(shù)似然比模塊對輸入的LLR進行計算，將所得結(jié)果作為下一階段輸入的LLR或者傳遞到P結(jié)點模塊。數(shù)據(jù)存儲模塊用來存儲對數(shù)似然比計算模塊產(chǎn)生的數(shù)據(jù)，該模塊受時序控制，可以保持數(shù)據(jù)存續(xù)多個周期，如果下次需要數(shù)據(jù)，可直接從該模塊取出，無需再次計算。數(shù)據(jù)選擇模塊用來選擇下一階段計算所需要的數(shù)據(jù)。部分和模塊用來計算g函數(shù)的指數(shù)項u_s?？刂破髂K對整個電路的數(shù)據(jù)分配以及周期跳轉(zhuǎn)進行控制。P結(jié)點模塊用來計算最后一階段的LLR，該階段可以同時譯碼兩個比特。

圖5 優(yōu)化的SC譯碼算法硬件架構(gòu)Figure 5. The hardware architecture of optimized SC decoding algorithm

3.2 對數(shù)似然比計算模塊

對數(shù)似然比計算模塊是指圖5中的PE陣列，將PE單元分別標號PE1～PE4。PE單元由兩個函數(shù)組成，分別是f函數(shù)與g函數(shù)，其中a為LLR(a)，b為LLR(b)，us為u_s，取值為0或1。

(1)

g(a，b，us)=(-1)usa+b

(2)

為了方便實現(xiàn)硬件電路，將上述數(shù)學表達式修改為如下3個函數(shù)。

f=sign(a)sign(b)min(|a|，|b|)

(3)

g0=a+b

(4)

g1=b-a

(5)

對于二叉樹某一節(jié)點的左孩子結(jié)點，本文采用f函數(shù)進行計算。對于右孩子結(jié)點，則根據(jù)之前譯碼出的部分比特用g0或者g1函數(shù)計算。將這3個函數(shù)的電路融合在一起構(gòu)成一個對數(shù)似然比計算模塊，即一個PE單元。

圖6 PE單元Figure 6. PE unit

如圖6所示，PE輸入輸出都是2的補碼形式。g0和g1函數(shù)直接利用加法器和減法器進行運算。f函數(shù)先將輸入的LLR(a)和LLR(b)通過補碼轉(zhuǎn)符號量(C2S)轉(zhuǎn)換成絕對值表達形式，再選擇出兩個絕對值中較小的一個，通過符號量轉(zhuǎn)補碼(S2C)轉(zhuǎn)成補碼形式，取補碼數(shù)值部分；然后由兩個輸入LLR的最高位MSB(sign(LLR))通過XOR異或構(gòu)成符號位；最后將符號位與補碼數(shù)值部分拼接起來，得到f函數(shù)的計算結(jié)果。

3.3 數(shù)據(jù)存儲陣列模塊

數(shù)據(jù)存儲模塊是指圖5中的數(shù)據(jù)存儲陣列。該模塊受時鐘信號控制，且模塊的大小與碼長有關。當二叉樹的深度為1～log2(N-1)時，每級深度的單類型存儲容量為2dv，因為每級都要存儲f、g0以及g1的計算結(jié)果，所以該級總的存儲容量為3×2dv。因此對于一個碼長為N的譯碼電路，該電路的存儲容量為3×(N-2)。

圖7 二叉樹與存儲單元對應關系Figure 7. The relationship between decoding binary tree and storage

如圖7所示，圖中深度為0的矩形表示P結(jié)點，無需存儲計算結(jié)果；深度為1時，該級容量為3×2；深度為2時，該級容量為3×4，總的存儲容量為18。

3.4 選擇陣列模塊

數(shù)據(jù)選擇模塊是指圖5中的選擇陣列。它用來選擇下一階段所需要的LLR。如圖4中的路徑①，計算得到的LLR通過數(shù)據(jù)選擇器選擇出路徑②計算所需的LLR。單個數(shù)據(jù)選擇器如圖8所示。

圖8 數(shù)據(jù)選擇器Figure 8. Data selector

數(shù)據(jù)選擇模塊的輸入數(shù)據(jù)為前一級計算得到的LLR，當u_s取0時，數(shù)據(jù)選擇器選擇g0輸出，否則選擇g1輸出。將選擇出的數(shù)據(jù)輸入下一級數(shù)據(jù)選擇器，當f_s為0時，選擇f輸出，否則輸出上一級數(shù)據(jù)選擇器選擇的值。f_s為0表示選擇二叉樹的左孩子結(jié)點譯碼，否則對右孩子結(jié)點譯碼。數(shù)據(jù)選擇陣列需要N/2個數(shù)據(jù)器，數(shù)據(jù)選擇模塊激活的數(shù)量隨著深度的降低可成倍數(shù)降低。

3.5 部分和模塊

部分和模塊用來計算g函數(shù)的指數(shù)項u_s，決定下一階段計算的數(shù)據(jù)是g0還是g1。為了使該模塊在產(chǎn)生譯碼比特時就能刷新電路，將該模塊設計為組合電路，具體電路結(jié)構(gòu)如圖9所示。

(a) (b)圖9 部分和模塊Figure 9. Partial sum accumulation module

傳統(tǒng)的SC部分和模塊如圖9(a)所示，該模塊每譯碼1 bit就刷新電路，得到新的u_s。由于優(yōu)化的譯碼算法在獲取信道的LLR時已知信道分布，且凍結(jié)比特信道傳輸0，因此部分和電路可以化簡為如圖9(b)所示的形式。經(jīng)過簡化得到的部分和模塊隨著碼長的增加，減少的加法器數(shù)量顯著增加。

3.6 控制器模塊

控制器模塊主要用來控制電路的狀態(tài)轉(zhuǎn)移，也具有數(shù)據(jù)分配等輔助功能。電路的狀態(tài)轉(zhuǎn)移如圖10所示。當Stage_en1激活時，遍歷圖4中的路徑①，同時在圖10中周期上標注了①。當Stage_en2激活時，遍歷圖4中的路徑②，譯碼兩個比特，同時在圖10中周期上標注了②。當Stage_en3激活時，遍歷圖4中的路徑③，同時在譯碼4個比特，在圖10中周期上標注了③。當Stage_en4激活時，輸出譯碼結(jié)果。

圖10 控制器模塊與譯碼關系Figure 10. The relationship between controller and decode

3.7 P結(jié)點模塊

P結(jié)點模塊采用2b-SC譯碼算法，在譯碼的最后一個階段同時譯碼2 bit，加快譯碼速度。如圖11所示，首先根據(jù)fr1、fr2決定使能信號。如果使能信號激活，則再根據(jù)LLR進行判斷，具體關系如表1所示。

圖11 P結(jié)點Figure 11. P node

表1 P結(jié)點譯碼真值表Table 1. P node decoding truth table

4 實驗結(jié)果與分析

本文設計了碼長為1 024，信息位為512的SC譯碼器，所需PE數(shù)目為512，譯碼周期為330。在SMIC40 nm工藝下測試得到電路數(shù)據(jù)，如表2所示，其中時鐘頻率為250.6 MHz，資源效率為2.204 Mbit·s-1·kGE-1，面積為0.18 mm2，電路門數(shù)為176 460，吞吐率為388.85 Mbit·s-1，在電壓為1.21 V的情況下功耗為19.89 mW。

表2 譯碼器在SMIC 40 nm工藝下的綜合結(jié)果Table 2. Comprehensive results of decoder under SMIC 40 nm process

為了保證對比分析的公平性，本文在CSMC 180 nm工藝下測試了電路，實驗對比結(jié)果如表3所示。其中clk是時鐘周期，即1 clk=1/Frequency ns。對比對象全部采用SC譯碼算法，但是采用的硬件結(jié)構(gòu)各不相同。文獻[15]采用了半并行架構(gòu)，雖然PE可以進行復用，提高了資源效率和吞吐率，但是每次譯碼只能譯碼一位數(shù)據(jù)，效率的提升幅度有限。文獻[16]采用了帶有P結(jié)點的樹型架構(gòu)，雖然可以加快譯碼速度，提高譯碼吞吐率，但是由于PE消耗太多，因此不適合提高資源效率。文獻[17]采用了PE位寬擴展的樹型譯碼架構(gòu)，同樣提高了譯碼吞吐率，加快了譯碼速度，但也存在資源效率不高的問題。與文獻[15～17]相比，提出的譯碼器譯碼周期分別減少了78.85%、78.48%和78.48%；吞吐率分別提升了601.22%、130.60%和172.70%；資源效率分別提升了629.96%、285.94%和296.14%。

表3 譯碼器在180 nm工藝下的結(jié)果對比Table 3. Comparative results of decoder in 180 nm process

譯碼器的功耗[18-19]也是一個重要的研究參數(shù)。本文中，3組譯碼器的功耗比較如表4所示，文獻[15]所提的譯碼器在工作電壓為1.5 V時的功耗為67 mW；文獻[16]所提出的譯碼器在工作電壓為1.8 V時的功耗為1 072.9 mW；在CSMC 180 nm工藝下，本文提出的譯碼器在工作電壓為1.61 V時的功耗為200 mW。

表4 譯碼器在180 nm工藝下的功耗對比Table 4. Comparisons of decoder power in 180 nm process

5 結(jié)束語

本文提出了優(yōu)化的高性能SC譯碼算法以及硬件架構(gòu)。首先對譯碼二叉樹進行了簡化，設計了PE單元存儲模塊；然后融合了2b-SC算法，設計了資源復用的對數(shù)似然比計算模塊；最終設計了碼長為1 024，信息位為512的SC譯碼器，并在CSMC 180 nm和SMIC 40 nm標準工藝下完成ASIC實現(xiàn)和電路測試。測試結(jié)果表明，該算法可以顯著降低延時，提升吞吐率與資源效率，從而提升譯碼器的性能，增強譯碼器的實用性。但是，文本所提新模型的電路功耗仍然有改善的空間，低功耗極化碼SC譯碼器也將是未來的重點研究方向之一。