一种低硬件复杂度极化码译码器的FPGA实现

丁响

（西南电子技术研究所 四川省成都市 610036）

信道编码用于对抗信息传输过程中的干扰，将因干扰导致的错误信息进行纠正，提高通信的可靠性。经过几十年的发展演变，Turbo码和LDPC从众多信道编码方案中展现出优势，是当前应用最多的两种编码方案，其性能优越，但是复杂度较高，且不能完全达到香浓极限。由E.Arikan[1]提出的极化码(Polar Code)作为第一种理论上可以使信道容量达到香农极限的编译码方法，成为编译码领域的的研究热点。华为公司对极化码做了大量研究，取得了较多专利成果，并成功将极化码推举为5G控制信道的编码方案，使得我国在通信领域走上了世界舞台。

出于知识产权的原因，越来越多的项目要求使用极化码编译码方案。当前，极化码的研究主要集中在如何提高译码性能、降低计算复杂度、减少译码延迟、节省硬件资源等问题上，使其能应用于实际系统。

在算法研究方面，E.Arikan在提出极化码构造理论的同时，给出了一种极化码SC译码算法，该算法与置信度传播（Brief Propagation，BP）算 法 和最大似 然 比（MaximumLikelyhood，ML）算法相比，译码复杂度最低。Vardy[2]等学者提出的连续删除列表（SCL）算法和Niu.K[3]等学者提出的连续删除堆栈（SCS）算法是基于SC 算法的改进，都是通过增加SC算法中的候选路径来提高译码性能，降低误码率，但同时也增加了译码的复杂度。

在硬件实现方面，最早Leroux 等人提出了几种SC译码器的硬件实现结构[4-5]，其中经典结构有树形以及线性结构等。后来，Leroux等人对其进一步优化，提出了SC译码的半平行译码结构[6]，该结构通过牺牲较小的吞吐率来大幅度降低系统复杂度，但内存复杂度没有改善。随后，诸多学者先后提出了SCL[7-8]、CA-SCL[9]等算法的硬件实现方法，这些算法的系统复杂度相对SC算法也显著提高。

图1：译码器整体结构

图2：LLR计算单元

图3：部分和更新矩阵

面向某项目物联网超低功耗的实际应用，本文设计了（1024，512）的polar码，基于译码性能和硬件实现复杂度的综合考虑，选取SC算法，采用半平行的硬件实现结构，研究其性能和复杂度的改善。通过对半平行结构的SC译码器的研究，给出了完整硬件架构，详细的分析和介绍硬件设计中各子模块，优化了论文中[6]部分和更新模块，在仅增加极小的译码时延的情况下大大降低了硬件资源。

1 极化码编译码原理

1.1 极化码编码原理

极化码为一种线性分组码，通过编码使码字产生极化现象，即部分信道（码字的位）的信道容量趋于0，即纯噪声信道，另外一些则趋近于1，即完美信道。因此，编码时将待编码的比特放置在信道容量高的位上，冗余位放在信道容量低的位上，一般将冗余位设置为0。

极化码码长为N，对于信息位长为K的编码，首先需要知道N个信道的信道容量大小排序。将K个信息比特放在K个信道容量最大的信道位置上，其余为0，称为冻结比特，排序后的序列记为根据线性分组码的编码方式进行编码初始信息为生成的码字。根据信道组合方法可以迭代得到生成矩阵其中F为核矩阵为F的n阶Kronecker积，n=log2(N)。BN为比特翻转操作，其目的是将输入序列的位置进行置换，如xi的下标i的二进制表示为〈i〉2= (in-1in-2…i0)，其中ij∈{0,1}，经过比特翻转操作后的二进制表示为〈i〉2= (i0i1…in-1)。

1.2 极化码SC译码算法

SC译码是通过对每个传输码字的LLR（对数似然比）进行计算，进而译出码字。定义第i个比特的对数似然比为其中为条件转移概率为接收序列为前i-1个已知信息的估计值，其判决准则为：

其中λ=n,n-1,…,1，f和g分别为：

为了便于硬件实现，使用最小和算法计算f(α,β)≈f(α,β)≜sign(α)sign(β)min(|α|,|β|)，其可以直接由比较器和加法器实现，避免了使用乘法器和除法器等比较复杂的电路。

1.3 半平行SC算法

线性SC算法在l=n-λ 层被激活时，有2l个计算单元（PE）在同时计算，且只有其中一种函数（f或g）被激活，在一个码字向量译码过程中共被激活2λ次。所以，总的译码时长为：

图4：硬件资源

当SC译码算法采用半平行结构时[6]，提高了PE使用率，大幅减少了PE的数量，仅增加了少量时延，是一种降低SC译码器复杂度的有效方法。不失一般性，设置PE结构数量为P=2p，当2l≤P时，对时延没有影响，当2l>P时需要个时钟周期完成l层的更新。故半平行译码结构的时长为：

2 改进的SC译码器硬件结构设计

本文根据项目需求，设计码长为1024，码率为1/2的极化码。经仿真论证，对于码长大于1024的码块，当PE的并行度为64时，可达到90%以上的吞吐率，故选取P=64。定点化译码器中的数据，并对译码器数据溢出采用饱和处理，保证译码器的位宽不变，极大地降低硬件复杂度，同时译码器性能几乎无损耗。译码器的整体硬件结构主要包括以下模块: 信道LLR缓存、中间计算结果LLR缓存 、LLR计算单元PE、信息比特估算单元、部分和更新以及存储单元，如图1 所示。

2.1 LLR计算单元

为了便于硬件实现，本文将f函数和g函数两者融合为一个节点，亦即一个计算单元PE，通过复用器可以实现二者的功能转换。f函数的进一步简化为：

其中|X|代表变量X的幅值，ψ(X)为他的符号，在verilog语言中，

g函数符号项的输出将由λa，λb的幅值大小以及的大小决定，计算公式如下：

PE最终输出结果由B(l,i)决定，即

B(l,i) 由计算层数l和码字序列的标号i决定，为B(l,i)=il。

2.2 LLR存储

LLR存储分为两个部分：一是接收信道信息的LLR存储，另一个则为PE计算结果LLR存储。为了提高吞吐率，信道接收LLR的存储采用乒乓操作。定点化后LLR的数据位宽为Q-bit。在l层，函数f和g的计算交替进行，且计算的次数相等，都是2n-l⁄2次。采用时分多路技术，l层LLR的存储个数为N⁄2n-l，故LLR的存储空间只需要(3N-1)Q比特，其中2NQ比特用来存储接收信道LLR，(N-1)Q比特则用来存储由PE计算得到的内部LLR。由于码长仅为1024，为了避免添加多余的延迟，使得在一个时钟周期内可以同时读取PE的输入数据和存储PE计算的输出结果，本文采取寄存器的存储方式，使得控制简单，并且有效地利用了硬件资源。在l≤p层时，存储寄存器的位宽为比特，深度为1；在l>p层时，存储寄存器的位宽为比特，深度为2n-1-p。

以N=8，P=2的半平行结构设计为例。首先从l=3层开始读数，分两个时钟周期完成，第一个时钟周期读取的4个LLR数据并计算出l=2层的2个LLR数据，并存储到的低PQ位中，第二个时钟周期读取的4个LLR数据并计算出l=2层的2个LLR数据，并存储到的高PQ位中；接着读取l=2层的数据，只需一个时钟周期即可计算出l=1层的内部LLR，并将其存储到的PQ位中；第四个时钟周期读取l=1层的LLR，且只需要一个时钟周期即可计算出l=0层的内部LLR，此时PE的并行度Puse少于P，仅需存储Puse个PE的计算结果，即存储到的Q位中。

2.3 部分和的存储和更新优化

在整个译码过程中，当PE进行g函数的操作时，应指定具体部分和项，即一旦被估计出来，部分和项就需同步更新。由论文[2]可知，部分和存储为Cλ[β][i mod 2]，其中β为分支，0≤β<2n-λ，λ为层数，0≤λ

图5：算法仿真结果（N=1024）

论文[6]中部分和更新较为复杂，本文对部分和更新方法进行了优化，具体实现如下：部分和更新是在信息比特估算完成的时候同步进行，即在层数l为0时进行更新，而每层的更新策略如下：在l层时，当[in-l-1,in-l-2),…,i0]所有位均为1， l层部分和的更新公式为：

2.4 控制模块

译码器控制单元是译码器正常工作的关键，用于控制和协调各阶段的译码过程。这部分主要包括LLR输入数据的写入和读取，译码进程计数器，硬判决比特的RAM的读写地址和控制信号，冻结比特存储单元ROM的读地址和控制信号。

信道缓存需要将累计接收的2P个数据依次写入reg寄存器中，直至一帧数据接收完毕，才开始译码。

译码进程计数器主要包括输出当前译码比特的序列号i（i∈{0,1,…,N-1}），当前计算的层数l，以及当前层内部计算所需的时钟数ϵ，i的计算比较简单，即当层数l=0时，i加1。层数l的计数依赖于当前译码比特的序列号i和当前层数内部计算的时钟数ϵ。译码开始时，即i=0时，层数l=n-1，当时，l=l-1，当层数l减少到0时，将l更新为layerini，layerini是从低位查找二进制表示的i中第一个为1的比特位置索引号，例如以N=1024为例，i=0,1,2,3,4,5,6,7,8,9,……，则当前译码比特i对应的层数l的起始层数为layerini=9,0,1,0,2,0,1,0,3,0,……。由于l层需要2l次计算，则需要个时钟，因此ϵ的计数从0到时复位。

ROM块用于存储冻结比特的信息，提供信道信息给译码器进行译码，ROM的地址索引与当前比特的序列号一一对应。

3 仿真结果与性能分析

本文实现译码器的硬件平台为Xilinx公司的V7系列型号xc7vx485tあg1157-2的FPGA芯片，使用2017.4版本的Vivado进行综合，得到的资源占用情况如图4所示，资源使用率仅为4%左右。

仿真结果表明，在码长1024，工作频率100M，译码器的时延为0.02081ms，即译出一个码块需要2081个时钟周期。

根据吞吐率计算公式：

得到译码器吞吐率为49.2Mbps，与全平行结构相比，吞吐率降低了2%，而硬件资源节约了大概67%。

硬件译码算法的另一个评判标准为误码率，本文中8bit量化与未量化的误码率BER（bit error rate）和误帧率FER（frame error rate）如图5所示，统计帧数为106。从图中可以看出，量化之后BER、FER与理论未量化之间相差不超过0.05dB，表明了该译码器算法硬件实现可以获得与浮点计算同等的优异性能。

4 结语

对码长为1024，码率为1⁄2的极化码，选取硬件复杂度最低的SC 译码算法，采用半平行的硬件架构，详细论述了LLR计算单元、LLR存储、控制模块的实现，并新设计了一种易于实现的部分和更新模块。相较于平行结构，该设计减少了67%的系统硬件资源占用，显著降低了FPGA实现的复杂度，同时吞吐量达到了49.2Mbps，仅降低2%，体现出较高的工程应用价值。