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

本章内容□一些基本概念■信道编码定理□

常用信道编码方法—线性分组码、卷积码基本概念□一些基本概念一些概念□差错和差错图案：若包含个码元的接心女码字R=(含：个码元的发送码字C=(

箱发

牛了差

错

；差错图案E

是用来表示接吸码字和发送码字是如何不同的：E=R-C若发送码字和接收码字都是二进制的，则愿=R

C其

中。

十

代

表

模

2

和

：

荒

错

图

率E=(

(

e

6

g

)

。

①

表

示该码元没有发牛差错。二表示该码元发生了差错。差错图架各元素中1的个数。叫傲该差僭图窦拘重量。一些概念■差错控制编码及分类差错控制编码：通过增加冗余码元，提高通信的可靠性。如：k个码元的信息码组m=(m,1,c)

四(n>”k),,

m该,n

个)码,元

元，

冗余。分类：√

从功能角度：检错码(可以检测出发生了差错)、纠错码(可以

纠正一定数量的差错)对信息序列的处理方法：分组码(相关性只分布于组内)、卷积

码(组间也有相关性)√码元与原始信息位的关系：线性码(所有码元由信息码元线性组合得到)、非线性码(所有码元由信息码元非线性组合得到)差错类型：纠随机差错码、纠突发差错码等其余k

个是的码字C=(,独立的n

个码是到只有个组合得一些概念■差错控制系统的分类前向纠错

(FEC)

:

发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错(信息传递只有前向的：从发送端到接收

端

)√

反馈重发

(ARQ):

收端通过检测接收码是否符合编码规律来判断，

如判定码组有错，则通过反向信道通知发端重发该码(须有反馈信

道：从接收端到发送端的信息传递)√

混合纠错

(HEC):

前向纠错和反馈重发的结合，发端发送的码兼

有检错和纠错两种能力i,j,k一些概念■

译码规则√

译码：就是接收端收到接收符号集Y={b,b₂,…,bm}中的

某

一

符号

b,,据此来判断(或者说猜测。因为信道是有扰信道，输入符号和

输出符号不是一一对应的)发送端发送的是发送符号集

X={a,a₂,…,a.}

中的哪个符号ai,

即设计一个规则F(b)=a。√最大后验概率译码(MAP

)

:

设接收端收到符号b,的条件下，发送

端发送符号a;

的概率为P(a,/b,),

如果设计的译码规则为Fb)=a,

那

么,译码正确的概率就是P(a/b₃),而译码错误的概率则为1-P(a,/b,)。如

果想使错误概率最小，则需要P(a/b,)最大，即：a,

=

maxP(a,/bP(a./b)

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

最大似然译码

(ML):

a.=max

P(b./a)

称为最大似然译码，称为似然概率。i,j,k一些概念■

最小汉明距离译码：对于二进制对称信道

(BSC)

来说，似然概率于一般

p<<1,1-p≈1

,所以d越小，似然函数P(r/c)就越大，因此，对C

信道，最大似然译码就等价于最小汉明距离译码。若发送码字矢量为C,

接受码字矢量为R,

其汉明距离(接受码字和发送码字按比特比较，不同的比特个数)为d,此时似然函数是一些概念■

矢量空间√正交完备基：n维空间由n个相互正交的基底张成，n

维空间的任何一

个矢量，可以由这n个基底线性组合而得到。这组基底称为正交完备

基。例如：三维空间可由三个相互正交的单位矢量

i,j,k

张成。√矢量的表示：

n维空间的一个矢量，可以由n个元素组成的数组表示，

是这个矢量的端点坐标。这个数组也叫做n重。如√

子空间：

n维空间的一个人维子空间，可以用一个k维n重来表示：

C=c),n

个元素

中

的k

个

是独

立

的

，

而

另

外n-k

个

元素可由k个元素线性组合得到。例如：三维空间中令z=x+y(即：3重数

组中的2个：x、y是独立的，而由x、y组合而成),则可以得到一个2维子空间。√

矢量空间中点的个数：1.实数空间：有无穷多个点；2.

整数空间：对q进制，n维空间的每个坐标轴上有q

个不同取值(0,1,…,q-1),故共有q"个点。i,j,k8一些概念■

码

空

间

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

(k

维n重

)

。从矢量空间的角度来看：>一个码字可以看成矢量空间(整数空间)的一个点；>码空间可以看成n维空间的一个人维子空间(码字的n个码元，只有k个是独立的);>

码空间

(k

维空间)共有q小个点，特别地，对二进制，共有2个点；i,j,k>n维空间共有q"个点；将一个信息码组

(k

个码元)编码成一个码字

独立的),

可以看成是将一个k

维码空间映射n维空间共有q"个点，选择了其中的q1个称为许用点；其余的q"-q

个点称为禁用点：码字通过信道传输，

如果发生了某些码元错识错到一个禁用点，就可以检测到错误(检错，以

纠错)禁用

越多

(n-k越

大

)

,检错纠错能力越强一些概念信道编码定理■信道编码定理信道编码定理□如果不考虑速率，当然可以达到任意高的可靠性。这没有

意义。□那么,就应该考虑可靠性和速率之间的关系。香农把问题定义为：在可以使解码错误概率渐近于零的条件下，信道的最高传

输速率是多少?□这是香农信道编码定理要解决的问题。信道编码定理■

定

理

：若一个离散无记忆信道的信道容量为C,只要平均信息

率R

小于信道容量C,

总存在一种信道编码方法和相应的译

码规则，使译码错误概率P

任意小。□

证

明

思

路

：采用随机编码，如果随机编码的平均译码错误概率可以趋近于零，则一定有一部分“好码”,其错误概率趋近于零，Gaillager在1965年证明，平均译码错误概率的上界为：信道编码定理其中，N为码长，R

为信息速率，E(R)

称为可靠性函数，

E(R)~R关系曲线如下图所示：曲线表明：只要信息速率R<信道容量C,

可靠性函数E(R)>0,

因此，只要码长N

足够大，总可以使平均译码错误

概率趋近于零。信道编码定理下图为不同信道容量时的E(R)~R关系曲线。可以看出：1.

对同样的信息码率R,

信道容量C

越大，可靠性函数E(R)的值越大，可靠性越高。2.对同样的信道容量C,

信息速率R

越小，可靠性函数E(R)的值越大，可靠性越高。E(R)▲CC₁<C₂

R0R₁<R₂信道编码定理因此，为提高可靠性，降低译码错误概率，可以：1.

增大信道容量C。

根据香农公C.=Wlog(1+SNR),要增大信

道容量，可以：增加带宽；增加信号功率。2.

减小速率R。3.

增大码长N。16信道编码定理信源信道联合编码定理：信源编码定理说，只要信息率R>

信源熵H(X),

就可以实现

无失真编码；信道编码定理说，只要信息率R

<信道容量C,

就可以实现无

差错泽码。将两者结合，就可以得到信源信道联合编码定理若离散无记忆信源熵为H(X),

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

。17常用信道编码方法□

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

线性分组码如前所述，线性分组码的编码，就是从k维k重信息空间

映射到一个n维空间的k维子空间(码空间)。线性分组码的编码：n维空间由n个正交基底矢量8n-1,8n-2…,81,80张成，n

维空

间的k维子空间可以由这n个基底矢量中的k

个张成。不失

一般性，可以选Bk-1,8k-2)…,g1,80

张成k维子空间。于

是

，k维k重信息空间的一个信息码组m=(m.1,m₂2,…m,mo)

到n维空间的k维子空间的映射，就是这k个基底矢量的线性组合：常用信道编码方法—线性分组码C=mk-1gk-1+mk-2gk-2+…+m₁g₁+m₀g₀写成矢量形式，就是：上式可以理解成：由信息码组的k个码元，组合得到码

字的r个码元，其中k个是独立的，n-k

个是冗余。可以看出，给定了矩阵G,

一个信息码组m,

就可以映

射为一个码字C。C=mG常用信道编码方法—线性分组码1.生成矩阵：所以矩阵G

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

组成的矩阵叫做校验矩阵：常用信道编码方法—线性分组码2.校验矩阵：由于码空间的基底和校验空间的基底矢量是相互正交的，

故码空间和校验空间相互正交：GHT=0cHT=0上式可用于检验一个接收矢量R

是不是码字。如果

RH¹=0

,则R

一定不是码字。这也是H

被叫做校验矩阵的原因

。常用信道编码方法—线性分组码3.系统形式的生成矩阵：如果码字C=(m1,2,m2,3,……,m0,cn-k-1,c1,,c)即：码字的前k个码元就是信息码元，后n-k

个码元是由信息码元组合得到的冗余码元则：这样的码字叫做系统码。一般形式的生成矩阵C,用C=mC

得不到系统码。为此，需要对生成矩阵G

系统化。2

5常用信道编码方法—线性分组码4.生成矩阵的系统化：如果生成矩阵是如下形式：则可以得到系统码。可以通过对普通形式的生成矩阵G做行运算得到系统形

式的生成矩阵G26常用信道编码方法—线性分组码注意：系统化时对生成矩阵G只能做行运算!而不能做列运算。原

因

：生成矩阵的每一行，是n维矢量空间的一个基底矢量。行运算相当于对基底矢量的线性组合。这种运算并不会改变

其张成的矢量空间(码空间)。如果做列运算，则改变了基底矢量本身。常用信道编码方法—线性分组码对系统形式的生成矩阵：G=[I:P]容易证明，其对应的校验矩阵为：H=[-PInk]若为二进制，则：H=[PTIn₋k]28常用信道编码方法—线性分组码线性分组码的编码电路：用移位寄存器、加法器和拨档开关等电路元件可实现由

信息码元得到码字码元的编码过程，组成编码电原理图，可

参见下例。常用信道编码方法—线性分组码例题：

若一个(6,3)线性分组码的生成矩阵为：试：

①计算码集，列出信息码组与码字的映射关系；②将该码系统化，计算系统码码集，并列出映射关系；③计算系统码的校验矩阵H。若收码为r=[100110]

,检验它

是否为码字。④根据系统码生成矩阵，画出编码器电原理图。信

息码

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

由系统形式的生成矩阵可得，

码字的各个码元与信息码元

的

关系

为

：34常用信道编码方法—线性分组码故电原理图为：mo

m₁

m₂输出Co

C1

C2输入常用信道编码方法—线性分组码线性分组码的译码：为简单起见，以下讨论均对二进制而言。通信系统的发送端发送码字C,

接收端收到接收矢量R:R=C

E其中E为差错图案。如果译码端可以得到差错图案E,则可以译出发码C:C=R

出

E36常用信道编码方法—线性分组码线性分组码的译码：1.求解差错图案E收发两端是合作的，所以收端知道生成矩阵G和校验矩

阵

H。○定义伴随式S:S=RHIT由于CHIT=0,故

：S=RFIT=(C+E)HI=CHIT

EHT=EFI!常用信道编码方法—线性分组码线性分组码的译码：1.求解差错图案ES=RH!=EHI!也就是说：伴随式S只和差错图案有关。如果得到接收矢量R

后，由S=RHI计算出伴随式S,再

由S=EH计算得到差错图案E,

则可以得到译码结果。但是，差错图案

E=(e1,e2,……,e0),e₀),

个变量；而RH!=EHI!

是矢量方程，共有n-k个方程(R是1×n的矢量，

是n×(n-k)

的矩阵)。常用信道编码方法—线性分组码线性分组码的译码：1.求解差错图案En个未知数，n-k个方程，未知数个数>方程个数。差错图案E

是二元域上，每一个元素为0(对应码元没有差错)或1(对应码元发生了差错)。少1个方程，则有2组解(多出的未知数可以为0或1);少2个方程，则有4组解；少k个方程，则有2组解。常用信道编码方法—线性分组码线性分组码的译码：1.求解差错图案E应该选择这2k

解中的哪组解?前面说过：对二进制通信，最大似然译码等价于最小汉明距离译码。发码和收码的汉明距离最小，就意味着对应的差错图案的重量最轻。因此，应该选2组解中重量最轻的那个。常用信道编码方法—线性分组码线性分组码的译码：1.求解差错图案E一旦选定了差错图案，则可以得到发码，译码结束：C=R

E41常用信道编码方法—线性分组码线性分组码的译码：2.标准阵列译码表如果每一次译码，都要解一次方程组求出差错图案E,

则译码比较复杂。回顺一下求差错图察译码的过程：接收矢量R→

伴随式S→

解方程组求E→译码结果C

=R

E如果我们对所有可能的接收矢量R(共有2种》,都预

先做了上述译码过程，并将结果存到一个表果面，译码的时

候，只要根据控收矢量R

查表，就可以得到译码结果C,

则可以大大降低译码时的复杂度。常用信道编码方法—线性分组码线性分组码的译码：2.标准阵列译码表下图是一个标准阵列译码表：解线性表6-2标准阵列译码表E₀+C₀=0+0=0E+C=C1…E₀+C:=C…E

+C₄=C起E+C。=E…Ei+C。=;·E

+G

i…E+C…EC……………E+G

1…EsfC…E、+c1…

·……

·……***个方程组S→ES

E.EE2小常用信道编码方法—线性分组码线性分组码的译码：2.标准阵列译码表该表共有2-k行，2

列

。每一行代表一种伴随式S

(伴随式S是1×(n-k)的向量，对二进制来说，共有2-k种不同的伴随式),也就是一种差错

图案E,(每一个伴随式对应的2个解中重量最轻的那个);每一列对应一个发码C,

共有2个不同的发码(信息码组是1×k

的向量);表中共有2n-k×2=2个元素，代表2个不同的收码。常用信道编码方法—线性分组码线性分组码的译码：2.标准阵列译码表实际构造标准阵列译码表时，并不需要对每一种伴随式解方程组得到对应的差错图案!2n-k种不同的伴随式，每种伴随式有2个差错图案解，共有2-k×2=2

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

所以选择的一定是差错图案中重量最轻的2-k个。常用信道编码方法—线性分组码线性分组码的译码：2.标准阵列译码表可以先选择重量为0的差错图案(1种，全零差错图案E=(0,0,…,0));接下来选择重量为1的差错图案

(n

种，“1”分别位于n个不同的位置);直到选够个不同的差错图案为止。常用信道编码方法—线性分组码线性分组码的译码：2.标准阵列译码表每一行叫做一个“陪集”,每一个陪集的第一个元素叫做“陪集首”。陪集首就是各差错图案E。每一列叫做一个“子集”,每一个子集的第一个元素叫做“子集头”。子集头就是各发送码字。00000000110101001101111010011010101111010111100000000100110001001001111110011110101011010011100100001000111101000101110010010010100111111111010000100001001010111011010100010101111110001111100001000000101011011010110101110100011111101110000010000011101000011001110110110111011100101101000100000101101110011111110000110001011010101011000100001101100110010111111000111001010010100011001线性分组码的译码：例题

：设(6,3)码的生成矩阵为其标准阵列译码表为：常用信道编码方法—线性分组码常用信道编码方法—线性分组码线性分组码的译码：若发送码字为C=[101011],E=[010000],

则接收码字R=C+E=[111011],

查标准阵列表可知，它所在子集头为C=[101011],因此译码正确。又如同一码字C=[101011],若其差错图案为E=[001100],接收码字R=C+E=[100111],查表可得此收码R

对应的C=[100110],

译码出现错误。为什么?常用信道编码方法—线性分组码线性分组码的译码：回顾一下上述构造标准阵列译码表的过程：第1行选的是全0差错图案；第2行到第7行选的是6个(n=6)

重量为1的

差错图案；由于2-

k=2⁶-³=8

故需要8行，目前已有7行，还

差一行，要选用1个重量为2的差错图案。重量为2的伴随式有

应该选哪一个?这15种差错图案，重量均为2,所以概率相同，只能随便选一个。这就造成了不同的选法，

得到不同的标准阵列译码表，因此有时会得到不同的译码结果。上述译码错误，就是这个原因造成的。常用信道编码方法—线性分组码线性分组码的性质：定理6.1:

线性分组码的最小码距等于码集中非零码字的最小重量

：dmin=min{W(C)}

C;∈C

且

C;∉0定理6.2:任何最小码距为的线性分组码，其检错能力为：纠错能力为常用信道编码方法—线性分组码线性分组码的性质：定理6.3:

(n,

性分组码最小码距等于

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

dmin-1列线性无关。定理6.4:

线性分组码的最小码距必定小于等于(n-k+1),

常用信道编码方法—线性分组码线性分组码之循环码：线性分组码用生成矩阵来表示，只要给定生成矩阵，线性分组码的编码方式就被确定下来。但用矩阵形式来表示，

书写和运算都多有不便有没有一种办法解决?常用信道编码方法—线性分组码循环码空间：1.矢量的多项式表示码矢量C来表示，

C(x)称

为2.循环码空间：.一个(n,k)线性分组码集C,

若它的任意一个码字每一循环移位仍是码集C

的一个码字，则C

是一个循环码。·如果C

=c。C

..C₁C。是循环码的一个码字，那么对C

的元素循环移一位得到的C'=的一个码字。,也是循环码[C,n-2…C₁Coc,m₋1]常用信道编码方法—线性分组码循环码空间：3.循环移位的多项式运算表示：对码矢量C

LCn1Cm2…CiCI循环左移一位得到新的码矢量

C=[c2

,

可用多项式运算(x)=xCx)mod

(x+1来表示，

其中mod

除

余运算。常用信道编码方法—线性分组码循环码空间：例三维空间n=3,一组正交

1

、

用数分别为：i(1,0,0)、用多项式表示分别为i=1x²+0x+0=x²j=0x²+1x+0=xk=0x²+0x+1=1i循环左移一位，则ximod(x³+1)=xx-mod(x³+1)=即：循环左移一位得到k;同样地，k循环左移一位得到j,j循环左移一位得到i。常用信道编码方法—线性分组码循环码的生成多项式：生成矩阵的每一行，是一个基底矢量，基底矢量也是码矢量，也满足循环移位性质。只要给定一个基底矢量的码多

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

三x-K

十

g1x-K-1

十

.

.

十

8x-+g1X+1的(n-k)次首一码多项式(即(n-k)次项的系数为1),使得所有的码多项式都是g(x)的倍式

(x)

,

且g(x)一定是

(x"+1)的

因子

。常用信道编码方法—线性分组码循环码的生成多项式：如果生成多项式g(x)=8n-kx”-k+8n-k-1x”-k-1+…+8₁x+g。经k-1次循环移位，

就可得到k个码多项式：g(x),xg(x)xk-¹g(x)

。

写成矩阵形式，就可得到多项式形式的生成矩阵：常用信道编码方法—线性分组码循环码的生成多项式：将给定的一个m=(m-1,mk-2,…m,m₀)

写万式

：则可得码多项式：C(x)=m(x)g(x)59常用信道编码方法—线性分组码循环码的生成多项式：例：设二进制(7,4)循环码的生成多项式为

g(x)=x³+x+1求其生成矩阵G

及生成的码字。解

：消息码字消息码字000000000001000101100000010001011100011010011001000101101010100111000110011101101110001010100010110011001110100010101001111101111111101100111010111011000100111011000111111101001常用信道编码方法—线性分组码循环码的生成多项式：由此生成矩阵G

生成的(7,4)循环码的码字如表所示：常用信道编码方法—线性分组码循环码的生成多项式：也可用信息多项式方法得到码字，例如，对于信息码组

“1101”,其对应的信息多项式为：m(x)=x³+x²+1故码多C(x)=

m(x)g(x)=(x³+x²+1)*(x³+x+1)=x⁶+x⁵+x⁴++x³+x²+x+1可得码字为(1111111)常用信道编码方法—线性分组码循环码的校验多项式：由于生成多项式g(x)是多项式x+1的因子，故

：x¹+1=

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

问题如何在不增加码长n,充分利用各个码字之间的相关

性，等价于增加了码长，从而提高系统性能，但译码复

杂度并无太多增加?卷积码的编码□将信息序列分隔成长度k的一个个分组□某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的L个分组。■称L+1

为约柬长度■最重要的三个参数(n,k,L)m。m…mi-1m…m:1m₆²…m²…m“m;…m输入…………卷积编码器(线性组合器)…编码输出CCc…Cn-2C-1(n,k,L)卷积编码示意第i分组第i-1分

组

第i-2分

组

第i-L

分组卷积码的编码■也可以将卷积编码器画成下图所示的一般结构。1.

图中每一列是一个信息码组，最左列是当前信息码组；2、

所有信息码组

(L+1

个)一起进入线性组合器，组合得到

当前码字的各个码元。卷积编码器的一般结构卷积编码器的一般结构□输出码元与信息码元的关系可写为：其中，8

表示第1个信息码

个信息码元对输出码字的第j个码元的贡献。对二进

=1,表示第1个信息码组的第p个信息码元对输出码字的第j个码元有贡献：8m=0

则表示第1个信息码组的第p个信息码元对输出码字的第j个码元没有贡

献。卷积编码器的转移函数矩阵一个信息码组的各个码元，对码字各个码元的贡献，可以用一个k×n

的矩阵来表示其中，这实际上就是线性分组码的生成矩阵。由于(n,k,L

)

卷积码有L+1个信息码组参与线性组合，因此会有

L+1

个k×n的矩阵。或者说

，

n,k,L

卷积码的生成矩阵是一个k×n×(L+1)的三维矩阵。可以把三维生成矩阵的第三维压缩在一起，变成一个二维矩阵，以便书写。该二维矩阵的每一个元素，实际上是第三维的L+1

个元素的叠加。为了能区分出来，用多项式表示：卷积编码器的转移函数矩阵8,(D)=8其

中

，D对应项的系数，即为第三维的第该矩阵叫做卷积码的转移函数矩阵。例6-3某二元(3,1,2)卷积码的转移函数转移

函数矩阵为C(D)=(1,1+D,1+D+D²),试画出其编码器电原理图。该卷积码信息缓存矩阵为1×3,三维矩阵中

的平面数目

(L+1)

为3,根据转移函数矩阵=

(1,1+D,1+D+D²)可分解出三个平面(分别

对应缓存矩阵的三列)对应的二维矩阵为：G⁰=(1,1,1),G¹=(0,1,1),G²=(0,0,1)信号入m

m

。

m¹

m;²输出CC₂卷积编码器的状态流图卷积编码器除了可用转移函数矩阵表示，还可用状态流图来表示。卷积编码器输出的某一码字，除了和当前时间单元的信息码组有关，还和当前时间单元以前的信息有关。可以把当前时刻之前工个信息码组，作为当前时刻所处的状态。卷积编码器当前的输出码字，由当前时间单元的信息码组和当前时间单元以前的L

组信息码组决定，即：C¹=f(m²,m²-1,…,m¹-L)卷积编码器的状态流图如果把当前单元之前的L组信息码元作为当前的状态，并且，随着当前时间单元信息码组的出现，下一时间单元的状态会随之发生变化：Si=h(m²-¹,…,m²-L)C¹=f(m³,S)即

：则

：卷积编码器的状态流图于是，随着信息码组的不断出现，状态之间相互转移，

并且随着状态转移而产生码字序列。我们可以用状态流图来

表

示

。卷积编码器的状态流图例6-4:例6-3中的(3,1,2)卷积编码器，试画出其状态流图。如果输入信息码组序列为10110

…,给出输出码字序列。解：由于(3,1,2)卷积编码器的L=2,

故当前时间单元的状态由前面两个信息码组决定。每个信息码组只有1比特，

所以共有四种不同的状态，如表所示：状态m⁻¹m⁻

²S₀00S₁01S₂10S₃11卷积编码器的状态流图在每一种状态下，随着当前时间单元信息码组m(m²=0或1)的到来，线性组合器会输出相应的码字序列，如

表

所示

：输

入状态m=0m'=1000111S₁001110S₂011100S₃010101卷积编码器的状态流图而且，由于新的信息码组到来，使得状态发生了变化，如表所示

：输

入

状态m%=0m。=1S₀S₂S₀S₂S₁S₃S₁S₃卷积编码器的状态流图■将其画成状态流图，如图所示：□假如输入信息序列是10110,则

图6-7(3.1,2)卷积码状态流图卷积编码器的网格图■随着信息码组序列的输入，

状态流图是在状态转移图上循

环往复，不能清楚地表明编码过程。■网格图可以清楚地表明整个编码过程。可以看成是状态流图随着信息码组序列输入过程的时间展开。■

例6-4的网格图如下图所示：卷积编码器的网格图输入信息序列是10110

…

,输出码字是111,011,110,100,010….第二部分：编码轨迹(路径)图第二部分：编码轨迹(路径)图0/0001/1100/011S₂(10)0/010

1/100S₃(11)1/101

t=0

T1/1002T

3T

4T第

一部分：网格图第一部分：网格图1/1100/010/0/000

0/0000/0011/111S₀(00)1/111S₁(01)0/0011/1100/011卷积码的译码■对于线性分组码，由于码字之间没有关系，所以每个码字可以单独译码，如果采用最大似然译码准则，对于二进制

编码来说，就是最小汉明距离译码：对一个收码R,

在所有许用码字中，选择一个和收码汉明距离最小的，作为译码输出

。卷积码的译码■对于卷积码来说，由于码字之间是有相关性的，前一个码字的输出，还同时决定了下一个状态，而下一个码字的输出，是和状态有关的。因此，对一个时刻的收码R,

译成和其汉明距离最小的许用码字，从码字序列的整体来看，就不一定是最好的。卷积码的译码例6-5:例6-3中的(3,1,2)卷积码，假定目前处于S0状态,连续三个收码分别为010、011,101。如果按照线性分组码的最大似然译码，每个码字独立译码，则译码过程为：输出码字为000(与收码汉明距离为1)、111(与收码汉明距离为1)和011(与收码汉明距离为2)。如果把序列作为整体，则译码序列与收码序列汉明距离为4。卷积码的译码实际上，由于每次从某个状态出发，可以有两条路径，当收到3个收码以后，可以有2³=8条路径，

如下图所示：000↵100

S₃So↵S₂↵100

010→101↵

S₃000

Sn↵111↵→011山000卷积码的译码相应地，有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说明，对于卷积码，由于码字之间是有关系的，因此，即使译码时某条译码路径当时看来是最好的，但也有可能该路径是一个错误路径，导致沿着该路径输出错误的译码码字序列，后续码字的译码将会出现较多比特的错误。卷积码的译码■由此看来，

卷积码的译码过程中，似乎每一条可能路径都不能随便舍弃掉，因为不到译码结束，每一条允许路径都是可能的译码路径。■但是，如果在译码结束前保留每一条允许译码路径的话，将导致译码路径数指数级增加，因为允许路径数为2,M为收码序列中收码的个数。并且由于只有译码结束的时候,才可以输出最佳的译码结果，使得译码时延很大。卷积码的译码■

1967年，维特比(Viterbi)提出了一种用于卷积码的最大似然译码方法。它对(n,k,L)

卷积码中约束长度L较小的卷积码的译码很容易实现，因此被广泛地应用于现代通信中

,称为维特比算法或维特比译码。卷积码的译码-维特比译码■

维特比译码方法①路径舍弃实际上，译码过程并不需要记忆所有的允许路径。在译码过程中，有些路径会随着译码过程的进行不断被舍弃。设有两条(或多条)不同路径在当前时刻均到达状态S。此后的译码，只和当前时刻的状态有关，而与如何到达本状态的路径无关；因此，根据最大似然原则，到达本状态的多条路径中，与收码序列汉明距离最小的那条路径，是最佳的，应该保留,称为幸存路径；而剩余其他的路径，就可以舍弃掉。卷积码的译码-维特比译码■

维特比译码方法①路径舍弃若有T

种不同的状态，由于到达每一种状态的幸存路径只有一个，所以每个时刻只会保留T

条幸存路径。卷积码的译码-维特比译码例6-6:例6-3中的(3,1,2)卷积码，假定起始时刻处于S₀

状态，连续三个收码分别为110、111,011,用PM(i)表示第i个状态在第1个时刻的路径度量(所谓路径度量，即该路径上译码输出序列与收码序列的汉明距离)。分析各时刻可能的译码路径、该路径的路径度量及幸存路径(若到达某

一状态多条路径的路径度量相同，则可取其中的任一条做为幸存路径，因为它们具有相同的差错概率)。卷积码的译码-维特比译码解：i)

起始时刻(=0)起始时刻处于SO

状

PM⁰(O)=0PM°(1)=∞PM°(2)=∞PM⁰(3)=00ii)

第1个时刻(此时各状态对应的PM'(i)如下图所示：So

…PM(0)=2↵S₁

·PM°(1)=0↵S₂

·PM°(2)=1↵SoPM°(0)=QS1

·PM°(1)=∞S₂

·PM°(2)=S₃

·S₃·PM°(3)=0

PM°(3)=00↵R=110卷积码的译码-维特比译码iii)

第2个时刻

(l=2)此时各状态对应的PM!(i)

如下图所示：R=110

So

R=110PM°(0)=2PM°(0)=5↵S₁

·

S₁PM°(1)=

PM⁰(1)=2↵S₂

S₂PM°(2)=1

PM⁰(2)=2↵S₃

·

S₃↵PM⁰(3)=のPM⁰(3)=3↵SoPM°(0)=0

S₁

·PM⁰(1)=の

S₂

·PM°(2)=の

S₃

·PM°(3)=の卷积码的译码-维特比译码iv)

第3个时刻(l=3)此时各状态对应的PM(i)

如下图所示：So

R=110

So

R=111So

R=011PM°0)=0

PM¹(O)=2

PM²(0)=5

PM³(0)=3↵S₁

·S₁

·S₁