李怡 高軍萍 李琦 王嬌 王彤

摘要 在極化碼連續(xù)消除列表（SCL）算法中譯碼時(shí)延是提升譯碼性能的關(guān)鍵，度量排序是譯碼時(shí)延的重要部分。為了降低譯碼時(shí)度量排序的時(shí)間消耗，首次將并行全比較排序應(yīng)用到極化碼譯碼度量排序中，并提出一種簡化全比較（SPF）改進(jìn)結(jié)構(gòu)以降低硬件消耗。經(jīng)過數(shù)據(jù)分析表明，在硬件相差無幾的情況下，當(dāng)列表長度為8時(shí)，傳統(tǒng)剪切雙調(diào)排序結(jié)構(gòu)（PBS）的延時(shí)是簡化全比較（SPF）結(jié)構(gòu)的2.25倍。FPGA仿真的實(shí)驗(yàn)結(jié)果表明，簡化全比較（SPF）結(jié)構(gòu)具備排序延時(shí)低和硬件效率高的特點(diǎn)。

關(guān) 鍵 詞 極化碼;SCL譯碼;度量排序;并行算法;全比較

中圖分類號(hào) TN911.22? ? ?文獻(xiàn)標(biāo)志碼 A

An improved metrics sorter for SCL decoding of polar codes

LI Yi， GAO Junping， LI Qi， WANG Jiao， WANG Tong

（School of Electronics and Information Engineering， Hebei University of Technology， Tianjin 300401， China）

Abstract The successive cancellation list （SCL） decoding is an effective method for decoding polar codes. During SCL decoding， time consumption is significantly caused by metrics sorting. In order to reduce the sorting latency， parallel full comparison is applied for the first time to sort metrics of SCL decoding. We propose an improved SPF so to reduce hardware consumption. The latency of traditional pruned bitonic sorter （PBS） is 2.25 times that of our proposed simplified structure， when the list size is 8. With the analysis and the simulation of FPGA in our paper， we can prove that our simplified architecture can preserve the low-latency and get the high hardware efficiency.

Key words polar codes; SCL decoding; metrics sorting; parallel algorithm; full comparison

0 引言

應(yīng)用于5G控制信道的極化碼是一種基于信道極化現(xiàn)象的信道編碼方式，因其編譯碼復(fù)雜度低且理論上已證明可達(dá)信道容量，故而成為信道編碼領(lǐng)域的研究熱點(diǎn)[1-2]。極化碼的一種譯碼算法——連續(xù)消除列表（Successive Cancellation List，SCL）算法在對(duì)信息位比特進(jìn)行估計(jì)時(shí)，保留的L條路徑會(huì)擴(kuò)展為2L條候選路徑，每條候路徑都對(duì)應(yīng)一個(gè)度量值[3]。在SCL譯碼電路設(shè)計(jì)中，一個(gè)比較關(guān)鍵的問題是從2L條候選路徑中選出度量最小的L條路徑，該功能由度量排序器完成。因此，在SCL譯碼算法的譯碼電路中，度量排序器的設(shè)計(jì)至關(guān)重要[4]。

減少排序延時(shí)和硬件消耗是度量排序器設(shè)計(jì)的關(guān)鍵。為了降低排序時(shí)延，全雙調(diào)排序系統(tǒng)（Full Bitonic Sorter，F(xiàn)BS）被應(yīng)用到度量排序中，其利用了雙調(diào)序列的結(jié)構(gòu)特點(diǎn)，具有靈活性強(qiáng)、有利于模塊化的優(yōu)點(diǎn)[4]。為了進(jìn)一步降低排序時(shí)延和硬件消耗，在原雙調(diào)排序的基礎(chǔ)上，提出一種剪切的雙調(diào)排序方法（Pruned Bitonic Sorter，PBS）。為了改善度量比較器在保留路徑數(shù)較小時(shí)的性能，一種基于冒泡排序算法的簡化冒泡排序結(jié)構(gòu)（Simplified Bubble Sorter，SBS）得到了更低的時(shí)延 [5]。在減少硬件消耗方面，奇偶排序系統(tǒng)（Odd-even Sorter，OES）將奇數(shù)度量和偶數(shù)度量分開處理，大大減少了所需比較交換器的數(shù)量[6]。以上度量排序器存在排序延時(shí)隨保留路徑數(shù)遞增的特點(diǎn)，制約了譯碼實(shí)時(shí)性研究的發(fā)展。為了降低排序延遲，本文首次將一種并行全比較排序網(wǎng)絡(luò)應(yīng)用到度量排序中，并給出一種簡化結(jié)構(gòu)以降低硬件損耗。并行全比較排序網(wǎng)絡(luò)是一種“以空間換時(shí)間”的并行排序結(jié)構(gòu)[7]。其應(yīng)用在極化碼譯碼度量排序時(shí)，即使保留路徑數(shù)L的值較大，仍只用4個(gè)時(shí)鐘周期完成度量排序輸出。對(duì)比其他的排序結(jié)構(gòu)，其排序度量延遲低的優(yōu)勢十分明顯。但當(dāng)L值較大時(shí)，全排序網(wǎng)絡(luò)硬件損失較大。為了降低硬件損耗，應(yīng)用全比較排序的對(duì)稱性和度量值的特性，給出一種排序延時(shí)低、硬件消耗相對(duì)較小的簡化度量排序結(jié)構(gòu)。

1 背景

本文重點(diǎn)研究的度量排序器是對(duì)2L個(gè)度量進(jìn)行排序，得到其中較小的L個(gè)。這里給出極化碼SCL譯碼算法的度量計(jì)算特點(diǎn)和一些重要度量排序，以便與本文提出度量排序結(jié)構(gòu)進(jìn)行比較分析。

1.1 度量計(jì)算

在極化碼連續(xù)消除列表算法（SCL）中，設(shè)碼長為N，傳輸碼字為[ui]，[i∈{1，2，3，...，N}]，接收序列為[yN1]。為便于下文描述，規(guī)定用[ui-11]表示向量[（u1，u2，…，ui-1）]。用[W（i）N：x→yN×xi-1，1≤i≤N]表示經(jīng)信道極化后的極化信道。用信道輸出序列[yN1]和前[i-1]個(gè)估計(jì)值對(duì)[ui]取值進(jìn)行估計(jì)，[W（i）NyN1，ui-11l/ui]即是[ui]取0或1時(shí)的信道傳輸概率。假設(shè)[ui]為信息比特，[ui]的估計(jì)值為[ui]，則可用式（1）計(jì)算[ui]的對(duì)數(shù)似然比。

并行全比較方法應(yīng)用于度量排序時(shí)，只需固定的4個(gè)時(shí)鐘周期即可完成排序輸出。每個(gè)周期具體完成的工作主要如下：

1） 在第1個(gè)時(shí)鐘周期內(nèi)完成數(shù)據(jù)的比較，用上述FC基礎(chǔ)比較單元完成比較，并記錄結(jié)果如表1所示。表1中Z值為輸入度量兩兩比較結(jié)果，這里將其賦值給變量a-g。用FPGA仿真語言verilog表示為：

//m1和所有除自己外的其他數(shù)據(jù)比較

if（m1 > m2）? a1 <= 1′b1;? else a1 <= 1′b0;

if（m1 > m3）? a2 <= 1′b1;? else a2 <= 1′b0;

……

//m2和所有除自己外的其他數(shù)據(jù)比較

if（m2 > m1）? b1 <= 1′b1;? else b1 <= 1′b0;

if（m2 > m3）? b2 <= 1′b1;? else b2 <= 1′b0;

……

2）在第2個(gè)時(shí)鐘周期，將第1個(gè)時(shí)鐘周期過后得到的比較值累加，由累加后的結(jié)果即可得到序列從小到大的順序。如表格1中的m1（20）的累加值為0，則其為最小值;m4（60）的累加值為2，則其在序列中為第3小值。用FPGA仿真語言verilog表示上述累加過程為：

mid1 <= a1 + a2 + a3 + a4 + a5 + a6 + a7;

mid2 <= b1 + b2 + b3 + b4 + b5 + b6 + b7;

mid3 <= c1 + c2 + c3 + c4 + c5 + c6 + c7;

……

3）在第3個(gè)時(shí)鐘周期，將相應(yīng)的輸入賦值給排序空間，即將各個(gè)度量值按序存放在一個(gè)中間變量中。

out_temp[mid1] <= m1;

out_temp[mid2] <= m2;

out_temp[mid3] <= m3;

……

4）在4個(gè)時(shí)鐘周期，將存儲(chǔ)在中間變量中的排序結(jié)果輸出，即為我們要得到的。由于下一次迭代只需要保留最小的4個(gè)度量，則只需輸出最小的4個(gè)值。

out0 <= out_temp[1];

out1 <= out_temp[2];

out2 <= out_temp[3];

out3 <= out_temp[4];

全比較排序的排序延遲只有固定的4個(gè)周期，不會(huì)隨著輸入數(shù)據(jù)量變化，但其排序所需的硬件處理空間是與輸入度量的數(shù)量有關(guān)的。并行全比較排序的輸入數(shù)據(jù)量為n，則排序結(jié)構(gòu)共需要[（n-1）2]個(gè)基礎(chǔ)比較單元。極化碼的譯碼算法SCL的保留路徑數(shù)為L，則更新度量后要排序的輸入量為2L，相應(yīng)的排序延遲為4個(gè)時(shí)鐘周期，[（2L-1）2]個(gè)基礎(chǔ)比較單元。

2.2 簡化并行全比較（Simplified Full Comparison，SFC）

并行全比較結(jié)構(gòu)時(shí)鐘延遲較小，但所消耗的排序空間較大。根據(jù)式（6）、式（7）所示度量特點(diǎn)對(duì)全比較排序結(jié)構(gòu)進(jìn)行改進(jìn)，使其在保留排序時(shí)延低的同時(shí)，降低排序所用空間，最終達(dá)到降低譯碼硬件損耗的目的。

首先，表格1中沿對(duì)角線對(duì)稱分布的比較，兩個(gè)輸入值相同，只是調(diào)換了順序，其比較結(jié)果如a1與b1、a2與c1是互補(bǔ)的。根據(jù)該特點(diǎn)，這里將基礎(chǔ)比較單元的輸出從原來的2條增加至4條，即可減少一半基礎(chǔ)比較單元的數(shù)量。這里給出基礎(chǔ)比較單元如圖5所示，其比較邏輯為：若[A>B]，則比較結(jié)果[Z1=1，Z2=0]，否則[Z1=0，Z2=1]。使用該基礎(chǔ)比較單元邏輯結(jié)構(gòu)，即可將比較器減少至原來的一半。

由式（6）和式（7）中度量值的特點(diǎn)，當(dāng)輸入度量值數(shù)量為8時(shí)，則滿足[m1

1）在第1個(gè)時(shí)鐘周期內(nèi)完成數(shù)據(jù)的比較，除去已知的比較結(jié)果和關(guān)于對(duì)角線對(duì)稱的比較單元，記錄結(jié)果如表格2所示。表格2中0、1分別是根據(jù)已知的度量關(guān)系得到的結(jié)果，a1與aa1、a2與aa2、c1與cc1等是對(duì)稱互補(bǔ)的輸出，每一對(duì)只需要1個(gè)基礎(chǔ)比較單元。基于SFC的基礎(chǔ)比較單元，按照表2，8個(gè)輸入的度量比較器只需9個(gè)基礎(chǔ)比較單元。簡化全比較SFC的第1個(gè)處理周期，用FPGA仿真語言verilog表示為： //m2與其他度量值的比較

if（m2 > m3）? begin a1 <= 1'b1; aa1 <= 1'b0;end

else? ? ? ? ?begin a1 <= 1′b0; aa1 <= 1′b1;end

if（m2 > m4）? begin b1 <= 1′b1; bb1 <= 1′b0;end

else? ? ? ? ?begin b1 <= 1′b0; bb1 <= 1′b1;end

……

if（m2 > m7）? begin b1<= 1'b1; bb1 <= 1′b0;end

else? ? ? ? ?begin b1 <= 1′b0; bb1 <= 1′b1;end

2）在第2個(gè)時(shí)鐘周期，將第1個(gè)時(shí)鐘周期過后得到的比較值累加，如表2所示。

mid1 <= 1′b0;

mid2 <= 1′b1 + a1 + a2 + a3 + a4 + a5;

……

mid7 <= 1′b1 + 1′b1 + 1′b1 + aa5 + bb3 + cc1;

3）、4）與原并行全比較的處理方式一致。

改進(jìn)后的簡化全比較排序器時(shí)延仍為4個(gè)周期，而排序所需的基礎(chǔ)比較單元卻大為減少。根據(jù)排序結(jié)構(gòu)特點(diǎn)，若改進(jìn)后的簡化全比較（SPF）排序器的輸入數(shù)據(jù)量為n，則排序結(jié)構(gòu)共需要基礎(chǔ)比較單元的數(shù)量變?yōu)閇（n/2-1）2]。假設(shè)極化碼的譯碼算法SCL的更新度量后需要排序的輸入量為2L，簡化全比較（SPF）排序器的排序延遲為4個(gè)時(shí)鐘周期，則基礎(chǔ)比較單元的數(shù)量為[（L-1）2]，遠(yuǎn)遠(yuǎn)小于全比較排序方法的[（2L-1）2]。改進(jìn)后的簡化全比較（SPF）排序器具有較低的排序延遲和硬件消耗。

3 結(jié)果分析

度量排序器用階數(shù)表征譯碼延遲，而所用的基礎(chǔ)比較器數(shù)代表了硬件的復(fù)雜程度。本文提出的全比較排序除了用到比較器以外，還使用了加法器，但加法器的數(shù)量與基礎(chǔ)比較器的數(shù)量相比很小，因此這里只比較基礎(chǔ)比較器的數(shù)量。對(duì)于傳統(tǒng)的3種方法PBS、SBS、OES和本文給出的FC和SFC，按照保留路徑數(shù)L的不同，表3、表4給出了度量排序結(jié)構(gòu)所用的階數(shù)和基礎(chǔ)比較單元數(shù)。

從排序時(shí)延上分析，并行全比較算法的排序時(shí)延是固定的4個(gè)周期，而其他排序方法是隨著L值增大的。表3中，當(dāng)L = 32時(shí)，F(xiàn)C/SFC的時(shí)延僅是PBS的0.2。當(dāng)L > 4時(shí)，F(xiàn)C/SFC所需的排序時(shí)延最少，且其時(shí)延低優(yōu)勢明顯。從表4中分析不同排序結(jié)構(gòu)所需比較器數(shù)量可知，當(dāng)L值比較大時(shí)，F(xiàn)C排序器的硬件消耗比較大，但對(duì)其改進(jìn)后的SFC硬件效率明顯提高。如L = 8時(shí)，SFC所需基礎(chǔ)比較單元數(shù)僅為FC的0.217。

綜合考慮排序延遲和硬件消耗，由表3、表4中數(shù)據(jù)可得，當(dāng)L = 8時(shí)，PBS與SFC所用比較器個(gè)數(shù)相差不多，但PBS的排序時(shí)延是SFC的2.25倍。在極化碼SCL譯碼的保留路徑數(shù)是常用的8、16時(shí)，在排序時(shí)延上，F(xiàn)S、SFC具有很大的優(yōu)勢，且其硬件消耗也相對(duì)較低，同時(shí)滿足了通信中對(duì)實(shí)時(shí)性和實(shí)用性的要求。

在Xilinx ISE 14.7用FPGA仿真，選用設(shè)備為xs6s1x75-3fgg676，得到5種方法的仿真結(jié)果。硬件仿真采用的度量數(shù)據(jù)是使用MATLAB軟件仿真并量化成32位。實(shí)驗(yàn)所得的延時(shí)是在相同時(shí)鐘周期下的實(shí)驗(yàn)結(jié)果，LUTs代表了FPGA仿真的硬件消耗。由硬件仿真結(jié)果可知，本文給出的兩種度量排序器結(jié)構(gòu)可得到正確的排序結(jié)果。從表5可以看出，在相同的時(shí)鐘周期下，時(shí)鐘延遲和表1中階數(shù)結(jié)果一致，表格6中LUTs硬件消耗也與表2中基礎(chǔ)比較單元的數(shù)量結(jié)果一致。

4 結(jié)論

本文首次將并行全比較網(wǎng)絡(luò)應(yīng)用到極化碼譯碼算法SCL度量排序中，并提出了一種簡化全比較結(jié)構(gòu)以降低硬件消耗。實(shí)驗(yàn)分析表明，當(dāng)SCL譯碼長度滿足L > 4時(shí)，相較于3種傳統(tǒng)方法，全比較排序結(jié)構(gòu)的時(shí)延最小?；谌容^排序器提出的簡化全比較排序結(jié)構(gòu)，在保留譯碼延遲低的同時(shí)大大降低了硬件消耗。由FPGA仿真可知，簡化全比較排序結(jié)構(gòu)是一種兼?zhèn)鋵?shí)時(shí)性和實(shí)用性的度量排序器設(shè)計(jì)方案。

參考文獻(xiàn)：

[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]? ? ARKAN E. A performance comparison of polar codes and reed-muller codes[J]. IEEE Communications Letters，2008，12（6）：447-449.

[3]? ? TAL I，VARDY A. List decoding of polar codes[J]. IEEE Transactions on Information Theory，2015，61（5）：2213-2226.

[4]? ? LIN J，YAN Z Y. An efficient list decoder architecture for polar codes[J]. IEEE Transactions on Very Large Scale Integration （VLSI） Systems，2015，23（11）：2508-2518.

[5]? ? BALATSOUKAS-STIMMING A，BASTANI PARIZI M，BURG A. On metric sorting for successive cancellation list decoding of polar codes[C]//2015 IEEE International Symposium on Circuits and Systems （ISCAS）. Lisbon. New York，USA：IEEE，2015：1993-1996

[6]? ? YONG KONG B，YOO H，PARK I. Efficient sorting architecture for successive-cancellation-list decoding of polar codes[J]. IEEE Transactions on Circuits and Systems II：Express Briefs，2016，63（7）：673-677.

[7]? ? 師廷偉，金長江. 基于FPGA的并行全比較排序算法[J]. 數(shù)字技術(shù)與應(yīng)用，2013（10）：126-127.

[8]? ? BALATSOUKAS-STIMMING A，BASTANI PARIZI M，BURG A. LLR-based successive cancellation list decoding of polar codes[J]. IEEE Transactions on Signal Processing，2015，63（19）：5165-5179.

[9]? ? BATCHER K E. Sorting networks and their applications[C]// American Federation of Information Processing Societies：AFIPS Conference Proceedings. Spring Joint Computer Conference，Atlantic City，NJ，USA，1968.

[責(zé)任編輯? ? 田? ? 豐]