卷积码和维特比译码

卷积码

基本概念

卷积码常记为(n, k, N)：

$n$ 为模2和相加器的个数
$N$ 为输入移位寄存器的段数（称为约束长度）
$k$ 表示每段有 $k$ 级

编码效率为 $R_c = \frac{k}{n}$

距离特性

纠错能力的度量：最大的最小距离
最小距 $d_{\min}$ ：卷积码中长度为 $nN$ （ $N$ 为约束长度）的编码后序列之间的最小汉明距离。
自由距 $d_{free}$ ：任意长编码后序列之间的最小汉明距离

表示方法

其实，前面的基本概念看书基本都能理解，但是表示方法确实挺让人费解的，下面捎带解读地介绍卷积码的表示方法。
只介绍常用的树状图和网格图，解析法一般不用。

树状图（以(2, 1, 3)卷积码为例）

见下图。

卷积码编码过程示意
输入序列为 $M = m_1m_2\ldots m_j$ ，从左往右依次输入。

在时刻 $j$ 输入 $m_j$ ，此时寄存器的状态为 $m_{j-1}m_{j-2}$
编码过程：
$x_{1,j} = m_j\oplus m_{j-1}\oplus m_{j-2}$
$x_{2,j} = m_j\oplus m_{j-2}$

那么当输入序列为 $M = 01010101$ 时，可以得到下面的状态列表。

输入 $m_j$	当前状态 $m_{j-1}m_{j-2}$	输出 $x_{1,j}x_{2,j}$	下一状态 $m_jm_{j-1}$
0	00	00	00
1	00	11	10
0	10	10	01
1	10	01	11
0	01	11	00
1	01	00	10
0	11	01	01
1	11	10	11

简要解释一下。寄存器初始状态为0，按照上述的编码过程，输入 $m_0 = 0$ 时， $x_{1,0} = m_0\oplus 0\oplus 0 = 0$ ， $x_{2,0} = m_0\oplus 0 = 0$ ，下一状态为 $m_jm_{j-1} = 00$ 。
输入 $m_1 = 1$ 时， $x_{1,1} = m_1\oplus 0\oplus 0 = 1$ ， $x_{2,1} = m_1\oplus 0 = 1$ ，下一状态为 $m_jm_{j-1} = 10$ （表格中已标红）。
依此类推，得到整个表格。
为了方便表示，记状态 $a: 00$ ；状态 $b: 10$ ；状态 $c: 01$ ；状态 $d: 11$
因此可以得到下面的树状图，其中节点表示状态，树杈上所标注的数字表示输出比特。

（2，1，3）卷积码树状图表示

简要解释一下。
从最左边开始，初始状态为 $a, 00$ ，上面树杈上的蓝色的0表示输入比特，黑色的00表示输出比特 $x_{1,0}x_{2,0}$ ，查表格可知，当输入为0，当前状态为00，输出为00时，下一状态仍为00，也就是状态 $a$ ；
再来看第一个 $a$ 下面的树杈，同样，蓝色的1表示输入比特，黑色的11表示输出比特 $x_{1,1}x_{2,1}$ ，查表格可知，当输入为1，当前状态为00，输出为11时，下一状态是10，也就是状态 $b$ 。
后面的树杈也就同理可得了。

注：上图不该写成“共 $2^j = 16$ 条树杈”，而是每个节点会引出 $2^j$ 条支路。

网格图

其实原理还是一样的，只不过是换了一种表示方法，看起来更简洁而已。将二叉树的上支路（对应输入比特0）用实线表示，下支路（对应输入比特1）用虚线表示，仍然根据表格来确定下一步的状态。

至此，卷积码应该就讲清楚了。

维特比译码

根据书上所说，卷积码的译码方法有三种：

维特比译码：性能最佳，硬件实现最复杂；
门限译码：性能最差，硬件简单；
序列译码：性能和硬件介于维特比译码和门限译码之间。

目前应用最广的就是维特比译码。

译码原理

首先还是应该介绍译码原理，举例子或者解读只是为了更好的理解原理。
在维特比译码算法中，把汇聚在每个节点上的两条路径的对数似然函数累加值进行比较，然后把具有较大对数似然函数累加值的路径保存下来，而丢弃另一条路径，经挑选后低 $N+1$ 级只留下 $2^N$ 条幸存路径，选出的路径连同它们的对数似然函数累加值一起被存储起来。
总结来说就是加-比-选，即每级求出对数似然函数累加值，然后两两比较并作出选择。

译码例子（以(2, 1, 3)卷积码为例）

不失一般性，假设编码器输出序列为全0码。假设接收序列为 $Y = 001001000000$ ，由于输出为全0码，则可知有两个位置发生了错误（两个1）。
用下图表示随着接收序列的串行输入，维特比译码器中各路径的取舍情况。圆圈中的数字表示从起始点到某节点的该路径与接收序列的之间的汉明距（最大对数似然函数 = 最小汉明距）。

维特比译码过程的网格图表示

图中画了卷积码的网格图，上支路对应输入0，下支路对应输入1。

图一，根据上面的状态表格，输入0的输出为00，输入1的输出为11，汉明距分别为0，2，标在了支路末端；
图二，同样地，根据状态表格，画出网格图。关注红色路径，输出分别为11，10，对比接受序列 $Y$ ，见图中红色下划线和蓝色下划线，00和11地汉明距为2，10和10的汉明距为0，故红色路径总的汉明距为 $2+0=2$ ，其他路径同理；
图三，前面不变，根据状态表格，这时出现了路径终点重合的情况，因此需要进行比较-选择，每条路径的汉明距也分别标注出来，选择较小的那个（汉明距相同的则任意选），也就是图中红色对勾的那条路径；
依此类推，可得到图十的情况，这时译码过程也就结束了。

补充说明

事实上，在第三步即可断定第一条支路应为 $Y=00$ 支路，这是因为所有幸存路径都是从同一点出发的（汉明距为0的点）。由此可见，不必等到最后得到唯一一条路径才做出最后的判断，因而也不需要等整个译码序列输入后再加 $N-1$ 个已知的结束信息。译码器可以以少量时延连续不断地工作，做出基本正确的判断。

参考资料

曹志刚，宋铁成，杨鸿文.通信原理与应用 [M].北京：高等教育出版社,2015