極化碼SCL譯碼器設(shè)計?

丁 冉 仰楓帆

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

1 引言

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

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

極化碼屬于線性分組碼［10］的一種。假設(shè)信道為二進制離散對稱信道，極化碼的碼長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個獨立的子信道傳輸后在接收端得到信道輸出序列為 y=(…，yN-1)。在接收端采用SCL（Succes?sive Cancellation List）譯碼方法對 y進行譯碼得到輸入信號的估計 (u^0，u^1，…，u^N-1)。

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

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

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

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

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

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

4.1 LLR值計算模塊

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

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

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

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

4.2 度量值計算模塊

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

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

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

4.3 度量值排序模塊

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

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

4.4 反饋模塊

反饋模塊用來提供LLR值計算中g(shù)運算的指數(shù)值u^2i-1。反饋模塊對u^2i-1的計算原理與LLR值計算原理相同，但更新方向相反，故兩者頂層模塊結(jié)構(gòu)相同，設(shè)計思路類似，均分為控制模塊和計算模塊。計算模塊同樣是由L個節(jié)點反饋信息更新單元組成的計算陣列?？刂颇K產(chǎn)生對應的讀寫控制信號，為計算模塊提供正確的輸入并將更新后的結(jié)果存入正確的地址單元中。每當產(chǎn)生新的碼字ui時，先存入頂層，再從頂層到底層依次按層更新。更新的方式根據(jù)節(jié)點類型的不同也有兩種，以N=8為例，如圖6所示，圖中有f節(jié)點和g節(jié)點。若當前節(jié)點是f節(jié)點，則直接將當前層數(shù)據(jù)存入下一層的f節(jié)點，若當前節(jié)點是g節(jié)點，則將當前層數(shù)據(jù)直接存入下一層的g節(jié)點，并將下一層f節(jié)點的內(nèi)容取出與當前數(shù)據(jù)模二加后，再重新存入下一層f節(jié)點。圖7為單個節(jié)點反饋信息更新單元結(jié)構(gòu)圖。flag信號是輸出結(jié)果選擇信號，flag=1時輸出g節(jié)點的值，flag=0時輸出f節(jié)點的值。flag信號由反饋模塊的控制單元提供。

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

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

4.5 控制模塊

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

4.6 路徑恢復模塊

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

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

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

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

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

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

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

6 結(jié)語

本文基于極化碼的SCL譯碼算法，設(shè)計N=1024，L=32時的基于此算法的譯碼器，并完成了在FPGA上的實現(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］.國防工業(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.