基于FPGA的極化碼半平行CA-SCL譯碼器設計?

王美芹 仰楓帆 趙春麗

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

1 引言

極化碼［1］是在2007年由土耳其教授Erdal Ari?kan首次提出的一種基于信道極化現象［2］的信道編碼，并且其被當作是目前唯一可被證明能達到香農極限［3］的信道編碼，且具有較低的復雜度，因此極化碼的研究在學術界掀起了一股熱潮。隨后，學者對SC譯碼算法做進一步改進，提出了SCL譯碼算法［4～6］，極大地提升了譯碼性能。尤其是在2013年，由 Niu.K，K.Chen提出的 CA-SCL譯碼算法［7～8］，其獲得了優于最大似然算法［9］的性能。與此同時，眾多學者也研究了極化碼的工程上實現。在眾多的SC譯碼結構［10～13］的基礎上，Leroux等設計了半平行結構［14］，其以犧牲較小的吞吐量為代價，大幅度的降低了系統復雜度，并具有較小的時延。在本文中，通過對CA-SCL［15］的半平行譯碼結構的研究分析，提高了硬件吞吐量的同時，又降低了譯碼的時延，使得硬件資源復用和內部結構優化。

2 極化碼

Arika在研究信道的組合和拆分［16］過程中發現，在將N個相互獨立的信道進行組合和拆分后，系統的總體容量沒有發生改變，而總體截止速率得到了提升。因此，Arikan將N個相互的完全相同的二進制離散無記憶（B-DMC）信道通過組合并為信道WN，并將WN拆分為N個相關子信道，隨著N的不斷變大，其子信道容量趨向0或1兩個極端，這即為信道極化現象。通常情況下，我們將信道容量趨向于1的子信道用來傳送信息比特，而信道容量趨向于0的子信道用來傳送收發雙方均已知的固定比特，其默認值為0。

如何挑選信道非常重要，在學者們不斷研究中涌現許多高性能的信道挑選方法［17～19］。Arikan 指出，通常情況下對于任意信道都可以使用BEC信道下的信道挑選方法而不會產生較大的性能損失，通常令初始信道容量為，使用式（1）迭代公式進行信道挑選：

且極化碼編碼的碼率可以調節任意K/N，其中0≤K≤N編碼塊長度N的大小為2n，任意給定一個N，使用式（2）對信息比特進行編碼：

3 CA-SCL譯碼算法

CA-SCL譯碼算法是極化碼的SCL譯碼算法的基礎上添加CRC校驗位，以較少的碼率為代價來獲取最高的性能。此算法是迄今為止性能最佳的一種極化碼譯碼算法，并且具有較低的譯碼復雜度能。

3.1 SCL譯碼算法

SCL譯碼算法的基本思想是在極化碼的譯碼樹上，按照后驗概率最大原則尋找最合適路徑得到譯碼序列。假定極化碼的碼長為N，譯碼樹中的每個節點代表一個比特，第i層中共有2i-1個節點，表示給定所有可能值的情況下比特ui的取值結果。在樹的每一層，根據式（3）計算每條路徑的路徑度量值的大小，然后進行路徑的排序、選擇和淘汰，最后選擇路徑度量值最大的路徑作為最后的譯碼結果。L為路徑的搜索列表寬度，當路徑數大于L時，每層保留L條后，下一層延伸時總是需要計算2L個路徑的度量值。

3.2 CRC校驗

這里將加入CRC校驗碼后的極化碼詳細編譯碼描繪如圖1所示。

圖1 極化碼的CA-SCL譯碼框圖

如圖1所示，在本算法中，在輸入信息位為k比特，添加m位CRC碼的編碼器中，使得輸入為K=k+m比特，對此K比特的信息位進行極化碼編碼，可以得到N位信道輸入，經過信道傳輸后送入CA-SCL譯碼器進行譯碼。當SCL譯碼器譯出L個候選序列之后，將此L個序列所對應的路徑度量值以由大到小的順序進行排序，并按照這個順序進入解CRC碼單元。當譯出的序列不滿足CRC的關系時，此單元將會通過SCL譯碼器繼續傳送到下一個序列。就這樣直到輸入解CRC碼單元的序列通過CRC校驗，譯碼結束后，解除CRC校驗碼，CA-SCL譯碼器譯出的碼字就是最后得到的輸出序列。

4 半并行硬件譯碼結構

在硬件實現上，經典SC譯碼單元有幾種典型的譯碼結構，比如樹形結構、線性結構、半平行結構。下面詳細介紹本文所采用的半平行結構。

圖2為N=8時的SC譯碼FFT結構，該結構是CA-SCL譯碼結構的基礎。其蝶形算法可應用于硬件實現的“從右往左”蝶形算法。從信道層開始，按照順序依次計算節點的LLR值并存儲在起來作為中間LLR供后面計算調用，避免了在硬件中進行遞歸調用，同時能達到與遞歸算法相同的復雜度，如圖2中加粗線條為一比特計算過程。

圖2 基于蝶形圖的典型FFT結構

從圖2可以發現，無論第l階段的節點在何時被激活，實際上在該階段都只有2m-l-1個節點的值得到更新或被下一階段所使用。我們將f函數和g函數通過復用器融合為一個計算單元（Process Element，PE），通過狀態控制來指示當前使用的函數為f函數還是g函數。在保證譯碼結構具有較低的硬件復雜度的同時，還需要盡可能地減少PE的數量，以降低資源利用率。因此，Leroux等提出了SC譯碼的半平行結構，能夠以較小的時延大幅降低硬件復雜度，是目前較為優秀的硬件實現架構。

表1 半平行譯碼結構時序表

如表1所示，以碼長N=8的SC譯碼為例，在半平行結構中只使用了2（N4）個PE，整個譯碼周期中PE單元基本上都同時工作，使得利用率高，實現資源占用率低。

若PE結構數量為P，則半平行譯碼結構的時延周期為

另外，半平行結構譯碼器的利用率為

相較于全平行的譯碼結構，半平行結構的譯碼速度因子為

對于CA-SCL譯碼算法，若L為列表寬度，那么總的PE單元數量為LP。

5 CA-SCL譯碼器硬件結構設計

5.1 譯碼器整體結構設計

在本次的譯碼器設計中，設置條件為碼長N=1024，碼率是R=1/2，信道挑選方法為BEC方法，列表寬度L=32，采用LTE協議建議的24位CRC檢驗碼，其生成多項式為對譯碼器中的數據進行8比特量化，路徑度量值進行12比特量化。對譯碼過程中發生的溢出采用截斷處理，使得位寬不會逐級遞增，在僅有較小性能損失的情況下，就可大大簡化了譯碼器的設計復雜度。

如圖3所示，整體譯碼結構主要包括以下幾個頂層模塊：LLR計算模塊（LLR_top）、修正模塊（Corrected）、度量值計算模塊（Metric_top）、排序模塊（Sort_top）、反饋模塊（Feedback）、控制模塊（Con?troller）、路徑恢復模塊（Path_recover）、CRC串行譯碼模塊（CRC）等。

在實現半平行結構譯碼開始之前，要解決的是LLR存儲結構問題。先將信道LLR分組，存入位寬為64，深度為256的RAM中作為初始LLR，即圖中的LLR_based RAM。

5.2 LLR存儲結構

對于碼長為N的極化碼，信道輸出序列經過計算得到N個信道LLR。本文選定量化寬度為，所以總存儲單元大小為，而對于總體結構一個時鐘下必須有2P個輸入LLR以及P個輸出LLR，對于LLR存儲模塊，以為一組，記為一個存儲單元，其中每比特為一組PE結構的兩個輸入信道LLR，單時鐘讀入一個存儲單元作為所有P個PE結構的輸入，全部存儲深度為N/2P。據此分析，在時鐘和讀地址的控制下，讀完全部的數據需要N/2P個時鐘周期。由前面的分析可知，無論碼長和碼率為多少，初始LLR在整個譯碼的過程中僅被使用兩次，即該RAM將僅被讀取兩次。

圖3 譯碼器整體結構

因為每條路徑包含P個PE單元，所以單次計算會產生P個內部中間LLR，所以每次需要存儲的數據為PQLLR，其中QLLR為每個LLR數據的存儲位寬，所以內部LLR存儲模塊輸入位寬為PQLLR，同時每次計算需要2P個初始LLR數據，所以內部LLR存儲模塊輸出位寬為2PQLLR，為實現這一結構，本文采用雙SRAM來實現2PQLLR數據的輸出。

圖4 N=8，P=2的LLR存儲器結構

以N=8的雙PE結構的半平行設計為例，圖4即為N=8，P=2的LLR存儲器結構。

5.3 LLR計算模塊

如圖5所示的LLR計算模塊硬件結構，該模塊主要是由控制單元（LLR_control）、PE計算單元（Polar_fg）、排序器（LMUXL）組成。控制模塊用于控制數據讀取地址和索引信息；排序器的作用是將輸入的LLR數據按照index進行重排，然后傳入到L條路徑中計算LLR的值；而PE計算結構是由P個式（4）中的f或g模塊構成，在單次頂層LLR的計算中，每一層都僅激活f或g節點中的一種。

圖5 LLR計算模塊硬件結構

5.4 度量值計算模塊

在得到32條路徑對應的頂層LLR之后，要對當前2L=64條路徑的度量值進行計算，如圖6所示為路徑度量值計算模塊的硬件結構。用一塊1024*1的ROM存放信息比特和凍結比特的位置信息，0對應凍結比特，1對應信息比特。當本模塊開始工作時，從Bit_location ROM中讀取位置信息和頂層LLR的符號位一起作為控制模塊的輸入，來控制式（3）中所對應的三種情況。

在計算出候選比特為0和1格子的路徑度量值后，使用一個選擇器輸出其中的較大值和較小值以及它們對應的候選比特。然后對路徑進行冒泡排序，將前32條路徑度量值進行存儲，供下次計算使用。

圖6 路徑度量值計算模塊硬件結構

5.5 部分和更新模塊

圖7為部分和更新模塊硬件框圖。其中虛線部分為部分和項的存儲結構，指針只讀取其中實現框內的存儲單元。

圖7 路徑度量值模塊硬件結構

根據前面討論可知g函數的計算中需要部分和的輸入，所以需要在每個碼字被估計出來之后對部分和項進行更新，為了不影響系統吞吐率，我們采用寄存器進行存儲，觀察譯碼蝶形圖，每個碼字的譯碼最多同時利用N/2個比特的部分和，所以本文為了節省硬件資源，采用N/2 bit的寄存器長度，每次更新都對寄存器進行清零。

5.6 CRC串行譯碼模塊

本文CRC譯碼模塊采用的是串行逆序譯碼結構，這是因為在路徑恢復模塊譯出來的信息比特為逆序排列，逆序的CRC校驗碼是在逆序信息比特序列前面，且序列為串行輸出。因此，使用此結構，與并行譯碼相比不僅減少了資源消耗，所需時間也不會發生改變。該模塊如圖8所示使用了24個寄存器，這些寄存器是用于存放CRC檢驗碼。解碼開始，前24個時鐘，按順序將24個CRC校驗碼分別存入24個寄存器中。而從第25個數據將按下圖的數據流向進行計算，根據生成多項式生成加法器。整個結構如圖8所示。

圖8 CRC串行逆序譯碼模塊

6 譯碼器綜合結果與分析

在本文的極化碼CA-SCL譯碼器設計實現的過程中，采用的FPGA芯片是Altera公司Strtix V系列的5SGXEA7H3F35C3，使用QuartusⅡ15.0綜合后的結果如表2所示。

表2 極化碼CA-SCL譯碼器硬件資源統計

吞吐率T是評價硬件譯碼器性能的重要指標。其計算公式為

在本文設計中，碼長為1024，譯碼器的工作頻率為150MHz。譯碼器平均時延為0.040ms，所以吞吐率可以達到由于系統用兩個時鐘存儲更新LLR，因此總的時延可以計算如式（9）：

根據譯碼結果，本文設計的譯碼算法譯出一個碼字大概需要6000個時鐘周期，與理論值5120個時鐘周期相差不大，而系統面積的占用率僅為7%。

硬件譯碼算法的另一個重要評價指標是誤碼率（BER），如圖9所示為本文8 bit量化與理論未量化譯碼算法之間BER的性能比較。

如圖9所示，CA-SCL半平行譯碼算法在對數據進行8 bit量化、路徑度量值進行12 bit量化后的性能與理論未量化之間比較接近，在誤碼率BER=10-5時，量化后的BER只與理論值相差0.1dB左右，驗證了優異的譯碼器性能。

圖9 量化與未量化CA-SCL譯碼算法比較

7 結語

對碼長為1024的極化碼采用了性能優良的CA-SCL譯碼算法，在FPGA下設計實現，對每條候選路徑運用半平行計算的硬件架構，相較于平行結構大幅減少了系統硬件資源占用，完成了對該算法占用較大系統面積的優化，在此情形下的吞吐率表現并沒有達到理想狀況。接下來對如何進一步在速度與面積之間取得平衡，來提高系統頻率降低平均時延，是后續主要的研究方向。