基于FPGA的Viterbi译码器

1、 毕业设计(论文)基于FPGA的Viterbi译码器 姓 名： 学 院： 专 业： 班 级： 指 导 教 师： 摘 要 卷积编码是深度空间通信系统和无线通信系统中常采用的一种编码方式,广泛应用于卫星通信、无线通信等多种通信系统。在1967年，Viterbi 提出了卷积码的Viterbi 译码算法，它是一种卷积码的最大似然译码算法，通过寻找译码器接收序列和卷积编码器的输出序列的最大似然函数来得出译码结果。该算法译码性能好、速度快，并且硬件实现结构比较简单，是最佳的卷积码译码算法。随着可编程逻辑技术的不断发展，使用FPGA实现viterbi译码器的设计方法逐渐称为主流。因此设计viterbi译码器

2、，使其能够满足多种通信系统的应用要求，具有重要的现实意义。本文的主要内容是基于FPGA 的Viterbi 译码器设计。在对viterbi译码算深入研究过程中，重点研究了Viterbi 译码器各个模块的主要功能。在本设计中，采用了硬判决计算输入信息码元与各状态的期望码元之间的分支度量值，用串行加比选碟型算法来寻找编码器网格图上的幸存路径，用回溯法(trace-back)算法来对幸存路径做处理得到译码输出，用乒乓方式对幸存路径进行存储。本论文设计输入是采用硬件描述语言VHDL来完成的，通过在各种EDA工具下的仿真和综合，验证了本文所设计的Viterbi 译码器的正确性和实用性。关键词：卷积码；维特

3、比；译码器；现场可编程门阵列 ABSTRACTConvolutional coding has been used in communication systems including deep space communications and wireless communications,which are widely used in satellite communications and wireless communication. The Viterbi algorithm , proposed in 1967 by Viterbi ,is a maximum-likelihoo

4、d algorithm for convolutional codes. The Viterbi decoder attempts to find the maximum-likelihood function of the decoded code word against received code word. This method is better decoding performance, fast, and relatively simple hardware architecture, is the best convolutional code decoding algori

5、thm. With the continuous development of programmable logic technology, the use of FPGA implementation viterbi decoder design method called mainstream gradually. Therefore, the design viterbi decoder so that it can meet the application requirements of a variety of communication systems, has important

6、 practical significance.The main content of this paper is to design a Viterbi decoder with FPGA technology. In-depth study of the viterbi decoding calculation process, focusing on the main functions of each module Viterbi decoder. In this paper, the parallel ACS (add-compare-select) Butterfly algori

7、thm is used to find the survivor path in encoder trellis. We also use trace-back algorithm to dispose the survivor path and receive the decoded results. In addition, the behavior of a design is described in VHDL. The emulated and synthesized results of this design are received by all kinds of EDA to

8、ols. Through these results the Viterbi decoders correctness and practicability can be validated.Key words：Convolutional Code; Viterbi; Viterbi; FPGA 目 录绪 论5第一章 纠错码的基本原理71.1 差错控制的基本方式71.2 纠错编码的基本原理91.3 纠错编码的分类11第二章 卷积码和Viterbi算法122.1 卷积码基础122.1.1 卷积码编码原理122.1.2 卷积码的描述142.2 Viterbi译码原理182.2.1Viterbi算法

9、描述182.2.2Viterbi算法举例192.2.3 Viterbi译码器的特点23第三章 Viterbi译码的FPGA实现243.1 Viterbi译码器的基本结构243.2 分支度量模块（BMU）263.3 加比选模块(ACS)273.3.1状态间的蝶形运算关系273.3.2 加比选的实现方式303.3.3 溢出处理313.4 路径度量存储模块（PMU）323.5 幸存路径寄存模块（SMU）333.5.1 寄存器交换法343.5.2 回溯法353.6 回溯模块(TBU)37 第四章 Viterbi译码器的设计与仿真结果394.1 卷积码编码器设计394.2 Viterbi 译码器的设计4

10、0第五章 结束语43参考文献44附录45英文文献61 谢 辞75 绪 论 随着现代通讯的发展，我们对通信的技术的质量跟速度提出了更高的要求。但是，由于信道的不理想以及加性噪声和人为干扰的影响，使得信号在信道传输过程中会因为各种干扰而产生失真现象，使得通信质量下降。不同的系统在信号传输过程中会受到不同的干扰，产生不同的差错率，进而使传输的可靠性也不同。随着传输速率的提高，可靠性问题更加突出。为了提高传输的可靠性，降低误码率，有两种方法：一是降低信道本身引起的误码，可采用的方法有选择高质量的传输线路、改善信道的传输特性、增加信号的发送能量、选择有较强抗干扰能力的调制解调方案等；另外一种方法就是采用

11、差错控制编码，即信道编码。这种方法主要是对输入信息序列进行各种变换，使得原来相互独立的信息码元产生相关性，在接收端利用这些信息码元的相关性检测出错码就纠正过来。在许多情况下，信道的改善需要大量的能量与功率，实现起来比较困难与不经济，这时采用差错控制编码方法比较合理。而在 GSM、IS - 95、WCDMA 系统中有广泛应用的卷积码译码算法是 A. J.Viterbi 在 1967 年提出的Viterbi算法(VB 算法),该算法是针对卷积码的一种最佳的最大似然译码方法。本设计实现了在IS-95中的前项链路所使用的(2,1,9)卷积码，具有一定的实际意义。 FPGA以运行速度快、编程方便、可以实

12、现系统集成、功耗低、价格低、可以反复地编程与擦除使用的优点，在通信领域越发显示出强大的优势，受到广大电子技术人员的青睐。 本设计具有以下特点：在本设计中采用了串行的加比选单元结构，这样可以节省大量的资源，降低对硬件的要求。在对幸存路径的处理上，一般来说有寄存器交换法和回溯法两种处理手段，在本设计中采用了回溯法。本设计中 Viterbi 译码器的设计输入是用硬件描述语言VHDL写的，设计平台使用的是Altera 公司的Quartus II 软件，本设计中的输入、功能仿真、综合、适配及时序仿真都是在这个平台上来完成的。本论文的具体安排如下：第一章对纠错码进行了简单的介绍。第二章主要介绍了卷积码的基

13、础知识以及Viterbi 译码的基本原理，并通过举例来具体说明。第三章主要介绍了viterbi译码器的FPGA的实现设计思路，viterbi译码器总体框体，然后还介绍了各个模块的主要功能和实现方法。第四章简要的介绍了FPGA的发展历程及特点，同时给出了FPGA的一般设计方法。给出了本设计的仿真验证，从而证明了本设计的正确性。 第一章 纠错码的基本原理1.1 差错控制的基本方式 数字信号在传输过程中，由于加性噪声和人为干扰的影响，使得数字信号产生失真现象。由于剩性干扰引起的失真现象可以采用均衡方法来消除。而因为加性干扰引起的误码现象则需要采用其他方法来消除，可以首先考虑增加数字信号发送端的发送功

14、率或采取合理的调制解调方案，使加性干扰不足以影响达到误码率要求。在仍不能满足要求时，就要考虑采用差错控制措施了。一些通用的系统，其误码率要求因用途而异，也可以把差错控制作为附加手段，在需要时加用。 根据加性干扰引起错码分布规律的不同，可以把信道分成三类：突发信道、随机信道和混合信道，在不同的信道中，应采用不同的差错控制方式。差错控制方式基本上分为两类，一类称为“反馈纠错”，另一类称为“前向纠错”。在这两类基础上又派生出一种称为 “混合纠错”，如图1-3所示。图1-3 差错控制的基本方式（1） 检错重发ARQ 检错重发方式的发送端发出有一定检错能力的码，接收端接受到这些码元后，利用码元本身的检错

15、能力进行检测，当检测到有错码时，接收端通过反向信道向发送端发送信息，要求发送端重发，直到接受到正确码元为止。ARQ只能检测到是否有错码，但检测到错码后，不知道如何纠正错码，要求发送端重新发送一遍。在二进制系统中，这种情况发生在不知道一组接收码元中哪个码元错了。 该方法是通过发送有一定检错能力的码元进行检错的，因此它的优点是只需要少量的多余码就可以降低误码率。另外，由于该方法的检错与纠错能力与信道干扰情况没有关系，因此可以应用于各种类型的信道，适应性比较强，特别适合于短波、有线等干扰情况复杂而又要求误码率较低的场合。主要缺点是必须有反馈信道，不能进行同播。当信道干扰较大时，造成错码概率较大，系统

16、可能就处于重发循环中，信息传输的实时性和连贯性就比较差。 （2）前向纠错FEC 前向纠错方式是在发送端发送具有纠错能力的码元，接收端的纠错译码器接受这些码元后，检测到错码后能及时把这些错码纠正过来。 该方式的优点是译码实时性好，不需要反馈信道，能够进行一个用户对多个用户的广播式通信，而且控制电路简单，特别适用于移动通信。缺点是译码设备比较复杂难以实现，而且所选用的纠错码必须与信道干扰情况相匹配，因而对信道变化的适应性差。为了获得较低的误码率，必须以最坏的信道条件来设计纠错码。 （3）反馈校验 反馈校验方式不需要在发送序列中加入差错控制码元。这种方式的基本思路是接收端将接受到的码字原封不动地发送

17、到发送端，与发送端的码字逐一进行比较，如果检测到与发送端的码字不相同，就认为接收端收到的码字中有错码，发送端需要重新发送。这种技术的优点是原理和设备都很简单，缺点是需要双向信道，传输效率也较低，因为每个码元都需要占用两次的传输时间。 （4）检错删除 检错删除和检错重发的区别在于，在接收端发现错码后，立即将其删除，不要求重发。这种方法只适用在少数待定系统中，在那里发送码元中有大量多余度，删除部分接收码元不影响应用。例如，在循环重复发送某些遥测数据时。又如，用于多次重发仍然存在错码时，这时为了提高传输效率不再重发，而采取删除方法。这样做在接收端当然会有少许损失，但却能够及时接受后续的消息。 以上几

18、种技术可以结合使用。例如，“混合纠错”就是“前向纠错”和“反馈纠错”两种方式的混合。当接收端出现少量错码并有能力纠正错码时，采用前向纠错技术；当接收端出现较多错码没有能力纠正时，采用检错重发技术。 1.2 纠错编码的基本原理差错控制编码又称为纠错编码（error-correcting coding）。有的编码方法只能检错而不能纠错，不同的编码方法，其检错或纠错能力是不同的。一般来说，增加的监督码元个数越多，检（纠）错的能力越强。而通常有多余度来衡量增加的监督码个数。例如，若编码序列中平均每三个信息码元就添加一个监督码元，则这种编码的多余度为1/4。或者说，这种码的编码效率（简称码率）为3/4。

19、我们假设编码序列中总码元数为n，其中信息码元数量为k，则监督码元数量为n-k，则码率就是信息码元数量与总码元数量的比值kn；而冗余度就是监督码元数（n-k）和信息码元数k之比（n-k）/k。 先用一个例子说明纠错编码的基本原理。用一个由3位二进制数字构成的码组来表示各种天气，这些码组有8种可能的组合方式，表示天气情况如下表表1-1 各种天气的表示方法 码组000001010011100101110111 天气晴云阴雨雪霜雾雹 其中任一码组在传输过程中若发生一个或多个错码，则将变成另一个信息码组，这时，接收端接受到的码字是错码，表示的天气信息跟发送端的完全不一样，接收端将无法发现其错误。但若上述

20、8中码组只准使用其中4种来传送天气，例如：000表示天气晴，011表示天气云，101表示天气阴，110表示雨。这时，虽然只能传送4种不同的天气，但是在接收端有可能发现码组中的一个错码。例如，若011（云）在传输过程中发生一个错码，则接受码组将变成111或001或010。这3种码组是不能表示任何天气的，是禁止使用，称为禁用码组。接收端收到禁用码组后，就认为有错码。当传输过程中发生3个错码时，011变成100，100也是禁用码组，故接收端也能检测出3个错码。但如果011（云）中发生2个错码，接受码组就有可能变成000或110或101，这些都是许用码组，接收端就不能检测到错码，因此这种编码不能检测出

21、2个错码。上面这种编码只有检错能力，没有纠错能力。例如，如果接收端收到禁用码组111时，接收端能检测出发生错码，但不能纠正过来，因为011（云）、101（阴）、110（雨）发生一个错码都能变成111，天气晴000发生3个错码也能变成111，接收端无法判定是哪个码组发生错码得到的。要想能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：000表示天气晴，111表示天气雨，其他的码组都为禁用码组。这种编码方式不仅能检测出两个以下错码，还能纠正一个错码。例如，当接收端收到禁用码组001时，倘若该码组是在传输过程中发生一位错码，则接收端能够判断该码组是由000（晴）产生一位错码得来的，因为11

22、1（雨）产生一位错码无论如何都得不到001，接收端就可以纠正为000（晴）。但倘若发生错码的个数为1个或2个时，则接收端无法纠正过来，因为111（雨）发生2个错码码组可以变成001，000（晴）发生一个错码也可以变成001，这时接收端只能检测到错码而无法纠正过来，因此这种编码方式只能纠正一个错码。从上面的例子中，我们可以了解到关于“分组码”的一般概念。如果不要求有检（纠）错能力，为了传输4种不同的消息，用两位的码组就够了，即可以用：00、01、10、11。这些两位码称为信息位。而在上面中使用了3位码，增加的那位称为监督位。把这种将信息码分组，为每组新码附加若干监督码的编码称为分组码。分组码一般

23、用符号（n，k）表示，其中n是码组的总位数，又称为码组的长度（码长），k是码组中信息码元的数目，n-k=r为码组中的监督码元数目。在分组码中，把码组中“1”的个数目称为码组的重量，简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称为汉明距离。1.3 纠错编码的分类 随着数字通信技术的发展，各种差错控制编码方案越来越多，其检错与纠错能力也是不一样的，数学模型也不一样，可以从不同的角度对差错控制编码进行分类。根据对信息元处理方式的不同，可以将纠错码分为分组码与卷积码。分组码是将信息序列以k个码元为一组分成几组，每组又根据一定的编码规则生成若干个r个监督码元，输出一个码长

24、为n=k+r的码组。分组码中的监督码元只与当前码组的信息元有关，与其他码组的信息元没有关系。卷积码则不一样，卷积码不对信息序列进行分组编码，而且卷积码中的监督码不仅与当前时刻的信息码元有关，还与之前时刻输入的信息码元有关。卷积码的缺点是目前还没有找到有效的数学工具和系统理论对卷积码进行分析，但它的实用性远远超过分组码，因此卷积码在数字通讯领域得到广泛的应用。 根据信息码元与监督码元之间的关系的不同，可以将纠错码分为线性码与非线性码。顾名思义，线性码就是指信息码元与监督码元之间呈一定的线性关系，即满足线性叠加原理；如果信息码元与监督码元不满足这种关系，则为非线性码。由于非线性码的分析比较困难，实

25、现较为复杂，所以我们讨论多为线性码。 根据差错控制编码的功能不同，可分为检错码、纠错码和纠删码等。检错码只能检测出错码而无法纠正错码；纠错码不仅具备识别错码功能，同时具备纠正错码功能；纠删码则不仅具备纠错码的所有功能，即检测出错码并纠正错码，而且当错码超过纠正范围无法纠正时，可以把无法纠正的信息删除。 根据每个码元取值不同，可以将纠错码分为二进制码和q进制码。根据信息码元在编码以后形式是否发生改变，可以分为系统码和非系统码。系统码是指信息码元在编码之后保持原来的形式不变，而在非系统码中，信息码元会改变其原有的信号序列。由于原有的码位发生了变化，使译码电路更为复杂，故较少选用。 第二章 卷积码和

26、Viterbi算法 卷积码是1955年由伊莱亚斯（Elias）提出一种非分组码。分组码编码是将输入的信息序列分成长度为k的分组，然后按照一定的编码规则，将长度为k的信息员附加上长度为r的监督元，生成长为n=k+r的码组。在一个码组中，r个监督元仅与本组的k个信息元有关，而与其他各码组均无关。分组译码时，也仅从本码组的码元内提取有关译码信息，而与其他码组无关。卷积码则不同，他先将信息序列分成长度为k的子组，然后编成长为n的子码，其中长为n-k的监督元不仅与本子码的k个信息码元有关，而且还与前面m子码的信息元密切相关。换句话说，各子码内的监督元不仅对本子码有监督作用，而且对前面m个子码内的信息元也

27、有监督作用。因此常用（n，k，m）表示卷积码，其中m为编码记忆，它反映了输入信息元在编码器中需要存储的时间长短；N=m+1称为卷积码的约束度，单位是组，它是相互约束的子码的个数；N*n被称为约束长度，单位是位，它是相互约束的二进制码元的个数。 在线性分组码中，单位时间内进入编码器的信息序列一般都比较长，k可达8100。因此，编出的码字n也较长。对于卷积码，考虑到编、译码器设备的可实现性，单位时间内进入编码器的信息码元的个数k通常比较小，一般不超过4，往往取k=1。2.1 卷积码基础2.1.1 卷积码编码原理 我们可以通过一个例子来说明卷积码的编码原理，如图2-1是（3，1，2）卷积码编码器的原

28、理框图。如图所示，（3，1，2）卷积码编码器主要是由两个移位寄存器（m j-1，m j-2）和两个模2加法器组成。编码前，各级移位寄存器清零，输入端依次输入信息序列m 1，m 2，。 。m j，。每输入一个信息码元m j时，输出端开关依次接到X1,j，X2,j和X3,j各端点一次。其中X1,j，X2,j和X3,j由下式决定 X1,j=m j X2,j=m j+m j-2 （2.1.1） X3,j=m j+m j-1+m j-2 由式（2.1.1）中可以看出，编码器输出的信息码元X1,j，X2,j和X3,j不仅与当前时刻的信息码元m j相关，还跟之前时刻的两个信息码元m j-1、m j-2相关，

29、因此编码记忆m=2，约束度N=m+1=3（组），约束长度N*n=9（位）。 X1,j输入 X2,j 输出 m j-1m j-2m1,m2,.mj. X3,j 图2-1 （3，1，2）卷积码编码器表2-1 (3,1,2)编码器状态表 m j 1 1 0 1 0 0 0 0 m j-1。m j-2 00 01 11 10 01 10 0000 X1,j，X2,j.X3,j 111 110 010 100 001011000000 状态 a b d c b c a a 表2-1列举了图2-1所示编码器的状态。其中a，b，c，d表示 m j-1m j-2的四种可能的状态：00，01，10，11。当第一

30、位信息比特为1时，即m1=1，因移位寄存器的状态 m j-1。m j-2=00，故输出比特 X1,j，X2,j.X3,j=111；第二位信息比特为1时，因m j-1。m j-2=01，故输出比特 X1,j，X2,j.X3,j=110；其余类推。为了保证输入的全部信息位为11010都能通过寄存器，还必须在信息位后加3个零。卷积码编码时，信息码流按顺序依次输入进行编码。分组码却不一样，它需要先对信息码流进行分组，分组完后才能进行编码，因此卷积码编码只需要少量的缓冲和存储空间。2.1.2 卷积码的描述卷积编码有集中描述方法，其中使用比较多的是树状图、网络图和状态图，现在我们以（2，1，2）卷积码为例

31、来说明各种卷积码的描述方法。1、 树状图 卷积码的树状图能形象的描述卷积码编译码的工程，图2-2画出(2,1,2)卷积码的树状图。树状图从节点so开始，此时移位寄存器状态为00。现在规定：输入信息位为“0”时，则状态往上支路移动；输入信息位为“1”时，则状态往支路移动。如图2-1所示，当第一个输入信息位m1=0时，输出码元为00，移位寄存器的状态仍为so=00；若第一个输入信息位m1=1时，输出码元为11，状态并转换到s1=01。因此从so出发有两条支路可供选择，m1=0时取上面一条支路，m1=1时则取下面一条支路。输入第二个信息位时，移位寄存器右移一位后，上支路情况下移位寄存器状态仍为so，

32、下支路的状态为s1。新的一位输入信息位到来时，随着移位寄存器状态和输入信息位的不同，树状图继续分叉成4条支路，2条向上，两条向下。当输入第二个信息位时，若此时移位寄存器的状态仍为so，则由m2=“0”或“1”和寄存器的状态可得，输出码元为00或11，状态也传换到so或s1状态；若此时移位寄存器的状态为s1，则由m2=“0”或“1”和寄存器的状态可得，输出码元为10或01，状态也传换到s2=10或s3=11状态。如此继续，即可得到图2-2所示的二叉树图形。树状图中，每个树杈上所标注的码元为输出信息位，每个节点上标注的so，s1，s2，s3为移位寄存器的状态。显然，对于第j个输入信息位，有2j条支

33、路，但在j=N3时，树状图的节点自上而下开始重复出现4中状态。 图2-2 （2，1，2）卷积码的树状图 设现在输入码元序列为1000时，根据上面所述，可得到输出码元为11，10，11，00，相对应的寄存器的状态为s1，s2，so，so，在2-2图中用一条粗黑线描绘出来。 2、状态图 由（2，1，2）编码器结构可知，输出码元不仅决定于当前输入信息位，还决定于前两位信息位。移位寄存器中就有四种可能的状态so=00，s1=01，s2=10，s3=11，编码器相应的也有4种状态。当输入端依次输入信息序列时，编码器就不断地从当前时刻的状态转移到下一时刻的状态，并输出信息码元。卷积码的状态图就是用来描述这

34、种状态转移的过程。图2-3所描述就是卷积码（2，1，2）的状态图，虚线表示输入信息位为“1”时状态转变的路线，实线表示输入信息位为“0”时状态转变的路线，线条旁的数字如0/11表示输入信息位为0，输出码元为11，各状态之间的连线与箭头表示状态转移方向。设编码器的初始状态为so，若输入信息位为“0”时，输出码元为00，状态仍为so，；若输入信息位为“1”时，输出码元为11，下一时刻状态仍为s1。随着信息序列的不断输入，编码器就会不断从一个状态转移到另外一个状态，利用这些转移路径不仅可以表示出该转移过程中对应的输出码元，还可以表示出所对应输入信息位。 图2-3 （2，1，2）卷积码的状态图 3、网

35、络图虽然状态转移图能够描述在不同的信息序列下，编码器的各个状态之间的转移关系，但是它不能描述编码器的状态和时间的关系。为了表示这种关系，我们引进了网络图，以时间为横坐标，编码器的状态为纵坐标，将一个平面划分成网格状，就可以得到卷积码的网络图。图2-4 （2，1，2）卷积码网络图上图表示是（2，1，2）卷积码网络图，它是由节点和分支组成，L=5，所以一共有L+m+1=8个节点（即时间单位），用0到7加以标号。在网络图中，把树状图中具有相同状态的节点合并在一起，每一状态都有两个输入分支和两个输出分支。上分支表示输入信息码元为“0”时状态转移路线，用实线表示；下分支表示输入信息码元为“1”时状态转移

36、路线，用虚线表示。而每一分支上的n个数字(n=2)表示编码器输出信息序列。可以看出，在时间单位3以后的网络图形完全是重复2时间单位的图形，这就反映了该卷积码的约束长度为2。若编码器从状态so（00）开始，在6个时间单位后结束于状态so（00）。在（2，1，2）卷积码网络图中，由于约束长度为2，编码器在最开始的2个时间单位（t=0，t=1）状态由最开始的so状态向别的状态转移，因此t=1编码器的状态只有可能处于so或s1状态中一个。编码器在最后的2个时间单位内（t=6，t=7），编码器的状态由别的状态返回so状态。为了在t=7时刻编码器的状态结束于so，编码器在t=6时状态只能为状态so或s2中

37、的一个。而从t=2至第t=5时间单位中，编码器的状态可以处于4个状态s0，s1，s2，s3中的任意一个。一般情况下，网络图中应有2N-1种状态，输入信息序列有2kL中可能，因而网络图中路径也可能有2kL条，相应于编码器输出的2kL个不同的码序列。例如若给出输入信息位为1101000时，则这时的输出编码序列是11 10 10 00 01 11 00。由上述可见，用网络图表示编码过程和输入输出关系比树状图更为简练。2.2 Viterbi译码原理2.2.1Viterbi算法描述Viterbi算法是一种最大似然译码算法，它是通过计算累积码距，在卷积网络图上寻找一条与接受序列R具有最小码距的最大似然路径

38、。假定编码器输入信息序列为C，经过离散无记忆信道传输后，译码器接受到的序列为R,输入信息序列C与接受信息序列R的关系为R=C+E，E是信息序列在信道传输过程中产生的错误序。译码器根据接受到的信息序列R，根据最大似然原则在卷积网络图上寻找到一条与接受序列R具有最小码距的最大似然路径，这个过程就是译码器寻找有“最大”度量的路径过程，也就是寻找最大似然函数Maxf=logbp(R/Cj),j=1,2,.2kL的过程，其中L表示时间单位数，k表示输入的bit位数，p（*）表示概率。最大似然函数Maxf=logbp(R/Cj)是Cj的似然函数，也称为Cj的路径度量，Cj表示某一个可能的输入信息序列。对二

39、进制同步信道（BSC）来说，寻找具有最大路径度量的路径（即寻找最大似然函数）相当于寻找与接受序列R有着最小汉明距离的路径，即寻找 Minj=d(R,Cj), j=1,2,.2KL （2.2.1-2）其中，d（*）是表示汉明距。 我们现在假定L=200，n=2，k=1时，那么卷积码的网络图中就有2200条路径，如果每一条路径都与接受序列R进行逐一比较后寻找最大度量路径，工作量太大啦，因此直接用上述方法进行译码难以实现。为了解决这一困难，Viterbi算法应用而生。Viterbi算法不需要把每一条路径都与接受序列R进行比较，而是接受一段，计算一段，比较一段，选择其中“最大”度量分支，再进行下一轮的

40、比较。当接受完序列R时，幸存下来的那条路径就是我们要寻找的最大路径度量路径。Viterbi译码的总体流程是比较各分支的度量值，选择一段最可能的分支，更新状态的度量，并根据比较结果获得状态转移表，最后通过状态转移表的回溯算法完成译码，其具体步骤如下：（1） 从某一时间单位j=m开始，对每一状态路径长度为j段的路径计算其路径度量值，然后进行比较，对于每一个状态，选择其中有着最大度量的部分路径幸存下来，并存储该部分路径的度量值PM，保留下来的路径称为幸存路径SP。（2） j+1，计算该时刻进入各个状态的分支度量值BM，把计算得到的分支度量值BM与上一步中幸存路径的路径度量值PM相加，然后进行比较，选

41、择其中相加数最小的路径作为该状态的幸存路径，并更新状态的路径度量值PM，幸存路径就又延长了一个分支。（3） 若jL+m，则重复以上的两个步骤。若j=L+m，则译码结束，译码器就可得到有最大路径度量的路径。 2.2.2Viterbi算法举例 设卷积码编码器（2，1，2）输入信息序列为M=(1011100),经过卷积码编码器后，输出的序列C=(11,10,00,01,10,01,11)，而译码器接受到的序列为R=(10,10,00,01,11,01,11)，可见因为信道的干扰与噪声影响，已经产生了2个错码。下面对照网络图来说明维特比译码的方法。图2-5描述的是维特比译码器译码的过程。图中d表示各个

42、时刻进入每一个状态的幸存路径的度量值（即最小汉明距离），m表示与此相对应的译码器估计的信息序列。由图可以看出，在某一时刻，如j=3时刻，这一时刻接受到的子码R2=00。寻找S1状态的幸存路径方法如下：这时刻进入S1状态有两条分支，上分支是由前一时刻状态S2在编码器输入信息码元“1”转移而来的，这条路径的度量值d0（S2，00）=d0（11，10,00）=ds2+0=1+0=1;下分支是由前一时刻由前一时刻状态S0在编码器输入信息码元“1”转移而来的，这条路径的度量值d1（S0，11）=d1（00，00,11）=ds0+2=2+2=4。根据最小汉明距离准测可得，进入S1状态应保留上分支，即第三时

43、刻S1状态的幸存路径应为C（S2，00）=（11，10，00），这条路径的度量值是d=1，译码器估计的信息序列m=101。若某一时刻进入某一状态的两条路径有相同的度量，可以选择其中任意一条路径作为幸存路径，并不会影响译码结果的正确性。如第四时刻，进入S2状态的两条路径（11，10，00，10）和（00，11，01，01），它们的度量d都为3，故可任选一条作为S2状态的幸存路径，在图中选择（11，10，00，10）。在其他时刻及进入其余状态的幸存路径的选择与此完全相同。按照这种方法依次译码，到了L+m=7个时刻以后，4条幸存路径只剩一条，这条路径就是我们要找的具有最大似然函数的路径，译码器输出的

44、估值序列C=（11，10，00，01，10，01，11），把接受信息序列R中的两个错误纠正过来啦，相应的估值信息序列M=(1011100),，译码结果跟编码器输入信息序列一样。 图2-5 维特比译码器的译码过程2.2.3 Viterbi译码器的特点综上所述，维特比译码器应具备如下特点： （1）（n.k.m）卷积码编码器中寄存器共有2km个状态，每一个状态都应该配置一个路径存储器和一个PM存储器。路径存储器用来存储译码起点，PM存储器用来存储各个状态的PM值。因为维特比译码器的硬件资源和设置复杂度随约束长度k值呈指数增加，因此在实际应用中，为了避免viterbi译码器功耗过大和成本太高的问题，k

45、一般小于10。（2） 每个PM存储器存储路径的宽度是nL。L是卷积码译码时译码器需要存储的码序列节点总长度。若nL的取值过大，维特比译码器所占用存储资源的上升会给工程应用带来很多困难。而在一般实际情况中，经过5至6级节点后，各留选SP基本完全重和为一条SP。因此，XL的宽度不必很大，只需选择存储X段译码段即可满足译码需要。（3） 当译码器译码完第x段数据后，必须在所有数据仍为处理完毕前对存储器中SP进行截尾译码判决输出，虽然这样会使误码率稍高，但在工程应用的情况下，取x=(5-10)倍的约束长度，对译码器性能影响很小。下面介绍截尾译码算法。由图2-5可以看出，当译码器译完第5级节点以后，每个状

46、态留选路径的前几个分支已完全重合在一起，可以将相同的路径输出，从这一点我们可以得知:每个路径寄存器不必存储L很大的码序列(或信息序列M)，而只要存储L段子码即可。也就是当译码器接收并处理完第个码段后，找出最似然度量值所对应的幸存路径作为判决输出，当译码器接收并处理完第+1个码段时，信息元仍然可以用上面幸存路径存储器来存储。像这种不等处理完所有 L段码序列，译码器就开始进行判决和输出的译码方法称为Viterbi译码的截尾译码，也成回溯运算。第三章 Viterbi译码的FPGA实现3.1 Viterbi译码器的基本结构 Viterbi译码器的基本原理是就是将接受到的信息序列R与可能发送的信息序列进

47、行比较，比如发送一个k位序列，那发送的信息序列就有2k种可能，然后将这2k种可能的发送信息序列与接收到的信息序列R进行比较，选择其中汉明距离最小的信息序列作为译码结果。当k值很大时，计算量太大，存储量也很大，不适合直接使用译码方法。维特比算法就解决了这个问题，它不需要比较所有可能的2k种信息序列，而是接受一段，计算和比较一段，选择其中汉明距离最小的码段，再进行下一轮比较，最终找到一个有着最大似然值的信息序列。维特比译码器主要由分支度量模块（BMU）、加比选模块（ACS）、路径度量存储模块（PMU）、幸存路径寄存模块（SMU）、回溯模块（TBU）构成，系统框架图如图3-1。 图3-1 Viter

48、bi 译码器的内部结构图 系统工作过程可以分为以下几个步骤：（1） 首先从（2，1，9）卷积码编码器中输入相应的信息码元，编码器输出信息码元经过分支度量模块BMU，计算译码器接受的信息码元与各状态期望码元之间汉明距离，把计算得到的BM值送人ACS单元进行加比选操作。（2） ACS单元从路径度量存储模块PMU单元中取出前一时刻幸存路径的度量值old_metric,然后与送人ACS单元的分支度量模块BMU的分支度量值累计相加比较，相加度量值较小的作为该状态新的路径度量值new_metric存入PMU单元以备下一时刻加比选使用，并产生幸存路径信息survivor_bit存入幸存路径寄存模块SMU。这

49、个幸存信息表示在加比选操作中，该状态是由前一时刻进入该状态的哪条分支转移而来的，当survivor_bit=0时表示该状态是由偶状态（即上支路）转移而来，当survivor_bit=1时表示该状态是由奇状态（即下支路）转移而来。（3） 当达到回溯深度时，ACS单元会输出一个路径累加度量值最小的状态low_state送人TBU单元，TBU开始工作，同时SMU单元根据这个信号产生一个SMU地址lookup_state,根据这个地址可以从SMU单元中读出该状态的幸存信息lookup_bit,进入TBU单元进行译码操作输出。同时，也可以根据这个幸存比特反推出这个最小状态是由前一时刻哪个状态转移而来的，

50、而根据反推出来的状态又产生一个新SMU地址lookup_state，根据这个新的地址又可以从SMU单元中读出该状态的幸存信息lookup_bit,再进入TBU单元进行译码操作输出。如此循环下去，就可以得到在回溯深度这个时间段内将所有译码输出，再进行倒序处理，就可以得到正确的译码输出。系统工作操作流程如图3-2。 图3-2 译码器的工作流程图3.2 分支度量模块（BMU） 分支度量模块是比较输入码元与状态分支间的似然函数值，然后将其按照加比选模块提供的地址信号输出相应的数值。由于信道特性的不同，可以分为硬判决跟软判决两种判决方式，硬判决是使用汉明距离来表示分支度量，软判决是使用欧式距离来表示分支

51、度量，不同的判决方式计算接收码元序列跟期望序列之间的距离的计算方法也不一样。在硬判决中，需要设定一个门限值，高于这个门限值的就判决为1，低于这个门限值的就判决为0，因此硬判决只有两种距离,且这两种距离相差为1，这种判决较为简单。例如设期望序列v=v0，v1，.vn-1,接收到的序列为r=r0，r1，.rn-1,则汉明距离,而欧式距离为，如果收到序列r=0，1,期望序列v=1，0,使用硬判决，分支度量值就为=|1-0|+|0-1|=2，若使用3比特软判决，1量化为7（111），0量化为（000），则上述所对应的接受序列为r=5（101），4（100），期望序列v=7，0，所以分支度量值则为=。由

52、此可见使用软判决计算分支度量值时既有平方运算又有开方运算，运算较复杂，会占用比较多的硬件资源，影响运算速度。本次实验采用硬判决。 对于码率为R=k/n的卷积码来说，每个状态都2k条分支进入，分支度量计算模块就要计算2k个分支度量值，对于（2，1，9）卷积码来说，共有28个即256个状态，每个状态又有2条分支进入，所以总共要计算512个分支度量值。但是，每一个状态的输出期望码元只可能是00，01，10，11这四个中的一个，而且同一时刻接受序列是相同的，所以所有状态的分支度量值也只有4种可能，所以分支度量模块不需要把所有状态的分支度量值都计算出来，只需要把这四种可能的分支度量值计算出来，然后存储到

53、相应的寄存器中，以备不同状态的加比选模块选用。BM00表示期望码字00的分支度量值，BM01表示期望码字01的分支度量值，BM10表示期望码字10的分支度量值，BM11表示期望码字11的分支度量值。而对于码率R=1/3的卷积码来说，每一个状态输出期望码元只可能是000，001，010，011，100，101，110，111中的一个，同样，每一时刻接收到的序列是相同，因此所有状态的分支度量值也只可能有8中情况，分别为BM000，BM001，BM010，BM011，BM100，BM101，BM110，BM111。BM000表示期望码字000的分支度量值，BM001表示期望码字001的分支度量值，B

54、M010表示期望码字010的分支度量值，BM011表示期望码字011的分支度量值，BM100表示期望码字100的分支度量值，BM101表示期望码字101的分支度量值，BM110表示期望码字110的分支度量值，BM111表示期望码字111的分支度量值。3.3 加比选模块(ACS) 加比选模块是整个viterbi译码器的核心部分，可以说它的性能直接决定着整个译码器的性能。它的主要功能是，把路径度量存储单元（PMU）中存储的各状态所处的路径度量与BMU中相应状态的各分支度量值相加，比较这些结果，选择最小的那个作为该状态幸存路径再存入PMU，并得到路径选择的标志位存入SMU。因此，加比选模块由加法器、比较器、选择器组成。同时，当达到回溯深度时，加比选模块还必须选出累积路径度量值最小的那个状态，在回溯模块TBU译码时使用。 3.3.1状态间的蝶形运算关系 比较哪条路径与发送码字更接近，就是比较它们谁具有更大的似然函数，对于硬判决来说，也即比较谁具有更小的欧氏距离。此时我们面临的主要问题，对于到达某一状态的两条路径来说，它们分别来自哪两个状态。对于（n，k，m）卷积码来说，每个状态有2k条分支进入，其加比选运算如下式 （3-1） 当k=1时，转移到每个状态的分支为2条，每个状态也只可能转移到