文献标识码：A
DOI：10.16157/j.issn.0258-7998.181295
中文引用格式：廖海鹏，卿粼波，滕奇志，等. 基于FPGA的SCL译码算法优化与设计[J].电子技术应用，2018，44(12)：1-4，8.
英文引用格式：Liao Haipeng，Qing Linbo，Teng Qizhi，et al. The optimization and design of SCL decoding algorithm based on FPGA[J]. Application of Electronic Technique，2018，44(12)：1-4，8.
0 引言
2008年ARIKAN E提出了信道极化的概念并对信道极化现象进行了详细的描述[1]。极化码的主要过程是在编码系统中通过对信道进行结合与拆分，然后在其中选择好的部分信道来进行有效数据的传输。极化码被严格证明有以下两个特性：一是基于信道极化现象存在；二是在码长为无限长时，其信道容量可达香农极限。相比于经典的Turbo码与LDPC码，极化码具有更低的误码率和复杂度以及更高的吞吐率[2-3]。
极化码的译码算法研究近年来发展迅速，其中成为研究热点的连续删除（Successive Cancellation，SC）译码算法的基本思想是通过对信息位的比特似然概率值的判断来进行译码。但由于在译码时前一个译码值会对之后的译码值造成影响，因此导致译码性能较差[4]。在此基础上改进的序列连续删除（Successive Cancellation List，SCL）算法能在计算复杂度与空间复杂度之间实现更好的平衡[5]，相比于在软件上实现该算法，在FPGA上进行SCL译码可以使译码速度进一步加快[6]。目前极化码各方面都已经取得了硕果，但是在FPGA上的译码实现仍然存在着译码效率和吞吐率不够高等问题[6]。因此本文针对极化码的SCL译码算法进行了研究和优化，减少资源消耗同时提高译码效率；针对FPGA上的译码器设计进行了定点量化的改进；最后在Xilinx的VC707开发板上进行了译码器的实现与性能分析。实验结果表明译码器在码长为512时译码效率为143.988 MHz，吞吐率达到了28.79 Mb/s，具有较强的工程使用价值。
1 极化码的SCL译码算法
SCL译码算法实质是对SC译码算法的推广，SC译码算法的基本思想是通过对每个传输码字的LLR(对数似然比值)进行判断译出码字，LLR的定义如式(1)所示。
图1所示为SC译码路径示意图，由示意图和LLR计算公式可以看出SC译码在译码过程中前一个译码值与之后的译码值相互关联，这将对其译码算法的性能造成影响。
其中函数δ(x)=(1-sgn(δ))/2，符号函数sgn(x)表示在x>0时值为1，x<0时值为-1，x=0时值为0。l代表相应路径且初始值
如图2所示的SCL译码过程中，传输的码字为1010，其中前两位为固定比特，后两位为信息比特。传输码字从根节点出发向下扩展，可以得到相应的PM值，一直扩展到4条路径，此时取出PM值较小的两条路径继续扩展，其余路径删除，因此最终只有4条路径，其中最后算出的PM值最小的相应路径即为译码结果。图2中曲线代表此次PM值最小路径为1010，译码结果正确。
2 SCL译码的优化与设计
SCL译码算法的核心依然是SC译码算法，但其性能优于SC译码算法。在FPGA上进行SCL译码算法的实现会遇到如何提高译码效率和吞吐率以及如何合理利用FPGA片上资源等挑战。针对SCL译码算法的优化可以在基于其具有的递归结构下对译码计算过程进行简化，针对FPGA上的译码器设计可在运算过程中对浮点数进行量化，更有利于硬件实现。
2.1 SCL译码算法系统设计
图3所示为本文所设计的SCL译码系统图，针对在SCL译码的过程中有可能出现最小PM值路径译码不是正确译码的情况，可以通过采用文献[8]中的增加循环冗余校验（Cyclic Redundancy Check，CRC）辅助的方法来进行解决。在编码系统中先对源码进行校验码的添加，然后进行极化码的编码生成相应的码字进行传输。解码系统在FPGA上使用设计的译码器对传输过来的码字进行极化码译码以及校验码校验，在译码最后阶段的路径选择时从最小PM值逐条校验，一旦出现校验通过的路径即为译码结果。
2.2 SCL译码算法优化
SCL译码过程实质是L个SC译码算法同时进行，图4所示为码长为8时的SC译码算法递归流程图，图中传递的信息
均为LLR，其中S代表计算层数，i代表相应码字标号。
在SC译码算法中，LLR的计算公式如下：
2.3 FPGA中实现算法的改进
在图4所示的SC译码算法流程图中实线部分代表执行的f函数，虚线部分代表执行的g函数。分别定义如下：
在SCL译码过程中的LLR计算值均为浮点数，直接在FPGA中计算会使得译码复杂度较高，因此将浮点数进行定点量化转变成定点数，定点量化的结果通过（O，R，D）来表示，定义如表1所示。
对f函数进行改进之后，译码过程中的计算不再涉及乘除法，因此信道输出和LLR的小数位数可以一致。由于采用定点量化用量化值代替了原始值，必定会对译码结果造成一定影响，因此选择合适的量化比特数和小数位数尤为重要。通过对信道输出值以及运算过程中的对数似然比值进行详细的分析以及对比实验，选出了三种如下较好的量化方式。图5所示为量化前后的BER曲线图。
如图5所示的三种量化方式相比，(4，4，0)由于LLR量化的比特数过小，导致效果不是很理想。(4，5，0)和(5，6，1)的量化选择基本没有降低SCL的译码性能，而(4，5，0)这种没有小数位的量化选择更有利于在FPGA上进行计算，因此译码器的设计选用(4，5，0)的量化方式。
3 译码硬件平台与译码测试结果
3.1 硬件平台选择
本文选择在Xilinx的VC707开发板上对译码器进行实现。该开发板的主芯片为XC7VX485T，包含有485 760个逻辑单元、2 800个DSP Slice、37 080 KB内存以及700个I/O引脚等资源。其最高运行频率可以达到741 MHz，可以用来实现极化码的译码。图6为该评估板实物图。
3.2 译码的仿真与测试
为了对SCL和SC算法进行对比以及选择一个合适的路径删减值L，在译码器编写前对各L值下的SCL算法进行了MATLAB仿真，仿真结果如图7所示。
由图7可知当L=1和L=2时误比特率差别较大，再继续加大L值时虽然可以使误比特率进一步降低，但是差别已经没有那么明显，为了在FPGA上能够更容易实现SCL算法，选择L=2来进行路径删减实现算法。
接着对译码器的正确性进行验证，先通过ModelSim仿真软件对译码器进行硬件仿真。然后使用ISE软件带有的Chipscope在线逻辑分析仪去抓取在FPGA上的译码结果，通过硬件仿真结果与FPGA上的译码结果对比来验证译码的正确性。
如图8所示上半部分为在ModelSim上码长为64时的仿真结果，data_u_out和data_uhat_out分别为输入源码字和译码仿真结果。下半部分为使用Chipscope抓取的FPGA中运行结果波形图，data_u和data_uhat分别为输入源码字和实际译码结果。输入源码中有一半码字为固定比特，因此有效码字只有32位。由图8可以看出源码字和仿真结果以及FPGA译码结果均为69ab4d68，因此本次译码结果正确。
图9和图10所示分别为码长为128和512时的仿真结果和译码结果波形图。在抓取512码长的波形时，由于码长太长，因此在Chipscope中分成了四段进行显示，由于Chipscope与ModelSim显示顺序不同，因此用相应数字表示了相应的结果顺序，可以看出译码结果均正确。
3.3 译码性能分析
下面对算法的性能以及工程占用资源等进行综合分析，在ISE软件上的综合报告中可以查看译码器在FPGA上的资源使用结果，如表2所示。
通过综合资源结果可以对译码器的吞吐率进行计算，公式如下：
式中N为有效码长，fmax为最大时钟频率，td为译码延迟的时钟周期数。吞吐率计算结果如表3所示。
4 结论
如今极化码正越来越受到研究者们的重视，而国内在极化码译码算法研究方面有待深入，尤其是在硬件平台中实现的较少。基于此本文主要针对极化码的SCL译码算法进行了研究与优化，并在FPGA上设计了译码器，最后在Xilinx的VC707开发板上进行译码器的实现。该译码器的设计降低了译码复杂度以及FPGA上的资源消耗，在码长为512时译码最高频率为143.988 MHz，吞吐率为28.79 Mb/s，有较强的工程实用性。
参考文献
[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] SASOGLU E，TELATAR I E，ARIKAN E.Polarization for arbitrary discrete memoryless channels[C].Information Theory Workshop，2009 ITW.IEEE，2009：144-148.
[3] ZHANG T，PARHI K K.A 54 Mbps (3,6)-regular FPGA LDPC decoder[C].Signal Processing Systems.IEEE，2002：127-132.
[4] 李廷墅.极化码译码算法的研究和分析[D].广州：华南理工大学，2013.
[5] LI B，SHEN H，TSE D.An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check[J].IEEE Communications Letters，2012，16(12)：2044-2047.
[6] 魏一鸣.极化码性能研究及其SCL译码算法的FPGA实现[D].南京：南京航空航天大学，2017.
[7] BALATSOUKAS-STIMMING A，RAYMOND A J，GROSS W J，et al.Hardware architecture for list successive cancellation decoding of polar codes[J].IEEE Transactions on Circuits & Systems II Express Briefs，2014，61(8)：609-613.
[8] 江涛，王涛，屈代明，等.极化码与奇偶校验码的级联编码：面向5G及未来移动通信的编码方案[J].数据采集与处理，2017，32(3)：463-468.
作者信息:
廖海鹏，卿粼波，滕奇志，何小海，邓媛媛
（四川大学 电子信息学院，四川 成都610065）