基于單調排序與并行選擇的連續刪除堆棧譯碼器的硬件實現

曾文坦，葉龍建，翟雄飛，韓國軍

（廣東工業大學 信息工程學院, 廣東 廣州 510006）

信道極化概念在文獻[1]中首次被提出，是目前唯一能夠被嚴格證明在二進制無記憶信道中可達到信道容量上限的一種編碼方式?；谶@一原理，文獻[1]提出一種全新的編碼方式，命名為極化碼。經過逐步完善，極化碼被選定為5G標準中控制信道的信道編碼方式。

文獻[1]中同樣提出了極化碼編碼相對應的譯碼算法，連續刪除(Successive Cancellation, SC) 譯碼算法，由于SC具有低復雜度的特點，所以SC譯碼算法成為最主流的一類極化碼譯碼算法之一。然而SC譯碼算法同時也面臨著糾錯性能較差、吞吐率較低等問題。為了解決這些缺陷，文獻[2-3]中引入了多路徑度量競爭的思路，提出連續刪除列表(Successive Cancellation List, SCL) 譯碼和連續刪除堆棧(Successive Cancellation Stack, SCS) 譯碼算法。SCL譯碼算法基于廣度優先的原則對最優路徑搜索，同時擴展多條譯碼路徑。而SCS譯碼算法基于深度優先原則，對最優路徑進行擴展。這兩種改進算法具有相近的糾錯性能且相較于SC譯碼算法有著顯著的提升，而SCS在高信噪比(Signal-to-Noise-Ratio, SNR)時對比于SCL譯碼算法具有更低的復雜度。除此之外，部分其余的改進算法也值得關注，文獻[4]提出循環冗余校驗(Cyclic Redundancy Check, CRC) 級聯的方法，在SC譯碼中加入CRC從而提高糾錯性能，這一方法易于實現且未對SC算法本身做出改動，因此可以與其他許多的優化算法疊加使用，例如在文獻[5-6]將CRC推廣到SCL與SCS譯碼中，提出CRC輔助SCS(CRC Assist-SCS, CA-SCS) 譯碼算法和CRC輔助SCL譯碼算法(CRC Assist-SCL, CA-SCL) 。在非SC類譯碼算法中，目前關注度較高的是置信度傳播(Belief Propagation, BP) 譯碼算法[7]，并且在文獻[8-9]中加入比特翻轉(Bit-Flipping) 使其糾錯性能得到進一步提升。BP算法本身具有高度并行性，在吞吐率方面具有較大優勢，但這同樣也造成了較高的運算復雜度和空間復雜度，因此在硬件實現中BP算法的應用場景較窄，并沒有在硬件實現中成為一種主流的譯碼算法。

而極化碼譯碼算法能否進行高效硬件實現，是以上算法得以實際應用的前提。根據SC類譯碼算法的遞歸運算原理可知，其遞歸運算由基本的運算單元組成。文獻[10]提出了樹形結構，將運算單元以樹形連接。然而該結構的硬件利用率低，每個周期僅有一層的運算單元被激活。而文獻[11]在這一基礎上提出平行結構與半平行結構，以極小的時延為代價，將運算單元數量減少至原來的1/4，同時提高了硬件利用率。此外，提高譯碼器吞吐率也是在硬件設計中所面臨的另一項挑戰。文獻[12-14]主要在硬件吞吐率上做進一步的改進，例如引入2-bits判決策略，提出矢量交疊架構實現幀間流水線等方式。文獻[15]針對SCL譯碼提出低延遲列表譯碼(Reduced Latency List Decoding, RLLD) 算法，通過減少節點的訪問來提高譯碼速度。文獻[16]考慮了架構的靈活性提出可配置的SCL譯碼器，擴展了SCL譯碼器的應用場景。文獻[17]則針對SCS譯碼排序提出雙堆棧結構實現路徑排序功能。然而這種雙堆棧結構受到讀寫與比較策略的限制，其路徑選擇過程效率較低并且受SNR影響。而且，堆棧存儲的結構使得同一路徑的不同類型的數據必須進行捆包打包，對于不同類型的路徑信息讀寫不靈活。另外，對于SC類譯碼算法，文獻[18-19]提出的部分和更新的結構，通過寄存器存儲的方式可以用較少的硬件資源實現部分和的層內并行、層間串行的更新。

針對當前SCS譯碼在路徑選擇中效率較低與路徑信息存儲信息不夠靈活的問題，本文針對SCS譯碼算法提出一種基于并行比較和升調排序的路徑選擇方式，利用存儲器組代替堆棧結構。相較于目前的SCS路徑存儲策略，該策略更具備靈活性，通過對不同路徑值(Path Value, PV) 的獨立存儲，實現單條路徑中不同類型的信息單獨讀寫。 另外，本文在部分和更新結構上，充分利用FPGA的并行性，直接利用組合邏輯進行運算，能夠實現多層并行，提高了部分和更新的效率。

1 SC類譯碼算法

1.1 SC譯碼算法

利用接收端所接收到的信息序列y1N與部分已經譯出的碼字序列u?i1-1對當前比特u?i進行判決。判決函數為

式(3)中，當i∈A表明該索引位屬于信息比特，根據LLR值作比特判決，當LLR值大于等于0時，比特判決為“0”，若小于0則判為“1”。而當i∈Ac時，則表明該索引位為凍結比特，凍結比特不包含任何信息，通常固定為比特“0”。

部分和值傳遞至上一層節點后，上層節點繼續向其他未被激活的節點進行LLR值遞歸運算與比特判決，直至二叉樹中所有葉子節點都完成比特判決即完成譯碼。

1.2 SCS譯碼算法

SCS算法的主要思路是通過引入路徑度量值(Path Metric，PM)計算，通過PM值大小來對每個路徑的優劣程度進行度量，每次只對當前最優路徑進行擴展，其余次優路徑存儲于堆棧中，一直擴展至路徑長度(Path Length, PL) 值等于碼長N結束。用p表示當前出棧的路徑。PV值與比特索引值等價，可用i表示，當前出棧路徑的LLR值遞歸運算結果用Lip表示，PM值定義為

式中：B={i|(-1)u?i=sign(Lip)}。

圖2為N=4的SCS譯碼算法的譯碼過程演示圖，向左擴展為比特“0”擴展，向右為比特“1”擴展，實線箭頭表示被激活的路徑，虛線則表示未被激活的路徑，節點下方的數值為當前路徑的PM值。與SCL算法中通過對多條路徑同步擴展的策略不同，SCS譯碼算法僅對堆棧中的最優路徑進行擴展，其余候選路徑存于堆棧中。相當于將整個搜索過程合理“串行化”，這樣做的最大好處在于可以節省大量的不必要的路徑搜索，降低計算復雜度。

SCS譯碼過程中涉及兩個重要參數，堆棧深度和搜索寬度，分別用D和L表示，兩者都對SCS譯碼算法的性能起到重要影響，堆棧深度D表示最多能保留下來的候選路徑數量，而搜索寬度L則表示等長路徑可以保留的最大數。

譯碼器在接收到信息矢量y1N解調后得到長度為N的LLR值矢量用L1N=[L1,L2,···,LN]表示。另外，用bi1=[b1,b2,···,bi]和ci1=[c1,c2,···,ci]表示當前譯碼的最優路徑矢量和一個計數器矢量，用于記錄在堆棧中同等長度的路徑數量。堆棧中當前存儲的路徑數量為s，完整的算法流程如算法1所示。

1.3 算法復雜度分析

SCS譯碼算法的時間復雜度取決于當前信道的S NR值，但是相較于SCL譯碼算法，SCS譯碼算法避免了大量的不必要的路徑擴展，特別是在高SNR的場景下，時間復雜度可以減少至O(Nlog2N)，而SCL的時間復雜度為O(LNlog2N)。在低SNR的情景下，SCS譯碼算法的時間復雜度至多為O(LNlog2N)。

而對于空間復雜度來說，SC譯碼算法的空間復雜度為O(N)， SCL和SCS的空間復雜度分別為O(LN)和O(DN) 。 一般情況下D＞L，所以SCS相較于SCL擁有更高的空間復雜度。

在現有的SCS譯碼算法的硬件實現架構中，在路徑排序部分，通常使用雙堆棧結構進行路徑排序與路徑選擇，一個作為候選路徑存儲的堆棧，另一個則作為排序過程中臨時存儲的數據，通過遍歷堆棧中原有路徑與新路徑逐一比較的方式進行排序。這種排序方式在一個時刻內只能進行一次比較，效率較低，特別在堆棧存儲數據量大時會造成大量時延，在最壞的情況下，排序的時延等于2D。

2SCS譯碼器的硬件架構

為了優化上述所提到的問題，本文提出一種新的SCS譯碼器硬件架構，如圖3所示，總共包含4個模塊：SC譯碼單元(SC Decode Unit) 、路徑度量單元(Path Metric Unit) 、路徑選擇單元(Path Selection Unit)和控制單元(Control Unit) 。下面對主要單元進行進一步詳細說明和介紹。

2.1 SC譯碼單元

SC譯碼單元主要包含：LLR存儲器、部分和更新模塊和計算單元模塊。信道LLR值經過定點量化后存入LLR存儲器中，在進行遞歸運算時根據當前路徑長度讀出相應LLR值。根據SC譯碼算法原理，SC遞歸運算主要包含f運算和g運算。在硬件實現中，將這兩種運算功能合并成一個模塊，成為運算單元(Process Element, PE) ，如圖4所示。

圖4中，上半部分實現f運算功能，下半部分實現g運算功能，LA, LB為LLR值輸入，P_SUM為部分和值。在進行LLR遞歸運算時。根據選通信號FG_SEL來決定選通具體運算功能。在硬件實現中的LLR值需要經過定點量化，由于量化位寬有限，在計算完成后必須對LLR值進行溢出判斷以及數據溢出后的操作。因此在計算單元中引入飽和截斷功能，使得LLR值在溢出后數據固定量化為最大值，從而保證LLR值的符號不會失真。判定原則如式(8)所示，其中Lg為g運 算后的LLR值結果，Lmax為預設最大值。

在遞歸運算結構上，基于硬件開銷與運算時延的綜合考慮，本文使用半平行架構實現遞歸運算，其結構示意如圖5所示。

圖5以碼長為8的遞歸運算結構為例，左側CH_LLR為初始LLR值，右側MID_LLR則為中間運算的LLR值。根據SC譯碼算法的遞歸運算原理，層內并行運算，所以每個周期內最多有N/2個PE被激活。然而繼續分析可知，僅有在u?1和u?N/2時才會有N/2個PE被激活，其余比特至多激活N/4個PE。所以，N/4個PE已經可以滿足絕大部分情況，在u?1和u?N/2索引位置上，對N/4個PE復用兩次即可實現相同效果。這種結構在時延上比傳統平行結構多出兩個周期的時延，卻可以將PE數量減少50%。

傳統的部分和模塊都是對前一比特的部分和數據進行暫存，在暫存的部分和數據的基礎上進行更新，并且這種策略每一層數據都依賴上一層的更新結果，在策略上無法實現層間并行。同時，根據SCS譯碼算法的特點，SCS譯碼算法在譯碼過程中由于路徑不等長，存在路徑回溯的情況，所以該策略不適用于SCS譯碼。本文的部分和更新中，利用當前最優路徑的PV值，直接對下一索引的部分和進行更新，不再對前一索引的部分和數據進行暫存。同時在層間使用組合邏輯的方式進行運算，充分利用硬件的高并行性的特點，實現層間并行運算。圖6為N=8的部分和更新模塊，左側ESI_U0～ESI_U7為輸入PV值，PATH_LEN為路徑長度值，PS_OUT為部分和輸出，部分和輸出選擇器根據當前PL值來判斷輸出的對應長度值。

2.2 路徑選擇單元

在經過路徑值度量單元對路徑進行擴展及計算出對應的PM值后，兩條新路徑將被輸入至路徑選擇模塊，向“0”和“1”擴展的兩條新路徑分別用PATH0和PATH1表示。路徑選擇單元包含候選路徑存儲器組和路徑選擇模塊，每條候選路徑都包含3種信息：路徑度量值PM、路徑值PV及路徑長度值PL。在傳統的路徑選擇單元中，每條候選路徑的這3種信息會被打包然后送入堆棧中。在進行路徑選擇時，根據SCS譯碼原理，進行路徑選擇操作僅需要使用PM值數據。然而因為數據在堆棧中被打包的緣故，所對應的PV值及PL值都會被讀出，造成了大量的不必要讀寫，增加了路徑選擇過程中的復雜度。針對這一問題，本文中的路徑選擇單元對這3種不同的信息進行單獨存儲，通過統一的地址讀寫控制來保證其信息的對應性。而在進行路徑選擇過程中，僅需要對PM值存儲器進行單獨的操作即可，在最后完成路徑選擇后才對其余對應的PL值和PV值進行讀出，減少了在中間過程中大量不必要的讀寫。

在路徑選擇模塊中，本文采用分組單調排序與并行比較相結合的方式。這種方式相較于傳統的SCS譯碼器效率更高，其結構圖如圖7所示，在完成新路徑寫入后，將度量值存儲器中所有PM值讀出，讀出的PM值與所對應的地址值拼接，送入路徑選擇模塊中。在s＜D-1時，路徑選擇模塊僅返回最優路徑地址，用POP_ADDR表示。而當存儲器組即將存滿或已經存滿，即s≥D-1時，地址控制模塊使能路徑值選擇模塊中的最劣路徑選擇功能，此時路徑選擇模塊返回最優路徑地址與最劣路徑地址。最劣路徑即PM值最大的路徑，在存儲器存滿的情況下，最劣的路徑成為最優先被淘汰的路徑，用DEL_ADDR表示。

新路徑寫入存儲器組的策略分為存儲器存滿和未存滿兩種情況，如圖8所示。圖8(a)為未存滿情況下的存儲策略，由于每次路徑選擇完成后，最優路徑必然讀出，這就意味著該最優路徑POP_ADDR地址在下一次譯碼時處于空閑狀態，所以將POP_ADDR作為下輪譯碼中PATH0的寫入地址。同時定義一個計數器指針CNT_ADDR，該指針一直指向最小的空閑地址，該地址作為PATH1的寫入地址，將PATH1按順序存入存儲器，直至存儲器存滿。而在存儲器即將存滿時，如圖8(b)所示，地址控制器將使能路徑選擇模塊中的最劣路徑選擇功能，此時路徑選擇模塊則會返回兩個地址值：最優路徑地址POP_ADDR和最劣路徑地址DEL_ADDR，設上一個譯碼周期返回的最優地址和最劣地址分別為a1和a2。PATH0依然以POP_ADDR作為寫入地址，PATH0寫入a1。而CNT_ADDR由于存儲器存滿后將失效，所以此時應使用DEL_ADDR作為PATH1的寫入地址，PATH0寫入a2。通過直接覆蓋原有的最劣路徑數據的方式實現PATH1的寫入與最劣路徑的淘汰。

3 實驗結果及分析

在硬件實現上，本文所有硬件設計均在Xilinx系列xc7v585tffg的FPGA平臺中進行，時鐘頻率Fclk設定為200 MHz。對碼長結構(N,K) =(256, 128) 進行實現，堆棧深度D=64和搜索寬度L=16。并對文獻[17]的架構在同樣碼長下在同平臺進行復現對比，碼率R均為0.5。均使用高斯近似(Gaussian Approximation, GA)，仿真場景使用加性白高斯信道模型，并使用二進制相移鍵控(Binary Phase Shift Keying, BPSK) 調制方式。

3.1 基于MATLAB的LLR值量化分析

由于LLR值為浮點數，在硬件實現中都需要將數據進行定點量化才能進行處理，而具體的量化方案將直接影響到硬件的性能以及硬件開銷，所以在方案上需要做出合理的選擇，使得硬件開銷和性能損失都在可接受的范圍內。

用 (Qc,Qf)表示初始LLR值和小數位的量化位寬。圖9為 SCS譯碼算法在比特信噪比(Eb/N0) 在1～3.5 dB范圍內，不同量化方案下的誤比特率(Bit Error Ratio, BER) 對比，對(8,1) 、(8,3) 、(6,1) 、(6,3) 這4種量化方案進行性能仿真對比。通過(Qc,Qf)=(8,3)與(Qc,Qf)=(6,3)的對比，兩者小數位寬相等，而整數位寬被壓縮造成了 (Qc,Qf)=(6,3)的性能損失明顯，所以整數位寬應當設定為大于等于5 bits。而(Qc,Qf)=(8,3)和 (Qc,Qf)=(6,1)擁有等長的整數位寬，小數位寬的壓縮并未造成明顯的性能損失。最后對比(Qc,Qf)=(8,3) 和 (Qc,Qf)=(8,1)可以說明整數位寬大于5 bits的情況下沒有明顯增益。因此，基于性能和資源開銷綜合考慮，本文選擇 (Qc,Qf)=(6,1)作為最后的量化方案。

3.2 基于FPGA的硬件平臺仿真

本文所提出的硬件結構資源消耗如表1所示。與文獻[17]相比較，本文譯碼器整體資源消耗在查找表(Look Up Table, LUT)、寄存器(Register) 和塊隨機存儲器(Block Random Access Memory, BRAM) 上分別減少了24.06%、56.42%和39.29%。特別地，將路徑選擇模塊與部分和模塊的資源消耗進行單獨比較，本文的方案在路徑選擇模塊上，LUT和Register平均多出40.65%和18.32%的開銷。然而在部分和模塊中，本文的方案在LUT和Register則平均減少了7.68%與77.98%的開銷，并且由于沒有使用到存儲模塊，因此BRAM消耗為0。在吞吐率方面，根據譯碼器吞吐率公式：

表1 不同架構的性能對比情況Table 1 The comparisons of different structures

在200 MHz的工作頻率下，本文譯碼器的平均時延為0.046 ms，因此在此情況下吞吐率T=256/(0.046×10-3)=5.51 Mbit/s，相較于復現的譯碼器提高了約24.38%。

除了硬件性能外，本文進一步驗證了譯碼器的糾錯性能，圖10為本文設計的SCS譯碼器與同碼長的SC譯碼器在硬件實現和MATLAB仿真中的誤比特率性能對比。其中黑色線為MATLAB的仿真結果，其余為FPGA實現結果。從結果對比圖可得知在FPGA上的實現與仿真結果相近，這得益于量化比特數的合理選擇，從而在實現過程中未造成明顯性能損失。而對比SC與SCS的FPGA實現結果可知，相較于SC譯碼算法，本文所提出的SCS譯碼器有0.6 dB的性能增益。

圖1 SC譯碼過程圖Fig.1 The process of SC decoding

圖2 N=4下SCS譯碼流程圖Fig.2 The process of SCS decoding with N=4

圖3 SCS譯碼器頂層架構Fig.3 The top architecture of SCS decoder

圖4 PE運算單元Fig.4 The architecture of PE

圖5 N=8半平行結構Fig.5 The architecture of semi-parallel with N=8

圖6 N=8 的部分和更新模塊Fig.6 The architecture of partial sum module with N=8

圖7 路徑選擇模塊結構圖Fig.7 The architecture of path selection

圖8 路徑寫入策略示意圖Fig.8 Examples of paths writing strategy

圖9 在不同( Qc,Qf)下的BER比較Fig.9 The comparisons of BER with different(Qc,Qf)

圖10 SCS譯碼器與SC譯碼器碼長為(N,K) = (256,128) 性能比較Fig.10 The comparison of SCS and SC with (N,K) =(256,128)

從硬件平臺實現結果看出SCS譯碼器在性能上明顯優于SC譯碼器。同時合理的量化比特選取也使硬件實現中的性能損失非常小。

4 結論

本文主要針對SCS譯碼器的路徑選擇模塊提出了一種新的架構，從而提升路徑選擇模塊的性能。通過硬件實現驗證，本文所提出的架構通過對堆棧存儲策略的改善，不同種類的路徑信息讀寫變得更加靈活。在路徑選擇上利用分組單調排序與并行比較相結合的策略使得最佳路徑搜索更加高效。另外，在部分和模塊中本文提出用路徑值實時計算部分和的方法，部分和反饋更加高效，充分利用了FPGA強大的并行性。實驗結果表明，本文中所提出的硬件架構的整體資源消耗降低且吞吐率有小幅提升，在路徑選擇模塊中需要更多的LUT和Registers，但在部分和模塊中需要更少的資源。同時，本文提出的結構糾錯性能優于SC譯碼器并與SCS譯碼算法的理論結果接近。

然而，SCS譯碼器在低SNR時會頻繁出現路徑回溯現象，這一現象主要由LLR量化精度損失所造成。文獻[20]中所提出的通過算法模型來動態調整量化參數的策略具有一定啟發性，在SCS譯碼中根據SNR與PL值通過一定算法來動態調整量化參數也許可以進一步提升譯碼器性能。