極化碼SCS譯碼器的FPGA實(shí)現(xiàn)

席 藝 仰楓帆 葉 明

（南京航空航天大學(xué)電子信息工程學(xué)院 南京 211106）

1 引言

2007年，Arikan教授發(fā)現(xiàn)了信道極化現(xiàn)象［1］，在文章“Channel Polarization：A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels［2］”中，Arikan 正式提出了極化碼這一概念，并通過(guò)總結(jié)編碼過(guò)程和一系列數(shù)學(xué)計(jì)算給出了極化碼的編碼矩陣，同時(shí)還給出了用于極化碼譯碼的連續(xù)刪除（Successive Cancellation，SC）算法。隨后Vardy等學(xué)者在SC算法的基礎(chǔ)上提出連續(xù)刪除列表（Successive Cancellation List，SCL）算法［3］，將SC算法中單一的候選路徑增加稱列表，進(jìn)一步降低誤碼率。Niu.K，K.Chen提出同屬SC類的新算法連續(xù)刪除堆棧（Successive Cancellation Stack，SCS）譯碼算法［4］，采用了與SCL算法相同的增加SC算法候選路徑的思想，將度量值最大的路徑置于堆棧頂，通過(guò)只拓展頂層路徑的方法，在取得跟SCL算法相似性能的同時(shí)極大地減小了運(yùn)算復(fù)雜度。與此同時(shí)，為了探尋極化碼工程上實(shí)現(xiàn)的可能性，眾多學(xué)者開(kāi)始致力于極化碼硬件實(shí)現(xiàn)并開(kāi)始提出了一些SC譯碼硬件結(jié)構(gòu)［5～9］。隨后，相繼提出了 SCL［10～11］、CA-SCL［12］等算法的硬件結(jié)構(gòu)。本文重點(diǎn)設(shè)計(jì)極化碼SCS算法譯碼器的硬件結(jié)構(gòu)，基于FPGA給出了一套可實(shí)現(xiàn)的硬件實(shí)現(xiàn)方案，最后給出了硬件仿真結(jié)果。

2 極化碼的編譯原理

2.1 極化碼編碼方法

極化碼的編碼［13］是依據(jù)生成矩陣產(chǎn)生的，同大多數(shù)線性分組碼一樣滿足：

極化碼的碼長(zhǎng)一般取N=2n,n≥0，根據(jù)極化碼的遞歸構(gòu)造模型，通常定義其生成矩陣為

2.2 極化碼SCS譯碼算法

極化碼發(fā)展至今已有多種譯碼方法，其中SC類算法是主流譯碼算法。SCS算法性能優(yōu)越，且具有較低的譯碼復(fù)雜度，下面將分SC譯碼算法和SCS譯碼算法兩部分介紹。

2.2.1 SC譯碼算法部分

對(duì)上述規(guī)則進(jìn)行細(xì)化，令對(duì)數(shù)似然比（Log Likelihood-Ratio， LLR） 為，根據(jù)迭代公式推算最終可以回歸到初始值的計(jì)算，在AWGN信道下初始信道LLR為，σ2為噪聲方差。如圖1所示為L(zhǎng)=8時(shí)的SC譯碼算法流程圖。

圖1 L=8時(shí)SC譯碼流程

圖中，f節(jié)點(diǎn)和g節(jié)點(diǎn)的計(jì)算公式使用最小和算法［15～16］表示為

該算法僅含有加減運(yùn)算，適合用于硬件實(shí)現(xiàn)。其中u?s為已經(jīng)譯出的碼字的部分和。在硬件實(shí)現(xiàn)中往往將兩者融合為一個(gè)節(jié)點(diǎn)，被稱為一個(gè)計(jì)算單元（Processing Element，PE），并通過(guò)復(fù)用器來(lái)實(shí)現(xiàn)二者的功能轉(zhuǎn)換。

2.2.2 SCS譯碼算法部分

在SC譯碼算法中，每個(gè)階段僅存在一條候選路徑，錯(cuò)誤極易累加，SCS算法擴(kuò)大譯碼階段候選路徑，利用堆棧來(lái)存儲(chǔ)候選路徑，并始終沿著候選路徑中度量值最大的一條路徑進(jìn)行擴(kuò)展。路徑度量值PM與當(dāng)前候選比特的LLR有關(guān)，計(jì)算公式為

初始階段只有一條空路徑，且PM()φ=0。

根據(jù)式（5），每條路徑中的度量值都大于其后續(xù)路徑的度量值，因此我們將候選路徑按度量值大小順序存儲(chǔ)在堆棧中，棧頂為度量值最大的路徑，每次只取棧頂路徑出棧進(jìn)行路徑擴(kuò)展，根據(jù)式（5）計(jì)算擴(kuò)展路徑的度量值，再將新的路徑按度量值大小排入堆棧中。如此進(jìn)行循環(huán)，直至棧頂路徑長(zhǎng)度達(dá)N，此時(shí)該路徑的度量值將大于所有等長(zhǎng)路徑的度量值，即為譯碼結(jié)果。

設(shè)計(jì)堆棧深度D和路徑擴(kuò)展寬度L，用i表示當(dāng)前路徑長(zhǎng)度，向量表示候選路徑，表示該路徑的度量值，| S |表示堆棧中的路徑數(shù)量，設(shè)定計(jì)數(shù)器向量表示具有對(duì)應(yīng)長(zhǎng)度的出棧路徑數(shù)量，例如ci為路徑長(zhǎng)度為i的出棧路徑數(shù)。SCS算法具體過(guò)程［17］可分以下幾步進(jìn)行。

步驟一：數(shù)據(jù)初始化。將各存儲(chǔ)空間清除緩存數(shù)據(jù)，并給堆棧中傳入空序列，置長(zhǎng)度i=0，度量值=0，路徑數(shù) |S |=1，計(jì)數(shù)器=(0,0,...,0)。

步驟三：棧頂序列擴(kuò)展。將出棧的原棧頂序列擴(kuò)展為兩條路徑，和，并計(jì)算兩條路徑的度量值為

步驟四：候選路徑入棧。首先判斷是否棧滿，若 ||S≥D-2，則直接刪去棧底兩條路徑度量值較小的路徑；若未滿則繼續(xù)操作，將擴(kuò)展的兩條路徑按照度量值大小按順序入棧。

步驟五：路徑競(jìng)爭(zhēng)。計(jì)數(shù)器ci記錄了堆棧中長(zhǎng)度為i的路徑數(shù)量，若ci=L，說(shuō)明前i位路徑已經(jīng)被擴(kuò)展了L次，達(dá)到了搜索寬度，因此我們遍歷堆棧，刪除長(zhǎng)度小于等于i的路徑。

步驟六：譯碼終止判決。判斷棧頂路徑長(zhǎng)度是否為N，若滿足，則該路徑直接出棧作為譯碼結(jié)果；若不滿足終止條件則返回執(zhí)行步驟二。

當(dāng)D與L足夠大時(shí)，SCS算法可確保找到最大似然解；當(dāng)L有限時(shí)，其性能等同于相同搜索寬度的SCL算法，但由于SCS算法只沿著最佳候選路徑進(jìn)行擴(kuò)展，其算法復(fù)雜度必然在一定程度上優(yōu)于SCL算法，并且在信道信噪比大時(shí)更為明顯。

3 SCS譯碼器硬件結(jié)構(gòu)設(shè)計(jì)

3.1 譯碼器整體結(jié)構(gòu)設(shè)計(jì)

本次的譯碼器設(shè)計(jì)設(shè)置碼長(zhǎng)為1024，碼率為1/2，SCS算法堆棧深度D=256，搜索寬度L=32，采用BEC-Z()W 方法進(jìn)行信道選擇，輸入信息的量化位寬為8bit。

極化碼SCS譯碼器整體架構(gòu)如圖2所示，輸入譯碼模塊的是存儲(chǔ)在LLR-based RAM中經(jīng)過(guò)量化的初始LLR，輸出的譯碼結(jié)果是Stack中的頂層數(shù)據(jù)。譯碼模塊結(jié)構(gòu)根據(jù)功能主要包括兩個(gè)部分：度量值計(jì)算和堆棧結(jié)構(gòu)。度量值計(jì)算包括LLR_top module（LLR計(jì)算模塊）、Corrected module（修正模塊）、Metric_top module（度量值計(jì)算模塊）、Feedback module（反饋模塊），以及它們相應(yīng)的數(shù)據(jù)存儲(chǔ)模塊；堆棧結(jié)構(gòu)Stack module并不等同于軟件算法中的堆棧，而是根據(jù)SCS算法和堆棧特點(diǎn)，利用硬件結(jié)構(gòu)寫出的類似堆棧功能的Stack模塊。

圖2 SCS譯碼器整體硬件結(jié)構(gòu)

為了更好地協(xié)調(diào)各個(gè)模塊工作，我們引入狀態(tài)機(jī)，狀態(tài)機(jī)一共有12個(gè)工作狀態(tài)，對(duì)應(yīng)不同時(shí)刻譯碼器的算法流程，用S0～S11來(lái)表示，各狀態(tài)之間的轉(zhuǎn)移關(guān)系如圖3所示。

圖3 控制模塊狀態(tài)轉(zhuǎn)移圖

S0～S11代表的工作狀態(tài)含義如表1所示。

表1 工作狀態(tài)對(duì)應(yīng)表

3.2 堆棧模塊

由于SCS譯碼器中使用的堆棧占用數(shù)量較大，考慮到硬件資源的問(wèn)題，不便于直接利用寄存器實(shí)現(xiàn)，因此我們考慮使用硬件中的雙FIFO結(jié)構(gòu)根據(jù)SCS算法需求實(shí)現(xiàn)特定功能的堆棧，其中FIFO1為堆棧數(shù)據(jù)存儲(chǔ)模塊，F(xiàn)IFO2為對(duì)堆棧進(jìn)行相關(guān)處理的緩存模塊，如圖4所示。

圖4 雙FIFO結(jié)構(gòu)堆棧設(shè)計(jì)示意圖

圖中可以看到，設(shè)置FIFO1和FIFO2深度為256，存儲(chǔ)數(shù)據(jù)寬度為1043bit，包括11bit路徑長(zhǎng)度、1024bit候選路徑和8bit路徑度量值，按照度量值從大到小的順序進(jìn)入隊(duì)列，從而保證最先輸出的堆棧頂層為度量值最大的路徑。FIFO1初始輸入數(shù)據(jù)為空序列，進(jìn)入譯碼階段后的輸入為經(jīng)過(guò)處理后從FIFO2中傳入的數(shù)據(jù)。FIFO1中的頂層數(shù)據(jù)輸出，在其他模塊進(jìn)行路徑擴(kuò)展和度量值計(jì)算，再按照度量值大小進(jìn)行排序，依舊按照度量值從大到小的順序?qū)⒙窂綌?shù)據(jù)輸入FIFO2。FIFO2中存儲(chǔ)經(jīng)過(guò)路徑擴(kuò)展的路徑序列和度量值，將其出棧進(jìn)行路徑競(jìng)爭(zhēng)，完成譯碼算法對(duì)搜索寬度的限制，最后將通過(guò)路徑競(jìng)爭(zhēng)的路徑數(shù)據(jù)重新存入FIFO1，再進(jìn)行下一輪譯碼。

3.3 LLR計(jì)算模塊

SC類算法中LLR計(jì)算方法［18～19］都相同，其模塊也在各類SC算法可通用，這里設(shè)計(jì)LLR計(jì)算包括控制模塊LLR_control、計(jì)算單元狀態(tài)模塊IDX_control、計(jì)算單元Polar_fg和修正模塊Correcred，如圖5所示。LLR_control模塊負(fù)責(zé)整體數(shù)據(jù)的地址傳輸和使能控制，IDX_controll模塊根據(jù)出棧路徑長(zhǎng)度top_length控制計(jì)算單元的狀態(tài)，Polar_fg模塊根據(jù)輸入兩個(gè)LLR值、u?s和PE的計(jì)算狀態(tài)Fg_sel計(jì)算出下一階段的LLR，Correcred解決由于運(yùn)算導(dǎo)致的LLR數(shù)據(jù)溢出問(wèn)題，并通過(guò)wdata信號(hào)將數(shù)據(jù)輸出。

圖5 LLR計(jì)算模塊硬件結(jié)構(gòu)

圖5 中，top_length來(lái)自于頂層出棧數(shù)據(jù)，表示出棧路徑長(zhǎng)度，IDX_control模塊根據(jù)該信號(hào)得出計(jì)算單元應(yīng)處于 f函數(shù)或g函數(shù)的計(jì)算狀態(tài)，并通過(guò)IDX信號(hào)傳入LLR_control中，并經(jīng)過(guò)LLR_control模塊地址控制通過(guò)Fg_sel信號(hào)串行傳入Polar_fg中。當(dāng)前階段LLR數(shù)據(jù)rdata來(lái)自于LLR_base RAM或LLR_MID RAM中，兩個(gè)RAM通過(guò)一個(gè)二選一選擇器傳入Polar_fg，選擇器使能端為 ram_sel，rdata 讀取地址為 raddr。中間 u?s數(shù)據(jù)udata來(lái)自Feedback模塊，直接傳入Polar_fg，其讀取地址為uaddr。Polar_fg模塊計(jì)算出的LLR由于大量計(jì)算其位寬會(huì)變得越來(lái)越大，容易造成數(shù)據(jù)溢出，因此通過(guò)idata信號(hào)傳入Corrected模塊進(jìn)行修正處理，最終得到下一階段LLR再次存入LLR_MID RAM中，寫地址為waddr。

3.4 度量值計(jì)算模塊

圖6所示為路徑度量值計(jì)算模塊的硬件結(jié)構(gòu)圖。

度量值的計(jì)算方法如式（5）所示，根據(jù)公式可知度量值計(jì)算中的輸入數(shù)據(jù)為出棧路徑的度量值、擴(kuò)展路徑LLR值、路徑擴(kuò)展位ui以及初始信道的位置信息。圖中bit_location表示初始信道的位置信息，來(lái)源于大小為1024×1bit的Bit_location ROM中，0表示凍結(jié)比特，1表示信息比特。當(dāng)進(jìn)行度量值計(jì)算時(shí)，Metric_top從Bit_location ROM中讀取位置信息bit_location，和LLR計(jì)算模塊傳入LLR信號(hào)的符號(hào)位一起作為Sel_ctl控制模塊的輸入，來(lái)控制式（5）中所對(duì)應(yīng)的三種情況。

圖6 路徑度量值計(jì)算模塊硬件結(jié)構(gòu)

為縮減運(yùn)算量，在計(jì)算出候選比特為0和1各自的路徑度量值后，使用一個(gè)選擇器進(jìn)行初步比較，按度量值順序?qū)U(kuò)展路徑先后與FIFO1中的出棧路徑度量值進(jìn)行比較并輸入堆棧緩存模塊FIFO2。另外，擴(kuò)展位與凍結(jié)比特不符的路徑度量值為負(fù)無(wú)窮，此時(shí)可省去比較過(guò)程直接將路徑數(shù)據(jù)輸入FIFO2隊(duì)尾。

3.5 反饋模塊

LLR值計(jì)算時(shí)需要來(lái)自Feedback模塊的中間u?s數(shù)據(jù)，隨著路徑不斷擴(kuò)展，需要反饋模塊將新的u?s存儲(chǔ)并傳入LLR計(jì)算模塊，每進(jìn)行一次路徑擴(kuò)展，我們需要將對(duì)應(yīng)路徑的u?s進(jìn)行反饋更新，這里的反饋與LLR蝶形計(jì)算結(jié)構(gòu)的數(shù)據(jù)流動(dòng)方向相反，根據(jù)圖1得到N=8時(shí)的反饋結(jié)構(gòu)，如圖7所示。

圖7 N=8時(shí)反饋模塊結(jié)構(gòu)

按圖中從左到右的順序，計(jì)算規(guī)則：新生成的比特存入頂層，隨后判斷當(dāng)前層的IDX值，如果為0則將當(dāng)前層的數(shù)據(jù)存入下一層的 f單元。如果是1，則將當(dāng)前層的數(shù)據(jù)存入下一層的g單元，并取出f中的數(shù)據(jù)與當(dāng)前層數(shù)據(jù)相加后繼續(xù)存入 f單元，然后繼續(xù)通過(guò)判斷當(dāng)前層進(jìn)行下一層的計(jì)算。這里的 f和g單元只有存儲(chǔ)功能，并非LLR計(jì)算模塊中 f和g單元。

4 仿真結(jié)果與分析

本文的極化碼SCS譯碼器設(shè)計(jì)使用了Altera公司Strtix V系列的5SGXEA7H3F35C3作為FPGA芯片，使用QuartusⅡ15.0綜合后的結(jié)果如表2所示，整體譯碼器的系統(tǒng)面積占用率僅為4%。

表2 極化碼SCS譯碼器綜合資源表

仿真后得到整體譯碼器的譯碼結(jié)果。在600MHz的工作頻率下，一幀碼字的譯碼需要約49000個(gè)時(shí)鐘周期，平均時(shí)延為0.082ms。

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

SCS譯碼器的工作頻率為600MHz，譯碼器平均時(shí)延為0.082ms，在此情況下吞吐率可達(dá)1024/(0.082×10-3)=12.49Mbps。

除了吞吐率外，譯碼器的糾錯(cuò)能力也是評(píng)價(jià)其性能的重要指標(biāo)。采用BEC刪除概率為0.5的BEC-Z（W）方法進(jìn)行信道選擇，碼長(zhǎng)為1024bit，碼率為0.5，SCS譯碼算法的堆棧深度D=256，搜索寬度L=32，硬件計(jì)算中量化位寬為8，路徑度量值計(jì)算時(shí)位寬為12；模擬的AWGN信道下每個(gè)點(diǎn)傳輸105幀數(shù)據(jù)，并統(tǒng)計(jì)每一點(diǎn)的誤碼率得到圖8。

圖8 SC、SCS算法軟件理論性能和SCS硬件實(shí)現(xiàn)仿真結(jié)果的比較

圖中以SC算法和SCS算法的在軟件實(shí)驗(yàn)中的理論性能作為對(duì)比參考，在誤碼率為10-4時(shí)，SCS算法比SC算法的理論性能增益［20］為0.5dB，SCS硬件譯碼器仿真結(jié)果比SC算法軟件理論性能的增益也可達(dá)0.45dB。而SCS算法的軟件理論與硬件仿真結(jié)果的性能較為接近，其誤差主要來(lái)源于硬件實(shí)現(xiàn)的計(jì)算過(guò)程中對(duì)軟件仿真中的浮點(diǎn)數(shù)進(jìn)行了量化，因此必然損失了一定的計(jì)算精度，根據(jù)對(duì)圖8的分析，在誤碼率BER=10-4時(shí)，硬件實(shí)現(xiàn)結(jié)果比理論性能相差僅約0.05dB，故硬件實(shí)現(xiàn)也可獲得近似浮點(diǎn)計(jì)算的性能。

5 結(jié)語(yǔ)

對(duì)碼長(zhǎng)為1024的極化碼采用了SCS算法進(jìn)行譯碼分析，提出了一種基于FPGA的極化碼SCS譯碼器設(shè)計(jì)，設(shè)置使用于硬件實(shí)現(xiàn)的各種參數(shù)，并分堆棧模塊、LLR計(jì)算模塊、度量值計(jì)算模塊、反饋模塊四個(gè)功能部分進(jìn)行詳細(xì)實(shí)現(xiàn)說(shuō)明。大膽提出譯碼器雙FIFO有序堆棧結(jié)構(gòu)和結(jié)合了IDX模塊、控制模塊、計(jì)算單元和修正模塊四部分的單元LLR計(jì)算結(jié)構(gòu)的硬件設(shè)計(jì)，設(shè)計(jì)了能有效協(xié)作LLR計(jì)算模塊工作的反饋模塊，簡(jiǎn)化了LLR的硬件計(jì)算過(guò)程，提高譯碼器的吞吐率。使用Verilog HDL語(yǔ)言在QuartusⅡ上進(jìn)行模塊編寫后，調(diào)用Modelsim進(jìn)行仿真，在系統(tǒng)時(shí)鐘頻率為600MHz的情況下，譯碼器的吞吐率可達(dá)12.49Mbps，資源利用率僅為4%。