一种改进的极化码SCL译码度量排序器设计

李怡 高军萍 李琦 王娇 王彤

摘要 在极化码连续消除列表（SCL）算法中译码时延是提升译码性能的关键，度量排序是译码时延的重要部分。为了降低译码时度量排序的时间消耗，首次将并行全比较排序应用到极化码译码度量排序中，并提出一种简化全比较（SPF）改进结构以降低硬件消耗。经过数据分析表明，在硬件相差无几的情况下，当列表长度为8时，传统剪切双调排序结构（PBS）的延时是简化全比较（SPF）结构的2.25倍。FPGA仿真的实验结果表明，简化全比较（SPF）结构具备排序延时低和硬件效率高的特点。

关 键 词 极化码;SCL译码;度量排序;并行算法;全比较

中图分类号 TN911.22     文献标志码 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 引言

应用于5G控制信道的极化码是一种基于信道极化现象的信道编码方式，因其编译码复杂度低且理论上已证明可达信道容量，故而成为信道编码领域的研究热点[1-2]。极化码的一种译码算法——连续消除列表（Successive Cancellation List，SCL）算法在对信息位比特进行估计时，保留的L条路径会扩展为2L条候选路径，每条候路径都对应一个度量值[3]。在SCL译码电路设计中，一个比较关键的问题是从2L条候选路径中选出度量最小的L条路径，该功能由度量排序器完成。因此，在SCL译码算法的译码电路中，度量排序器的设计至关重要[4]。

减少排序延时和硬件消耗是度量排序器设计的关键。为了降低排序时延，全双调排序系统（Full Bitonic Sorter，FBS）被应用到度量排序中，其利用了双调序列的结构特点，具有灵活性强、有利于模块化的优点[4]。为了进一步降低排序时延和硬件消耗，在原双调排序的基础上，提出一种剪切的双调排序方法（Pruned Bitonic Sorter，PBS）。为了改善度量比较器在保留路径数较小时的性能，一种基于冒泡排序算法的简化冒泡排序结构（Simplified Bubble Sorter，SBS）得到了更低的时延 [5]。在减少硬件消耗方面，奇偶排序系统（Odd-even Sorter，OES）将奇数度量和偶数度量分开处理，大大减少了所需比较交换器的数量[6]。以上度量排序器存在排序延时随保留路径数递增的特点，制约了译码实时性研究的发展。为了降低排序延迟，本文首次将一种并行全比较排序网络应用到度量排序中，并给出一种简化结构以降低硬件损耗。并行全比较排序网络是一种“以空间换时间”的并行排序结构[7]。其应用在极化码译码度量排序时，即使保留路径数L的值较大，仍只用4个时钟周期完成度量排序输出。对比其他的排序结构，其排序度量延迟低的优势十分明显。但当L值较大时，全排序网络硬件损失较大。为了降低硬件损耗，应用全比较排序的对称性和度量值的特性，给出一种排序延时低、硬件消耗相对较小的简化度量排序结构。

1 背景

本文重点研究的度量排序器是对2L个度量进行排序，得到其中较小的L个。这里给出极化码SCL译码算法的度量计算特点和一些重要度量排序，以便与本文提出度量排序结构进行比较分析。

1.1 度量计算

在極化码连续消除列表算法（SCL）中，设码长为N，传输码字为[ui]，[i∈{1，2，3，...，N}]，接收序列为[yN1]。为便于下文描述，规定用[ui-11]表示向量[（u1，u2，…，ui-1）]。用[W（i）N：x→yN×xi-1，1≤i≤N]表示经信道极化后的极化信道。用信道输出序列[yN1]和前[i-1]个估计值对[ui]取值进行估计，[W（i）NyN1，ui-11l/ui]即是[ui]取0或1时的信道传输概率。假设[ui]为信息比特，[ui]的估计值为[ui]，则可用式（1）计算[ui]的对数似然比。

并行全比较方法应用于度量排序时，只需固定的4个时钟周期即可完成排序输出。每个周期具体完成的工作主要如下：

1） 在第1个时钟周期内完成数据的比较，用上述FC基础比较单元完成比较，并记录结果如表1所示。表1中Z值为输入度量两两比较结果，这里将其赋值给变量a-g。用FPGA仿真语言verilog表示為：

//m1和所有除自己外的其他数据比较

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

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

……

//m2和所有除自己外的其他数据比较

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

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

……

2）在第2个时钟周期，将第1个时钟周期过后得到的比较值累加，由累加后的结果即可得到序列从小到大的顺序。如表格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个时钟周期，将相应的输入赋值给排序空间，即将各个度量值按序存放在一个中间变量中。

out_temp[mid1] <= m1;

out_temp[mid2] <= m2;

out_temp[mid3] <= m3;

……

4）在4个时钟周期，将存储在中间变量中的排序结果输出，即为我们要得到的。由于下一次迭代只需要保留最小的4个度量，则只需输出最小的4个值。

out0 <= out_temp[1];

out1 <= out_temp[2];

out2 <= out_temp[3];

out3 <= out_temp[4];

全比较排序的排序延迟只有固定的4个周期，不会随着输入数据量变化，但其排序所需的硬件处理空间是与输入度量的数量有关的。并行全比较排序的输入数据量为n，则排序结构共需要[（n-1）2]个基础比较单元。极化码的译码算法SCL的保留路径数为L，则更新度量后要排序的输入量为2L，相应的排序延迟为4个时钟周期，[（2L-1）2]个基础比较单元。

2.2 简化并行全比较（Simplified Full Comparison，SFC）

并行全比较结构时钟延迟较小，但所消耗的排序空间较大。根据式（6）、式（7）所示度量特点对全比较排序结构进行改进，使其在保留排序时延低的同时，降低排序所用空间，最终达到降低译码硬件损耗的目的。

首先，表格1中沿对角线对称分布的比较，两个输入值相同，只是调换了顺序，其比较结果如a1与b1、a2与c1是互补的。根据该特点，这里将基础比较单元的输出从原来的2条增加至4条，即可减少一半基础比较单元的数量。这里给出基础比较单元如图5所示，其比较逻辑为：若[A>B]，则比较结果[Z1=1，Z2=0]，否则[Z1=0，Z2=1]。使用该基础比较单元逻辑结构，即可将比较器减少至原来的一半。

由式（6）和式（7）中度量值的特点，当输入度量值数量为8时，则满足[m1

1）在第1个时钟周期内完成数据的比较，除去已知的比较结果和关于对角线对称的比较单元，记录结果如表格2所示。表格2中0、1分别是根据已知的度量关系得到的结果，a1与aa1、a2与aa2、c1与cc1等是对称互补的输出，每一对只需要1个基础比较单元。基于SFC的基础比较单元，按照表2，8个输入的度量比较器只需9个基础比较单元。简化全比较SFC的第1个处理周期，用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个时钟周期，将第1个时钟周期过后得到的比较值累加，如表2所示。

mid1 <= 1′b0;

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

……

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

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

改进后的简化全比较排序器时延仍为4个周期，而排序所需的基础比较单元却大为减少。根据排序结构特点，若改进后的简化全比较（SPF）排序器的输入数据量为n，则排序结构共需要基础比较单元的数量变为[（n/2-1）2]。假设极化码的译码算法SCL的更新度量后需要排序的输入量为2L，简化全比较（SPF）排序器的排序延迟为4个时钟周期，则基础比较单元的数量为[（L-1）2]，远远小于全比较排序方法的[（2L-1）2]。改进后的简化全比较（SPF）排序器具有较低的排序延迟和硬件消耗。

3 结果分析

度量排序器用阶数表征译码延迟，而所用的基础比较器数代表了硬件的复杂程度。本文提出的全比较排序除了用到比较器以外，还使用了加法器，但加法器的数量与基础比较器的数量相比很小，因此这里只比较基础比较器的数量。对于传统的3种方法PBS、SBS、OES和本文给出的FC和SFC，按照保留路径数L的不同，表3、表4给出了度量排序结构所用的阶数和基础比较单元数。

从排序时延上分析，并行全比较算法的排序时延是固定的4个周期，而其他排序方法是随着L值增大的。表3中，当L = 32时，FC/SFC的时延仅是PBS的0.2。当L > 4时，FC/SFC所需的排序时延最少，且其时延低优势明显。从表4中分析不同排序结构所需比较器数量可知，当L值比较大时，FC排序器的硬件消耗比较大，但对其改进后的SFC硬件效率明显提高。如L = 8时，SFC所需基础比较单元数仅为FC的0.217。

综合考虑排序延迟和硬件消耗，由表3、表4中数据可得，当L = 8时，PBS与SFC所用比较器个数相差不多，但PBS的排序时延是SFC的2.25倍。在极化码SCL译码的保留路径数是常用的8、16时，在排序时延上，FS、SFC具有很大的优势，且其硬件消耗也相对较低，同时满足了通信中对实时性和实用性的要求。

在Xilinx ISE 14.7用FPGA仿真，选用设备为xs6s1x75-3fgg676，得到5种方法的仿真结果。硬件仿真采用的度量数据是使用MATLAB软件仿真并量化成32位。实验所得的延时是在相同时钟周期下的实验结果，LUTs代表了FPGA仿真的硬件消耗。由硬件仿真结果可知，本文给出的两种度量排序器结构可得到正确的排序结果。从表5可以看出，在相同的时钟周期下，时钟延迟和表1中阶数结果一致，表格6中LUTs硬件消耗也与表2中基础比较单元的数量结果一致。

4 结论

本文首次将并行全比较网络应用到极化码译码算法SCL度量排序中，并提出了一种简化全比较结构以降低硬件消耗。实验分析表明，当SCL译码长度满足L > 4时，相较于3种传统方法，全比较排序结构的时延最小。基于全比较排序器提出的简化全比较排序结构，在保留译码延迟低的同时大大降低了硬件消耗。由FPGA仿真可知，简化全比较排序结构是一种兼备实时性和实用性的度量排序器设计方案。

参考文献：

[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]. 数字技术与应用，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.

[责任编辑    田    丰]