信息论与编码9

第九章卷积码内容提要卷积码充分利用了前后码段之间的相关性，是一种非常重要的差错控制编码。。本章首先介绍卷积码的基本概念，然后介绍卷积码的数学描述方法和图形描述方法，最后介绍一种最佳的卷积码概率译码方法—Viterbi译码。第九章

卷积码

卷积码用(n，k，m)表示，编码时n

k个检验元不仅与当前时刻的k个信息元有关，而且与前面m个时刻的信息段有关，因此卷积码的编码器中需要有存储m个信息段的记忆部件。定义m为编码存储，代表了信息段需存储的级数。定义(m+1)为编码约束度，表明编码过程中互相约束的码段个数。卷积码的k和n一般较小，码率较低。卷积码的冗余度高，纠错能力较强。9.1卷积码的基本概念卷积码编码器的原理图

例9.1

（2，1，2）卷积码的编码器

码段长n=2，每个码段的信息位长度k=1，编码存储m=2。第i时刻的码段不仅与当前的信息位ui有关，还与前2个码段的信息位ui

1，ui

2有关。

u=[u0u1u2…]时钟节拍输入u移存器初态移存器次态输出c110010112010011030010011设移位寄存器D0D1初始状态为全0，当输入信息序列u=[100]时，编码器的工作过程输入信息序列u

=[100]时，输出码字c=[111011]。每个码段的最左边码元与信息码元不同，所以是非系统码编码器。

例9.2

（3，2，2）卷积码的编码器

第i时刻信息段，码段，编码器由2个移存器构成。

输入u=[100000]的编码过程

时钟节拍输入ui移位寄存器初态移位寄存器次态输出ci110000110120001000013000000000输入u=[100000]的编码输出c

=[101001000]；同理输入u

=[010000]的编码输出c

=[010001001]；码段左边2个码元和输入的信息元始终一致，所以是系统码。9.２卷积码的数学描述9.2.1卷积码的矩阵描述讨论例9.2的（2，1，2）卷积码的生成矩阵

C=uG∞

，G

被称为（2，1，2）卷积码的生成矩阵，这是一个半无限矩阵。=[1110001000101100…]

G

完全由矩阵的第一行确定。将第一行取出并表示为码的基本生成矩阵

g

=[11101100…]g

其实就是当输入信息序列为冲激序列u

=[100…]时，卷积码编码器的冲激响应。令信息序列u=[10101]，则输出码字讨论例9.2（3，2，2）卷积码的生成矩阵冲激响应为u=

[100000…]时，c=

[101001000000…]；

u=

[010000…]时，c=

[010001001000…]得该码的基本生成矩阵为：将g

经移位得生成矩阵

基本生成矩阵g

=

[G0

G

1

G

2…G

m0…]

其中生成子矩阵生成矩阵中每一行的分组数（即码段数）为编码约束度m+1，矩阵的总行数取决于输入信息序列的长度。一般情况下，(n，k，m)卷积码的生成矩阵表示为9.2.2卷积码的多项式描述第j路输出码段延时算子x表示卷积码编码过程中一个时间单位的延时，第i路输入信息段

将生成子矩阵Gl（0≤l≤m）的i行j列(1≤j≤n，1≤i≤k)取出，组合后得到生成序列表示成多项式为

表示u(i)～C(j)的生成情况，其中代表了编码器中C(j)生成时u(i)的l次移位参与了异或，因此第j路输出的码多项式为生成多项式矩阵G(x)

码多项式为c(x)=u(x)﹒G(x)=[u(1)(x)u(2)(x)…

u(k)(x)]﹒G(x)=[c(1)(x)c(2)(x)…

c(n)(x)]=c(1)(xn)+x

c(2)(xn)+x2

c(3)(xn)+…

+xn

1c(n)(xn)例9.2（3，2，3）卷积码的多项式描述当u

=

[10110111]时，c(x)=u(x)﹒G(x)=

=[1+x+x3

x+x2+x31+x3+x4+x5]=[1+x2+x3+x4+x7+x9

+x10+x11+x14+x17]与码序列[101110010111001001000…]一致。9.3卷积码的图形表示方法

9.3.1状态图输入u

初态Si次态Sj

输出C000100010110001101011111

00001011011011010011100001011110

在卷积码编码器中，寄存器任一时刻存储的数据称为编码器的一个状态，随着信息序列的不断输入，编码器的状态在不断变化，同时输出的码元序列也相应地发生改变。例9.1（2，1，2）卷积码的状态表

状态图中，用实线表示信息0输入，虚线表示1输入，若输入信息u

=[10101]，状态转移为S0→S1→S2→S1→S2→S1→S2→S0，相应输出码元序列为[11100010001011]。编码器输出的码元序列是在信息序列的第一个码元输入直到最后一个码元完全移出移位寄存器所产生的。要求有用信息序列输入完毕后，应再向编码器输入mk个全0码元，所以最终状态应回到初始状态S0。9.3.2树图

树图中，节点处符号为移存器状态，分支上的数据为输出码段，上分支为输入信息0，下分支为输入信息1。

从码树图上观察，输入无限长信息序列，就可以得到一个无限延伸的树状结构图。输入不同的信息序列，编码器就走不同的路径，输出不同的码元序列。

码树图的最大特点是时序关系清晰，且对于每一个输入信息序列都有一个唯一的不重复的树枝结构相对应。缺点是进行到一定时序后，状态将产生重复且树图越来越复杂。

状态图从状态上看最为简洁，但时序关系不清晰。

一般地，对于(n，k，m)卷积码来说，从每个节点发出2k条分支，每条分支上标有n长输出数据，最多可有2km种不同状态。

9.3.3网格图

树图中，从某一阶节点开始所长出的分支从纵向看是周期重复的。因此在第m+1阶节点以后，将树图上处于同一状态的同一节点折叠起来加以合并，就可以得到网格图。

网格图中实线表示输入为0的分支，虚线表示输入为1的分支，分支上标志的n位数据表示相应的编码输出C。

网格图中每一种信息序列有唯一的网格编码路径。

从第m至

l节点，编码器处于稳定的状态转移中，并且各节点的网格结构均相同。在l节点后m个移存器尚需转移m个状态，才能回到初始状态S0。由于l

到l+m节点过程中输入补充0，所以只有实线分支。9.4Viterbi译码

Viterbi译码基于码的网格图结构，是一种极大似然译码方法。它具有以下优点：①有固定的译码时间；②适于译码器的硬件实现，运行速度快；③译码的错误概率可以达到很小；④容易实现，成本低。Viterbi译码步骤（1）在j=m节点处，对进入每一状态的长度为j=m

的部分路径，计算输出数据与对应接收的j个n长码段的汉明距离。将部分路径存储作为被留选的幸存路径。（2）j增加1，把此时进入每一状态的所有分支与前一阶节点处留选的幸存路径累积计算与相应接收码段的汉明距离，每个状态留选汉明距离最小者为对应的幸存路径，其余路径则删除。（3）重复步骤②，直至j=l+m，最终整个网格图中只剩一条幸存路径，译码结束。Viterbi译码方法采用分段处理，每个码段根据接收的码元序列，在网格图上寻找与接收码相比差距最小的可行路径。对于BSC信道，可等价为确定与接收码段具有最小汉明距离的路径。由m至l阶节点，网格图中2km个状态中每一个状态有一条幸存路径；但在l阶节点后，状态数目减少，幸存路径随之相应减少；至l+m阶节点时，仅剩一条幸存路径，它就是译码器输出的最佳估值码元序列的路径。如果在某阶节点，某状态的两条路径具有相同的汉明距离，这时需观察下一阶节点累积的汉明距离，再选定最小距离的路径。输入信息序列u

=[10101]至例10.1编码器，通过BSC送入译码器的序列y=[11100111001011]，采用Viterbi译码

yi为接收码段，d为汉明距离，为信息估值。在图(a)中，从初始状态到达j=2阶节点的4种状态有4条路径，它们与接收序列y0y1=[1110]的汉明距离分别为3，3，0，2，依次作为4种状态的幸存路径。j=2y0=11y1=10d0000

S0=003001111

S1=1030110

S2=0101001

S3=11211(a)

j=3时，沿前一阶节点的幸存路径到达S0状态有2条路径和，与y0y1y2=[111001]的汉明距离分别为4和1，选取后者为S0状态的幸存路径。同样S1，S2，S3状态也都有2条路径，分别留选距离最小者为幸存路径，其余路径则删除。j=3y0=11y1=10y2=01d00S011001111

11S111011000

S20101211001S33011(b)

由j=3的S0,S1,S2状态转移到j=4的S0，S1，S2，S3状态，有4条路径与y0y1y2y3=[11100111]比较，具有最小汉明距离，被留选下来。j=4y0=11y1=10y2=01y3=11dS0

1111

11

1121100

S111001100010S2210100101

01

S321011(c)j=5y0=11y1=10y2=01y3=11y4=00d00S02110001111

S111112101010010001010S2210010

0101

01S3210011(d)j=6时，有用信息已输入完毕，输入端补充0至编码器，所以只剩下S0，S2两种状态，而S0状态的2条路径与y0y1y2

y3y4

y5=[111001110010]的距离都是3，因此都被留存。j=6y0=11y1=10y2=01y3=11y4=00y5=10d00003110000S01001001111

11

11

11

S1

1010

1010

S200