卷积码

卷积码（英语：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个二模数加法器(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"（页面存档备份，存于互联网档案馆）