基于改进Viterbi解码器的FPGA速度与功耗优化

V.Prasanth, Rubia Tasneem

Assoc。印度普拉提工程学院电子与通信系教授。
印度Pragati工程学院电子与通信系硕士生。

摘要

低功耗、小面积和高速限制的超大规模集成电路技术的进步主要用于数据的编码和解码。本文提出了利用维特比解码器(VD)进行网格编码调制(TCM)时，在提高速度的同时降低功耗和成本。Viterbi译码器使用Viterbi算法进行TCM译码，但在接收端并没有实现有效的速度和功耗降低。本文提出了一种采用t算法的VD预计算流水线结构。优先级编码器与卷积编码器一起使用，在TCM系统中以1 / 2的码率优先发送高优先级的数据位。该架构在不降低性能的情况下降低80%的功耗。该体系结构中使用的时钟速度的降低可以忽略不计。利用Xilinx ISE对所提出的结构进行了仿真和综合，并利用FPGA Spartan-6 XC6SLX45对低功耗目标器件进行了分析。结果表明，该方法功耗低。

关键字

优先编码器，Spartan-6 XC6SLX45，网格编码调制(TCM)，维特比解码器。

介绍

在无内存噪声系统中，采用viterbi算法对卷积码进行译码。该算法可以应用于通信系统中遇到的主机问题。许多带效率系统采用网格编码调制技术[1]。TCM系统使用高速率卷积码，即使卷积码的约束长度是适度的，也会导致TCM解码器的维特比解码器(VD)的高复杂性。例如，用于深空通信[2]的4-D TCM系统中使用的速率-3/4卷积码的约束长度为7;然而，由于网格中有大量的过渡，相应VD的计算复杂度与约束长度为9的速率1/2卷积码的VD相当。

在TCM解码器中，维特比解码器在功耗方面占主导地位。为了降低计算复杂度和功耗，TCM解码器中VD应采用低功耗方案。现有工作已经很好地研究了低功耗VD设计的一般解决方案。可以通过减少状态数来实现VDs的功耗降低，例如，简化状态序列解码(RSSD)[3]。m -算法[4]和t -算法[5]或[6]通过过标供电电压[7]。包括VD在内的整个系统应该考虑供电电压的过度缩放，这不是我们研究的主要重点。在实际应用中，m -算法相对于RSSD[3]是一种高效的算法，因为m -算法需要在一个反馈回路中进行排序，而t -算法只搜索最优路径度量(PM)，即所有PM的最小值或最大值。

在降低功耗方面，t算法已被证明是非常有效的。[8],[9]。然而，在反馈回路中寻找最优PM仍然降低了解码速度，这是一个缺点。为了克服这一问题，提出了两种T -算法的变体:松弛自适应VD[8]，它建议使用估计的最优PM，而不是在每个循环中寻找真正的PM，以及基于稀缺状态转换(SST)[9]的有限搜索并行状态VD。在我们的初步工作[10]中，我们已经证明，当应用高速率卷积码时，松弛自适应VD遭受严重的误码率(BER)退化，这是由于性能固有的漂移误差发生在估计的最优PM和准确PM之间。另一方面，基于SST的方案需要预解码和重编码过程，不适合TCM解码器。编码后的数据总是通过TCM方案中的星座点映射器与复杂的多级调制方案相关联，如8元相移键控(8PSK)或16/64元正交振幅调制(16/64QAM)。在接收机处应采用软输入VD以保证良好的编码增益。因此，TCM信号的预解码和重编码以及计算开销和解码延迟都变得很高。在前期工作[10]中，在预计算的基础上，提出了一种采用T算法的VD加-比较-选择单元(ACSU)结构，该结构有效地提高了采用T算法的VD的3/4码的时钟速度。 In this work, we further analyze the pre-computation algorithm. A systematic way to determine the optimal pre-computation steps is presented, where the minimum number of steps for the critical path to achieve the theoretical iteration bound is calculated and the computational complexity overhead due to pre-computation is evaluated. Then, we discuss a complete low-power high-speed VD design for the rate-3/4 convolution code [2]. Finally low power fpga implementation results of the VD are reported, which have not been obtained in our previous work in [10].

本文的其余部分组织如下。第二节给出了VDs的背景信息。第三节介绍了基于t算法的预计算体系结构，并讨论了预计算步骤的选择。第三节讨论了一个设计示例的细节，包括对存活路径存储单元(SMU)的修改。第四节报告了综合和功率估计结果，第五节给出了结论，T -算法并讨论了预计算步骤的选择。第三节讨论了一个设计示例的细节，包括对生存路径存储单元(SMU)的修改。第四节报告了综合和功率估计结果，第五节给出了结论。

维特比译码器

一个典型的维特比解码器功能框图如图1所示。首先，在BM单元中，从接收到的符号计算BMU分支度量(BM)。该模块由TCM解码器中的转换度量单元(TMU)代替，它比BMU更复杂。然后，bm被递归地输入ACSU, ACSU计算pm并为每个可能的状态转换输出决策位。在此之后，决策位存储在它们从SMU检索，以便沿着最终的幸存者路径解码源位。PM单元(PMU)存储当前迭代的PM。T算法需要在ACSU回路中进行额外的计算来计算最优PM和穿刺状态。因此，直接实现T算法将大大降低解码速度，提高T算法时钟速度的关键是快速找到最优PM。

预先计算体系结构

A.预计算算法

在[9]中提出了预计算算法思想。考虑VD的卷积码，约束长度为k，其中每个状态接收p条候选路径。首先，我们将当前时隙n(PMs(n))的PMs展开为n(PMs(n-1))的函数，以形成最优PM-PM opt(n)的超前计算。如果分支度量是根据欧几里得距离计算的，

然后，将状态分组为若干簇，以减少前视计算带来的计算开销。通常格子蝴蝶有一个对称结构的VD。换句话说，可以将状态分组到集群中，其中所有集群具有相同数量的状态，并且同一集群中的所有状态将由相同的bm扩展。

因此，(1)可以改写为:

对于每个集群，min(BMs)可以很容易地从BMU或TMU中获得，同时在每个集群中n -1时刻的min(PMs)可以在ACSU更新n时刻的新pm时预计算。理论上，当我们连续分解pm (n -1);PMs(n - 2);. .. ..，预计算方案可以扩展到q步，其中q是小于n的任意正整数，因此，PMopt(n)可以直接由PMs(n-q)在q个周期内计算出来

B.预计算步骤的选择

在[9]中，我们通过一个设计实例表明，q步预计算可以流水线化到q个阶段，随着q的增加，各阶段的逻辑延迟不断减小。从而大大提高了低功耗VD的解码速度。但是，在达到一定的步数qb后，由于ASCU循环固有的迭代界，进一步的预计算不会产生额外的收益。因此，讨论最优预计算步数是有价值的。在TCM系统中，卷积码的编码率通常为R/R+1,R=2,3,4，..............因此，在(1)中，p=2R, ACSU的逻辑延迟为TACSU=Tadder+Tp-in-comp，其中Tadder是用于计算到达相同状态的每个候选路径的pm的加法器的逻辑延迟，Tp-in-comp是用于确定每个状态的幸存者路径(具有最小度量的路径)的p输入比较器的逻辑延迟。，迭代界比TACSU略长，因为如果VD(3)采用T算法，循环中会有另一个双输入比较器来比较新的PM和预设的T，如下图所示。

在实现(3)所示迭代界的每个流水线阶段中，对于预计算，我们将比较限制在仅p或2p个度量之间。为了简化我们的评估，我们假设每个阶段将指标的数量减少到其输入指标的1/p(或2- r)，如图2所示。满足理论迭代界的最小预计算步数(qb)应满足(2R)qb≥2k-1.因此，qb≥(k-1)/R,qb表示为(4)，其中ÃⅱÂ - Â。Ã①Â—Â为ceiling函数

在[9]所示的设计实例中，编码率为1 / 2，约束长度为7，根据式(4)，VD满足迭代界的最小预计算步数为2，与我们从直接架构设计[9]中得到的值相同。在某些情况下，在添加了bm之后，剩余指标的数量可能会在某个管道阶段略微增加。额外的延迟通常可以通过优化的架构或电路设计来吸收。即使很难消除额外的延迟，得到的时钟速度也更接近理论边界。我们可以添加另一个管道阶段，以完全实现迭代边界，尽管这是非常昂贵的，如下所示。计算开销(与传统T算法相比)是一个需要仔细评估的重要因素。最大的计算开销来自于在每个阶段向指标添加bm，如(2)所示。换句话说，如果在一个阶段比较后还有m个剩余的指标，则该阶段的计算开销至少为m个加法操作。根据卷积代码的网格图，具体的开销因情况而异。同样，我们考虑一个具有约束长度k和q预计算步骤的代码来简化计算。此外，我们假设每个剩余的度量将导致一个加法操作的计算开销。在这种情况下，度量指标的数量将以2(k-1)/q的比例减少，总体计算开销为(用加法运算测量)。

当k = 7且q≤6时，根据(5)估计的计算开销为63/(26/q -1)，几乎呈指数增长到q。在真正的设计中，当考虑到其他因素(如我们上面提到的指标的比较或扩展)时，开销的增长甚至比(5)给出的还要快。因此，即使不能完全满足迭代界，也可以选择少量的预计算步骤。在大多数情况下，好的选择是一到两步预计算。上述分析还表明，对于低速率卷积码(速率为1/Rc;Rc = 2;3;)，因为通常需要两步以上才能有效地减小关键路径(在这种情况下，(4)中R = 1, qb为k - 1)。在TCM系统中采用高速率卷积码时，这两步预计算可以达到迭代界或在时钟速度方面产生很大影响。因此，计算开销很小。

低功耗高速维特比译码器设计

我们仍然使用[2]中描述的4-D8PSK TCM系统作为示例。TCM系统采用的rate-3/4卷积码如图3所示。在[10]中讨论了ACSU单元的初步误码率性能和结构设计。在本节中，我们将进一步讨论采用码率½的SMU设计问题。在下一节的稍后部分，我们将报告以前没有获得的各种FPGA家族实现结果。

采用T算法的VD在加性高斯白噪声信道上不同T值的误码率性能如图4所示。该仿真基于采用rate3/4代码的4-D 8PSK TCM系统

由于TCM系统中存在其他未编码的比特，总体编码率为11/12后。与理想的viterbi算法相比，阈值“T pm”可以降低到0.3，性能损失不超过0.1db;计算复杂度可降低90%以上，性能与传统t算法相当

A.ACSU设计

我们得出结论，两步预计算是速率3/4码VD的最佳选择。为了便于讨论，我们将图3中最左边的寄存器定义为最高有效位(MSB)，最右边的寄存器定义为最低有效位(LSB)。64个状态和pm被标记为0到63。两步预计算表示为

采用两步预计算t算法的VD功能框图如图5所示。在BMU或TMU中计算每个BM组(BMG)的最小值，然后传递给“阈值生成器”单元(TGU)进行计算(PMopt+T)。新的pm和(PMopt+T)然后在“吹扫单元”(PU)中进行比较。TUG的体系结构如图6所示，其中实现了两步预计算方案的关键功能。在图6中，每个聚类中求最小值的“MIN 16”单元由两级四输入比较器构成。为了满足迭代边界，对该体系结构进行了优化，与传统的Talgorithm相比，该体系结构的计算开销为12个加法运算和1个比较运算，略多于求值(5)。

B. SMU设计

在本节中讨论了使用t算法时SMU设计的一个重要问题。文献中有两种不同类型的SMU:寄存器交换(RE)和回溯(TB)方案。如果采用RE方案，SMU总是从固定状态将解码后的数据输出到常规VD中，不需要任何低功耗方案(可以提前任意选择)，如果采用TB方案，则从固定状态追溯幸存者路径，以降低复杂度。对于采用t算法的VD，没有状态保证在所有时钟周期都是活跃的。因此，不可能为输出解码位(RE方案)或启动回溯过程(TB方案)指定一个固定的状态。在传统t算法的实现中，解码器可以使用最优状态(带有PMopt的状态)来输出或追溯数据，解码器始终处于启用状态。在搜索PMopt的过程中，作为副产品可以得到最优状态的索引。但是，当估计前一个时间段的pm时，很难找到最优状态的指标。一种实用的方法是通过2(k-1)到- (k-1)优先级编码器找到启用状态的索引。假设我们已经标记了从0到63的状态。The output of the priority encoder would be the unpurged state with the lowest index. Assuming the other states are assigned the flg”1” and purged states have the flag”0”,the truth table of such priority encoder is shown in table1,where the “flag” is the input and “index” is the output

C.门限发生器

为了产生阈值，使用了一个阈值发生器单元，它将在每个阶段取最大值或最小值。实现这样一个表并非易事。在我们的设计中，我们采用了一种基于三个4到2优先级编码器的64到6优先级编码器的高效架构，如下图7所示。64面旗帜，每面包含16面旗帜，首先分为4组。优先级编码器在级别1检测哪个组包含至少一个“1”，并确定索引[5:4]”。然后MUX2根据“index[5:4]”选择一组标志。第2级优先编码器的输入可以通过“或”操作从MUX2的输出中计算出来。通过引入另一个MUX (MUX1)，我们可以重用中间结果。第2级优先编码器的输出是“index[3:2]”。同样，“index[3:2]”选择四个标志(MUX3)作为优先级编码器级别3的输入。最后，最后一个编码器将确定“index[1:0]”。实现4到2优先级编码器比实现64到6优先级编码器简单得多。 Its truth table is shown in Table II and corresponding logics are shown in (7) and (8)

实现结果

仿真结果

采用Verilog HDL代码对全网格VD、两步预计算结构的VD和传统t算法的VD进行了建模。所有vd的软输入均采用7位量化。所有vd中的每个PM被量化为12位。SMU采用生存长度为42的RE方案，并对与清除状态相关联的寄存器阵列进行时钟控制，以降低SMU的功耗。对于ASIC的合成，我们使用TSMC的90纳米CMOS标准电池。每种情况下实现最大时钟速度的综合目标和结果如表三所示

表II显示，与全网格VD相比，采用两步预计算架构的VD仅降低了11%的时钟速度。同时，硬件面积增长约17%。由于t算法VD的迭代界固有地比全网格VD的迭代界长，因此时钟速度的下降是不可避免的。此外，任何类型的低功耗方案都会引入额外的硬件，如图5所示的吹扫单元或SMU中的时钟门模块。因此，所提议的VD的硬件开销是可以预期的。另一方面，采用传统t算法的VD无法达到全网格VD时钟速度的一半。

因此，对于高速应用，不应考虑。值得一提的是，传统的talgorithyvd比提议的架构需要更多的硬件，这是违反直觉的。这是因为前者的解码器有更长的关键路径，合成工具采取了额外的措施来提高时钟速度。显然，传统的t算法并不适合高速应用。如果目标吞吐量中等高，建议的架构可以在较低的电源电压下运行

这是违反直觉的。这是因为前者的解码器有更长的关键路径，合成工具采取了额外的措施来提高时钟速度。显然，传统的t算法不适合高速应用。如果目标吞吐量中等高，所提出的架构可以在较低的电源电压下运行，这将导致与传统方案相比的二次功耗降低。因此，我们接下来将重点放在全网格VD与所提方案的功率比较上。

在时钟速度为200Mb/s(电源为1.0 V，温度为300K)的情况下，我们估算了这两种设计的功耗。总共1133个接收到的符号(12000位)被模拟。结果见表四。

对于有限字长实现，阈值只能更改0.125。因此，为了保持良好的误码率性能，我们选择的最小阈值为0.375。由表IV可以看出，随着阈值的降低，所提VD的功耗也相应降低。为了达到相同的误码率性能，所提出的VD仅消耗全网格VD的30.8%的功率。

结论

我们提出了一种用于TCM系统的高速低功耗VD设计。结合t算法的预计算架构在不降低解码速度的情况下有效地降低了vd的功耗。分析了预计算算法，计算并讨论了最优预计算步骤。该算法适用于经常使用高速率卷积码的TCM系统。最后给出了一个设计案例。ACSU和SMU都经过修改以正确解码信号。ASCI综合和功率估计结果表明，与不采用低功耗方案的全网格VD相比，预计算VD功耗降低80%，最大解码速度仅降低11%。

参考文献

何金金，刘华平，王忠峰，黄新明，张凯。基于TCM解码器的高速低功耗Viterbi解码器设计
“高效带宽调制”，空间数据系统咨询委员会，马泰拉，意大利，CCSDS 401(3.3.6)绿皮书，第1期，2003年4月。
J. B. Anderson和E. Offer，“卷积码的简化状态序列检测”，IEEE Trans。《理论》，第40卷，no。3，第965-972页，1994年5月。
林志峰和J. B.安德森，“信道卷积码的-算法译码”，发表于普林斯顿会议信息。科学。系统。，Princeton, NJ, Mar. 1986.
S. J.西蒙斯，“基于自适应努力的宽度优先网格解码”，IEEE Trans。Commun。，vol. 38, no. 1, pp. 3–12, Jan. 1990.
F. Chan和D. Haccoun，“无记忆通道上卷积码的自适应维特比解码”，IEEE Trans。
R. A. Abdallah和N. R. Shanbhag，“抗错低功耗维特比解码器架构”，IEEE Trans。信号的过程。，第57卷，no。12, pp. 4906-4917, 2009年12月。
金俊杰和c.y。Tsui，“基于稀缺状态转换的低功耗有限搜索并行状态维特比译码器实现”，IEEE Trans。超大规模积分。(VLSI)系统。，vol. 15, no. 11, pp. 1172–1176, Oct. 2007.
孙飞，张涛，“低功耗状态并行松弛自适应viterbi译码器的设计与实现”，《IEEE ISCAS学报》，2006年5月，第4811-4814页。
何俊杰，刘海华，王正哲，“基于t算法的viterbi编码器的快速ACSU架构”，第43届IEEE Asilomar会议。第一版。，Nov. 2009, pp. 231–235.
何俊杰，王正哲，刘海华，“一种高效的4-D 8PSK TCM译码器架构”，IEEE学报。超大规模积分。(VLSI)系统。，vol.18, no. 5, pp. 808
Arkadiy Morgenshtein, M Moreinis和“VLSI系统上的异步门扩散输入(GDI)事务，12,pp.847-856。
El-Dib d.a.和M. I. Elmasry.2004，“用于低功率无线通信电路系统的改进Viterbi译码器。I, Reg. 51, pp. 371-378。
李松，易庆明。, 2006年。功耗双向维特比解码器的设计机器学习与控制论会议
Mohammad K.Akbari和Ali Jahanian, 2004年，IEEE欧洲数字系统设计会议论文集(DSD ' 04)。
Arkadiy Morgenshtein, Fish和i.a. Wagner输入(GDI) -一种新的功率高效方法详细方法学”，第14版IEEE Int. 39-43。
Arkadiy Morgenshtein, M Moreinis和“VLSI系统上的异步门扩散输入(GDI)事务，12,pp.847-856。
F. Chan和D. Haccoun。自适应维特比解码器编码无记忆通道。电子学报，45(11):1389 - 1400,1997。
http://www.xilinx.com/products/silicon-devices/fp
Denton J. Daily(2004)，“编程LogicXilinx ISE和cpld”，在Prentice Hall, 203页通信与信息学(ICCCI - 2013)， 1月04 - 06