魏一鳴 仰楓帆

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

1 引言

極化碼［1］是一種基于信道極化現(xiàn)象的信道編碼，是由土耳其教授Erdal Arikan在2007年首次提出，并指出其為當(dāng)下唯一可理論證明達(dá)到香農(nóng)極限［2］的信道編碼，且具有較低的編譯碼復(fù)雜度，由此學(xué)術(shù)界掀起了極化碼的研究熱潮。隨后，在Ari?kan的SC譯碼算法［1］的基礎(chǔ)上，有學(xué)者對(duì)其進(jìn)行了改進(jìn)，提出了 SCL［3］、CA-SCL［4］等譯碼算法，尤其是CA-SCL譯碼算法，獲得了優(yōu)于最大似然算法的性能［5］。與此同時(shí)，為了探尋極化碼工程上實(shí)現(xiàn)的可能性，眾多學(xué)者開(kāi)始致力于極化碼硬件實(shí)現(xiàn)并開(kāi)始提出了一些SC譯碼硬件結(jié)構(gòu)［6～10］。而其中的半并行結(jié)構(gòu)［8］僅以較小的吞吐量為代價(jià)，大幅減小了系統(tǒng)面積，在后續(xù)提出的 SCL［11～12］、CA-SCL［13］硬件結(jié)構(gòu)中也均采用此結(jié)構(gòu)。作為性能最好的CA-SCL譯碼算法，列表寬度L很大程度上制約了該算法的性能，而隨著L的增大，在半并行結(jié)構(gòu)下的系統(tǒng)資源將被大量消耗。本文所采用的單計(jì)算單元架構(gòu)使整個(gè)系統(tǒng)的計(jì)算單元保持為L(zhǎng)個(gè)，即每條候選路徑僅對(duì)應(yīng)一個(gè)計(jì)算單元，大大減少了系統(tǒng)面積。為了彌補(bǔ)此設(shè)計(jì)對(duì)吞吐率造成的影響，核心譯碼模塊采用流水線技術(shù)，提高了系統(tǒng)工作頻率。

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

Arikan在研究信道的組合和拆分的過(guò)程中發(fā)現(xiàn)［14～15］，在將 N 個(gè)相互獨(dú)立的信道進(jìn)行組合和拆分后，系統(tǒng)的總體容量沒(méi)有發(fā)生改變，而總體截止速率得到了提升?；诖搜芯?，Arikan將N個(gè)相互獨(dú)立的完全相同的二進(jìn)制離散無(wú)記憶（B-DMC）信道通過(guò)組合合并為信道WN，并將WN拆分為N個(gè)相關(guān)子信道∶1≤i≤N }，隨著 N 的不斷變大，其子信道容量)}趨向0或1兩個(gè)極端，此現(xiàn)象便被稱為信道極化現(xiàn)象，過(guò)程如圖1所示。通常地，我們使用信道容量趨向1的子信道傳送信息比特，而使用信道容量趨向0的子信道傳送收發(fā)雙方均已知的固定比特，其默認(rèn)值為0。

圖1 信道極化過(guò)程

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

3 極化碼的編譯碼算法

3.1 極化碼編碼方法

極化碼作為一種線性分組碼，其碼字的產(chǎn)生同樣需要一個(gè)生成矩陣：，其中為經(jīng)過(guò)信道挑選并混入固定比特的初始信息，為生成的碼字。根據(jù)信道的組合方法［1］可以迭代地得到生成矩陣GN=其中 F為核矩陣F?n為 F 的 n階Kronecker積［1］，n=log2N 。 BN為比特反轉(zhuǎn)操作：令xi=Vπ(i)，其中x的下標(biāo)i的二進(jìn)制 表 示 為 (b1b2…bn)， 轉(zhuǎn) 換 關(guān) 系 為i=·2n-k)+1。經(jīng)過(guò)比特反轉(zhuǎn)操作 π后，π(i)的二進(jìn)制表示為(bnbn-1…b1)。

3.2 極化碼CA-SCL譯碼算法

極化碼發(fā)展至今已有多種譯碼方法，其中CA-SCL譯碼算法性能最佳，且具有較低的譯碼復(fù)雜度。由于CA-SCL算法是在SCL算法的基礎(chǔ)上添加CRC檢驗(yàn)位［19］以提高譯碼性能，所以該算法也可以說(shuō)由三部分組成。

3.2.1 SC譯碼算法部分

圖2 L=8時(shí)SC譯碼流程

圖中，f節(jié)點(diǎn)和g節(jié)點(diǎn)的計(jì)算公式使用最小和算法［6，22］表示為

該算法僅含有加減運(yùn)算，適合用于硬件實(shí)現(xiàn)。其中u^s為已經(jīng)譯出的碼字的部分和。在硬件實(shí)現(xiàn)中往往將兩者融合為一個(gè)節(jié)點(diǎn)，被稱為一個(gè)計(jì)算單元（Processing Element，PE），并通過(guò)復(fù)用器來(lái)實(shí)現(xiàn)二者的功能轉(zhuǎn)換。

3.2.2 SCL譯碼算法部分

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

初始列表中只有一條空路徑，且PM(?)=0。我們可以將此過(guò)程表述為一個(gè)深度為N的滿二叉樹(shù)，一個(gè)N=4，L=2的譯碼過(guò)程如圖2所示，圖中的數(shù)字為當(dāng)前階段的路徑度量值PM。

圖3 N=4，L=2SCL譯碼碼樹(shù)圖

3.2.3 CRC校驗(yàn)部分

假設(shè)編碼器輸入為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)行由大到小排序，并以此順序依次進(jìn)入解CRC碼單元。當(dāng)譯出的序列不滿足CRC關(guān)系時(shí)，該單元將告知SCL譯碼器，繼續(xù)傳送下一個(gè)序列。就這樣直到輸入解CRC碼單元的序列通過(guò)CRC校驗(yàn)，譯碼結(jié)束，解除CRC校驗(yàn)碼，得到的輸出序列即為CA-SCL譯碼器譯出的碼字。

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

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

在本次的譯碼器設(shè)計(jì)中，碼長(zhǎng)為1024，碼率為1/2，信道挑選方法為BEC方法，列表寬度L=32，采用LTE協(xié)議建議的24位CRC檢驗(yàn)碼，其生成多項(xiàng)式為g(D)=D24+D23+D18+D17+D14+D11+D10+D7+D6+D5+D4+D3+D+1。對(duì)譯碼器中的數(shù)據(jù)進(jìn)行8比特量化，路徑度量值進(jìn)行12比特量化，對(duì)譯碼過(guò)程中發(fā)生的溢出采用截?cái)嗵幚?，使得位寬不?huì)逐級(jí)遞增，大大簡(jiǎn)化了譯碼器的設(shè)計(jì)復(fù)雜度，且只有極小的性能損失。整體結(jié)構(gòu)主要包括以下幾個(gè)頂層模塊：LLR計(jì)算模塊（LLR_top）、修正模塊（Corrected）、度量值計(jì)算模塊（Metric_top）、度量值排序模塊（Sort_top）、反饋模塊（Feedback）、控制模塊（Controller）路徑恢復(fù)模塊（Path_recover）、CRC串行譯碼模塊（CRC），如圖4所示。在譯碼開(kāi)始之前，首先將信道LLR兩兩分組，存入位寬為16，深度為512的RAM中作為初始LLR，即圖中的LLR_based RAM。

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

4.2 LLR計(jì)算模塊

模塊的整體結(jié)構(gòu)如圖5所示，由LLR控制單元和計(jì)算單元組成。如圖2所示在單次頂層LLR的計(jì)算中，每一層都僅激活 f或g節(jié)點(diǎn)中的一種，所以令總控制模塊生成位寬為10的狀態(tài)寄存器IDX，最低位對(duì)應(yīng)頂層，最高位對(duì)應(yīng)信道層，IDX(i)=0表示第i層處于工作狀態(tài)的是 f節(jié)點(diǎn)，否則為g節(jié)點(diǎn)。當(dāng)計(jì)算下一比特對(duì)應(yīng)的頂層LLR時(shí)，在時(shí)鐘的控制下令I(lǐng)DX加1，即可進(jìn)入當(dāng)前狀態(tài)。譯碼開(kāi)始時(shí)，在IDX的控制下讀取信道LLR，將計(jì)算后的結(jié)果存于中間值存儲(chǔ)器LLR MID RAM中。當(dāng)讀地址到達(dá)512，表示信道LLR讀取完畢，開(kāi)始讀中間值，由此不斷計(jì)算，直到得出頂層LLR的值。

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

由于本設(shè)計(jì)采用單計(jì)算單元架構(gòu)，所以針對(duì)每一條路徑都僅使用1個(gè)PE進(jìn)行相應(yīng)的LLR計(jì)算。本文設(shè)計(jì)的系統(tǒng)中，32個(gè)PE處于并行處理狀態(tài)，即同時(shí)處理來(lái)自不同路徑的計(jì)算請(qǐng)求，最終同時(shí)計(jì)算得到頂層LLR。單個(gè)PE的硬件結(jié)構(gòu)如圖6所示。

圖6 計(jì)算單元PE硬件結(jié)構(gòu)

其中，f節(jié)點(diǎn)的輸出選擇信號(hào)sign為sgn(L2+L1)⊕sgn(L2-L1)、sgn(L1)和sgn(L2)三者的拼接，其8種狀態(tài)所對(duì)應(yīng)的輸出如下：1）000：L1；2）001：L1；3）010：L1；4）011：L1；5）100：L1；6）101：L1；7）110：L1；8）111：L1。

由于g節(jié)點(diǎn)的計(jì)算由加（減）法構(gòu)成，因此在計(jì)算的過(guò)程中就存在溢出的可能性，如果不加以處理，隨著計(jì)算層數(shù)的增加，LLR的位寬會(huì)變得越來(lái)越大。對(duì)此，我們對(duì)g節(jié)點(diǎn)輸出的結(jié)果均除以2。

4.3 修正模塊

在進(jìn)行這樣的處理之后，g節(jié)點(diǎn)的計(jì)算結(jié)果與預(yù)期結(jié)果不同，會(huì)導(dǎo)致最后得到的頂層LLR與預(yù)期值相差2n倍，n為在一次計(jì)算頂層LLR過(guò)程中所經(jīng)過(guò)路徑含有g(shù)節(jié)點(diǎn)的數(shù)量，即IDX信號(hào)中1個(gè)個(gè)數(shù)。因此，在頂層LLR計(jì)算完成后與進(jìn)行度量值計(jì)算前需要添加一個(gè)修正模塊還原正確的LLR值。所以，該模塊的功能為根據(jù)IDX信號(hào)中1的個(gè)數(shù)n對(duì)LLR做乘2n處理。如果最終得到的LLR新值已經(jīng)超過(guò)了度量值的位寬，則輸出溢出信號(hào)給后面的度量值計(jì)算模塊。

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

如圖7所示為路徑度量值計(jì)算模塊的硬件結(jié)構(gòu)圖。

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

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

在計(jì)算出候選比特為0和1格子的路徑度量值后，使用一個(gè)選擇器輸出其中的較大值和較小值以及他們對(duì)應(yīng)的候選比特。所以在2L條路徑送入排序模塊之前，我們可以對(duì)齊進(jìn)行初步排序，根據(jù)頂層LLR的符號(hào)位，將路徑i分支出來(lái)的兩個(gè)度量值中較大的放在第i個(gè)位置，較小的放在第i+L個(gè)位置。這樣做是因?yàn)楫?dāng)前錯(cuò)誤比特對(duì)度量值的影響往往比不同路徑對(duì)度量值帶來(lái)的影響要大，當(dāng)將數(shù)據(jù)送入排序模塊進(jìn)行排序后可以顯著減小排序算法的收斂時(shí)間。

4.5 排序模塊

對(duì)路徑度量值計(jì)算模塊傳送過(guò)來(lái)的條路徑進(jìn)行冒泡排序，將前32個(gè)輸出路徑度量值結(jié)果存于Metric_reg寄存器中，用于下次路徑度量值的計(jì)算。同時(shí)輸出結(jié)果格式為：最高位代表所選擇的比特，后五位代表所屬的上一層的路徑，這樣有利于路徑恢復(fù)模塊從排序結(jié)果恢復(fù)出路徑，將此結(jié)果輸出至反饋模塊。

4.6 反饋模塊

在經(jīng)過(guò)排序模塊之后得到了32條候選路徑所對(duì)應(yīng)的頂層估計(jì)比特和相應(yīng)的路徑索引，反饋模塊的作用就是據(jù)此更新下一次計(jì)算所需要的g節(jié)點(diǎn)u^s的值，并把結(jié)果存入RAM（圖4中Feedback RAM），最終反饋至LLR計(jì)算模塊輸入端。反饋模塊的結(jié)構(gòu)與LLR的計(jì)算結(jié)構(gòu)相似，數(shù)據(jù)的流動(dòng)方向是相反的，仍以N=8為例，如圖8所示。

圖8 N=8時(shí)反饋模塊結(jié)構(gòu)

計(jì)算規(guī)則如下：1）新生成的比特先存入頂層，如圖中最左側(cè)所示；2）判斷當(dāng)前層的IDX值，如果為0則將當(dāng)前層的數(shù)據(jù)存入下一層的 f單元。如果是1，則將當(dāng)前層的數(shù)據(jù)存入下一層的g單元，并取出 f中的數(shù)據(jù)與當(dāng)前層數(shù)據(jù)相加后繼續(xù)存入f單元，然后以規(guī)則2）繼續(xù)下一層的計(jì)算。這里的f和g單元只有存儲(chǔ)功能，并沒(méi)有LLR計(jì)算模塊中f和g單元的計(jì)算功能。令LLR計(jì)算模塊中數(shù)據(jù)的讀地址和u^s的讀地址相同，保證了當(dāng)前計(jì)算g節(jié)點(diǎn)的正確性。

4.7 路徑恢復(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ù)此步驟直到讀到第一位比特，最終將輸出的碼字發(fā)送到Result_RAM中，其深度為512，數(shù)據(jù)位寬為32。

4.8 控制模塊

由控制模塊生成的IDX信號(hào)實(shí)質(zhì)上控制這整個(gè)譯碼器的工作狀態(tài)，當(dāng)IDX=1111111111，下一狀態(tài)為全0表示譯碼器已完成全部比特的譯碼。在狀態(tài)機(jī)的控制下，控制模塊通過(guò)嚴(yán)格的時(shí)序保證各個(gè)模塊之間協(xié)同有序的工作。

4.9 CRC串行譯碼模塊

由于恢復(fù)模塊的原因，譯出來(lái)的信息比特以逆序排列，逆序的CRC校驗(yàn)碼在逆序信息比特序列前面，且序列為串行輸出。故CRC譯碼模塊采用了串行逆序譯碼結(jié)構(gòu)，與并行譯碼相比減少了資源消耗而且所需時(shí)間并不會(huì)發(fā)生改變。該模塊如圖9所示使用了24個(gè)寄存器用于存放CRC檢驗(yàn)碼。譯碼開(kāi)始，前24個(gè)時(shí)鐘輸入的是CRC校驗(yàn)碼，按順序存入24個(gè)寄存器中，從第25個(gè)數(shù)據(jù)開(kāi)始按下圖的數(shù)據(jù)流向計(jì)算，根據(jù)生成多項(xiàng)式生成加法器。整個(gè)結(jié)構(gòu)如圖9所示。

圖9 CRC串行逆序譯碼模塊

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

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

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

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

如圖10所示，為對(duì)數(shù)據(jù)進(jìn)行8位定點(diǎn)量化、對(duì)路徑度量值進(jìn)行12位定點(diǎn)量化后的CA-SCL算法性能與浮點(diǎn)計(jì)算（未量化）的性能之間的比較。由于浮點(diǎn)數(shù)無(wú)法被EDA工具所綜合，在實(shí)現(xiàn)中必然要使用量化后的數(shù)據(jù)，并將其轉(zhuǎn)化為二進(jìn)制比特。在轉(zhuǎn)換的過(guò)程中損失了一定的計(jì)算精度，性能自然要比浮點(diǎn)計(jì)算差。在誤碼率BER=10-3時(shí)，二者性能相差大約0.1dB，故譯碼器的硬件實(shí)現(xiàn)也可以獲得接近于浮點(diǎn)計(jì)算的性能。

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

6 結(jié)語(yǔ)

對(duì)碼長(zhǎng)為1024的極化碼采用了公認(rèn)性能優(yōu)良的CA-SCL譯碼算法，對(duì)每條候選路徑運(yùn)用計(jì)算單元的硬件架構(gòu)，完成了對(duì)該算法占用較大系統(tǒng)面積的優(yōu)化，在此情形下的吞吐率表現(xiàn)并沒(méi)有達(dá)到理想狀況。為了進(jìn)一步在速度與面積之間取得平衡，后續(xù)將對(duì)大量調(diào)用的單計(jì)算單元結(jié)構(gòu)進(jìn)行優(yōu)化以減小關(guān)鍵路徑的長(zhǎng)度，從而提高系統(tǒng)頻率降低平均時(shí)延。

［1］Arikan E.Channel Polarization：A Method for Construct?ing Capacity-Achieving Codes for Symmetric Binary-In?put Memoryless Channels［J］.IEEE Transactions on Infor?mation 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 In?ternational Symposium on Information Theory Proceed?ings.IEEE，2011：1-5.

［4］Niu K，Chen K.CRC-Aided Decoding of Polar Codes［J］.IEEE Communications Letters，2012，16（10）：1668-1671.

［5］Niu K，Chen K，Lin J，et al.Polar codes：Primary con?cepts and practical decoding algorithms［J］.IEEE Commu?nications Magazine，2014，52（7）：192-203.

［6］Leroux C，Tal I，Vardy A，et al.Hardware architectures for successive cancellation decoding of polar codes［J］.2010，125（3）：1665-1668.

［7］Leroux C，Raymond A J，Sarkis G，et al.Hardware Imple?mentation of Successive Cancellation Decoders for Polar Codes［J］.Journal of Signal Processing Systems，2012，69（3）：305-315.

［8］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.

［9］Zhang C，Yuan B，Parhi K K.Reduced-latency SC polar decoderarchitectures［J］.ComputerScience，2011：3471-3475.

［10］Zhang C，Parhi K K.Low-Latency Sequential and Over?lapped Architectures for Successive Cancellation Polar Decoder［J］.IEEE Transactions on Signal Processing，2013，61（10）：2429-2441.

［11］Lin J，Xiong C，Yan Z.A High Throughput List Decoder Architecture for Polar Codes［J］.IEEE Transactions on Very Large Scale Integration Systems，2015，24（6）：2378-2391.

［12］Balatsoukas-Stimming A，Raymond A J，Gross W J，et al.Hardware Architecture for List Successive Cancella?tion Decoding of Polar Codes［J］.Circuits&Systems II Express Briefs IEEE Transactions on，2014，61（8）：609-613.

［13］Balatsoukas-Stimming A，Bastani Parizi M，Burg A.LLR-Based Successive Cancellation List Decoding of Po?lar Codes［J］.IEEE Transactions on Signal Processing，2015，63（19）：5165-5179.

［14］Arikan E.Systematic Polar Coding［J］.IEEE Communi?cations Letters，2011，15（8）：860-862.

［15］Arikan E.Channel combining and splitting for cutoff rate improvement［J］.IEEE Transactions on Information The?ory，2005，52（2）：628-639.

［18］Li H，Yuan J.A practical construction method for polar codes in AWGN channels［C］//Tencon Spring Confer?ence.IEEE，2013：223-226.

［19］Mori R，Tanaka T.Performance of polar codes with the construction using density evolution［J］.IEEE Communi?cations Letters，2009，13（7）：519-521.

［20］Tal I，Vardy A.How to Construct Polar Codes［J］.IEEE Transactions on Information Theory，2013，59（10）：6562-6582.

［21］Peterson W W，Brown D T.Cyclic Codes for Error Detec?tion［J］.Proceedings of the Ire，1961，49（1）：228-235.

［22］Fossorier M P C，Mihaljevic M，Imai H.Reduced com?plexity iterative decoding of low-density parity check codes based on belief propagation［J］.IEEE Transactions on Communications，1999，47（5）：673-680.