《信息论与编码》 课件 第6章信道编码

第5章介绍了信源编码，是关于有效性的，第5章与第2章（第4章）是一条有效性主线；本章将介绍信道编码，是关于可靠性的，第6章与第3章是一条可靠性主线。1第6章信道编码2本章内容一些基本概念信道编码定理常用信道编码方法—线性分组码、卷积码3基本概念一些基本概念4

一些概念5差错控制编码及分类：差错控制编码：

通过增加冗余码元，提高通信的可靠性。如：k个码元的信息码组m=（mk-1，mnk2，…，m1，m0），组合得到n个码元的码字C

=（cn-1，cn-2，…，c1，c0）（n>k），该n个码元只有个是独立的，其余k个是冗余。分类：从功能角度：检错码（可以检测出发生了差错）、纠错码（可以纠正一定数量的差错）对信息序列的处理方法：分组码（相关性只分布于组内）、卷积码（组间也有相关性）码元与原始信息位的关系：线性码（所有码元由信息码元线性组合得到）、非线性码（所有码元由信息码元非线性组合得到）差错类型：纠随机差错码、纠突发差错码等一些概念6差错控制系统的分类：前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错（信息传递只有前向的：从发送端到接收端）反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码（须有反馈信道：从接收端到发送端的信息传递）混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力一些概念7译码规则：译码：就是接收端收到接收符号集中的某一符号，据此来判断（或者说猜测。因为信道是有扰信道，输入符号和输出符号不是一一对应的）发送端发送的是发送符号集中的哪个符号，即设计一个规则。最大后验概率译码（MAP）：设接收端收到符号的条件下，发送端发送符号的概率为，如果设计的译码规则为，那么，译码正确的概率就是，而译码错误的概率则为。如果想使错误概率最小，则需要最大，即：

称为后验概率，因此，上述的译码规则，称为最大后验概率

译码。最大后验概率译码使最佳译码。最大似然译码（ML）：称为最大似然译码，称为似然概率。一些概念8最小汉明距离译码：对于二进制对称信道（BSC）来说，似然概率

若发送码字矢量为C，接受码字矢量为R，其汉明距离（接受码字和发送码字按比特比较，不同的比特个数）为d，此时似然函数是

由于一般，，所以d越小，似然函数就越大，因此，对于BSC信道，最大似然译码就等价于最小汉明距离译码。一些概念9矢量空间：正交完备基：n维空间由n个相互正交的基底张成，n维空间的任何一个矢量，可以由这n个基底线性组合而得到。这组基底称为正交完备基。例如：三维空间可由三个相互正交的单位矢量张成。矢量的表示：

n维空间的一个矢量，可以由n个元素组成的数组表示，是这个矢量的端点坐标。这个数组也叫做n重。如C

=（cn-1，cn-2，…，c1，c0）是一个n重。子空间：n维空间的一个k维子空间，可以用一个k维n重来表示：C

=（cn-1，cn-2，…，c1，c0），

n个元素中的k个是独立的，而另外n

-k个元素可由k个元素线性组合得到。例如：三维空间中令z=x+y（即：3重数组中的2个：x、y是独立的，而由x、y组合而成），则可以得到一个2维子空间。矢量空间中点的个数：实数空间：有无穷多个点；整数空间：对q进制，n维空间的每个坐标轴上有q个不同取值（0，1，…，q-1），故共有qn个点。一些概念10码空间：

以(n,k)分组码为例。所谓(n,k)分组码，是将信息码流分成k个一组（称为信息码组，也叫k维k重），通过增加个n-k码元的冗余，变成n个码元的一个码字（k维n重）。

从矢量空间的角度来看：一个码字可以看成矢量空间（整数空间）的一个点；码空间可以看成n维空间的一个k维子空间（码字的n个码元，只有k个是独立的）；码空间（k维空间）共有qk个点，特别地，对二进制，共有2k个点；一些概念11n维空间共有qn个点；将一个信息码组（k个码元）编码成一个码字（n个码元，其中k个是独立的），可以看成是将一个k维码空间映射到一个n维空间的k维子空间上；n维空间共有qn个点，选择了其中的qk个点作为码空间qk个点的映射，称为许用点；其余的qn-

qk个点称为禁用点；码字通过信道传输，如果发生了某些码元错误，则可能从一个许用点错到一个禁用点，就可以检测到错误（检错，通过某些机制，甚至可以纠错）；禁用点越多（n-k越大），检错纠错能力越强，但付出的代价（n-k是冗余）越大。一些概念12信道编码定理信道编码定理13信道编码定理如果不考虑速率，当然可以达到任意高的可靠性。这没有意义。那么，就应该考虑可靠性和速率之间的关系。香农把问题定义为：在可以使解码错误概率渐近于零的条件下，信道的最高传输速率是多少？这是香农信道编码定理要解决的问题。14信道编码定理定理：

若一个离散无记忆信道的信道容量为C，只要平均信息率R小于信道容量C，总存在一种信道编码方法和相应的译码规则，使译码错误概率PE任意小。证明思路：采用随机编码，如果随机编码的平均译码错误概率可以趋近于零，则一定有一部分“好码”，其错误概率趋近于零。Gallager在1965年证明，平均译码错误概率的上界为：15信道编码定理

其中，N为码长，R为信息速率，E(R)称为可靠性函数，E(R)~R关系曲线如下图所示：曲线表明：只要信息速率R<信道容量C，可靠性函数E(R)>0，因此，只要码长N足够大，总可以使平均译码错误概率趋近于零。16信道编码定理

下图为不同信道容量时的E(R)~R关系曲线。可以看出：对同样的信息码率R，信道容量C越大，可靠性函数E（R）的值越大，可靠性越高。对同样的信道容量C，信息速率R越小，可靠性函数E（R）的值越大，可靠性越高。17信道编码定理

因此，为提高可靠性，降低译码错误概率，可以：增大信道容量C。根据香农公式，要增大信道容量，可以：增加带宽；增加信号功率。减小速率R。增大码长N。18信道编码定理

信源信道联合编码定理：信源编码定理说，只要信息率R>信源熵H(X)，就可以实现无失真编码；信道编码定理说，只要信息率R<信道容量C，就可以实现无差错译码。将两者结合，就可以得到信源信道联合编码定理：

若离散无记忆信源熵为H(X)，离散无记忆信道容量为C，只要：H(X)<C，则总存在一种信源信道联合编码方法，使得信源输出信息能够以任意小的差错概率通过该信道可靠传输。19常用信道编码方法

常用信道编码方法20常用信道编码方法

香农的信道编码定理说明，一定存在“好码”。但怎么样构造“好码”，香农没有给出方法。下面介绍两种常用的信道编码方法：线性分组码卷积码21常用信道编码方法—线性分组码

线性分组码如前所述，线性分组码的编码，就是从k维k重信息空间映射到一个n维空间的k维子空间（码空间）。线性分组码的编码：n维空间由n个正交基底矢量张成，n维空间的k维子空间可以由这n个基底矢量中的k个张成。

不失一般性，可以选张成k维子空间。

于是，k维k重信息空间的一个信息码组到n维空间的k维子空间的映射，就是这k个基底矢量的线性组合：22常用信道编码方法—线性分组码

写成矢量形式，就是：上式可以理解成：由信息码组的k个码元，组合得到码字的n个码元，其中k个是独立的，

n-k个是冗余。

可以看出，给定了矩阵G，一个信息码组m，就可以映射为一个码字C。23常用信道编码方法—线性分组码

1.生成矩阵：所以矩阵G叫做生成矩阵：24常用信道编码方法—线性分组码

2.校验矩阵：把n个基底矢量剩余的k个基底张成的空间叫做校验空间。组成的矩阵叫做校验矩阵：25常用信道编码方法—线性分组码

2.校验矩阵：由于码空间的基底和校验空间的基底矢量是相互正交的，故码空间和校验空间相互正交：上式可用于检验一个接收矢量R是不是码字。如果，则R一定不是码字。这也是H被叫做校验矩阵的原因。26常用信道编码方法—线性分组码

3.系统形式的生成矩阵：如果码字C

=（mk-1，mk-2，…，

m0，cn-k-1，c1，c0）即：码字的前k个码元就是信息码元，后n-k个码元是由信息码元组合得到的冗余码元则：这样的码字叫做系统码。一般形式的生成矩阵G，用C=mG得不到系统码。

为此，需要对生成矩阵G系统化。

27常用信道编码方法—线性分组码4.生成矩阵的系统化：如果生成矩阵是如下形式：则可以得到系统码。

可以通过对普通形式的生成矩阵G做行运算得到系统形式的生成矩阵Gs

28常用信道编码方法—线性分组码注意：系统化时对生成矩阵G只能做行运算！而不能做列运算。原因：生成矩阵的每一行，是n维矢量空间的一个基底矢量。行运算相当于对基底矢量的线性组合。这种运算并不会改变其张成的矢量空间（码空间）。如果做列运算，则改变了基底矢量本身。29常用信道编码方法—线性分组码对系统形式的生成矩阵：容易证明，其对应的校验矩阵为：若为二进制，则：30常用信道编码方法—线性分组码线性分组码的编码电路：

用移位寄存器、加法器和拨档开关等电路元件可实现由信息码元得到码字码元的编码过程，组成编码电原理图，可参见下例。31常用信道编码方法—线性分组码例题：若一个（6，3）线性分组码的生成矩阵为：

试：①计算码集，列出信息码组与码字的映射关系；②将该码系统化，计算系统码码集，并列出映射关系；③计算系统码的校验矩阵H。若收码为，检验它是否为码字。④

根据系统码生成矩阵，画出编码器电原理图。32常用信道编码方法—线性分组码1.信

息码

字系统码字00000000000000000101110100101101011000101011001110110001110110011101010011110110011110110011000101111000111101011011101033常用信道编码方法—线性分组码2.对生成矩阵G做行运算，原第1、3行相加作为第1行，原第1、2、3行相加作为第2行，原第1、2行相加作为第三行，可得系统化后的生成矩阵为：34常用信道编码方法—线性分组码3.系统形式的生成矩阵为：故校验矩阵为：

，所以r不是码字。35常用信道编码方法—线性分组码4.由系统形式的生成矩阵可得，码字的各个码元与信息码元的关系为：36常用信道编码方法—线性分组码故电原理图为：37常用信道编码方法—线性分组码

38常用信道编码方法—线性分组码

39常用信道编码方法—线性分组码

线性分组码的译码：

1.求解差错图案E

S=RHT=EHT也就是说：伴随式S只和差错图案有关。如果得到接收矢量R后，由S=RHT计算出伴随式S，再由S=EHT计算得到差错图案E，则可以得到译码结果。但是，差错图案E=（en-1，en-2，…，e1，e0），共有n个变量；而RHT=EHT是矢量方程，共有n-k个方程（R是1×n的矢量，是n×（n-k）的矩阵）。40常用信道编码方法—线性分组码

线性分组码的译码：

1.求解差错图案En个未知数，n-k个方程，未知数个数>方程个数。

差错图案E是二元域上，每一个元素为0（对应码元没有差错）或1（对应码元发生了差错）。少1个方程，则有2组解（多出的未知数可以为0或1）；少2个方程，则有4组解；……少k个方程，则有2k组解。41常用信道编码方法—线性分组码

线性分组码的译码：

1.求解差错图案E

应该选择这2k组解中的哪组解？

前面说过：对二进制通信，最大似然译码等价于最小汉明距离译码。发码和收码的汉明距离最小，就意味着对应的差错图案的重量最轻。

因此，应该选2k组解中重量最轻的那个。42常用信道编码方法—线性分组码

43常用信道编码方法—线性分组码

44常用信道编码方法—线性分组码

线性分组码的译码：

2.标准阵列译码表

下图是一个标准阵列译码表：45常用信道编码方法—线性分组码

线性分组码的译码：

2.标准阵列译码表

该表共有2n-k行，

2k列。

每一行代表一种伴随式Si（伴随式S是1×（n-k）的向量，对二进制来说，共有2n-k种不同的伴随式），也就是一种差错图案Ei（每一个伴随式对应的2k个解中重量最轻的那个）；每一列对应一个发码Cj，共有2k个不同的发码（信息码组是1×k的向量）；表中共有2n-k×2k=2n个元素，代表2n个不同的收码。46常用信道编码方法—线性分组码

线性分组码的译码：

2.标准阵列译码表

实际构造标准阵列译码表时，并不需要对每一种伴随式解方程组得到对应的差错图案！2n-k种不同的伴随式，每种伴随式有2k个差错图案解，共有2n-k

×2k=2n个差错图案，刚好遍历了所有可能的差错图案。

每2k个差错图案解中，选一个重量最轻的，共选2n-k了种不同的差错图案；由于重量轻的优先被选择，并且差错图案是被遍历的，所以选择的一定是差错图案中重量最轻的2n-k个。

47常用信道编码方法—线性分组码

线性分组码的译码：

2.标准阵列译码表

可以先选择重量为0的差错图案（1种，全零差错图案E=（0，0，…，0））；

接下来选择重量为1的差错图案（n种，“1”分别位于n个不同的位置）；

……直到选够个不同的差错图案为止。48常用信道编码方法—线性分组码

线性分组码的译码：

2.标准阵列译码表每一行叫做一个“陪集”，每一个陪集的第一个元素叫做“陪集首”。陪集首就是各差错图案Ej。

每一列叫做一个“子集”，每一个子集的第一个元素叫做“子集头”。子集头就是各发送码字。49常用信道编码方法—线性分组码

线性分组码的译码：

例题：设(6,3)码的生成矩阵为其标准阵列译码表为：000000001101010011011110100110101011110101111000000001001100010010011111100111101010110100111001000010001111010001011100100100101001110111111010000100001001010111011010100010101111110001111100001000000101011011010110101110100011111101110000010000011101000011001110110110111011100101101000100000101101110011111110000110001011010101011000100001101100110010111111000111001010010100011001

其标准阵列如表6-3所示：表6-3(6,3)码的标准阵列译码表50常用信道编码方法—线性分组码

线性分组码的译码：若发送码字为C=[101011]，E=[010000]，则接收码字R=C+E=[111011]，查标准阵列表可知，它所在子集头为C=[101011]，因此译码正确。又如同一码字C=[101011]，若其差错图案为E=[001100]，接收码字R=C+E=[100111]，查表可得此收码R对应的C=[100110]，译码出现错误。为什么？51常用信道编码方法—线性分组码

线性分组码的译码：回顾一下上述构造标准阵列译码表的过程：第1行选的是全0差错图案；第2行到第7行选的是6个（n=6）重量为1的差错图案；由于，故需要8行，目前已有7行，还差一行，要选用1个重量为2的差错图案。重量为2的伴随式有种。

应该选哪一个？这15种差错图案，重量均为2，所以概率相同，只能随便选一个。这就造成了不同的选法，得到不同的标准阵列译码表，因此有时会得到不同的译码结果。上述译码错误，就是这个原因造成的。52常用信道编码方法—线性分组码

线性分组码的性质：定理6.1：线性分组码的最小码距等于码集中非零码字的最小重量：定理6.2：任何最小码距为的线性分组码，其检错能力为:

纠错能力为53常用信道编码方法—线性分组码

线性分组码的性质：

定理6.3：（n，k)线性分组码最小码距等于

的必要条件是：校验矩阵中有

列线性无关。

定理6.4：（n，k）线性分组码的最小码距必定小于等于（n-k+1），即：54常用信道编码方法—线性分组码

线性分组码之循环码：

线性分组码用生成矩阵来表示，只要给定生成矩阵，线性分组码的编码方式就被确定下来。但用矩阵形式来表示，书写和运算都多有不便。有没有一种办法解决？55常用信道编码方法—线性分组码

循环码空间：1.矢量的多项式表示：

码矢量C＝[cn-1cn-2

…c1c0]可用多项式C(x)=cn-1xn-1+cn-2xn-2

+…+c1x+c0来表示，

C(x)称为码多项式。2.循环码空间：一个(n,k)线性分组码集C，若它的任意一个码字每一循环移位仍是码集C的一个码字，则C是一个循环码。如果C＝[cn-1cn-2

…c1c0]是循环码的一个码字，那么对C的元素循环移一位得到的C’＝[cn-2

…c1c0cn-1]，也是循环码的一个码字。56常用信道编码方法—线性分组码

循环码空间：3.循环移位的多项式运算表示：

对码矢量C＝[cn-1cn-2

…c1c0]循环左移一位得到新的码矢量C’＝[cn-2

…c1c0cn-1]，可用多项式运算C’(x)=xC(x)mod(xn+1)来表示，

其中mod为除余运算。57常用信道编码方法—线性分组码

循环码空间：例：三维空间n=3，一组正交基分别为i、j、k，用数组表示分别为：i=（1，0，0）、j=（0，1，0）、k=（0，0，1；用多项式表示分别为：，和i循环左移一位，则

ximod(x3+1)=

xx2

mod(x3+1)=

x3

mod(x3+1)=1=k即：i循环左移一位得到k;同样地，

k循环左移一位得到j，

j循环左移一位得到i。58常用信道编码方法—线性分组码

循环码的生成多项式：

生成矩阵的每一行，是一个基底矢量，基底矢量也是码矢量，也满足循环移位性质。只要给定一个基底矢量的码多项式，经循环移位，就可以得到所有k个基底矢量的码多项式，从而确定生成矩阵。这样的基底多项式，叫做生成多项式。定理：(n,k)循环码中，一定存在一个g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1的(n-k)次首一码多项式（即(n-k)次项的系数为1），使得所有的码多项式都是g(x)的倍式，即c(x)=m(x)g(x)

，且g(x)一定是(xn+1)的因子。59常用信道编码方法—线性分组码

循环码的生成多项式：如果生成多项式为

，再经k-1次循环移位，就可得到k个码多项式：，，…，

。写成矩阵形式，就可得到多项式形式的生成矩阵：60常用信道编码方法—线性分组码

循环码的生成多项式：将给定的一个信息码组写成信息多项式：则可得码多项式：61常用信道编码方法—线性分组码

循环码的生成多项式：

例：设二进制(7,4)循环码的生成多项式为，求其生成矩阵G及生成的码字。解：即：62常用信道编码方法—线性分组码

循环码的生成多项式：由此生成矩阵G生成的(7,4)循环码的码字如表所示：消息码字消息码字00000000000100010110000001000101110001101001100100010110101010011100011001110110111000101010001011001100111010001010100111110111111110110011101011101100010011101100011111110100163常用信道编码方法—线性分组码

循环码的生成多项式：也可用信息多项式方法得到码字，例如，对于信息码组“1101”，其对应的信息多项式为：故码多项式为：可得码字为（1111111）。64常用信道编码方法—线性分组码

循环码的校验多项式：由于生成多项式g(x)是多项式xn+1的因子，故：xn+1＝g(x)h(x)其中，h(x)叫做该循环码的一致校验多项式，其阶次为k。h(x)的校验作用表现在：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码字与h(x)的乘积必不为0：C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)循环码是一种特殊的线性分组码，故线性分组码的译码方法也完全适用于循环码。65常用信道编码方法—卷积码卷积码的产生分组码以孤立码块为单位编译码信息流割裂为孤立块后丧失了分组间的相关信息分组码长n越大越好，但译码运算量随n指数上升问题

如何在不增加码长n，充分利用各个码字之间的相关性，等价于增加了码长，从而提高系统性能，但译码复杂度并无太多增加？卷积码的编码将信息序列分隔成长度k的一个个分组某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的L个分组。称L＋1为约束长度最重要的三个参数(n,k,L)(n,k,L)卷积编码示意卷积码的编码也可以将卷积编码器画成下图所示的一般结构。图中每一列是一个信息码组，最左列是当前信息码组；所有信息码组（L+1个）一起进入线性组合器，组合得到当前码字的各个码元。卷积编码器的一般结构卷积编码器的一般结构输出码元与信息码元的关系可写为：其中，表示第l个信息码组的第p个信息码元对输出码字的第j个码元的贡献。对二进制，，表示第l个信息码组的第p个信息码元对输出码字的第j个码元有贡献；则表示第l个信息码组的第p个信息码元对输出码字的第j个码元没有贡献。卷积编码器的转移函数矩阵一个信息码组的各个码元，对码字各个码元的贡献，可以用一个k×n的矩阵来表示其中，这实际上就是线性分组码的生成矩阵。由于（n,k,L）卷积码有L+1个信息码组参与线性组合，因此会有L+1个k×n的矩阵。或者说，（

n,k,L）卷积码的生成矩阵是一个k×n×(L+1)的三维矩阵。可以把三维生成矩阵的第三维压缩在一起，变成一个二维矩阵，以便书写。该二维矩阵的每一个元素，实际上是第三维的L+1个元素的叠加。为了能区分出来，用多项式表示：卷积编码器的转移函数矩阵

其中，Dl对应项的系数，即为第三维的第l个元素。于是可以写成：该矩阵叫做卷积码的转移函数矩阵。例6-3某二元（3,1,2）卷积码的转移函数转移函数矩阵为G(D)=(1,1+D,1+D+D2)，试画出其编码器电原理图。该卷积码信息缓存矩阵为1×3，三维矩阵中的平面数目（L+1）为3，根据转移函数矩阵=（1,1+D,1+D+D2）可分解出三个平面（分别对应缓存矩阵的三列）对应的二维矩阵为：G0=(1,1,1),G1=(0,1,1)，G2=(0,0,1)卷积编码器的状态流图

卷积编码器除了可用转移函数矩阵表示，还可用状态流图来表示。

卷积编码器输出的某一码字，除了和当前时间单元的信息码组有关，还和当前时间单元以前的信息有关。可以把当前时刻之前L个信息码组，作为当前时刻所处的状态。

卷积编码器当前的输出码字，由当前时间单元的信息码组和当前时间单元以前的L组信息码组决定，即：卷积编码器的状态流图

如果把当前单元之前的L组信息码元作为当前的状态，即：则：

并且，随着当前时间单元信息码组的出现，下一时间单元的状态会随之发生变化：卷积编码器的状态流图

于是，随着信息码组的不断出现，状态之间相互转移，并且随着状态转移而产生码字序列。我们可以用状态流图来表示。卷积编码器的状态流图例6-4：例6-3中的（3，1，2）卷积编码器，试画出其状态流图。如果输入信息码组序列为10110…，给出输出码字序列。解：由于（3，1，2）卷积编码器的L=2，故当前时间单元的状态由前面两个信息码组决定。每个信息码组只有1比特，所以共有四种不同的状态，如表所示：状态S000S101S210S311卷积编码器的状态流图

在每一种状态下，随着当前时间单元信息码组mi（mi=0或1）的到来，线性组合器会输出相应的码字序列，如表所示：输入

状态S0000111S1001110S2011100S3010101卷积编码器的状态流图

而且，由于新的信息码组到来，使得状态发生了变化，如表所示：输入

状态S0S0S2S1S0S2S2S1S3S3S1S3卷积编码器的状态流图0/000

S01/1110/0011/110

S2

S10/0111/1000/010

S31/101

图6-7(3,1,2)卷积码状态流图将其画成状态流图，如图所示：假如输入信息序列 是10110…，则

卷积编码器的网格图随着信息码组序列的输入，状态流图是在状态转移图上循环往复，不能清楚地表明编码过程。网格图可以清楚地表明整个编码过程。可以看成是状态流图随着信息码组序列输入过程的时间展开。例6-4的网格图如下图所示：卷积编码器的网格图输入信息序列是10110…，输出码字是111，011，110，100，010…第一部分：网格图 第二部分：编码轨迹（路径）图卷积码的译码对于线性分组码，由于码字之间没有关系，所以每个码字可以单独译码，如果采用最大似然译码准则，对于二进制编码来说，就是最小汉明距离译码：对一个收码R，在所有许用码字中，选择一个和收码汉明距离最小的，作为译码输出。卷积码的译码对于卷积码来说，由于码字之间是有相关性的，前一个码字的输出，还同时决定了下一个状态，而下一个码字的输出，是和状态有关的。因此，对一个时刻的收码R，译成和其汉明距离最小的许用码字，从码字序列的整体来看，就不一定是最好的。卷积码的译码例6-5：例6-3中的（3，1，2）卷积码，假定目前处于S0状态，连续三个收码分别为010、011，101。如果按照线性分组码的最大似然译码，每个码字独立译码，则译码过程为：

输出码字为000（与收码汉明距离为1）、111（与收码汉明距离为1）和011（与收码汉明距离为2）。如果把序列作为整体，则译码序列与收码序列汉明距离为4。卷积码的译码实际上，由于每次从某个状态出发，可以有两条路径，当收到3个收码以后，可以有23=8条路径，如下图所示：卷积码的译码相应地，有8种译码输出序列：①000、000、000，译码序列与收码序列汉明距离为5；②000、000、111，译码序列与收码序列汉明距离为4；③000、111、011，译码序列与收码序列汉明距离为4；④000、111、100，译码序列与收码序列汉明距离为3；⑤111、011、001，译码序列与收码序列汉明距离为3；⑥111、011、110，译码序列与收码序列汉明距离为4；⑦111、100、010，译码序列与收码序列汉明距离为8；⑧111、100、101，译码序列与收码序列汉明距离为5。卷积码的译码可以看出：序列④和序列⑤具有最小的序列汉明距离（汉明距离为3），按照最大似然规则，应该译为序列④（或序列⑤，两者具有相同的差错概率）；按照线性分组码的单独译码算法得到的结果，实际上是这里的序列③，序列汉明距离为4，显然不是最佳的。卷积码的译码例6-5说明，对于卷积码，由于码字之间是有关系的，因此，即使译码时某条译码路径当时看来是最好的，但也有可能该路径是一个错误路径，导致沿着该路径输出错误的译码码字序列，后续码字的译码将会出现较多比特的错误。卷积码的译码由此看来，卷积码的译码过程中，似乎每一条可能路径都不能随便舍弃掉，因为不到译码结束，每一条允许路径都是可能的译码路径。但是，如果在译码结束前保留每一条允许译码路径的话，将导致译码路径数指数级增加，因为允许路径数为2M，M为收码序列中收码的个数。并且由于只有译码结束的时候，才可以输出最佳的译码结果，使得译码时延很大。卷积码的译码1967年，维特比(Viterbi)提出了一种用于卷积码的最大似然译码方法。它对（n，k，L）卷积码中约束长度L较小的卷积码的译码很容易实现，因此被广泛地应用于现代通信中，称为维特比算法或维特比译码。卷积码的译码-维特比译码维特比译码方法①

路径舍弃

实际上，译码过程并不需要记忆所有的允许路径。在译码过程中，有些路径会随着译码过程的进行不断被舍弃。

设有两条（或多条）不同路径在当前时刻均到达状态Si。

此后的译码，只和当前时刻的状态有关，而与如何到达本状态的路径无关；因此，根据最大似然原则，到达本状态的多条路径中，与收码序列汉明距离最小的那条路径，是最佳的，应该保留，称为幸存路径；而剩余其他的路径，就可以舍弃掉。卷积码的译码-维特比译码维特比译码方法①

路径舍弃

若有T种不同的状态，由于到达每一种状态的幸存路径只有一个，所以每个时刻只会保留T条幸存路径。卷积码的译码-维特比译码例6-6：例6-3中的（3，1，2）卷积码，假定起始时刻处于S0状态，连续三个收码分别为110、111，011，用PMl（i）表示第i个状态在第l个时刻的路径度量（所谓路径度量，即该路径上译码输出序列与收码序列的汉明距离）。分析各时刻可能的译码路径、该路径的路径度量及幸存路径（若到达某一状态多条路径的路径度量相同，则可取其中的任一条做为幸存路径，因为它们具有相同的差错概率）。卷积码的译码-维特比译码解：i）起始时刻（l=0）起始时刻处于S0状态，ii）第1个时刻（l=1）此时各状态对应的