1 引言

　　viterbi译码算法是一种最大似然译码算法，目前广泛应用于各种数据传输系统，特别是卫星通信和移动通信系统中。近年来随着fpga技术的迅速发展，使得基于fpga实现viterbi译码的算法成为研究的热点。

　　由于viterbi译码器的复杂性随约束长度k成指数增加，大约束度不但使viterbi译码器硬件复杂度大为增加，同时也限制了译码速度。而其中以加比选(add compareselect，acs)运算为最主要的瓶颈，的递归运算使流水线结构的应用变得困难。本文以(2，1，9)卷积码为例，用fpga实现大约束度viterbi译码器，其中acs设计采用串并结合的方法来兼顾面积和速度，并用流水线结构来提高译码速度，对路径度量存储则采用同址存储方法，实现了在占用少量硬件资源的前提下，提高译码速度。

2 算法简述及系统结构分析

　　viterbi译码原理详见文献[1，2],下面仅作简要说明。

　　图1为(2，1，9)卷积码的2个状态之间的状态转移图。根据输入路径的不同(图中实线表示输入为0，虚线表示输入为1)，仅仅首位不同的两个状态可转移到仅仅末位不同的两个状态。将所有状态的状态转移图按时间往前衍生，即可得到(2，1，9)卷积码的网格(trellis)图。viterbi译码过程就是：根据接收序列，按照最大似然法则，分段地在网格图上计算寻找有最大度量的路径的过程。一般来说，维特比泽码器主要有4个单元所组成，其结构框图如图2所示。

　　分支度量单元(bmu) 主要是计算分支度量值。所谓分支度量值就是码字与接收码之间的距离。

　　加-比较-选择单元(acsu) 主要是做路径度量值与分支度量值的叠加，并决定幸存路径度量值及决定位元(decision bit)。

　　路径度量存储单元(pmmu) 主要用来存储幸存路径度量值。

　　幸存路径存储单元(smu) 主要用来存储决定位元。

　　如图2所示，接收序列先通过分支度量单元计算出各状态所有分支度量，然后经过acs单元，将上一时刻的路径度量值与当前时刻的分支度量值作加-比较-选择等运算，计算出当前时刻的幸存路径和路径度量值，并找出决定位元(decision bit)，把新的路径度量值存储到路径度量存储单元(pmmu)，并把相应的幸存路径的决定位元(de-cision bit)存储到幸存路径存储单元(smu)，当译码到译码深度后，判决输出单元输出译码序列。由此可见：

　　(1) 每计算一接收序列，所有状态的路径度量都要更新一次。若这些路径度量存储于一块ram中，则ram读写的次数为待译卷积码的状态数，当卷积码的约束度比较大时，对ram的读写周期要求将会很高，很可能成为限制译码速度的瓶颈；

　　(2) 在acs单元，要完成路径度量的累加，比较并选择有最大度量的路径，是算法实现的关键电路，也是硬件资源耗费最大的部分。所以acs单元的数目太多会大大增加译码器的硬件规模，太少则影响译码速度。因此，合理安排acs单元与路径度量ram是提高译码速度，减少硬件消耗的关键所在。

　　针对问题(1)，本文从改进viterbi译码算法和路径度量ram分块两方面同时人手。首先，表示viterbi算法过程的网格图可以进行分解与折叠。图3所示为(2，1，9)卷积码的部分网格图的分解与折叠。可以看出折叠后，acs计算时由读写状态路径度量，得出一步后的更新结果，变为读写四状态路径度量，得出两步后的更新结果。省去了中间路径度量的读写，减少了ram的读写次数。

　　当然，这种分解与折叠很容易扩展为基8或基16的网格图，ram的读写次数将进一步减少，但此时acs要同时处理8个或16个路径度量，复杂性几乎成指数增加，其计算速度也可能成为新的瓶颈。综合考虑，本文采用4个基4算法，每次同时处理16个状态。在基于4个基4算法的16个状态路径度量读写中，本文将路径度量ram分为16块，每块存储16个状态的路径度量。16块ram并行工作时，对每块ram的读写周期要求降为原来的1／16。

　　针对问题(2)，综合考虑资源占用与译码速度，并兼顾基4算法的实现，决定采用4个基4蝶形单元并行工作，每个蝶形单元(acs)串行处理16个状态的串并结合方式。

　　在viterbi译码器的实现过程中，计算当前时刻的路径度量需用到前一时刻的路径度量，所以必须对路径度量加倍缓存。本文提出了一种同址的路径度量存储方法，可以减少存储单元数量，而不影响译码速度。下面将详述该方法的原理及实现过程。

3 路径度量同址存储的原理与实现

　　viterbi译码器的复杂性及所需存储器容量随着约束长度k成指数增加，viterbi译码器每解码一位信息位就需对2k-1=28=256个寄存器进行路径度量，并对相应的存储单元进行读写，这样度量路径的存储管理就成了提高译码速度的一个重要环节。

1 引言

　　viterbi译码算法是一种最大似然译码算法，目前广泛应用于各种数据传输系统，特别是卫星通信和移动通信系统中。近年来随着fpga技术的迅速发展，使得基于fpga实现viterbi译码的算法成为研究的热点。

　　由于viterbi译码器的复杂性随约束长度k成指数增加，大约束度不但使viterbi译码器硬件复杂度大为增加，同时也限制了译码速度。而其中以加比选(add compareselect，acs)运算为最主要的瓶颈，的递归运算使流水线结构的应用变得困难。本文以(2，1，9)卷积码为例，用fpga实现大约束度viterbi译码器，其中acs设计采用串并结合的方法来兼顾面积和速度，并用流水线结构来提高译码速度，对路径度量存储则采用同址存储方法，实现了在占用少量硬件资源的前提下，提高译码速度。

2 算法简述及系统结构分析

　　viterbi译码原理详见文献[1，2],下面仅作简要说明。

　　图1为(2，1，9)卷积码的2个状态之间的状态转移图。根据输入路径的不同(图中实线表示输入为0，虚线表示输入为1)，仅仅首位不同的两个状态可转移到仅仅末位不同的两个状态。将所有状态的状态转移图按时间往前衍生，即可得到(2，1，9)卷积码的网格(trellis)图。viterbi译码过程就是：根据接收序列，按照最大似然法则，分段地在网格图上计算寻找有最大度量的路径的过程。一般来说，维特比泽码器主要有4个单元所组成，其结构框图如图2所示。

　　分支度量单元(bmu) 主要是计算分支度量值。所谓分支度量值就是码字与接收码之间的距离。

　　加-比较-选择单元(acsu) 主要是做路径度量值与分支度量值的叠加，并决定幸存路径度量值及决定位元(decision bit)。

　　路径度量存储单元(pmmu) 主要用来存储幸存路径度量值。

　　幸存路径存储单元(smu) 主要用来存储决定位元。

　　如图2所示，接收序列先通过分支度量单元计算出各状态所有分支度量，然后经过acs单元，将上一时刻的路径度量值与当前时刻的分支度量值作加-比较-选择等运算，计算出当前时刻的幸存路径和路径度量值，并找出决定位元(decision bit)，把新的路径度量值存储到路径度量存储单元(pmmu)，并把相应的幸存路径的决定位元(de-cision bit)存储到幸存路径存储单元(smu)，当译码到译码深度后，判决输出单元输出译码序列。由此可见：

　　(1) 每计算一接收序列，所有状态的路径度量都要更新一次。若这些路径度量存储于一块ram中，则ram读写的次数为待译卷积码的状态数，当卷积码的约束度比较大时，对ram的读写周期要求将会很高，很可能成为限制译码速度的瓶颈；

　　(2) 在acs单元，要完成路径度量的累加，比较并选择有最大度量的路径，是算法实现的关键电路，也是硬件资源耗费最大的部分。所以acs单元的数目太多会大大增加译码器的硬件规模，太少则影响译码速度。因此，合理安排acs单元与路径度量ram是提高译码速度，减少硬件消耗的关键所在。

　　针对问题(1)，本文从改进viterbi译码算法和路径度量ram分块两方面同时人手。首先，表示viterbi算法过程的网格图可以进行分解与折叠。图3所示为(2，1，9)卷积码的部分网格图的分解与折叠。可以看出折叠后，acs计算时由读写状态路径度量，得出一步后的更新结果，变为读写四状态路径度量，得出两步后的更新结果。省去了中间路径度量的读写，减少了ram的读写次数。

　　当然，这种分解与折叠很容易扩展为基8或基16的网格图，ram的读写次数将进一步减少，但此时acs要同时处理8个或16个路径度量，复杂性几乎成指数增加，其计算速度也可能成为新的瓶颈。综合考虑，本文采用4个基4算法，每次同时处理16个状态。在基于4个基4算法的16个状态路径度量读写中，本文将路径度量ram分为16块，每块存储16个状态的路径度量。16块ram并行工作时，对每块ram的读写周期要求降为原来的1／16。

　　针对问题(2)，综合考虑资源占用与译码速度，并兼顾基4算法的实现，决定采用4个基4蝶形单元并行工作，每个蝶形单元(acs)串行处理16个状态的串并结合方式。

　　在viterbi译码器的实现过程中，计算当前时刻的路径度量需用到前一时刻的路径度量，所以必须对路径度量加倍缓存。本文提出了一种同址的路径度量存储方法，可以减少存储单元数量，而不影响译码速度。下面将详述该方法的原理及实现过程。

3 路径度量同址存储的原理与实现

　　viterbi译码器的复杂性及所需存储器容量随着约束长度k成指数增加，viterbi译码器每解码一位信息位就需对2k-1=28=256个寄存器进行路径度量，并对相应的存储单元进行读写，这样度量路径的存储管理就成了提高译码速度的一个重要环节。