基于FPGA的極化碼半平行CA-SCL譯碼器設(shè)計(jì)?

王美芹 仰楓帆 趙春麗

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

1 引言

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

2 極化碼

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

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

且極化碼編碼的碼率可以調(diào)節(jié)任意K/N，其中0≤K≤N編碼塊長(zhǎng)度N的大小為2n，任意給定一個(gè)N，使用式（2）對(duì)信息比特進(jìn)行編碼：

3 CA-SCL譯碼算法

CA-SCL譯碼算法是極化碼的SCL譯碼算法的基礎(chǔ)上添加CRC校驗(yàn)位，以較少的碼率為代價(jià)來(lái)獲取最高的性能。此算法是迄今為止性能最佳的一種極化碼譯碼算法，并且具有較低的譯碼復(fù)雜度能。

3.1 SCL譯碼算法

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

3.2 CRC校驗(yàn)

這里將加入CRC校驗(yàn)碼后的極化碼詳細(xì)編譯碼描繪如圖1所示。

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

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

4 半并行硬件譯碼結(jié)構(gòu)

在硬件實(shí)現(xiàn)上，經(jīng)典SC譯碼單元有幾種典型的譯碼結(jié)構(gòu)，比如樹形結(jié)構(gòu)、線性結(jié)構(gòu)、半平行結(jié)構(gòu)。下面詳細(xì)介紹本文所采用的半平行結(jié)構(gòu)。

圖2為N=8時(shí)的SC譯碼FFT結(jié)構(gòu)，該結(jié)構(gòu)是CA-SCL譯碼結(jié)構(gòu)的基礎(chǔ)。其蝶形算法可應(yīng)用于硬件實(shí)現(xiàn)的“從右往左”蝶形算法。從信道層開始，按照順序依次計(jì)算節(jié)點(diǎn)的LLR值并存儲(chǔ)在起來(lái)作為中間LLR供后面計(jì)算調(diào)用，避免了在硬件中進(jìn)行遞歸調(diào)用，同時(shí)能達(dá)到與遞歸算法相同的復(fù)雜度，如圖2中加粗線條為一比特計(jì)算過(guò)程。

圖2 基于蝶形圖的典型FFT結(jié)構(gòu)

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

表1 半平行譯碼結(jié)構(gòu)時(shí)序表

如表1所示，以碼長(zhǎng)N=8的SC譯碼為例，在半平行結(jié)構(gòu)中只使用了2（N4）個(gè)PE，整個(gè)譯碼周期中PE單元基本上都同時(shí)工作，使得利用率高，實(shí)現(xiàn)資源占用率低。

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

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

相較于全平行的譯碼結(jié)構(gòu)，半平行結(jié)構(gòu)的譯碼速度因子為

對(duì)于CA-SCL譯碼算法，若L為列表寬度，那么總的PE單元數(shù)量為L(zhǎng)P。

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

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

在本次的譯碼器設(shè)計(jì)中，設(shè)置條件為碼長(zhǎng)N=1024，碼率是R=1/2，信道挑選方法為BEC方法，列表寬度L=32，采用LTE協(xié)議建議的24位CRC檢驗(yàn)碼，其生成多項(xiàng)式為對(duì)譯碼器中的數(shù)據(jù)進(jìn)行8比特量化，路徑度量值進(jìn)行12比特量化。對(duì)譯碼過(guò)程中發(fā)生的溢出采用截?cái)嗵幚恚沟梦粚挷粫?huì)逐級(jí)遞增，在僅有較小性能損失的情況下，就可大大簡(jiǎn)化了譯碼器的設(shè)計(jì)復(fù)雜度。

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

在實(shí)現(xiàn)半平行結(jié)構(gòu)譯碼開始之前，要解決的是LLR存儲(chǔ)結(jié)構(gòu)問題。先將信道LLR分組，存入位寬為64，深度為256的RAM中作為初始LLR，即圖中的LLR_based RAM。

5.2 LLR存儲(chǔ)結(jié)構(gòu)

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

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

因?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ù)的輸出。

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

以N=8的雙PE結(jié)構(gòu)的半平行設(shè)計(jì)為例，圖4即為N=8，P=2的LLR存儲(chǔ)器結(jié)構(gòu)。

5.3 LLR計(jì)算模塊

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

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

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

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

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

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

5.5 部分和更新模塊

圖7為部分和更新模塊硬件框圖。其中虛線部分為部分和項(xiàng)的存儲(chǔ)結(jié)構(gòu)，指針只讀取其中實(shí)現(xiàn)框內(nèi)的存儲(chǔ)單元。

圖7 路徑度量值模塊硬件結(jié)構(gòu)

根據(jù)前面討論可知g函數(shù)的計(jì)算中需要部分和的輸入，所以需要在每個(gè)碼字被估計(jì)出來(lái)之后對(duì)部分和項(xiàng)進(jìn)行更新，為了不影響系統(tǒng)吞吐率，我們采用寄存器進(jìn)行存儲(chǔ)，觀察譯碼蝶形圖，每個(gè)碼字的譯碼最多同時(shí)利用N/2個(gè)比特的部分和，所以本文為了節(jié)省硬件資源，采用N/2 bit的寄存器長(zhǎng)度，每次更新都對(duì)寄存器進(jìn)行清零。

5.6 CRC串行譯碼模塊

本文CRC譯碼模塊采用的是串行逆序譯碼結(jié)構(gòu)，這是因?yàn)樵诼窂交謴?fù)模塊譯出來(lái)的信息比特為逆序排列，逆序的CRC校驗(yàn)碼是在逆序信息比特序列前面，且序列為串行輸出。因此，使用此結(jié)構(gòu)，與并行譯碼相比不僅減少了資源消耗，所需時(shí)間也不會(huì)發(fā)生改變。該模塊如圖8所示使用了24個(gè)寄存器，這些寄存器是用于存放CRC檢驗(yàn)碼。解碼開始，前24個(gè)時(shí)鐘，按順序?qū)?4個(gè)CRC校驗(yàn)碼分別存入24個(gè)寄存器中。而從第25個(gè)數(shù)據(jù)將按下圖的數(shù)據(jù)流向進(jìn)行計(jì)算，根據(jù)生成多項(xiàng)式生成加法器。整個(gè)結(jié)構(gòu)如圖8所示。

圖8 CRC串行逆序譯碼模塊

6 譯碼器綜合結(jié)果與分析

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

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

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

在本文設(shè)計(jì)中，碼長(zhǎng)為1024，譯碼器的工作頻率為150MHz。譯碼器平均時(shí)延為0.040ms，所以吞吐率可以達(dá)到由于系統(tǒng)用兩個(gè)時(shí)鐘存儲(chǔ)更新LLR，因此總的時(shí)延可以計(jì)算如式（9）：

根據(jù)譯碼結(jié)果，本文設(shè)計(jì)的譯碼算法譯出一個(gè)碼字大概需要6000個(gè)時(shí)鐘周期，與理論值5120個(gè)時(shí)鐘周期相差不大，而系統(tǒng)面積的占用率僅為7%。

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

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

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

7 結(jié)語(yǔ)

對(duì)碼長(zhǎng)為1024的極化碼采用了性能優(yōu)良的CA-SCL譯碼算法，在FPGA下設(shè)計(jì)實(shí)現(xiàn)，對(duì)每條候選路徑運(yùn)用半平行計(jì)算的硬件架構(gòu)，相較于平行結(jié)構(gòu)大幅減少了系統(tǒng)硬件資源占用，完成了對(duì)該算法占用較大系統(tǒng)面積的優(yōu)化，在此情形下的吞吐率表現(xiàn)并沒有達(dá)到理想狀況。接下來(lái)對(duì)如何進(jìn)一步在速度與面積之間取得平衡，來(lái)提高系統(tǒng)頻率降低平均時(shí)延，是后續(xù)主要的研究方向。