极化码SCS译码器的FPGA实现

席 艺 仰枫帆 叶 明

（南京航空航天大学电子信息工程学院 南京 211106）

1 引言

2007年，Arikan教授发现了信道极化现象［1］，在文章“Channel Polarization：A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels［2］”中，Arikan 正式提出了极化码这一概念，并通过总结编码过程和一系列数学计算给出了极化码的编码矩阵，同时还给出了用于极化码译码的连续删除（Successive Cancellation，SC）算法。随后Vardy等学者在SC算法的基础上提出连续删除列表（Successive Cancellation List，SCL）算法［3］，将SC算法中单一的候选路径增加称列表，进一步降低误码率。Niu.K，K.Chen提出同属SC类的新算法连续删除堆栈（Successive Cancellation Stack，SCS）译码算法［4］，采用了与SCL算法相同的增加SC算法候选路径的思想，将度量值最大的路径置于堆栈顶，通过只拓展顶层路径的方法，在取得跟SCL算法相似性能的同时极大地减小了运算复杂度。与此同时，为了探寻极化码工程上实现的可能性，众多学者开始致力于极化码硬件实现并开始提出了一些SC译码硬件结构［5～9］。随后，相继提出了 SCL［10～11］、CA-SCL［12］等算法的硬件结构。本文重点设计极化码SCS算法译码器的硬件结构，基于FPGA给出了一套可实现的硬件实现方案，最后给出了硬件仿真结果。

2 极化码的编译原理

2.1 极化码编码方法

极化码的编码［13］是依据生成矩阵产生的，同大多数线性分组码一样满足：

极化码的码长一般取N=2n,n≥0，根据极化码的递归构造模型，通常定义其生成矩阵为

2.2 极化码SCS译码算法

极化码发展至今已有多种译码方法，其中SC类算法是主流译码算法。SCS算法性能优越，且具有较低的译码复杂度，下面将分SC译码算法和SCS译码算法两部分介绍。

2.2.1 SC译码算法部分

对上述规则进行细化，令对数似然比（Log Likelihood-Ratio， LLR） 为，根据迭代公式推算最终可以回归到初始值的计算，在AWGN信道下初始信道LLR为，σ2为噪声方差。如图1所示为L=8时的SC译码算法流程图。

图1 L=8时SC译码流程

图中，f节点和g节点的计算公式使用最小和算法［15～16］表示为

该算法仅含有加减运算，适合用于硬件实现。其中uˆs为已经译出的码字的部分和。在硬件实现中往往将两者融合为一个节点，被称为一个计算单元（Processing Element，PE），并通过复用器来实现二者的功能转换。

2.2.2 SCS译码算法部分

在SC译码算法中，每个阶段仅存在一条候选路径，错误极易累加，SCS算法扩大译码阶段候选路径，利用堆栈来存储候选路径，并始终沿着候选路径中度量值最大的一条路径进行扩展。路径度量值PM与当前候选比特的LLR有关，计算公式为

初始阶段只有一条空路径，且PM()φ=0。

根据式（5），每条路径中的度量值都大于其后续路径的度量值，因此我们将候选路径按度量值大小顺序存储在堆栈中，栈顶为度量值最大的路径，每次只取栈顶路径出栈进行路径扩展，根据式（5）计算扩展路径的度量值，再将新的路径按度量值大小排入堆栈中。如此进行循环，直至栈顶路径长度达N，此时该路径的度量值将大于所有等长路径的度量值，即为译码结果。

设计堆栈深度D和路径扩展宽度L，用i表示当前路径长度，向量表示候选路径，表示该路径的度量值，| S |表示堆栈中的路径数量，设定计数器向量表示具有对应长度的出栈路径数量，例如ci为路径长度为i的出栈路径数。SCS算法具体过程［17］可分以下几步进行。

步骤一：数据初始化。将各存储空间清除缓存数据，并给堆栈中传入空序列，置长度i=0，度量值=0，路径数 |S |=1，计数器=(0,0,...,0)。

步骤三：栈顶序列扩展。将出栈的原栈顶序列扩展为两条路径，和，并计算两条路径的度量值为

步骤四：候选路径入栈。首先判断是否栈满，若 ||S≥D-2，则直接删去栈底两条路径度量值较小的路径；若未满则继续操作，将扩展的两条路径按照度量值大小按顺序入栈。

步骤五：路径竞争。计数器ci记录了堆栈中长度为i的路径数量，若ci=L，说明前i位路径已经被扩展了L次，达到了搜索宽度，因此我们遍历堆栈，删除长度小于等于i的路径。

步骤六：译码终止判决。判断栈顶路径长度是否为N，若满足，则该路径直接出栈作为译码结果；若不满足终止条件则返回执行步骤二。

当D与L足够大时，SCS算法可确保找到最大似然解；当L有限时，其性能等同于相同搜索宽度的SCL算法，但由于SCS算法只沿着最佳候选路径进行扩展，其算法复杂度必然在一定程度上优于SCL算法，并且在信道信噪比大时更为明显。

3 SCS译码器硬件结构设计

3.1 译码器整体结构设计

本次的译码器设计设置码长为1024，码率为1/2，SCS算法堆栈深度D=256，搜索宽度L=32，采用BEC-Z()W 方法进行信道选择，输入信息的量化位宽为8bit。

极化码SCS译码器整体架构如图2所示，输入译码模块的是存储在LLR-based RAM中经过量化的初始LLR，输出的译码结果是Stack中的顶层数据。译码模块结构根据功能主要包括两个部分：度量值计算和堆栈结构。度量值计算包括LLR_top module（LLR计算模块）、Corrected module（修正模块）、Metric_top module（度量值计算模块）、Feedback module（反馈模块），以及它们相应的数据存储模块；堆栈结构Stack module并不等同于软件算法中的堆栈，而是根据SCS算法和堆栈特点，利用硬件结构写出的类似堆栈功能的Stack模块。

图2 SCS译码器整体硬件结构

为了更好地协调各个模块工作，我们引入状态机，状态机一共有12个工作状态，对应不同时刻译码器的算法流程，用S0～S11来表示，各状态之间的转移关系如图3所示。

图3 控制模块状态转移图

S0～S11代表的工作状态含义如表1所示。

表1 工作状态对应表

3.2 堆栈模块

由于SCS译码器中使用的堆栈占用数量较大，考虑到硬件资源的问题，不便于直接利用寄存器实现，因此我们考虑使用硬件中的双FIFO结构根据SCS算法需求实现特定功能的堆栈，其中FIFO1为堆栈数据存储模块，FIFO2为对堆栈进行相关处理的缓存模块，如图4所示。

图4 双FIFO结构堆栈设计示意图

图中可以看到，设置FIFO1和FIFO2深度为256，存储数据宽度为1043bit，包括11bit路径长度、1024bit候选路径和8bit路径度量值，按照度量值从大到小的顺序进入队列，从而保证最先输出的堆栈顶层为度量值最大的路径。FIFO1初始输入数据为空序列，进入译码阶段后的输入为经过处理后从FIFO2中传入的数据。FIFO1中的顶层数据输出，在其他模块进行路径扩展和度量值计算，再按照度量值大小进行排序，依旧按照度量值从大到小的顺序将路径数据输入FIFO2。FIFO2中存储经过路径扩展的路径序列和度量值，将其出栈进行路径竞争，完成译码算法对搜索宽度的限制，最后将通过路径竞争的路径数据重新存入FIFO1，再进行下一轮译码。

3.3 LLR计算模块

SC类算法中LLR计算方法［18～19］都相同，其模块也在各类SC算法可通用，这里设计LLR计算包括控制模块LLR_control、计算单元状态模块IDX_control、计算单元Polar_fg和修正模块Correcred，如图5所示。LLR_control模块负责整体数据的地址传输和使能控制，IDX_controll模块根据出栈路径长度top_length控制计算单元的状态，Polar_fg模块根据输入两个LLR值、uˆs和PE的计算状态Fg_sel计算出下一阶段的LLR，Correcred解决由于运算导致的LLR数据溢出问题，并通过wdata信号将数据输出。

图5 LLR计算模块硬件结构

图5 中，top_length来自于顶层出栈数据，表示出栈路径长度，IDX_control模块根据该信号得出计算单元应处于 f函数或g函数的计算状态，并通过IDX信号传入LLR_control中，并经过LLR_control模块地址控制通过Fg_sel信号串行传入Polar_fg中。当前阶段LLR数据rdata来自于LLR_base RAM或LLR_MID RAM中，两个RAM通过一个二选一选择器传入Polar_fg，选择器使能端为 ram_sel，rdata 读取地址为 raddr。中间 uˆs数据udata来自Feedback模块，直接传入Polar_fg，其读取地址为uaddr。Polar_fg模块计算出的LLR由于大量计算其位宽会变得越来越大，容易造成数据溢出，因此通过idata信号传入Corrected模块进行修正处理，最终得到下一阶段LLR再次存入LLR_MID RAM中，写地址为waddr。

3.4 度量值计算模块

图6所示为路径度量值计算模块的硬件结构图。

度量值的计算方法如式（5）所示，根据公式可知度量值计算中的输入数据为出栈路径的度量值、扩展路径LLR值、路径扩展位ui以及初始信道的位置信息。图中bit_location表示初始信道的位置信息，来源于大小为1024×1bit的Bit_location ROM中，0表示冻结比特，1表示信息比特。当进行度量值计算时，Metric_top从Bit_location ROM中读取位置信息bit_location，和LLR计算模块传入LLR信号的符号位一起作为Sel_ctl控制模块的输入，来控制式（5）中所对应的三种情况。

图6 路径度量值计算模块硬件结构

为缩减运算量，在计算出候选比特为0和1各自的路径度量值后，使用一个选择器进行初步比较，按度量值顺序将扩展路径先后与FIFO1中的出栈路径度量值进行比较并输入堆栈缓存模块FIFO2。另外，扩展位与冻结比特不符的路径度量值为负无穷，此时可省去比较过程直接将路径数据输入FIFO2队尾。

3.5 反馈模块

LLR值计算时需要来自Feedback模块的中间uˆs数据，随着路径不断扩展，需要反馈模块将新的uˆs存储并传入LLR计算模块，每进行一次路径扩展，我们需要将对应路径的uˆs进行反馈更新，这里的反馈与LLR蝶形计算结构的数据流动方向相反，根据图1得到N=8时的反馈结构，如图7所示。

图7 N=8时反馈模块结构

按图中从左到右的顺序，计算规则：新生成的比特存入顶层，随后判断当前层的IDX值，如果为0则将当前层的数据存入下一层的 f单元。如果是1，则将当前层的数据存入下一层的g单元，并取出f中的数据与当前层数据相加后继续存入 f单元，然后继续通过判断当前层进行下一层的计算。这里的 f和g单元只有存储功能，并非LLR计算模块中 f和g单元。

4 仿真结果与分析

本文的极化码SCS译码器设计使用了Altera公司Strtix V系列的5SGXEA7H3F35C3作为FPGA芯片，使用QuartusⅡ15.0综合后的结果如表2所示，整体译码器的系统面积占用率仅为4%。

表2 极化码SCS译码器综合资源表

仿真后得到整体译码器的译码结果。在600MHz的工作频率下，一帧码字的译码需要约49000个时钟周期，平均时延为0.082ms。

根据吞吐率T的计算公式：

SCS译码器的工作频率为600MHz，译码器平均时延为0.082ms，在此情况下吞吐率可达1024/(0.082×10-3)=12.49Mbps。

除了吞吐率外，译码器的纠错能力也是评价其性能的重要指标。采用BEC删除概率为0.5的BEC-Z（W）方法进行信道选择，码长为1024bit，码率为0.5，SCS译码算法的堆栈深度D=256，搜索宽度L=32，硬件计算中量化位宽为8，路径度量值计算时位宽为12；模拟的AWGN信道下每个点传输105帧数据，并统计每一点的误码率得到图8。

图8 SC、SCS算法软件理论性能和SCS硬件实现仿真结果的比较

图中以SC算法和SCS算法的在软件实验中的理论性能作为对比参考，在误码率为10-4时，SCS算法比SC算法的理论性能增益［20］为0.5dB，SCS硬件译码器仿真结果比SC算法软件理论性能的增益也可达0.45dB。而SCS算法的软件理论与硬件仿真结果的性能较为接近，其误差主要来源于硬件实现的计算过程中对软件仿真中的浮点数进行了量化，因此必然损失了一定的计算精度，根据对图8的分析，在误码率BER=10-4时，硬件实现结果比理论性能相差仅约0.05dB，故硬件实现也可获得近似浮点计算的性能。

5 结语

对码长为1024的极化码采用了SCS算法进行译码分析，提出了一种基于FPGA的极化码SCS译码器设计，设置使用于硬件实现的各种参数，并分堆栈模块、LLR计算模块、度量值计算模块、反馈模块四个功能部分进行详细实现说明。大胆提出译码器双FIFO有序堆栈结构和结合了IDX模块、控制模块、计算单元和修正模块四部分的单元LLR计算结构的硬件设计，设计了能有效协作LLR计算模块工作的反馈模块，简化了LLR的硬件计算过程，提高译码器的吞吐率。使用Verilog HDL语言在QuartusⅡ上进行模块编写后，调用Modelsim进行仿真，在系统时钟频率为600MHz的情况下，译码器的吞吐率可达12.49Mbps，资源利用率仅为4%。