卷积码

　为了达成数据传输，卷积码被广泛使用在许多仪器或技术上，比如数字视频、广播、手机通信、卫星通信传输。信息通常通过'硬性决策方式'（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），如此便可以得到要传输的内容。

${\displaystyle output1=reg.1+reg.3\,}$

${\displaystyle 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）。

图二

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

图三

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

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

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

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

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

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

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

参见：Trellis modulation

图四

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

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

以图三的非递归编码器来说，假设现在${\displaystyle m_{0}}$存着'1'这一比特、'0'被存放在${\displaystyle m_{-1}}$(${\displaystyle 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"（页面存档备份，存于）