丁 冉 仰楓帆

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

1 引言

極化碼（polar code）是 Arikan［1］在 2008年首次提出的一種基于信道極化理論［2］的新的信道編碼。作為新的糾錯(cuò)編碼，極化碼因其簡(jiǎn)潔的構(gòu)造和有效的編譯碼方法而得到廣泛關(guān)注［3］。同時(shí)極化碼被證明在二進(jìn)制離散無記憶對(duì)稱信道上能達(dá)到香農(nóng)極限［4］，現(xiàn)在也被應(yīng)用于 AWGN（Additive White Gaussian Noise）信道等其他相關(guān)信道環(huán)境中［5］。從實(shí)踐的角度來看，Arikan在［1］中采用的SC譯碼方法的復(fù)雜度是ο(NlogN)，相比于Turbo和LDPC碼，其復(fù)雜度較低可行性較高，基于SC方法的譯碼器在硬件實(shí)現(xiàn)方面具有很大的應(yīng)用潛力［6～8］；Tal和Vardy針對(duì)Arikan的SC類算法提出了一種SCL（Successive Cancellation List）算法［9］，其克服了SC算法的錯(cuò)誤傳播問題，在此譯碼方法下，極化碼的性能接近于ML（Maximum Likelihood）限。

2 極化碼構(gòu)造和SCL譯碼原理

極化碼屬于線性分組碼［10］的一種。假設(shè)信道為二進(jìn)制離散對(duì)稱信道，極化碼的碼長(zhǎng)N=2n，用u=(u0，u1，…，uN-1) ，X=(x0，x1，…，xN-1) 表 示 輸 入序列和碼字，生成矩陣G為矩陣F的n次Kroneck?er積 F?n的列置換G=RNF?n，RN為置換陣，矩陣，則編碼碼字為x=uG，碼字x經(jīng)過N個(gè)獨(dú)立的子信道傳輸后在接收端得到信道輸出序列為 y=(…，yN-1)。在接收端采用SCL（Succes?sive Cancellation List）譯碼方法對(duì) y進(jìn)行譯碼得到輸入信號(hào)的估計(jì) (u^0，u^1，…，u^N-1)。

SCL譯碼算法的基本思想是在極化碼形成的一棵滿二叉樹上，按照后驗(yàn)概率最大原則尋找最合適路徑得到譯碼序列。碼長(zhǎng)為N的極化碼形成的碼樹的高度為N，根節(jié)點(diǎn)的深度為1，葉子節(jié)點(diǎn)的深度為N。樹中的每個(gè)節(jié)點(diǎn)代表一個(gè)比特，第i層中共有2i-1個(gè)節(jié)點(diǎn)，表示給定所有可能值的情況下比特ui的取值結(jié)果。深度為d的節(jié)點(diǎn)與深度為d+1的節(jié)點(diǎn)間有兩條邊相連，分別代表ud=0和取ud=1的兩條路徑。在樹的每一層，根據(jù)每條路徑的路徑度量值的大小，進(jìn)行路徑的排序、選擇和淘汰。路徑的度量值定義為式（1）。從根節(jié)點(diǎn)開始，當(dāng)某層的路徑數(shù)目大于L時(shí)，在該層只保留度量值前L位的路徑進(jìn)行下一層的延伸，下一層的路徑度量值更新計(jì)算公式如式（2）所示，一直延伸至葉子節(jié)點(diǎn)，此時(shí)選擇此層中路徑度量值最大的路徑作為最后的譯碼結(jié)果。L為路徑的搜索列表寬度，當(dāng)路徑數(shù)大于L時(shí)，每層保留L條后，下一層延伸時(shí)總是需要計(jì)算2L個(gè)路徑的度量值。

3 SCL譯碼器整體架構(gòu)

本次設(shè)計(jì)的碼長(zhǎng)為N=1024，搜索列表寬度L=32，SCL譯碼器整體架構(gòu)如圖1所示，其中包含三個(gè)主要模塊：譯碼模塊、路徑恢復(fù)模塊和輸入輸出模塊。輸入輸出模塊主要有包含輸入信息的信道信息Ram和包含輸出的譯碼結(jié)果Ram。譯碼模塊是譯碼器的核心模塊，承擔(dān)SCL算法各個(gè)譯碼環(huán)節(jié)的實(shí)現(xiàn)，其整體結(jié)構(gòu)如圖2所示。譯碼模塊主要分為L(zhǎng)LR值計(jì)算模塊LLR_calculate、反饋模塊Feed?back、度量值計(jì)算模塊Metric_calculate、度量值排序模塊Sort_top和整體控制模塊IDX_control。譯碼模塊的輸入是LLR值，輸出是路徑的排序結(jié)果，排序結(jié)果先存入路徑Ram中，等到1024個(gè)比特都譯碼結(jié)束時(shí)，路徑恢復(fù)模塊再?gòu)穆窂絉am中讀路徑排序結(jié)果，并根據(jù)此結(jié)果提取相應(yīng)的碼字，存入譯碼結(jié)果Ram。

圖1 SCL譯碼器整體架構(gòu)圖

圖2 譯碼器譯碼模塊整體架構(gòu)圖

4 SCL譯碼器分模塊具體結(jié)構(gòu)設(shè)計(jì)

4.1 LLR值計(jì)算模塊

本次設(shè)LLR計(jì)算模塊用來計(jì)算度量值更新式（2）中的頂層LLR值)，此LLR的計(jì)算與SC算法中相同，采用蝶形遞歸形式［1］。由LLR值的遞歸算法式（3）可知，單個(gè)LLR值的計(jì)算分為f和g兩種運(yùn)算。兩種運(yùn)算的輸入相同，均為一對(duì)LLR值L1和L2，故可用同一個(gè)計(jì)算單元實(shí)現(xiàn)。其中g(shù)運(yùn)算根據(jù)反饋模塊提供的指數(shù)值u^2i-1的值決定結(jié)果為 L2-L1或 L2+L1，f運(yùn)算的數(shù)值是取 L1和 L2數(shù)值位的最小值，符號(hào)是兩數(shù)符號(hào)位的異或。圖3是單個(gè)LLR計(jì)算單元的結(jié)構(gòu)圖。L1和L2為數(shù)據(jù)輸入，u為指數(shù)值u^2i-1，f_gn為輸出的選擇控制信號(hào)，當(dāng)f_gn=0時(shí)選擇f運(yùn)算結(jié)果作為輸出，當(dāng)f_gn=1時(shí)選擇g運(yùn)算結(jié)果作為輸出。

圖3 單個(gè)LLR值計(jì)算單元結(jié)構(gòu)

所有的輸入信號(hào)的輸入都要受針對(duì)LLR的控制模塊LLR_control控制。圖4是LLR計(jì)算頂層模塊結(jié)構(gòu)圖。LLR計(jì)算頂層結(jié)構(gòu)主要分為L(zhǎng)LR計(jì)算模塊和相關(guān)控制模塊。LLR計(jì)算模塊為L(zhǎng)個(gè)PE（Processing Element）組成的陣列，每個(gè)PE承擔(dān)單個(gè)LLR計(jì)算，其結(jié)構(gòu)如圖3所示。主要的控制模塊為L(zhǎng)LR_control模塊，其功能是為計(jì)算模塊選擇正確的輸入數(shù)據(jù)。由于本次設(shè)計(jì)中所有的LLR均存放在LLR_Mid_Ram中，故LLR_control模塊通過對(duì)Ram讀寫地址的控制得到正確位置上的數(shù)據(jù)和將更新的結(jié)果寫入正確的地址單元中。

圖4 LLR值計(jì)算頂層模塊結(jié)構(gòu)

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

度量值計(jì)算模塊用來完成式（2）的計(jì)算。由于路徑數(shù)L=32，故度量值更新時(shí)會(huì)得到64條路徑度量值。由計(jì)算公式可知，度量值計(jì)算時(shí)，需要根據(jù)當(dāng)前路徑對(duì)應(yīng)的比特ui分兩種情況討論，分別記為U0_PM和U1_PM。當(dāng)ui=0時(shí)，度量值計(jì)算為式（4）所示。當(dāng)ui=1時(shí)，度量值計(jì)算需要考慮第i位若為凍結(jié)位的特殊情況，為式（5）所示。

若ui=1且第i位是凍結(jié)位時(shí)，直接將度量值置為所能表示的最小值，即所有位全是1。圖5是度量值計(jì)算模塊的頂層結(jié)構(gòu)，信號(hào)Pre_PM是此路徑的上一層對(duì)應(yīng)的度量值PM()，其從路徑度量值存儲(chǔ)Ram中讀取。計(jì)算時(shí)需要讀取信道的狀態(tài)信息，其存于Bit Rom中。在將兩個(gè)度量值U0_PM和U1_PM均計(jì)算出后，對(duì)其進(jìn)行初步的排序，得到較大值Max_metric和較小值Min_metric以及對(duì)應(yīng)的選擇比特Umax和Umin，并將較大值依次放入前32個(gè)位置，較小值依次放入后32個(gè)位置上。這樣做是由于錯(cuò)誤的凍結(jié)位給度量值帶來的影響要大過不同路徑帶來的影響，將初步排序結(jié)果的大小值分前32位和后32位有序放置，將縮短后續(xù)的排序時(shí)間。

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

4.3 度量值排序模塊

度量值排序模塊采用常見的冒泡排序法，將相鄰的度量值兩兩一組，送入單個(gè)排序單元中，進(jìn)行兩個(gè)數(shù)的比較和交換。由于度量值模塊產(chǎn)生了64個(gè)度量值，故完成一輪排序需要32個(gè)排序單元。

在排序模塊中對(duì)應(yīng)的路徑選擇比特也需要根據(jù)度量值的排序結(jié)果進(jìn)行排序，同時(shí)還需要對(duì)每條路徑加比特索引，以供路徑恢復(fù)模塊針對(duì)每條路徑提取相應(yīng)碼字。

4.4 反饋模塊

反饋模塊用來提供LLR值計(jì)算中g(shù)運(yùn)算的指數(shù)值u^2i-1。反饋模塊對(duì)u^2i-1的計(jì)算原理與LLR值計(jì)算原理相同，但更新方向相反，故兩者頂層模塊結(jié)構(gòu)相同，設(shè)計(jì)思路類似，均分為控制模塊和計(jì)算模塊。計(jì)算模塊同樣是由L個(gè)節(jié)點(diǎn)反饋信息更新單元組成的計(jì)算陣列。控制模塊產(chǎn)生對(duì)應(yīng)的讀寫控制信號(hào)，為計(jì)算模塊提供正確的輸入并將更新后的結(jié)果存入正確的地址單元中。每當(dāng)產(chǎn)生新的碼字ui時(shí)，先存入頂層，再?gòu)捻攲拥降讓右来伟磳痈隆８碌姆绞礁鶕?jù)節(jié)點(diǎn)類型的不同也有兩種，以N=8為例，如圖6所示，圖中有f節(jié)點(diǎn)和g節(jié)點(diǎn)。若當(dāng)前節(jié)點(diǎn)是f節(jié)點(diǎn)，則直接將當(dāng)前層數(shù)據(jù)存入下一層的f節(jié)點(diǎn)，若當(dāng)前節(jié)點(diǎn)是g節(jié)點(diǎn)，則將當(dāng)前層數(shù)據(jù)直接存入下一層的g節(jié)點(diǎn)，并將下一層f節(jié)點(diǎn)的內(nèi)容取出與當(dāng)前數(shù)據(jù)模二加后，再重新存入下一層f節(jié)點(diǎn)。圖7為單個(gè)節(jié)點(diǎn)反饋信息更新單元結(jié)構(gòu)圖。flag信號(hào)是輸出結(jié)果選擇信號(hào)，flag=1時(shí)輸出g節(jié)點(diǎn)的值，flag=0時(shí)輸出f節(jié)點(diǎn)的值。flag信號(hào)由反饋模塊的控制單元提供。

圖6 N=8時(shí)反饋部分產(chǎn)生原理圖

圖7 單個(gè)節(jié)點(diǎn)反饋信息更新單元結(jié)構(gòu)

4.5 控制模塊

控制模塊由IDX索引控制寄存器和狀態(tài)機(jī)組成，主要控制功能由狀態(tài)機(jī)實(shí)現(xiàn)。譯碼器工作時(shí)，根據(jù)每個(gè)模塊的功能，設(shè)置每個(gè)狀態(tài)下的各個(gè)模塊開始或結(jié)束的標(biāo)志信號(hào)，在時(shí)序控制下，狀態(tài)機(jī)監(jiān)控中間進(jìn)程的標(biāo)識(shí)信號(hào)來完成狀態(tài)的轉(zhuǎn)換，保證模塊之間協(xié)同有序的工作。當(dāng)每次完成一輪狀態(tài)轉(zhuǎn)換后，IDX加1，表示進(jìn)行下一個(gè)比特的譯碼。直到1024個(gè)比特全部譯碼完畢時(shí)，IDX又清零，控制模塊啟動(dòng)路徑恢復(fù)模塊進(jìn)行工作。

4.6 路徑恢復(fù)模塊

路徑恢復(fù)模塊根據(jù)排序模塊提供的加了索引的路徑選擇比特進(jìn)行對(duì)應(yīng)路徑的碼字提取。排序結(jié)果按從后往前順序輸入路徑恢復(fù)模塊，每條路徑按照自己的索引，從最后一位比特的位置開始讀取排序結(jié)果，提取相應(yīng)的碼字，然后再根據(jù)排序的結(jié)果，更新下一次要讀的索引，然后重復(fù)上述步驟一直讀到第一位信息比特時(shí)結(jié)束。

5 譯碼器FPGA實(shí)現(xiàn)結(jié)果和性能分析

本次設(shè)計(jì)實(shí)現(xiàn)使用的是Altera公司Stratix V系列的5SGXEA7N2F45C1芯片，在Quartus II下的綜合后的資源占用如表1所示。

表1 SCL譯碼器綜合后資源占用表

譯碼器的吞吐率也是衡量其性能的重要指標(biāo)之一，本次設(shè)計(jì)中，譯碼器經(jīng)過大約40000個(gè)時(shí)鐘后輸出全部1024個(gè)比特，故譯碼時(shí)延為1/(300×106)×4×104≈0.15ms ，其 吞 吐 率 為1024b/(0.15×10-3)s≈6.5Mbps。

圖8是N=1024，L=32，采用SCL譯碼器，在信噪比為0～3dB時(shí)的誤碼率和誤幀率曲線圖，其中未量化的為理想曲線，8比特量化的為實(shí)際曲線。由圖可知兩者的曲線十分接近，在信噪比為1～2dB時(shí)，量化后的BER/FER只比理論值多0.1dB左右，驗(yàn)證了譯碼器性能的可靠性。

圖8 SCL譯碼器的FER/BER曲線

6 結(jié)語(yǔ)

本文基于極化碼的SCL譯碼算法，設(shè)計(jì)N=1024，L=32時(shí)的基于此算法的譯碼器，并完成了在FPGA上的實(shí)現(xiàn)，得到了6.5Mbps的吞吐率。此譯碼器在保證芯片面積和功耗較低的情況下，保持了較高的譯碼速率。

［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）：3051-3073.

［2］Arikan E.Channel combining and splitting for cutoff rate improvement［C］//Information Theory，2005.ISIT 2005.Proceedings.International Symposium on.IEEE，2005：671-675.

［3］N.Hussami，S.B.Korada，and R.Urbanke.Performance of polar codes for channel and source coding［C］//Internation?al Symposium on Information Theory，2009：1488-1492.

［4］E.Sasoglu，E.Telatar，and E.Arikan.Polarization for arbi?trary discrete memoryless channels［C］//Proc.IEEE Infor?mation Theory Workshop ITW，2009：144-148.

［5］E.Abbe and A.Barron.Polar code schemes for AWGN channel［C］//Information Theory Proceedings（ISIT），IEEE International Symposium，2011：194-198.

［6］Leroux C，Tal I，Vardy A，and Gross W.J.Hardware archi?tectures for successive cancellation decoding of polar codes［C］//Proc.IEEE int acoustics，speech and signal process?ing（ICASSP）conf，2011：1665-1668.

［7］Leroux C ，Raymond A.J，Sarkis etc，A semi-parallel suc?cessive-cancellation decoder of polar codes［C］//IEEE Transactions on Signal Processing，2013，61（2）：289-299.

［8］C.Zhang and K.KParhi.Low-latency sequential and over?lapped architectures for successive cancellation polar de?coder［J］.IEEE Transactions on Signal Processing，2013，61（10）：2429-2441.

［9］Tal I，Vardy A.List decoding of polar codes［C］//Informa?tion Theory Proceedings（ISIT），2011 IEEE International Symposium on.IEEE，2011：1-5.

［10］樊昌信，曹麗娜.通信原理［M］.國(guó)防工業(yè)出版社，2010（第六版）：335-340.

FAN Changxin，CAO Lina.Principles of Communication［M］.National Defense Industry Press，2010（Sixth Edi?tion）：335-340.

［11］Leroux C，Raymond A.J，Sarkis G，Tal I，Vardy A，and Gross W.J.Hardware implementation of successive can?cellation decoder of polar codes.Journal of Signal Pro?cessing Systems，2012，69（3）：305-315.