如何在FPGA中实现Viterbi译码

　　LTE采用下行正交频分多址（OFDM、上行单载波频分多址（SC-FDMA）的方式。OFDM是LTE系统的主要特点，其基本思想是把高速数据流分散到多个正交的子载波上传输，从而使子载波上的符号速率大大降低，符号持续时间大大加长，因而对时延扩展有较强的抵抗力，减小了符号间干扰的影响。在OFDM系统中，为了获得正确无误的数据传输，需要采用差错控制编码技术。卷积编码和Viterbi译码就是一种有效的前向纠错方法，它具有一定的克服突发错误的能力。LTE中采用Viterbi和Turbo加速器实现前向纠错。

　　1 Viterbi算法简介

　　Viterbi译码算法是由Viterbi于1967年提出的降低计算复杂度的算法。它是计算网格图上在时刻ti到达各个状态的路径和接收序列之间的相似度，或者说距离，去除不可能成为似然选择对象的网格上的路径。即如果有两条路径到达同一状态，则具有度量的路径被选中，称为幸存路径。对所有状态都进行这样的选路操作，译码器不断在网格上深入，通过去除可能性的路径实现判决，从而降低译码器的复杂性[3]。

　　Viterbi译码算法就是基于接收数据符号估计延时状态序列，重构通过整个网格的路径，实际包含度量更新和回溯过程。

　　2 Viterbi算法实现流程

　　Viterbi译码算法的实现流程如图1。由图1可以看出，Viterbi算法的主要实现过程可分为4大部分：分支度量计算（BMC）；加比选（ACS）；存储幸存路径存储器（SSM）；输出判决（OD）。

　　3 Viterbi译码实现过程

　　下面以一个（2，1，2）、回溯深度为10的软判决Viter-bi译码算法为例（如图2），通过这个例子可以比较清楚地了解Viterbi实现的过程。

　　在本例中，解码之前接收到20个编码后的符号。在某些应用中，Viterbi译码根据接收到的符号逐帧进行译码，与邻帧之间相互独立，即在每个帧内进行维特比译码，各帧之间相互独立。

　　3.1分支度量

　　本文按以下方法决定分支度量：

　　考虑接收到的编码后的比特G0（n）G1（n）。由于这里是进行软判决的维特比译码，因此在译码器的输入端将编码输出进行3bit的量化，量化范围为-4～3。假设这里传送的是11，则将11量化为（-4，-4）。若传送的为00，则量化为（3，3），即将0量化为3，1量化为-4。如图2，在0时刻和1时刻接收到的比特为（1，1），若（G0（n）G1（n））=（0，0），则对应的分支度量为-4（1）-4（1）=-8；若（G0（n），G1（n））=（1，0），对应的分支度量为-4（-1）-4（1）=0；（G0（n），G1（n））=（1，1），则为-4（-1）-4（-1）=8。

　　3.2路径度量

　　这里计算路径度量使用的是欧氏距离。PM（n，i）=Σ[Sj（n）-Gj（n）]2，j∈{与输入相关的输出比特}

　　n指示时间，i指示要计算的路径。上式可扩展为：

　　PM（n，i）=Σ[S2（n）-2S（n）G（n）+G2（n）]2，j∈{与输入相关的输出比特}

　　因为Sj（n）和Gj（n）在给定的符号周期内为常数，在找具有路径度量的过程中可以忽略这两个常数，因此可由下式决定路径度量：

　　PM′（n，i）=ΣSj（n）Gj（n）

　　注意，上式中系数-2已被剔除，所以寻找具有路径度量PM（n，i）的过程就转换为寻找具有路径度量PM′（n，i）的过程。在加比选的过程中做如下约定：凡是从上面状态转移过来的幸存路径，称之为“0”路径，如图3中实线所示；凡是从下面状态转移过来的幸存路径，称之为“1”路径，如图3中虚线所示。将这些幸存路径分别存储在相应的寄存器单元。

　　3.3幸存路径存储器

　　由以上分析可知，ACS在计算出新状态的路径度量的同时，也得出了到达这个状态的转移信息（用1bit表示），该路径转移信息就需要保存在幸存路径存储器中，这样多个转移信息就可以“串成”一条完整的幸存路径。在本设计中，幸存路径的长度L=10，所以使用4个10位的寄存器存储幸存路径。幸存路径存储模块如图4，每一个小方框是寄存器的一个位。对于每一个状态，由ACS模块得到的路径转移信息都移入各自的幸存路径。这样每一条幸存路径存储单元就是一个长度为10的移位寄存器。

　　3.4回溯

　　本设计的回溯算法如下：

　　（1）在4个状态的路径度量值中选取一个值；

　　（2）判断值对应的状态，作为回溯的起始状态，如果有多个，就根据状态的编号，按从小到大的顺序选取；

　　（3）根据幸存路径寄存器里存储的值进行判断，若是“0”，则是由上面状态转移过来；若为“1”，则是下面状态转移过来（如图3）。根据这些信息回溯到对应的前一状态。回溯节点逐级前移，从与之对应的幸存路径寄存器中获得路径转移信息；

　　（4）重复步骤（3），直到；

　　（5）输出译码结果。

　　从图4可以看出整个回溯的过程，这里假设路径度量值的是s0。图4中的译码输出比特流为0010110101。

　　3.5实现过程

　　从图2可以清楚看到，对输入的数据通过编码器进行卷积编码，到的输出译码结果，经历了以下几个过程：

　　（1）对输入的数据进行卷积编码，编码速率为1/2，即每输入1个比特编码输出2个比特。

　　（2）将每次编码输出的2个比特量化为相应的数值，通过每一组数值计算出该组4个状态（s0，s1，s2，s3）的分支度量值，即BM值。

　　（3）进行加比选（ACS）运算，同时保存路径信息。首先在0时刻给4个状态（s0，s1，s2，s3）赋初始路径向量值（PM）：假如起始点为状态s0，则状态s0的初始路径向量值为PM0=100（该数值根据实际的情况来定，如回溯深度和分支度量值等，以便计算），状态s1、状态s2、状态s3的初始路径向量赋值为PM1=PM2=PM3=0。

　　（4）ACS过程。因为到达每一个状态有两条路径（如图3），例如到达状态s0（00）的两条路径分别是s0（00）和s1（01），从中选出到达s0路径度量值的一条路径作为幸存路径。如图2，若从0时刻到1时刻：BM0=-8，BM1=0，max{PM0+BM0，PM1+BM1}=PM0+BM0=92，所以1时刻到达状态s0的保留路径为0时刻从状态s0来的路径，从而更新1时刻s0的PM0=92；同时由于1时刻到达s0的是“0”路径，所以保存的该时刻s0的路径信息是0（若是“1”路径，则保存的该时刻s0的路径信息为1）。以此类推，可求出该时刻到达状态s1、s2、s3的幸存路径，存储该路径信息，更新其路径度量值PM。

　　（5）输出判决（OD），即回溯过程，就是根据回溯深度以及ACS过程中所保存的PM值和幸存路径信息进行相应的算法回溯出译码结果。

　　4 时序仿真结果

　　使用Verilog语言在ISE[5]中进行综合和实现，布线后的时序仿真图如图5。图5为正确的维特比译码时序仿真图，输入的比特序列为一串随机数，经过卷积编码后输入到Viterbi译码器，输出的译码序列与输入序列一致。本译码器实现了正确的译码功能。

　　5 结果分析

　　考虑回溯深度对译码错误性能的影响，采用软判决译码，回溯深度为9、18、45，测试帧数为3000，仿真结果如图6。从仿真结果可以看出，回溯深度对BER有影响。回溯深度越深，性能越好。