例：设卷积码为(n, k, m) = (3, 1, 2)码


现在的发送信息位为1101
了3个“0”，即1101000
为了使移存器中的信息位全部移出，在信息位后面加入
编码后的发送序列：111 接收序列：111
110 010 100 001 011 000
010 010 110 001 011 000 (红色为错码)
000 111 001 100 010 101 011 100 010 101 101 d 011 001 000 011 a b c
a b
001
c d
110
13

若已知这3个码元是（为结尾而补充的）“0”，则在解码时 就预先知道在接收这3个“0”码元后，路径必然应该回到状 态a。而由图可见，
000 111 001 100 010 101 011 100 010 101 101 d 001 011 001 011 000 a b c
按照上表中的幸存路径画出的网格图示于下图中。
a
b
111 001
a 011 100 110 110 010 101 010 d b
100
c d
c
图中粗线路径是距汉明离最小（等于2）的路径。
12

在编码时，信息位后面加了3个“0”。若把这3个“0”仍然 看作是信息位，则可以按照上述算法继续解码。这样得到 的幸存路径网格图示于下图中。图中的粗线仍然是汉明距 离最小的路径。
3
4 5 6
aaab
abcb aabc abdc
000 000 111
111 001 100 000 111 001 111 110 010
6
4 7 1
否
是 否 是
7
8
aabd
abdd
000 111 110
111 110 101
6
4
否
是
比较到达每个状态的两条路径的汉明距离，将距离小的
一条路径保留，称为幸存路径。这样，就剩下4条路径 了，即表中第2, 4, 6和8条路径。
比较网格图中的这8条路径和接收序列之间的汉明距离。
011 011 011 b 100 100 100 001 001 001 001 c 110 110 110 110 010 010 010 d 101 101 101
9
将这8个比较结果列表如下：
序 号 1 2 路径 aaaa abca 对应序列 000 000 000 111 001 011 汉明距离 5 3 幸存否？ 否 是
例如，由出发点状态a经过3级路径后到达状态a的两条 路径中上面一条为“000 000 000”。它和接收序列“111 010 010”的汉明距离等于5；下面一条为“111 001 011”, 它和接收序列的汉明距离等于3。
a b c d 000 111 000 111 000 111 000 111 000 111 a
编码器的工作状态
b1 b3b2 状态
1 00 a
1 01 110 b
1 10 c
1 11 d
0 00 000 a
0 01 001 b
0 10 011 c
0 11 010 d
4
c1c2 c3 111
100 101
卷积码的解码 码树搜索法：(3, 1, 2)卷积码的码树图
c000c c c000c3 a 1 2 3 a c2 1 111 b c000c3 c2 1 a 001 c 111
19
维特比译码的特点

维特比算法是最大似然的序列译码算法 译码复杂度与信道质量无关 运算量与序列长度呈线性关系 存贮量与序列长度呈线性关系 运算量和存贮量都与状态数呈线性关系 状态数随分组大小k及编码深度m呈指数关系
20
维特比译码算法的演示
21
a b c d
110
只有两条路径可以回到a状态。所以，这时上图可以简化成：
a b
000 111 001 100 011 100 010 001 011 001
000 011
a b c
c d
110
010
14
d

在上例中卷积码的约束长度为N = 3，需要存储和计算8条
路径的参量。 由此可见，维特比算法的复杂度随约束长度N按指数形式 2N增长。故维特比算法适合约束长度较小（N 10）的编 码。
10

解码第2步：继续考察接收序列中的后继3个比特“110” 计算4条幸存路径上增加1级后的8条可能路径的汉明距 离。计算结果列于下表中。
路径
abca+a abdc+a abca+b abdc+b abcb+c
序号
1 2 3 4 5
原幸存路径的 距离
3 1 3 1 4
新增 路径段
aa ca ab cb bc
卷积码
1

卷积码的特点：

监督码元不仅和当前的k比特信息段有关，而且还同前面m = (N – 1)个信息段有关。


将N称为码组的约束长度。
将卷积码记作(n, k, m)，其码率为k/n。
2

卷积码的编码 一般原理方框图
每次输入 k比特
1 … k … 2k … 3k 1 … k 1 … k 1 … k … … … … … … … Nk 1 … k

15
维特比译码——收尾


最大似然序列译码要求序列有限，因此对卷积码 来说，要求能收尾。 收尾的原则：在信息序列输入完成后，利用输入 一些特定的比特，使M个状态的各残留路径可以 到达某一已知状态（一般是全零状态）。这样就 变成只有一条残留路径，这就是最大似然序列。
16
卷积码收尾的实现


非递归卷积码：约束长度为m+1的卷积码，只要 在信息序列输入完成后连续送入m个0，即可使任 一路径都到达最终的状态0。 递归卷积码：可通过将输入值置成反馈值，而使 m个时钟后的状态到达0。
17
卷积码收尾
非系统非递归码
D D
递归系统码
D D
18
维特比译码的复杂度

对信息序列长度为L，信息符号取自GF(p)，R=k/n， 约束长度为m+1的卷积码。状态数为pkm，因此对 每个时刻要做pkm次加比选得到pkm个状态的残留路 径，每次加比选包括pk次加法和pk-1次比较。因此 总运算量约为Lpkm次加比选。同时要能保存pkm条 残留路径，因此需要Lpkm个存贮单元。
Nk级 移存器
1
2
… … … …
n
n个模2 加法器
每输入k比特 旋转1周
编码输出
3

卷积码编码器的实例方框图：(n, k, m) =（3, 1, 2）
输入 1 b1 2 b2 3 b3
c3 c2 c1
编码输出
每当输入1比特时，此编码器输出3比特c1c2 c3：
c1 b1
c2 b1 b3 c3 b1 b2 b3
信息位
000 111 001 110 011 100 010 101 1
下 半 部
1
1
d
此法不实用：因为随信息位增多，分支数目按指数规律增长 5

卷积码的状态图 移存器状态和输入输出码元的关系
输入 1 b1 2 b2 3 b3
c1 b1
c3 c2 c1 编码输出
c2 b1 b3 c3 b1 b2 b3
前一状态 b3 b2 a (00) b (01) c (10) d (11)
当前输入 b1 0 1 0 1 0 1 0 1
输出 c1c 2c3 000 111 001 110 011 100 010 101
下一状态 b3 b2 a (00) b (01) c (10) d (11) a (00) b (01) c (10) d (11) 000 a 111 100 011 c
新增距离
2 2 1 1 3
总距离
5 3 4 2 7
幸存否？
否 是 否 是 否
6
7 8
abdd+c
abcb+d abdd&#dd
1
0 2
5
4 6
是
是 否
表中总距离最小为2，其路径是abdc+b，相应序列为
111 110 010 100。它和发送序列相同，故对应发送信息 位1101。 11
由于这是一个 (3, 1, 2)卷积码，发送序列的约束长度为N = m + 1 ＝ 3，所以首先需考察3个信息段，即考察3n ＝ 9比 特，即接收序列前9位“111 010 010”。
8

解码第1步
由网格图可见，沿路径每一级有4种状态a,
b, c和d。每 种状态只有两条路径可以到达。故4种状态共有8条到达 路径。
000 111 011 100 001
110 010
000 111
011 100 001 110 010 101
000 111
a
001 c d
a
b 111
110
101
011 b 100 001 c 110 010 d 101
a b
100
001 c
c
d
110
010
d
7

维特比算法

基本原理：将接收到的序列和所有可能的发送序列作比较， 选择其中汉明距离最小的序列当作是现在的发送序列
b
110 001 010 d 101

状态图
6
(3, 1, 2)卷积码的网格图 网格图中的编码路径举例 输入信息位为11010时 输出编码序列是： 111 110 010 100 001…