极化码SCL译码器设计∗

丁 冉 仰枫帆

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

1 引言

极化码（polar code）是 Arikan［1］在 2008年首次提出的一种基于信道极化理论［2］的新的信道编码。作为新的纠错编码，极化码因其简洁的构造和有效的编译码方法而得到广泛关注［3］。同时极化码被证明在二进制离散无记忆对称信道上能达到香农极限［4］，现在也被应用于 AWGN（Additive White Gaussian Noise）信道等其他相关信道环境中［5］。从实践的角度来看，Arikan在［1］中采用的SC译码方法的复杂度是ο(NlogN)，相比于Turbo和LDPC码，其复杂度较低可行性较高，基于SC方法的译码器在硬件实现方面具有很大的应用潜力［6～8］；Tal和Vardy针对Arikan的SC类算法提出了一种SCL（Successive Cancellation List）算法［9］，其克服了SC算法的错误传播问题，在此译码方法下，极化码的性能接近于ML（Maximum Likelihood）限。

2 极化码构造和SCL译码原理

极化码属于线性分组码［10］的一种。假设信道为二进制离散对称信道，极化码的码长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经过N个独立的子信道传输后在接收端得到信道输出序列为 y=(…，yN-1)。在接收端采用SCL（Succes⁃sive Cancellation List）译码方法对 y进行译码得到输入信号的估计 (u^0，u^1，…，u^N-1)。

SCL译码算法的基本思想是在极化码形成的一棵满二叉树上，按照后验概率最大原则寻找最合适路径得到译码序列。码长为N的极化码形成的码树的高度为N，根节点的深度为1，叶子节点的深度为N。树中的每个节点代表一个比特，第i层中共有2i-1个节点，表示给定所有可能值的情况下比特ui的取值结果。深度为d的节点与深度为d+1的节点间有两条边相连，分别代表ud=0和取ud=1的两条路径。在树的每一层，根据每条路径的路径度量值的大小，进行路径的排序、选择和淘汰。路径的度量值定义为式（1）。从根节点开始，当某层的路径数目大于L时，在该层只保留度量值前L位的路径进行下一层的延伸，下一层的路径度量值更新计算公式如式（2）所示，一直延伸至叶子节点，此时选择此层中路径度量值最大的路径作为最后的译码结果。L为路径的搜索列表宽度，当路径数大于L时，每层保留L条后，下一层延伸时总是需要计算2L个路径的度量值。

3 SCL译码器整体架构

本次设计的码长为N=1024，搜索列表宽度L=32，SCL译码器整体架构如图1所示，其中包含三个主要模块：译码模块、路径恢复模块和输入输出模块。输入输出模块主要有包含输入信息的信道信息Ram和包含输出的译码结果Ram。译码模块是译码器的核心模块，承担SCL算法各个译码环节的实现，其整体结构如图2所示。译码模块主要分为LLR值计算模块LLR_calculate、反馈模块Feed⁃back、度量值计算模块Metric_calculate、度量值排序模块Sort_top和整体控制模块IDX_control。译码模块的输入是LLR值，输出是路径的排序结果，排序结果先存入路径Ram中，等到1024个比特都译码结束时，路径恢复模块再从路径Ram中读路径排序结果，并根据此结果提取相应的码字，存入译码结果Ram。

图1 SCL译码器整体架构图

图2 译码器译码模块整体架构图

4 SCL译码器分模块具体结构设计

4.1 LLR值计算模块

本次设LLR计算模块用来计算度量值更新式（2）中的顶层LLR值)，此LLR的计算与SC算法中相同，采用蝶形递归形式［1］。由LLR值的递归算法式（3）可知，单个LLR值的计算分为f和g两种运算。两种运算的输入相同，均为一对LLR值L1和L2，故可用同一个计算单元实现。其中g运算根据反馈模块提供的指数值u^2i-1的值决定结果为 L2-L1或 L2+L1，f运算的数值是取 L1和 L2数值位的最小值，符号是两数符号位的异或。图3是单个LLR计算单元的结构图。L1和L2为数据输入，u为指数值u^2i-1，f_gn为输出的选择控制信号，当f_gn=0时选择f运算结果作为输出，当f_gn=1时选择g运算结果作为输出。

图3 单个LLR值计算单元结构

所有的输入信号的输入都要受针对LLR的控制模块LLR_control控制。图4是LLR计算顶层模块结构图。LLR计算顶层结构主要分为LLR计算模块和相关控制模块。LLR计算模块为L个PE（Processing Element）组成的阵列，每个PE承担单个LLR计算，其结构如图3所示。主要的控制模块为LLR_control模块，其功能是为计算模块选择正确的输入数据。由于本次设计中所有的LLR均存放在LLR_Mid_Ram中，故LLR_control模块通过对Ram读写地址的控制得到正确位置上的数据和将更新的结果写入正确的地址单元中。

图4 LLR值计算顶层模块结构

4.2 度量值计算模块

度量值计算模块用来完成式（2）的计算。由于路径数L=32，故度量值更新时会得到64条路径度量值。由计算公式可知，度量值计算时，需要根据当前路径对应的比特ui分两种情况讨论，分别记为U0_PM和U1_PM。当ui=0时，度量值计算为式（4）所示。当ui=1时，度量值计算需要考虑第i位若为冻结位的特殊情况，为式（5）所示。

若ui=1且第i位是冻结位时，直接将度量值置为所能表示的最小值，即所有位全是1。图5是度量值计算模块的顶层结构，信号Pre_PM是此路径的上一层对应的度量值PM()，其从路径度量值存储Ram中读取。计算时需要读取信道的状态信息，其存于Bit Rom中。在将两个度量值U0_PM和U1_PM均计算出后，对其进行初步的排序，得到较大值Max_metric和较小值Min_metric以及对应的选择比特Umax和Umin，并将较大值依次放入前32个位置，较小值依次放入后32个位置上。这样做是由于错误的冻结位给度量值带来的影响要大过不同路径带来的影响，将初步排序结果的大小值分前32位和后32位有序放置，将缩短后续的排序时间。

图5 度量值计算模块结构

4.3 度量值排序模块

度量值排序模块采用常见的冒泡排序法，将相邻的度量值两两一组，送入单个排序单元中，进行两个数的比较和交换。由于度量值模块产生了64个度量值，故完成一轮排序需要32个排序单元。

在排序模块中对应的路径选择比特也需要根据度量值的排序结果进行排序，同时还需要对每条路径加比特索引，以供路径恢复模块针对每条路径提取相应码字。

4.4 反馈模块

反馈模块用来提供LLR值计算中g运算的指数值u^2i-1。反馈模块对u^2i-1的计算原理与LLR值计算原理相同，但更新方向相反，故两者顶层模块结构相同，设计思路类似，均分为控制模块和计算模块。计算模块同样是由L个节点反馈信息更新单元组成的计算阵列。控制模块产生对应的读写控制信号，为计算模块提供正确的输入并将更新后的结果存入正确的地址单元中。每当产生新的码字ui时，先存入顶层，再从顶层到底层依次按层更新。更新的方式根据节点类型的不同也有两种，以N=8为例，如图6所示，图中有f节点和g节点。若当前节点是f节点，则直接将当前层数据存入下一层的f节点，若当前节点是g节点，则将当前层数据直接存入下一层的g节点，并将下一层f节点的内容取出与当前数据模二加后，再重新存入下一层f节点。图7为单个节点反馈信息更新单元结构图。flag信号是输出结果选择信号，flag=1时输出g节点的值，flag=0时输出f节点的值。flag信号由反馈模块的控制单元提供。

图6 N=8时反馈部分产生原理图

图7 单个节点反馈信息更新单元结构

4.5 控制模块

控制模块由IDX索引控制寄存器和状态机组成，主要控制功能由状态机实现。译码器工作时，根据每个模块的功能，设置每个状态下的各个模块开始或结束的标志信号，在时序控制下，状态机监控中间进程的标识信号来完成状态的转换，保证模块之间协同有序的工作。当每次完成一轮状态转换后，IDX加1，表示进行下一个比特的译码。直到1024个比特全部译码完毕时，IDX又清零，控制模块启动路径恢复模块进行工作。

4.6 路径恢复模块

路径恢复模块根据排序模块提供的加了索引的路径选择比特进行对应路径的码字提取。排序结果按从后往前顺序输入路径恢复模块，每条路径按照自己的索引，从最后一位比特的位置开始读取排序结果，提取相应的码字，然后再根据排序的结果，更新下一次要读的索引，然后重复上述步骤一直读到第一位信息比特时结束。

5 译码器FPGA实现结果和性能分析

本次设计实现使用的是Altera公司Stratix V系列的5SGXEA7N2F45C1芯片，在Quartus II下的综合后的资源占用如表1所示。

表1 SCL译码器综合后资源占用表

译码器的吞吐率也是衡量其性能的重要指标之一，本次设计中，译码器经过大约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 结语

本文基于极化码的SCL译码算法，设计N=1024，L=32时的基于此算法的译码器，并完成了在FPGA上的实现，得到了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］.国防工业出版社，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.