極化碼半平行SCL譯碼器的FPGA實現

梅 晟，仰楓帆

(南京航空航天大學 電子信息工程學院，江蘇 南京211106)

0 引言

極化碼由土耳其教授Erdal Arikan在文獻[1]中于2007年首次提出，它是一種基于信道極化現象的信道編碼，并且是唯一被證明能達到香農極限[2]的信道編碼，具有較低的編譯碼復雜度，受到了廣泛研究。隨后，學者對SC譯碼算法進一步優化，提出了SCL譯碼算法[3]，極大地提升了譯碼性能。同時也對極化碼的工程實現進行了研究。在眾多SC譯碼結構的基礎上，Leroux等人在文獻[4]中設計了半平行譯碼結構，該結構以犧牲較小的吞吐率為代價大幅度降低了系統復雜度，具有較小的時延。在前人的基礎上，本文通過對半平行結構的SCL譯碼器的分析，重點工作放在硬件資源復用和內存結構的優化上，提高了硬件吞吐量并降低了譯碼時延，最終通過VerilogHDL硬件描述語言進行實現，同時給出相應時延、資源占用率等關鍵測試數據。

1 信道極化現象

(1)

2 極化碼的編譯碼方法

2.1 極化碼編碼方法

2.2 極化碼SCL譯碼算法

極化碼發展至今已有多種譯碼方法，其中SCL譯碼算法性能較為優良，且具有較低的譯碼復雜度。

(2)

對上述規則進行細化，令對數似然比(Log Likelihood-Ratio，LLR)為:

(3)

(4)

式(3)為奇數下標記為f函數和式(4)為偶數下標記為g函數，通過對數域化簡能夠得到[10-11]：

(5)

在SC譯碼算法中，每個階段僅存在一條候選路徑，錯誤極易累加。所以在SCL譯碼算法中，每個譯碼階段都存在路徑度量值較大的L(L≥2)條候選路徑，而最終目的即為從這L條路徑中選出最佳路徑。與SC譯碼算法中對當前比特直接判決不同，SCL算法中每一個比特在譯碼過程中的頂層按式(6)進行路徑度量值PM的計算,

(6)

初始列表中只有一條空路徑，且PM(φ)=0?？梢詫⒋诉^程表述為一個深度為N的滿二叉樹。

3 SCL譯碼器硬件結構設計

3.1 譯碼器整體結構設計

在設計的譯碼器中，選取碼長為1 024，碼率為1/2，P=2，以BEC為信道挑選方法，列表寬度L=32。對譯碼器中的數據進行8 bit量化，路徑度量值進行12 bit量化，對譯碼過程中發生的溢出采用截斷處理，使得位寬不會逐級遞增，大大簡化了譯碼器的設計復雜度，且只有極小的性能損失。整體結構主要包括以下頂層模塊：LLR計算模塊(LLR_top)、修正模塊(Corrected)、度量值計算模塊(Metric_top)、度量值排序模塊(Sort_top)、反饋模塊(Feedback)、控制模塊(Controller)和路徑恢復模塊(Path_recover)，如圖1所示。在譯碼開始之前，首先將信道LLR分組，存入位寬為128，深度為64的RAM中作為初始LLR，即圖1中的LLR_based RAM。

圖1 譯碼器整體結構

3.2 LLR計算模塊

LLR計算模塊由LLR控制單元和計算單元PE組成，而PE結構又由P個式(5)中的f或g模塊構成，在單次頂層LLR的計算中，每一層都僅激活f或g節點中的一種。

為了更進一步降低SC譯碼器的復雜度，本文采用半平行譯碼結構。該結構以增加少量時延為代價大幅削減了PE的個數，從而降低了譯碼器的復雜度。

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

(7)

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

(8)

所以總的PE數量為LP，其中L為列表寬度。

3.3 LLR存儲單元

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

以N=8的雙PE結構的半平行設計為例，如圖2所示，首先從s=3層開始讀取數據，分2個時鐘完成，第1個時鐘可以計算出s=2層的4個LLR數據，并存儲到SRAM1內，第2個時鐘同理計算出s=2層的LLR數據，并存儲到SRAM2內；接著讀取s=2層的LLR數據，此時只需要一個時鐘就能完成，但是需要同時讀取SRAM1和SRAM2的數據送入2個PE結構中同時計算，得到s=1層的2組LLR，并存入SRAM1中；最后讀取s=1層的數據，此時只有單PE結構在工作，輸出的數據位寬不能滿足存儲要求，所以在高位補零達到存儲需要。此時得到的數據便是頂層LLR，需要接著進行路徑度量值的計算。

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

3.4 度量值計算模塊

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

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

3.5 反饋模塊

3.6 路徑恢復模塊

本模塊的功能為從排序結果中將路徑提取出來，這樣使得在SCL譯碼模塊中不再需要對路徑進行保存和復制。初始狀態下，將32條空路徑設置索引號0～31，每條路徑按照自己的索引從最后一個比特的位置讀取排序結果，提取相應的碼字。然后根據排序結果來更新下一次要讀的索引，重復此步驟直到讀到第1位比特，最終將輸出的碼字發送到譯碼結果存儲器中，其深度為512，數據位寬為32。

4 仿真結果與分析

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

表1 極化碼SCL譯碼器硬件資源統計

資源類型占用量百分比/%邏輯單元(ALMs)71 26518存儲器單元/bit2 170 8804端口315

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

(9)

本文設計中，碼長為1 024，譯碼器的工作頻率為100 MHz。譯碼器平均時延為0.040 ms，所以吞吐率可以達到1 024/(0.040×10-3)=25.6 Mbps?？梢杂^察到，本文設計的譯碼算法譯出一個碼字大概需要4 000個時鐘周期，而系統面積的占用率僅為6%。

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

圖3 SCL譯碼算法性能曲線

從圖3中可以看出，量化之后與理論未量化之間性能相差無幾，在量化后的BER只與理論值相差0.1 dB左右，驗證了優異的譯碼器性能。

5 結束語

對碼長為1 024的極化碼采用了公認性能優良的SCL譯碼算法，對每條候選路徑運用半平行計算的硬件架構，相較于平行結構大幅減少了系統硬件的資源占用，然而在吞吐量上卻與之相差較小，極大地降低了硬件實現的復雜度。考慮到PE結構的復雜度，如何進一步優化結構并在速度與面積之間取得平衡，是后續研究的方向。

[1] ARIKAN E.Channel Polarization：a Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels[J].IEEE Transactions on Information Theory，2009，55(7)：3051-3073.

[2] SHANNON C E.A Mathematical Theory of Communication[J].Bell Labs Technical Journal，1948，5(4)：3-55.

[3] TAL I，VARDY A.List Decoding of Polar Codes[C]∥IEEE International Symposium on Information Theory Proceedings，IEEE，2011：1-5.

[4] LEROUX C，RAYMOND A J，SARKIS G，et al.A Semi-Parallel Successive-Cancellation Decoder for Polar Codes[J].IEEE Transactions on Signal Processing，2013，61(2)：289-299.

[5] ARIKAN E.Systematic Polar Coding[J].IEEE Communications Letters，2011，15(8)：860-862.

[6] ARIKAN E.Channel Combining and Splitting for Cutoff Rate Improvement[J].IEEE Transactions on Information Theory，2005，52(2)：628-639.

[7] LI H，YUAN J.A Practical Construction Method for Polar Codes in AWGN Channels[C]∥Tencon Spring Conference，IEEE，2013：223-226.

[8] MORI R，TANAKA T.Performance of Polar Codes with the Construction Using Density Evolution[J].IEEE Communications Letters，2009，13(7)：519-521.

[9] TAL I，VARDY A.How to Construct Polar Codes[J].IEEE Transactions on Information Theory，2013，59(10)：6562-6582.

[10] FOSSORIER M P C，MIHALJEVIC M，IMAI H.Reduced Complexity Iterative Decoding of Low-density Parity Check

Codes Based on Belief Propagation[J].IEEE Transactions on Communications，1999，47(5)：673-680.

[11] LEROUX C，TAL I，VARDY A，et al.Hardware Architectures for Successive Cancellation Decoding of Polar Codes[C]∥IEEE International Conference on Acoustics，Speech and Signal Processing (ICASSP)，2011：1665-1668.