共计 1956 个字符，预计需要花费 5 分钟才能阅读完成。
本专栏蕴含信息论与编码的外围常识，按知识点组织，可作为教学或学习的参考。markdown 版本已归档至【Github 仓库：https://github.com/timerring/information-theory】或者公众号【AIShareLab】回复 信息论 获取。
卷积码根底
分组码—无记忆编码
卷积码—记忆编码
- 可能识记卷积码的基本概念;
- 可能依据连贯矢量画出卷积码的编码器，并进行编码;
- 可能依据编码器画出该卷积码状态转移图和网格图;
- 可能使用维特比译码算法对卷积码进行译码;
- 理解交错的概念。
卷积码的概念
卷积码由三个整数形容, (n, k, L), 其中 k / n 也示意编码效率，L 称为束缚长度; 示意在编码移位寄存器中 k 元组的级数，k 示意编码时一次输出编码器的码元数。
卷积码不同于分组码的一个重要特色就是编码器的记忆性，即卷积编码过程产生的 n 元组，不仅是以后输出 k 元组的函数，而且还是后面 L - 1 个输出 k 元组的函数。通常，n 和 k 取较小的值，通过 L 的变动来管制编码的能力和复杂度。
卷积码编码器的构造
(n, k, L) 卷积码: 下图为卷积码的编码器, 其中有 kL 级 移位寄存器, $\boldsymbol{L}$ 称为卷积码的束缚长度。
卷积码的编码器是一种无限状态机，它的状态数目为 $2^{(L-1) k}$。状态和以后输出的 $\boldsymbol{k}$ 元组决定了以后输入的 n 元组。
卷积编码器示意
这是一个 (2,1,3）卷积码，即 n =2, k=1,L=3。
为什么叫卷积码?
编码过程:
设输出信息序列 100101.
输入信息序列为 11 01 11 11 01 00 01 11
卷积码编码器初始状态为 0，编码之后需保障状态清零
1、连贯矢量（生成矢量)
形容编码器的一种办法是指定 n 个连贯矢量，每个矢量对应于一个模 2 加法器。每个矢量都是 L 维的，示意该模 2 加法器和编码移位寄存器之间的连贯。矢量中第 i 位上的 1 示意移位寄存器相应级与模 2 加法器连贯， 若是 0，则示意相应级与模 2 加法器之间无连贯。
2、状态形容和状态图
卷积码编码器属于一类称为无限状态机的器件。
“无限”表明状态机制只有无限个不同的状态。“状态”能够用设施的以后输出和起码的信息数量，来预测设施的输入。状态提供了无关过来序列过程及一组未来可能输入序列的限度，下一状态总是受到前一状态的限度。
以编码效率为 1 / n 的卷积码编码器为例, 状态就用最右端（L-1)级寄存器内容来示意（留神这里的最右端是指以后信息码元输出后移位寄存器最右端的寄存器）。
理解以后状态以及下一个输出，是确定下一输入的充要条件。
示意简略编码器的一种办法是状态图。
状态图方框内的状态示意寄存器最右端(L-1）级的可能内容，状态间的门路示意由此状态转移是的输入分支字。寄存器的状态示意为 a =00，b=01，c=10，d=11. 对应于两种可能的输出比特，从每一个状态登程只有两种转移，状态转移时的输入分支字标注在相应的转移门路旁。图中实线示意输出比特为 0 的门路，虚线示意输出比特为 1 的门路。
留神: 状态转移不是任意的。因为每次移入 1 个信息比特，故寄存器在每个比特工夫上只有两种可能的状态转移。
3、树图
尽管状态图齐全的形容了编码器的个性，但因为没有示意工夫的过程，采纳状态图跟踪编码器的状态转移很不不便。如果要展现出编码器输出、输入的所有可能状况，则可用树图形容。它是将编码器的状态图按工夫开展而成的。
4、网格图（The trellis Diagram）
网格图将树图上处于同一状态的同一级节点合并。
下图为 (2,1,3) 卷积码的网格图。网格图的节点代表了编码器的状态; 在每个工夫单元内, 网格图用 $2^{L-1}$ 个节点示意 $2^{L-1}$ 个可能的编码器状态。可见，会有反复。
某 (2,1,3) 卷积码的连贯矢量为:
$$
g_{1}=\left[\begin{array}{lll}
1 & 1 & 0
\end{array}\right], \quad g_{2}=\left[\begin{array}{lll}
0 & 1 & 1
\end{array}\right]
$$
(1) 请画出该卷积码的编码器、状态图和网格图。
(2) 当输出序列为 100011101001 时，求编码输入。
参考文献：
- Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
- Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
- 周炯槃. 通信原理（第 3 版）[M]. 北京：北京邮电大学出版社, 2008.
- 樊昌信, 曹丽娜. 通信原理（第 7 版）[M]. 北京：国防工业出版社, 2012.
