卷积码

卷积码（英语：convolution code）是频道编码（channel coding）技术的一种，在电信领域中，属于一种纠错码（error-correcting code）。相对于分组码，卷积码维持频道的记忆效应（memory property）。卷积码的由来，是因为输入的原始消息资料会和编码器（encoder）的冲激响应（impulse response）做卷积运算。卷积码具有以下特性：

一段m字符的消息(m字符的二进制元字符串)会被编码变换成n字符的符号，m/n即是编码率(code rate，n ≥ m)

卷积码的应用范围

　为了达成资料传输，卷积码被广泛使用在许多仪器或技术上，比如数码视频、广播、手机通讯、卫星通讯传输。资讯通常透过'硬性决策方式'（hard-decision code）来解码，例如里德-所罗门码。在涡轮码（turbo codes）出现之前，这种架构可以算是非常高效率的编码。

卷积码编码

原始消息资料依序由输入端（input）进入编码器的寄存器(register，图内简称reg.)，每一个寄存器会存储一个输入字符，而它们的起始值都是0。依图一而言，编码器内有3个模2加法器(modulo-2 adder，可等价于一个异或门（Boolean XOR gate），运算方式是0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0)对存储的3位元原始资料，做各自的加法运算。接着，寄存器（register）内的字符会移往下一格，(reg1 moves to reg2, reg2 moves to reg3)；然后继续将资讯传至输出端（output），如此便可以得到要传输的内容。

output1=reg.1+reg.3\,

output2=reg.1+reg.2+reg.3\,

运算后，输出端（output）则输出编码后的卷积码资料。

由于原始消息资料是依序输入至编码器，所以3个寄存器（register）存储的资料是不同时间点的输入值；reg. 1 存储目前消息资料，reg. 2存储前一周期的资料，reg. 3则是前前一周期的资料。因此，每笔卷积码资料皆与过去的消息资料有关系，因而保有记忆效应（memory property）。

G1 = (1,0,1), G2 = (1,1,1), 总输出数量是2个，有3个寄存器（register）。

递归以及非递归编码

图一是一个非递归编码（non-recursive code）的类型，而图二我们提供了一个递归编码（recursive code）再处理的类型，其即将被进行编码的输入信号同时也是输出信号(参见output 2)；此外，递归编码几乎都是系统性的（systematic），反之非递归编码则是非系统性的（non-systematic）。

冲激响应以及转移函数

卷积码之所以得其名是因为其处理方法是将输入端信号以及编码器中的冲激响应进行卷积。

y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}

此处 $x$ 是输入信号， $y^{j}$ 是输出信号j，而 $h^{j}$ 则是输出信号j的冲激响应。

卷积码的编码器是一个离散线性时不变系统，因此每个输出端子的消息都可以视为该编码器的转移函数；此外，冲激响应可以透过Z变换与转移函数建立关系性。

举一个例子，图三是一个非递归编码器，它的转移函数有三，如下：

$H_{1}(z)=1+z^{-1}+z^{-2},$
$H_{2}(z)=z^{-1}+z^{-2},$
$H_{3}(z)=1+z^{-2}.$

再者，图二的编码器转移函数如下：

$H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},$
$H_{2}(z)=1.$

树状图

参见：Trellis modulation（英语：Trellis modulation）

树状图（Trellis diagram）又称篱笆图，树图表。

卷积码的编码器（encoder）可以表示成有限状态机(finite-state machine, FSM)，拥有 $n$ 组输出端（output）的编码器在FSM上会有 $2^{n}$ 个状态（states）。

以图三的非递归编码器来说，假设现在 $m_{0}$ 存着'1'这一位元、'0'被存放在 $m_{-1}$ ( $m_{1}$ 不用列入考量因为它存放的是现在这个时刻的值)，那我们便定义现在位在"10"这个状态。而在下一个时刻，新的输入端信号进入编码器时可能产生'1'或者'0'，因此下一时刻编码器可抵达的状态是"01"或者"11"；整个树状图如图四所示，显而易见的，并不是所有的状态间都可以进行相连，比如"10"就不会连到"00"或者"10"这两个状态。

这个树状图是卷积码在解码（decode）时的基础，唯有能够从头连到尾的输出端信号（output sequences），才有可能是解码出来的结果，否则便会产生错误。

卷积码解码

现存有许多解码卷积码的方法。对于较小的输出端组数，维特比算法（Viterbi algorithm）是一种普遍被使用来解码的算法，其以最大似然估计（maximum likelihood）来查找最有可能产生观测事件串行的路径。

参考资料

This article incorporates public domain material （页面存档备份，存于互联网档案馆） from the General Services Administration （页面存档备份，存于互联网档案馆） document "Federal Standard 1037C"（页面存档备份，存于互联网档案馆）