极化码半平行SCL译码器的FPGA实现

梅 晟，仰枫帆

(南京航空航天大学 电子信息工程学院，江苏 南京211106)

0 引言

极化码由土耳其教授Erdal Arikan在文献[1]中于2007年首次提出，它是一种基于信道极化现象的信道编码，并且是唯一被证明能达到香农极限[2]的信道编码，具有较低的编译码复杂度，受到了广泛研究。随后，学者对SC译码算法进一步优化，提出了SCL译码算法[3]，极大地提升了译码性能。同时也对极化码的工程实现进行了研究。在众多SC译码结构的基础上，Leroux等人在文献[4]中设计了半平行译码结构，该结构以牺牲较小的吞吐率为代价大幅度降低了系统复杂度，具有较小的时延。在前人的基础上，本文通过对半平行结构的SCL译码器的分析，重点工作放在硬件资源复用和内存结构的优化上，提高了硬件吞吐量并降低了译码时延，最终通过VerilogHDL硬件描述语言进行实现，同时给出相应时延、资源占用率等关键测试数据。

1 信道极化现象

(1)

2 极化码的编译码方法

2.1 极化码编码方法

2.2 极化码SCL译码算法

极化码发展至今已有多种译码方法，其中SCL译码算法性能较为优良，且具有较低的译码复杂度。

(2)

对上述规则进行细化，令对数似然比(Log Likelihood-Ratio，LLR)为:

(3)

(4)

式(3)为奇数下标记为f函数和式(4)为偶数下标记为g函数，通过对数域化简能够得到[10-11]：

(5)

在SC译码算法中，每个阶段仅存在一条候选路径，错误极易累加。所以在SCL译码算法中，每个译码阶段都存在路径度量值较大的L(L≥2)条候选路径，而最终目的即为从这L条路径中选出最佳路径。与SC译码算法中对当前比特直接判决不同，SCL算法中每一个比特在译码过程中的顶层按式(6)进行路径度量值PM的计算,

(6)

初始列表中只有一条空路径，且PM(φ)=0。可以将此过程表述为一个深度为N的满二叉树。

3 SCL译码器硬件结构设计

3.1 译码器整体结构设计

在设计的译码器中，选取码长为1 024，码率为1/2，P=2，以BEC为信道挑选方法，列表宽度L=32。对译码器中的数据进行8 bit量化，路径度量值进行12 bit量化，对译码过程中发生的溢出采用截断处理，使得位宽不会逐级递增，大大简化了译码器的设计复杂度，且只有极小的性能损失。整体结构主要包括以下顶层模块：LLR计算模块(LLR_top)、修正模块(Corrected)、度量值计算模块(Metric_top)、度量值排序模块(Sort_top)、反馈模块(Feedback)、控制模块(Controller)和路径恢复模块(Path_recover)，如图1所示。在译码开始之前，首先将信道LLR分组，存入位宽为128，深度为64的RAM中作为初始LLR，即图1中的LLR_based RAM。

图1 译码器整体结构

3.2 LLR计算模块

LLR计算模块由LLR控制单元和计算单元PE组成，而PE结构又由P个式(5)中的f或g模块构成，在单次顶层LLR的计算中，每一层都仅激活f或g节点中的一种。

为了更进一步降低SC译码器的复杂度，本文采用半平行译码结构。该结构以增加少量时延为代价大幅削减了PE的个数，从而降低了译码器的复杂度。

若PE结构数量为P，则半平行译码结构的时延周期[11]为：

(7)

另外，半平行结构译码器的利用率为：

(8)

所以总的PE数量为LP，其中L为列表宽度。

3.3 LLR存储单元

因为每条路径包含P个PE单元，单次计算会产生P个内部中间LLR，所以每次需要存储的数据为PQLLR，其中QLLR为每个LLR数据的存储位宽，所以内部LLR存储模块输入位宽为PQLLR，同时每次计算需要2P个初始LLR数据，所以内部LLR存储模块输出位宽为2PQLLR，为实现这一结构，本文采用双SRAM来实现2PQLLR数据的输出。

以N=8的双PE结构的半平行设计为例，如图2所示，首先从s=3层开始读取数据，分2个时钟完成，第1个时钟可以计算出s=2层的4个LLR数据，并存储到SRAM1内，第2个时钟同理计算出s=2层的LLR数据，并存储到SRAM2内；接着读取s=2层的LLR数据，此时只需要一个时钟就能完成，但是需要同时读取SRAM1和SRAM2的数据送入2个PE结构中同时计算，得到s=1层的2组LLR，并存入SRAM1中；最后读取s=1层的数据，此时只有单PE结构在工作，输出的数据位宽不能满足存储要求，所以在高位补零达到存储需要。此时得到的数据便是顶层LLR，需要接着进行路径度量值的计算。

图2 N=8，P=2的LLR存储器结构

3.4 度量值计算模块

在得到32条路径对应的顶层LLR之后，要对当前2L=64条路径的度量值进行计算。用一块1 024*1的ROM存放信息比特和冻结比特的位置信息，0对应冻结比特，1对应信息比特。当本模块开始工作时，从Bit_location ROM中读取位置信息和顶层LLR的符号位一起作为控制模块的输入，来控制式(6)中所对应的3种情况。

在计算出候选比特为0和1格子的路径度量值后，使用一个选择器输出其中的较大值和较小值以及相对应的候选比特。然后对路径进行冒泡排序，将前32条路径度量值进行存储，供下次计算使用。

3.5 反馈模块

3.6 路径恢复模块

本模块的功能为从排序结果中将路径提取出来，这样使得在SCL译码模块中不再需要对路径进行保存和复制。初始状态下，将32条空路径设置索引号0～31，每条路径按照自己的索引从最后一个比特的位置读取排序结果，提取相应的码字。然后根据排序结果来更新下一次要读的索引，重复此步骤直到读到第1位比特，最终将输出的码字发送到译码结果存储器中，其深度为512，数据位宽为32。

4 仿真结果与分析

在本文的极化码SCL译码器设计实现的过程中，采用的FPGA芯片是Altera公司Strtix V系列的5SGXEA7H3F35C3，使用QuartusⅡ 15.0综合后的结果如表1所示。

表1 极化码SCL译码器硬件资源统计

资源类型占用量百分比/%逻辑单元(ALMs)71 26518存储器单元/bit2 170 8804端口315

吞吐率T是评价硬件译码器性能的重要指标，其计算公式为：

(9)

本文设计中，码长为1 024，译码器的工作频率为100 MHz。译码器平均时延为0.040 ms，所以吞吐率可以达到1 024/(0.040×10-3)=25.6 Mbps。可以观察到，本文设计的译码算法译出一个码字大概需要4 000个时钟周期，而系统面积的占用率仅为6%。

硬件译码算法的另一个重要评价指标是误码率(BER)，本文8 bit量化与理论未量化译码算法之间BER的性能比较如图3所示。

图3 SCL译码算法性能曲线

从图3中可以看出，量化之后与理论未量化之间性能相差无几，在量化后的BER只与理论值相差0.1 dB左右，验证了优异的译码器性能。

5 结束语

对码长为1 024的极化码采用了公认性能优良的SCL译码算法，对每条候选路径运用半平行计算的硬件架构，相较于平行结构大幅减少了系统硬件的资源占用，然而在吞吐量上却与之相差较小，极大地降低了硬件实现的复杂度。考虑到PE结构的复杂度，如何进一步优化结构并在速度与面积之间取得平衡，是后续研究的方向。

[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] SHANNON C E.A Mathematical Theory of Communication[J].Bell Labs Technical Journal，1948，5(4)：3-55.

[3] TAL I，VARDY A.List Decoding of Polar Codes[C]∥IEEE International Symposium on Information Theory Proceedings，IEEE，2011：1-5.

[4] LEROUX C，RAYMOND A J，SARKIS G，et al.A Semi-Parallel Successive-Cancellation Decoder for Polar Codes[J].IEEE Transactions on Signal Processing，2013，61(2)：289-299.

[5] ARIKAN E.Systematic Polar Coding[J].IEEE Communications Letters，2011，15(8)：860-862.

[6] ARIKAN E.Channel Combining and Splitting for Cutoff Rate Improvement[J].IEEE Transactions on Information Theory，2005，52(2)：628-639.

[7] LI H，YUAN J.A Practical Construction Method for Polar Codes in AWGN Channels[C]∥Tencon Spring Conference，IEEE，2013：223-226.

[8] MORI R，TANAKA T.Performance of Polar Codes with the Construction Using Density Evolution[J].IEEE Communications Letters，2009，13(7)：519-521.

[9] TAL I，VARDY A.How to Construct Polar Codes[J].IEEE Transactions on Information Theory，2013，59(10)：6562-6582.

[10] FOSSORIER M P C，MIHALJEVIC M，IMAI H.Reduced Complexity Iterative Decoding of Low-density Parity Check

Codes Based on Belief Propagation[J].IEEE Transactions on Communications，1999，47(5)：673-680.

[11] LEROUX C，TAL I，VARDY A，et al.Hardware Architectures for Successive Cancellation Decoding of Polar Codes[C]∥IEEE International Conference on Acoustics，Speech and Signal Processing (ICASSP)，2011：1665-1668.