无线通信系统-FFT与信道译码VLSI设计 课件 第6章 卷积码并行列表译码算法与硬件结构设计

第6章卷积码并行列表译码算法与硬件结构设计6.1卷积码并行列表译码方法6.2基于路径标识的非咬尾卷积码并行列表译码算法6.3并行列表译码器的硬件结构设计6.4理论分析与硬件测试本章小结

6.1卷积码并行列表译码方法

考虑一个表示为(c,1,u)的卷积码，其编码器中包含一个u级移位寄存器，并对每一个输入比特相应产生c个输出比特，因此编码码率为1/c。图6.1以(2,1,2)卷积码为例，对卷积码编码器结构以及译码网格图进行了说明。

图6.1卷积码编码器结构与相应的译码网格图

图6.1卷积码编码器结构与相应的译码网格图

6.1.1非咬尾卷积码的列表译码

为了在路径回溯阶段并行输出多条信息序列，并行列表译码在前向递推过程中需要保留到达每网格每一级每个状态的L条最优路径，这里L为列表长度。用

表示连结网格第n-1级状态sk与第n级状态s的分支度量，其中

；定义

表示连结初始状态与网格第n级状态s的第l+1条最优路径的路径度量。在非咬尾卷积码对应的网格中，初始状态确定为0状态，因此路径度量在网格第

级初始化为：

完成初始化操作后，对于

路径度量

在前向递推过程中按照如下方式进行计算：

其中

表示第n级网格状态s的M个前序状态索引，

表示到达每个状态的L条路径的路径次序。当l>0时，参数k,j进一步满足

在(6.3)中，

作为状态序号，表示到达网格第n级状态s的第l+1条最优路径在网格第n-1级经过s的前序状态

，而

作为路径次序序号，对应于路径在该前序状态的路径次序。上述前向递推过程可以用图示的方式进行描述，如图6.2(a)所示。定义2u×L维矩阵Kn和Rn，它们分别为网格第

级的状态索引矩阵和路径次序矩阵，用于存储前向递推过程中计算得到的参数

：

图6.2并行列表译码算法的前向递推与路径回溯操作

6.1.2咬尾卷积码的列表译码

咬尾卷积码只满足网格起始状态与结束状态相同，但具体的起始或终止状态是未知的。因此在咬尾卷积码网格中，连结未知初始状态与终止状态的最优路径需要从2u个子网格包含的所有路径中选出。根据这一定义，对咬尾卷积码执行列表长度为L的列表译码，首先应当搜索出每个子网格中的

条最优路径，然后再从所得的全部2uL条候选路径中选出最优的L条，并输出其对应的信息序列。为了降低译码复杂度，单次与多次状态估计方案通过给出初始状态的一个或一组估计值来使译码操作只涉及到少数子网格，以此来减小信息序列的搜索空间。

这样一来，咬尾卷积码列表译码器可以在非咬尾卷积码列表译码器的基础上通过添加初始状态估计单元来实现。用

表示未知初始状态的第l=1个最优估计，这里的“第l+1个最优”表示以

为初始l状态的咬尾路径是全部2u条咬尾路径中的第l+1条最优路径。进一步令

表示在以s为初始状态的子网格中通过列表译码确定的L条最优路径，用

表示咬尾卷积码网格中的第l+1条全局最优路径，则

6.2基于路径标识的非咬尾卷积码并行列表译码算法

在递归执行(6.6)来完成对pl的路径回溯过程中，我们可以得到路径次序序列

，它描述了pl在网格每一级的路径次序。对路径次序序列进行进一步研究，可以发现其具有非递减的数学性质，总结在下面的定理中：

路径次序序列能够用于揭示卷积码网格中非最大似然路径之间的关系。具体而言，利用路径次序序列，可以将非最大似然路径pl与前l条路径p0,...,pl-1

中的一条相关联。这样在得到前l条路径之后，不必回溯整个网格即可确定pl，有利于降低列表译码器并行路径回溯的复杂度。下面的定理对两条路径之间的关系进行了描述：

图6.3对定理6.2描述的路径间关联性进行了更为具体的说明。对于路径plʹ同样能得到与之相对应的路径次序序列

。特别地当lʹ时，定理6.1表明存在参数nʹ*使得plʹ在网格的第nʹ*级出现首个非零路径次序。注意到路径pl的非零路径次序出现于网格的第n*级，我们有

这是由于plʹ满足

，根据定理6.1对于

均有

。上面的分析使我们

能够通过少量参数来唯一确定每一条非最大似然路径，这些参数构成了该条路径的路径标识。

图6.3列表译码算法确定出的多条最优路径之间的关联性

6.2.1基于路径标识的前向递推运算

对于网格第n级的状态

，如果将其看作网格的终止状态，那么定理6.2也可以用来描述到达s的L条最优路径之间的关联性。具体而言，对于到达s的第l+1条最优路径，当l>1时定义与之相对应的路径标识为

，其中

♥表示与第l+1条最优路径相关联的路径在状态s的路径次序；

♥表示第l+1条最优路径的路径次序变为非零时所在的网格级数；

♥表示第l+1条最优路径在网格第

级所经历状态的前序状态索引。

6.2.2基于路径标识的路径回溯

图6.4基于路径标识的并行列表译码算法执行过程

6.2.3基于网格循环性的咬尾卷积码初始状态估计器

在前面我们提到，列表长度为L的咬尾卷积码列表译码需要基于网格未知初始状态的L个最优估计

来达到最优纠错性能。在已有的研究工作中，有的方案通过穷尽搜索全部子网格来确定

条咬尾路径的路径度量，再对路径度量排序来得到

，该方案具有极高的计算复杂度。本节我们将从咬尾卷积码网格的循环性入手，以低运算复杂度来实现对初始状态的有效估计。

图6.5基于网格循环性的初始状态估计算法流程图

图6.6不同初始状态估计方法下咬尾卷积码列表译码器BLER性能随Eb/N0变化曲线

图6.6不同初始状态估计方法下咬尾卷积码列表译码器BLER性能随Eb/N0变化曲线

6.3并行列表译码器的硬件结构设计

在硬件实现方面，基于路径标识的非咬尾卷积码并行列表译码器具有图6.7所示的顶层结构。

图6.7并行列表译码器顶层结构框图

了实现对咬尾卷积码的列表译码，需要在上述非咬尾卷积码列表译码器的基础上进一步配置初始状态估计器。这里的估计器利用6.2节所设计的算法依次确定并输出状态

。译码器所要执行的各类操作的先后次序以时序图的方式表示在了图6.8中。

图6.8咬尾卷积码并行列表译码器工作时序图

6.3.1并行列表译码器的ACS单元

在列表长度为L的并行列表译码器中，执行radix-M算法的ACS单元需要从LM个来自前序状态的路径度量中确定出L个最优的路径度量。故如图6.9所示，电路中需要消耗LM个加法器来实现路径度量与相应的分支度量的累积。随后，路径标识与相应的路径度量合并后通过由log2M级树形连接的比较器所组成的选择网络，而选择网络输出的路径标识进一步通过L-1个路径标识计算单元进行更新。最后将更新后的路径度量和路径标识送至寄存器进行缓存，用于网格下一级的ACS计算。

图6.9并行列表译码器中执行radix-M运算的ACS单元结构（M=2）

不同于Viterbi译码器的ACS单元所使用的2输入1输出比较器，并行列表译码器中用于构建ACS单元选择网络的比较器为2L

输入L输出模式：所接收的2组输入各包含L个按大小次序排列的路径度量，比较器选择其中L个最优度量并排序后作为输出。由于输入比较器的路径度量形成了分段有序序列，我们可以采用归并排序的策略来设计低复杂度的比较器结构。图6.10以L=4的情形为例给出了比较器的数据流图与电路结构。具体而言，首先利用归并网络从输入中选出L个最优路径度量，它们构成一个双调序列；然后利用双调排序器完成对输出路径度量的排序。在硬件实现上，2L输入L输出的比较器需要消耗L个最大值选择器和L/2·log2L个换向器，通过log2L+1轮比较操作来完成计算任务。

图6.102L输入L输出比较器的信号流图与电路结构（L=2）

图6.11以

的计算为例说明了路径标识计算单元的电路结构。一般地，

与

的计算只用到2个数据选择器和1个相等判断单元，这里相等判断单元通过按位异或的方式来判别两个输入数据是否相同；另一方面，基于(6.11)计算

要用到2l+1个相等判断单元和1个l输入的二进制编码器，其中二进制编码器的输入在任一时刻有且仅有一路信号维持高电平，编码器的输出为该路高电平信号的次序。

图6.11路径标识计算单元的电路结构

6.3.2并行列表译码器的路径回溯单元

为了并行恢复路径

及相应信息序列

，如图6.12(a)所示，电路中部署了L个路径回溯模块。路径回溯模块l一方面利用存储的前序状态索引递归计算路径p1的状态并将结果传递给之后的L-l-1个路径回溯模块，另一方面接收前l-1个模块所传递的状态值。如图6.12(b)所示，路径回溯模块0用于完成路径p0的恢复，它从网格第N级开始执行回溯操作，通过相邻两个状态值可以得到该状态转移所对应的信息符号，并将其缓存在先入后出（LastInputFirstOutput,LIFO）单元中。

路径p1

，l>0对应的路径回溯模块

具有图6.12(c)所示的电路结构，它从网格第

级开始执行回溯操作，并在这一级利用参数

从l-1个传递来的状态值中选出状态

作为回溯起始状态。由于回溯操作涉及到网格的第0级至第

级，故在理论上，用于缓存路径回溯模块l所产生的信息符号的LIFO单元深度应达到

。然而注意到路径p1所对应的路径次序满足

，即p1在网格的第0级至第

级是一条最大似然路径，因此如果卷积码的判决深度为D且D<

，路径p1在网格第

级会以很高概率与路径p0重合。利用这一性质，可以将路径回溯模块l所对应的LIFO单元深度进一步减小至

。

图6.12并行路径回溯单元的硬件结构设计

图6.12并行路径回溯单元的硬件结构设计

6.3.3初始状态估计器

图6.13给出了初始状态估计器的硬件设计方案。图6.13初始状态估计器的顶层结构图

图6.14给出了ACS单元的底层硬件结构图，可以看到ACS单元选用减法器来实现分支度量的累积，相应地比较单元选取两个路径度量中的最小值输出。这些设计旨在使ACS单元包含的计算资源能够同时承担其他计算任务，即当ACS单元完成Viterbi算法在网格中的前向递推运算后，再次复用其中的计算资源来计算咬尾路径度量估计值

，搜索状态

与

以及确定集合

。ACS单元内计算资源的不同使用方式在图6.15中进行了总结。

图6.14初始状态估计器中ACS单元的硬件结构设计

图6.15ACS单元中计算资源在不同阶段的执行的操作

图6.15ACS单元中计算资源在不同阶段的执行的操作

6.4理论分析与硬件测试

6.4.1非咬尾卷积码列表译码器存储资源分析

对于非咬尾卷积码的列表译码，表6.2总结了基于列表扩展算法和树形网格算法算法的两种串行列表译码方案、传统并行列表译码方案、文献[39]改进的并行列表译码方案以及本章提出的基于路径标识的并行列表译码方案所对应的存储资源消耗。

其中(c,1,u)卷积码的判决深度为D，M进制信息符号序列长度为N，译码器列表长度为L，输入软信息和路径度量分别量化为wc和ws

比特。译码器中输入软信息的缓存、前向递推中路径度量及相关参数的存储、路径回溯所需的辅助参数存储及LIFO构建均在表中进行了统计。进一步，图6.17选用EC-GSM系统的卷积码码型G0=133，G1=171，G2=145并固定信息序列长度为512比特，即Nlog2M

，在这些前提条件下研究了D=64，M分别取2和4的情况下译码器资源消耗与列表长度L的关系。

图6.17不同列表长度下非咬尾卷积码列表译码算法的存储资源需求

6.4.2基于FPGA的列表译码器硬件实现与性能测试

我们在FPGA上对不同的列表译码器设计方案进行了硬件实现与性能测试。所用的FPGA型号为具有-3速度等级的XilinxKintex7XC7K325T，编译器版本为ISE14.2。对于非咬尾卷积码的译码，我们选用Viterbi译码器作为基准方案来衡量不同列表译码器的硬件复杂度与性能，实验中测试了基于树形网格算法的串行列表译码方案、传统并行列表译码及其改进设计、以及本章提出的基于路径标识的并行列表译码。

对于非咬尾卷积码的译码，表6.3与表6.4的上半部分分别统计了不同译码器的FPGA资源消耗情况与译码时延、最大吞吐量以及编码增益提升量等性能指标。

6.4.3列表译码器的VLSI实现

利用130nmCMOS工艺，我们对前面在FPGA上测试的基于路径标识的并行列表译码进行了综合与布局布线操作，实验所用的编译器为Synopsys。图6.18(a)统计了不同列表长度下基于路径标识的并行列表译码在布局布线后的电路面积，作为对比，图6.18(b)同时