一、实验目的
1.了解维特比译码的原理
2.了解维特比译码的算法
二、实验原理
卷积码的译码方式有3种：维特比译码，序列译码和门限译码。维特比译码具有最佳性能，但硬件实现复杂：门限译码性能最差，但硬件简单；序列译码在性能和硬件方面介于维特比译码和门限译码之间。维特比译码和序列译码都是建立在最大似然译码原理的基础上。下面介绍卷积码的维特比译码的原理。
卷积码网络图中共有 种状态，每个节点（即每个状态）有 支路引出。为简便起见，讨论K=1的情形，从全0状态起始点开始讨论。
由网络图的前N-1条连续支路构成的路径互不相交，即最初的 条路径各不相同，当接收到第N条支路时，每条路径都有2条支路延伸到第N级上，而第N级上的每两条支路又都汇聚在节点上。在维特比译码算法中，把汇聚在每个节点上的两条路径的对数似然函数累加值进行比较，然后把具有较大对数似然函数累加值的路径保存下来，而丢弃另一条路径。经挑选后第N级只留下 条幸存路径，选出的路径连同它们的对数似然函数累加值一起被存储起来。由于每个节点引出两条支路，因此以后各级中路径的延伸都增大一倍，但比较它们的似然函数累加值后，丢弃一半，结果留存下来的路径总数保持常数。
由此可见，上述译码过程中的基本操作是“加－比－选”，每级求出对数似然函数累加值，然后两两比较，并做出选择。有时会出现两条对数似然函数累加值相等的情况，在这种情况下可以任意选择其中一条作为“幸存”路径。
在每一级中都有 条幸存路径，当序列发送完毕后，为了判断其最后结果，就要在网格图的终结处加上N-1个已知信息（即N-1条已知支路）作为结束信息。在结束信息到来时，由于每一状态中只有与已知发送信息相符那条支路被延伸，因而在每级比较后，幸存路径减少一半。因此，在接收到N-1个已知信息后，在整个网格图中就只有唯一的一条幸存路径保存下来。这就是译码所得的路径。即在已知接收到的序列的情况下，这条译码路径和发送序列是最相似的。
维特比译码整个过程并不复杂，译码器的运行是前向的，无反馈的。由于在每级中的每个状态上要进行“加－比－选”运算，译一个L比特的序列，译码操作的总次数为 ，因此译码器的复杂性与状态数成正比，也是随约束长度N的增加而呈指数增长的。因此目前只限于应用在 的卷积码中。
上述作为结束信息的已知信息实际上就是不发生错误的一段信息。因此，只要差错模式不超出卷积码的纠错能力，从一个节点开始分叉产生的各条幸存路径经过一段间隔后，总能正确地又合并成一条路径。但需要经过多长时间间隔，在何处合并，都是不确定的，与差错模式有关。而在实际实现时，不可能建立这种随机的译码深度，只能建立一个固定的译码深度。
Viterbi译码算法
Viterbi（维特比）算法根据可能的状态转移进行译码，状态转移可用网格图表示，图中状态表示编码器状态，路径状态表示编码器输出符号。
Viterbi译码译码过程就是根据接收到的数据符号，按最大似然译码准则找出编码器在网格图上所走过的路径。Viterbi译码算法的处理过程如图6-1所示。
图6-1 通用Viterbi译码算法处理流程
度量值的更改包括：
（1） 分支度量计算；
（2） 对每个新状态，将分支度量值与旧状态的度量值相加，得到新状态的度量值；
（3） 选择并保存最小度量值；
（4） 保存幸存路径；
（5) 每收到一个符号就进行状态转移，Viterbi译码算法必须计算前一个状态到各个新状态的分支度量值。当采用硬判决输入时，分支度量值可用汉明距表示；若用软判决输入时，用欧氏距离表示，对于编码速率为R=1/C的卷积码来说，其欧氏距离为
其中sdn表示接收序列，Gn(J)为网格图上每个路径状态的期望输入值，J是路径指示值，C为编码速率的倒数。将上式展开得
在进行路径度量值比较时，可以不加以考虑。这样省去表达式前面的负号，则在分支度量值比较时应取大值。对于编码速率为1/2的卷积码，
图6-2 （2,1,3）卷积码蝶型结构
其分支度量值为：T=sd0×G0(J)＋sd1×G1(J)，其中sdn与Gn(J)均用双极性表示，即0用＋1表示，而＋1用－1，在单片机编程的过程中，分别用T0到T1寄存器来表示，即T0＝＋sd0＋sd1，T1＝＋sd0－sd1。
分支度量值的更新可用如图6-2所示蝶型结构表示。该图给出了从一个旧状态到新状态的所有可能的卷积编码的转移分支路径。
用单片机AT89C2051（U402）对单片机AT89C2051（U401）输出的卷积编码序列进行译码，如图6-3所示。卷积编码序列DATA1（无误码）或DATA2（有一位误码）从U402的T1引脚串行输入，由开关K401决定接收哪种编码序列，信号波形见TP404，单片机U402对输入的卷积编码序列进行维特比译码后，从DATA4（RXD引脚，波形见TP405）串行输出，并从P1口并行输出，使发光二极管（D0－D7）显示8位译码输出序列。
图6-3 用单片机AT89C2051进行维特比译码电路图
三、实验内容
1.设置拨线开关。
把拨线开关（SW401）的第1-8设置输入序列为0DCH。设置拨线开关的第9位状态为1（即开关拨上），不产生误码，因此DATA1（TP402）和DATA2（TP403）的信号是一样的，用双踪示波器观察。
2. 用发光二极管观察译码输出的结果
把跳线器插在K401的1、2两端或2、3两端，使译码器U402（见TP404）接收的是无误码的卷积编码序列DATA1（波形见TP402，无误码）信号或DATA2（波形见TP403，插入误码）信号；观察发光二极管（D0－D7）显示的8位译码输出序列是什么（灯亮为1，灭为0），与拨线开关（SW401）的第1-8设置的输入序列是否一致，对比测量点TP401与TP405的波形。
当把拨线开关（SW401）的第1-8设置的输入序列分别为
（1） 00H；（2）7FH；（3）80H；（4）4BH；（5）0FFH等
读出发光二极管（D0－D7）显示的8位译码输出序列是什么，与拨线开关（SW401）设置的输入序列是否一致。同时用双踪示波器观察和记录DATA1（波形见TP402）和DATA2（波形见TP403）的卷积编码信号。
3. 用双踪示波器观察译码输出的结果
设置拨线开关的第9位状态为1（即开关拨上），不产生误码，把跳线器插在K401的1、2两端或2、3两端，使U402接收的是无误码的卷积编码序列DATA1信号或DATA2信号；当把拨线开关（SW401）的第1-8设置的输入序列为
（2） 1EH；（2）37H；（3）56H；（4）78H；（5）9CH等
用双踪示波器的两个探头分别接在DATA3（TP401，原始数字序列输入）和DATA4（TP405，译码还原数字序列输出），观察译码输出序列与输入序列是否一致。
4. 观察对有误码的卷积编码序列的维特比译码。
把拨线开关（SW401）的第1-8设置输入序列为0DCH。设置拨线开关的第9位状态为0（即开关拨下），产生误码。用双踪示波器观察和记录DATA1和DATA2的卷积编码信号。
把跳线器插在K401的2、3两端，使U402接收的是有误码的卷积编码序列DATA2信号；读出发光二极管（D0－D7）显示的8位译码输出序列是什么，与拨线开关（SW401）设置的输入序列是否一致。
当把拨线开关（SW401）的第1-8设置的输入序列分别为
（3） 00H；（2）7FH；（3）80H；（4）4BH；（5）0FFH等
读出发光二极管（D0－D7）显示的8位译码输出序列是什么，与拨线开关（SW401）设置的输入序列是否一致。用双踪示波器的两个探头分别接在DATA3（TP401，原始数字序列输入）和DATA4（TP405），译码还原数字序列输出），观察译码输出序列与输入序列是否一致。
四、实验报告要求
1. 掌握差错控制编码的基本概念
2. 掌握维特比译码的原理和算法
3. 画出各点波形，并做简要的说明
