極化碼半平行SCL譯碼器的FPGA實(shí)現(xiàn)

梅 晟，仰楓帆

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

0 引言

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

1 信道極化現(xiàn)象

(1)

2 極化碼的編譯碼方法

2.1 極化碼編碼方法

2.2 極化碼SCL譯碼算法

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

(2)

對(duì)上述規(guī)則進(jìn)行細(xì)化，令對(duì)數(shù)似然比(Log Likelihood-Ratio，LLR)為:

(3)

(4)

式(3)為奇數(shù)下標(biāo)記為f函數(shù)和式(4)為偶數(shù)下標(biāo)記為g函數(shù)，通過對(duì)數(shù)域化簡(jiǎn)能夠得到[10-11]：

(5)

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

(6)

初始列表中只有一條空路徑，且PM(φ)=0。可以將此過程表述為一個(gè)深度為N的滿二叉樹。

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

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

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

圖1 譯碼器整體結(jié)構(gòu)

3.2 LLR計(jì)算模塊

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

為了更進(jìn)一步降低SC譯碼器的復(fù)雜度，本文采用半平行譯碼結(jié)構(gòu)。該結(jié)構(gòu)以增加少量時(shí)延為代價(jià)大幅削減了PE的個(gè)數(shù)，從而降低了譯碼器的復(fù)雜度。

若PE結(jié)構(gòu)數(shù)量為P，則半平行譯碼結(jié)構(gòu)的時(shí)延周期[11]為：

(7)

另外，半平行結(jié)構(gòu)譯碼器的利用率為：

(8)

所以總的PE數(shù)量為L(zhǎng)P，其中L為列表寬度。

3.3 LLR存儲(chǔ)單元

因?yàn)槊織l路徑包含P個(gè)PE單元，單次計(jì)算會(huì)產(chǎn)生P個(gè)內(nèi)部中間LLR，所以每次需要存儲(chǔ)的數(shù)據(jù)為PQLLR，其中QLLR為每個(gè)LLR數(shù)據(jù)的存儲(chǔ)位寬，所以內(nèi)部LLR存儲(chǔ)模塊輸入位寬為PQLLR，同時(shí)每次計(jì)算需要2P個(gè)初始LLR數(shù)據(jù)，所以內(nèi)部LLR存儲(chǔ)模塊輸出位寬為2PQLLR，為實(shí)現(xiàn)這一結(jié)構(gòu)，本文采用雙SRAM來(lái)實(shí)現(xiàn)2PQLLR數(shù)據(jù)的輸出。

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

圖2 N=8，P=2的LLR存儲(chǔ)器結(jié)構(gòu)

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

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

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

3.5 反饋模塊

3.6 路徑恢復(fù)模塊

本模塊的功能為從排序結(jié)果中將路徑提取出來(lái)，這樣使得在SCL譯碼模塊中不再需要對(duì)路徑進(jìn)行保存和復(fù)制。初始狀態(tài)下，將32條空路徑設(shè)置索引號(hào)0～31，每條路徑按照自己的索引從最后一個(gè)比特的位置讀取排序結(jié)果，提取相應(yīng)的碼字。然后根據(jù)排序結(jié)果來(lái)更新下一次要讀的索引，重復(fù)此步驟直到讀到第1位比特，最終將輸出的碼字發(fā)送到譯碼結(jié)果存儲(chǔ)器中，其深度為512，數(shù)據(jù)位寬為32。

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

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

表1 極化碼SCL譯碼器硬件資源統(tǒng)計(jì)

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

吞吐率T是評(píng)價(jià)硬件譯碼器性能的重要指標(biāo)，其計(jì)算公式為：

(9)

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

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

圖3 SCL譯碼算法性能曲線

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

5 結(jié)束語(yǔ)

對(duì)碼長(zhǎng)為1 024的極化碼采用了公認(rèn)性能優(yōu)良的SCL譯碼算法，對(duì)每條候選路徑運(yùn)用半平行計(jì)算的硬件架構(gòu)，相較于平行結(jié)構(gòu)大幅減少了系統(tǒng)硬件的資源占用，然而在吞吐量上卻與之相差較小，極大地降低了硬件實(shí)現(xiàn)的復(fù)雜度?？紤]到PE結(jié)構(gòu)的復(fù)雜度，如何進(jìn)一步優(yōu)化結(jié)構(gòu)并在速度與面積之間取得平衡，是后續(xù)研究的方向。

[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.