《信息论与编码》 课件 杨守义 第5-7章 信源编码-网络信息论初步

信息论与编码2第5章信源编码目的：提高通信系统的有效性，即通过编码，用尽可能短的编码序列符号来表示原信源序列。基本思想是：1.尽可能去除原消息序列中符号之间的相关性；2.尽可能使编码后各符号出现的概率相等。3第5章信源编码主要解决两个方面的问题：1.“信源编码是用尽可能短的编码序列符号来表示原信源序列”，这个“短”，有没有极限？如果有，该极限是多少？2.用什么方法达到或者接近该极限？4非分组码和分组码将长消息序列按顺序分成若干个符号一组，对每一组独立进行编码，称为分组码；否则称为非分组码。定长码和变长码若编码后的码字长度都相同，则称为定长码；否则称为变长码。5.1信源编码的有关概念5.1.1几个概念5奇异码和非奇异码若编码前的信源组和编码后的码字是一一对应的，则称为非奇异码；否则称为奇异码。非唯一可译码和唯一可译码如果任意有限长的码元序列都只能被唯一地分割成一个个的码字，则称为唯一可译码；否则称为非唯一可译码。5.1信源编码的有关概念6非即时码和即时码在接收端接收码元序列的过程中，如果接收到的码元序列已经组成了一个码字，但接收端并不能立即判断出，还要等下一个码字开始接收的时候才能判断出前者已经是一个完整码字，从而开始译码，则称为非即时码；反之则称为即时码。5.1信源编码的有关概念75.1信源编码的有关概念5-1编码的分类85.1信源编码的有关概念信源符号ai符号出现的概率p(ai)码1码2码3码4码5a11/2000011a21/40111101001a31/8100000100001a41/811110110000001例5-1表5-1中的分组码1、码2、码3、码4和码5，从上述的4个方面分别判断属于什么类型的码。表5-1码的不同属性95.1.2克劳福特不等式唯一可译码存在的充分和必要条件各码字的长度Ki应符合克劳夫特不等式：

其中m是进制，n是信源可能取值的符号数。10例：设对符号集{ai,i=1,2,3,4}进行二进制编码；(1)对应的码长分别为K1＝1,K2＝2,K3＝2,K4＝3，试判断是否存在这样的唯一可译码；(2)

若K1=1,

K2=2,

K3=3,

K4=3又如何？答：(1)由克劳福特定理可得：因此不存在满足这种码长的唯一可译码。

11(2)由克劳福特定理可得：因此满足这种码长的唯一可译码是存在的,例如{0，10，110，111}。

克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。例如，{0,10,010,111}12无失真信源编码定理定长信源编码定理变长信源编码定理限失真信源编码定理

5.2信源编码定理135.2.1无失真信源编码（香农第一定理）X＝(X1X2…Xi…XL)Xi

{a1,a2,…,ai,…,an}

nL种信源编码器Yk

{b1,b2,…,bj,…,bm}

M=mKL种

KL

logm用Y表示L长的信源序列X，则送出一个信源符号所需要的信息率平均为

编码目的：使最小。

14无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码?

无记忆平稳信源平均符号熵为HL(X)，对任意

，只要

则当L足够大时，必可使译码差错概率小于δ；即可实现几乎无失真编码；

反之，当时，译码差错一定是有限值，而L足够大时，译码几乎必定出错。151.无失真定长信源编码定理：码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。反之，当时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。当时，则为临界状态，可能无失真，也可能有失真。16说明：L,,

,δ三者之间有什么关系？对于给定的

和δ，多大的L算足够大？17问题：式中

为信源序列的自信息方差，

为一正数。当

和

2均为定值时，只要L足够大，Pe可以小于任一正数

。即，如果给定差错概率上界δ，则

越小，要求的编码长度L就越大。L越大，编码器越复杂，且时延越大，在有时延要求的场合，往往难以满足实时性要求。增加

，可以减小对编码长度L的要求，但以牺牲编码效率为代价：18讨论：19例题5-3：设离散无记忆信源概率空间为若要求编码效率为90%，译码差错概率δ≤10-6试求所需要的编码序列长度L。20例题5-3：自信息方差为：若要求编码效率η=90%：若要求编码效率δ≤10-6：当L有限时，要做到高编码效率、低错误率，对于定长编码来说是不可能做到的。对例5-3中的信源，有8种不同的信源符号取值（a1~a8），如果用二进制序列来表示的话，每个符号需要3

bit（3位二进制数可以表示8中不同的符号）。但由于不是等概率的，所以其熵H(X)=2.55

bit，按照无失真定长信源编码定理，其极限编码长度是2.55bit，而，也就是说，只能表示5.856种不同的符号，其余的符号怎么办？实际上，由于a1~a8中部分符号的概率较小，如果序列长度L足够大，则总有某种序列出现的概率足够小，对这些概率足够小的序列，如果不设计对应的编码码字，造成的错误概率也非常小。21思考：222.无失真变长信源编码定理：平均码长：定长编码中，由于所有的码字都使用相同的长度，限制了其灵活性，导致或者效率不高，或者复杂度太高（L太大）。变长编码可以对出现概率大的信源尽量用短码，从而提高编码效率.（统计匹配）232.无失真变长信源编码定理：(1).单符号变长编码定理若离散单符号信源X：xi∈{a1,a2,…,an}的熵为H(X)，对每个单符号进行无失真变长编码，设yj∈{b1,b2,…,bm}。则24(2).离散平稳无记忆序列变长编码定理

对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中

为任意小正数。25例题5-4：设离散无记忆信源概率空间为试讨论其编码效率。若L=1,用二元定长编码(0，1)来构造一个即时码：x1→0，x2→1。平均码长＝1二元码符号/信源符号

编码效率为输出的信息率为26（续）例题5-4：若对长度为L=2的信源序列进行变长编码，其即时码如表5-2所示。27（续）例题5-4：xip(xi)即时码x1x19/160x1x23/1610x2x13/16110x2x21/16111表5-2长度为2的信源序列对应的即时码该码平均长度：单符号平均码长：编码效率为：28（续）例题5-4：29（续）例题5-4：L＝3

η3=0.985

R3＝0.985比特/二元码符号

L＝4

η4=0.991

R4＝0.991比特/二元码符号

30（续）例题5-4：定长二元码编码，要求编码效率达到96％时，允许译码错误概率δ≤10-5

。315.2.2限失真信源编码（香农第三定理）

信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D。

限失真信源编码定理：对于任意的D≥0和

＞0，当信息率R>R(D)时，一定存在一种编码方法，其译码失真小于或等于D+

，条件是编码的信源序列长度L足够长。反之，如果R<R(D)，则无论采用什么编码方法，其译码失真必大于D。325.2.2限失真信源编码（香农第三定理）香农第三定理是一个存在性定理，它只说明一定存在一种满足要求的编码方法。至于如何寻找这种最佳压缩编码方法，定理中没有给出。在实际应用中，该理论主要存在以下两类问题：（1）符合实际信源的R(D)函数的计算相当困难；（2）即使求得了符合实际的信息率失真函数，还需要研究采用何种编码方法，才能达到或接近极限值R(D)。335.2.2限失真信源编码（香农第三定理）34香农编码哈弗曼编码算术编码（非分组码）

5.3常用信源编码方法355.3.1

香农编码将信源消息符号按其出现的概率大小依次排列确定满足下列不等式的整数码长Ki

5.3常用信源编码方法36香农编码为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。

5.3常用信源编码方法37香农编码为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。

38香农编码

香农编码的基本做法：是把长度为1的整个累积概率区间，按照信源符号集中q个信源符号的概率大小，分成q份不同长度的子区间（每份子区间的长度正比于对应符号的概率大小），将每种信源符号xi，映射到其对应子区间上的一个点。这样，每个信源符号xi映射区间都是不重叠的，从而可以保证唯一可译码，而且可以证明，也是即时码；另一方面，码字长度由其概率决定，概率大的用短码。

39香农编码

例5.4设信源共7个符号消息

信源消息符号ai符号概率p(ai)累加概率Pi-logp(ai)码字长度Ki码字a10.2002.343000a20.190.22.413001a30.180.392.483011a40.170.572.563100a50.150.742.743101a60.100.893.3441110a70.010.996.667111111040香农编码

香农编码效率不高，不具有实际应用价值，但其概率匹配的思想很有指导意义。415.3.2

哈夫曼编码哈夫曼编码是按照概率匹配思想构建的一种具有实际使用价值的编码方法。哈夫曼编码是唯一可译码、即时码。421.哈夫曼树图5-1码树结构图43码树树根树枝数节点终端节点节数非满树满树码字的起点码的进制数码字或码字的一部分码字码长变长码等长码442哈夫曼编码(码树法)设信源符号集X={x1,x2,…,xq}，对应的概率为p(X)={p(x1),p(x2),…,p(xq)}，且所有的p(x)>0，其编码步骤如下：以q个信源符号的概率为权值，构造q个带权值的节点。每个节点作为一棵树，构造一个具有q棵树的森林；在森林中选出两棵根节点权值最小的树作为一棵新树的左、右子树，且置新树的附加根节点权值为其左、右子树上根节点权值之和；452哈夫曼编码(码树法)从森林中删除这两棵树，同时把新树加入到森林中；重复步骤②、③，直到森林中只有一棵树为止，此树便是哈夫曼树，需要编码的q个符号为该哈夫曼树的q个终端节点；(将哈夫曼树中指向左子树的分支标记为“0”，指向右子树的分支标记为“1”，从根节点到每个终端节点路径上的“0”、“1”组成的序列作为各个终端节点对应的编码，即得哈夫曼编码。462哈夫曼编码(码树法)例5-6：设给定信源X={x1,x2,x3,x4,x5,x6,x7}，对应的概率为p(X)={0.2,0.19,0.18,0.17,0.15,0.10,0.01}。给出哈夫曼编码过程。0.010.100.110.150.260.170.180.350.610.190.200.3910010

1010101图5-2

码树法哈夫曼编码过程472哈夫曼编码(图表法)将q个信源符号按概率分布的大小，以递减次序排列起来，设用“0”和“1”码符号分别代表概率最小的两个信源符号，并将两个概率最小的符号合并成一个符号，合并的符号概率为两个符号概率之和，从而得到只包含q-1个符号的新信源，称为缩减信源。482哈夫曼编码(图表法)把缩减信源的符号仍旧按概率大小以递减次序排列，再将其概率最小的两个信源符号分别用“0”和“1”表示，并将其合并成一个符号，概率为两符号概率之和，这样又形成了q-2个符号的缩减信源。依此继续下去，直至信源只剩下两个符号为止。将这最后两个信源符号分别用“0”和“1”表示。然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。492哈夫曼编码(图表法)表5-2图表法哈夫曼编码过程例5-6：设给定信源X={x1,x2,x3,x4,x5,x6,x7}，对应的概率为p(X)={0.2,0.19,0.18,0.17,0.15,0.10,0.01}。给出哈夫曼编码过程。502哈夫曼编码信源符号xi概率p(xi)码字Wi码长Kix10.20102x20.19112x30.180003x40.170013x50.150103x60.1001104x70.0101114512哈夫曼编码

码元/符号

bit/符号

52哈夫曼编码结果并不是唯一的哈夫曼树的左右分支表示“0”或者“1”，是可以互换的；当有多个节点具有相同的概率时，选择哪些节点进行合并是任意的。如果缩减信源中有两个以上的节点概率相同，则应优先选择未被合并过（或合并次数少）的节点进行合并，以便尽量减小编码方差，从而减小编码设备复杂度。53哈夫曼编码结果并不是唯一的例

设有离散无记忆信源给出哈夫曼编码过程。542哈夫曼编码哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。555.3.3

算术编码香农编码和哈夫曼编码，都是基于分组的块编码。分组编码方法没有考虑到组间符号的相关性，因此编码效率会有所损失。增加码长可以考虑更多符号间的相关性，但会增加编码复杂度及编码时延。算术编码是一种非分组编码方法，其基本思路是借鉴香农编码的区间映射思想。565.3.3

算术编码算术编码从全序列出发，将不同的信源序列的累计概率映射到[0,1]区间上，使每个序列对应区间上的一点，也就是说，把区间[0,1]分成许多互不重叠的小区间，不同的信源序列对应不同的小区间，可以证明，只要这些小区间互不重叠，就可以编得即时码。0(P1)P2

P3

P4P5……1

……p1

p2p3p4575.3.3

算术编码问题：是否需要等到要编码的序列全部都已知以后才开始进行区间映射（编码）吗？设P(S)表示序列S的累积概率（即其对应的子区间的起始点），A(S)为序列S对应的子区间长度，C(S)表示对序列S编码得到的的码字，pr表示m进制单符号xr的概率，Pr(r=0,1,2,…,m-1)表示m进制单符号xr的累计概率。可建立递推更新过程：585.3.3

算术编码符号符号概率pi符号累积概率Pja0.100(1/2)0.000b0.010(1/4)0.100c0.001(1/8)0.110d0.001(1/8)0.111例5-7

有4个符号a，b，c，d构成简单序列S＝abda，各符号及其对应概率如下表（二进制），试给出算术编解码过程。595.3.3

算术编码设起始状态为空序列∅，则A(∅)＝1，P(∅)＝0。605.3.3

算术编码设起始状态为空序列∅，则A(∅)＝1，P(∅)＝0。615.3.3

算术编码故编码后的码字C(abda)即为序列abda的累积概率P(abda)（二进制数）小数点后的7位：0101110.625.3.3

算术编码编码过程（为简化图，只给出了序列abd的编码过程）：图5-9算术编码过程63算术编码的译码过程C(abda)=0.010111<0.1

[0,0.1]

第一个符号为a

放大至[0,1](×pa-1)：

C(abda)×21＝0.10111

[0.1,0.110]

第二个符号为b64算术编码的译码过程去掉累积概率Pb：0.10111-0.1=0.00111

放大至[0,1](×pb-1)：

0.00111×22=0.111

[0.111,1]

第三个符号为d

去掉累积概率Pd：0.111-0.111=0

放大至[0,1](×pd-1)：0×24＝0

[0,0.1]第四个符号为a本章小结65第五章主要内容结构66本章小结本章学习思路码的分类→即时码存在的充分必要条件：克劳福特不等式→信源编码定理→常用信源编码方法：编码效率分析。67本章小结本章学习要点

1.信源编码的目的

信源编码的目的主要是提高通信系统的有效性，即通过编码，用尽可能短的编码序列符号来表示原序列。

68本章小结本章学习要点

2.无失真信源编码定理

（1）单符号无失真变长信源编码定理

（2）离散平稳无记忆序列无失真变长信源编码定理

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

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

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

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

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

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

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

由于一般，，所以d越小，似然函数就越大，因此，对于BSC信道，最大似然译码就等价于最小汉明距离译码。一些概念77矢量空间：正交完备基：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个点。一些概念78码空间：

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

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

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

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

Gallager在1965年证明，平均译码错误概率的上界为：83信道编码定理

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

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

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

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

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

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

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

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

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

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

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

n-k个是冗余。

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

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

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

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

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

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

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

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

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

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

Gs

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

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

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

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

息码

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

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

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

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

线性分组码的译码：

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）的矩阵）。108常用信道编码方法—线性分组码

线性分组码的译码：

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

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

线性分组码的译码：

1.求解差错图案E

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

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

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

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

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

线性分组码的译码：

2.标准阵列译码表

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

线性分组码的译码：

2.标准阵列译码表

该表共有2n-k行，

2k列。

每一行代表一种伴随式Si（伴随式S是1×（n-k）的向量，对二进制来说，共有2n-k种不同的伴随式），也就是一种差错图案Ei

（每一个伴随式对应的2k个解中重量最轻的那个）；每一列对应一个发码Cj，共有2k个不同的发码（信息码组是1×k的向量）；表中共有2n-k×2k=2n个元素，代表2n个不同的收码。114常用信道编码方法—线性分组码

线性分组码的译码：

2.标准阵列译码表

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

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

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

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

线性分组码的译码：

2.标准阵列译码表

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

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

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

线性分组码的译码：

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

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

线性分组码的译码：

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

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

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

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

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

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

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

线性分组码的性质：

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

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

列线性无关。

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

线性分组码之循环码：

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

循环码空间：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]，也是循环码的一个码字。124常用信道编码方法—线性分组码

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

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

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

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

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

循环码空间：例：三维空间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。126常用信道编码方法—线性分组码

循环码的生成多项式：

生成矩阵的每一行，是一个基底矢量，基底矢量也是码矢量，也满足循环移位性质。只要给定一个基底矢量的码多项式，经循环移位，就可以得到所有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)的因子。127常用信道编码方法—线性分组码

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

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

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

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

循环码的生成多项式：

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

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

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

循环码的校验多项式：由于生成多项式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)循环码是一种特殊的线性分组码，故线性分组码的译码方法也完全适用于循环码。133常用信道编码方法—卷积码卷积码的产生分组码以孤立码块为单位编译码信息流割裂为孤立块后丧失了分组间的相关信息分组码长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）此时各状态对应的PMl（i）如下图所示：卷积码的译码-维特比译码iii）第2个时刻（l=2）此时各状态对应的PMl（i）如下图所示：卷积码的译码-维特比译码iv）第3个时刻（l=3）此时各状态对应的PMl（i）如下图所示：卷积码的译码-维特比译码

在l=3时刻，到达每一状态均有两条路径，其中用实线表示的，是两条路径中路径度量较小者，为幸存路径，另一条路径用虚线表示，被舍弃。例如：在l=3时刻，有两条路径到达S0状态，一条是从上个S0状态到达，其路径度量为7；另一条是从状态S1到达，其路径度量为3，该条路径为幸存路径。

由于路径舍弃（只保留幸运路径），使得每个状态只保留一条路径（幸存路径），称为留存路径。因此，对维特比译码来说，在每个时刻（初始几个时刻除外），都有2k条留存路径（因为共有2k个不同的状态）。卷积码的译码-维特比译码②

提前输出

当收码序列全部接收完以后，比较每条留存路径的路径度量，路径度量最小的那条路径，就是最大似然路径，沿着该路径，就可以得到译码序列。如例6-6中，如果收码序列只有3个：110、111、011，则当接收完收码序列后，比较最后一个时刻（l=3）时各留存路径的路径度量可知,这条路径的路径度量最小（），所以该路径为最大似然路径，译码序列为：000、111、011.卷积码的译码-维特比译码但是，如果等收码序列全部接收完以后，再根据各留存路径的路径度量，找出最大似然路径，从而输出译码序列，将会导致很大的译码时延，而且每条留存路径都很长，需要较大的存储量。卷积码的译码-维特比译码实际上，随着收码不断到达译码器，各留存路径的路径度量是单调增加的，但增加的速度不一样。正确的译码路径，其路径度量值增大的程度，取决于接收码字的差错，一般来说，正常通信时，该差错概率比较小；而其他路径的路径度量值增大，是由于路径差异导致的，上升速度会很快。所以，经过一段时延后，正确路径的路径度量就会变成所有留存路径中最小的。卷积码的译码-维特比译码因此，随着收码不断到来，各状态留存路径较靠前的部分，有合并为一条的趋势。如例6-6中，在l=3时，状态S1的留存路径和状态S3的留存路径，靠前的部分，已经是一样的了（都是

）。也就是说，经过一段时间后，各条留存路径的靠前部分，已经有很大概率是一样的了，此时，我们可以把最靠前的一个译码码字输出，而不必等到全部收码序列都完成接收。卷积码的译码-维特比译码维特比译码方法，就是设定一个时延D（一般取卷积码状态数的5倍），当译码时间达到时延D时，就把当时的最佳留存路径（路径度量最小的路径）最前面的一个码字输出，而不必等到所有收码全部接收完。称之为提前输出。卷积码的译码-维特比译码例6-7：例6-3中的