第5章无失真信源编码定理精选文档.ppt

《第5章无失真信源编码定理精选文档.ppt》由会员分享，可在线阅读，更多相关《第5章无失真信源编码定理精选文档.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章无失真信源编码定理1本讲稿第一页，共三十六页第5章 无失真信源编码u5.1 编码器u5.2 等长码u5.3 渐进等分割性和e典型序列*u5.4 等长信源编码定理u5.5 变长码u5.6 变长信源编码定理2本讲稿第二页，共三十六页5.1 编码器u对对整整个个通通信信系系统统来来说说，要要解解决决两两个个问问题题：信信源源编编码和信道编码。码和信道编码。u对对信信源源来来说说有有两两个个重重要要问问题题：一一个个是是信信源源输输出出信信息息量量的的定定量量度度量量问问题题。这这在在前前面面信信源源及及其其信信息息熵熵章章中中已已讨讨论论。本本章章将将要要讨讨论论第第二二个个问问题题：如如何何

2、有有效效地地表表示示信信源源输输出出问问题题。即即将将重重点点讨讨论论对对信信源源进进行行无无失失真真信信源源编编码码的的要要求求、方方法法及及理理论论极极限限，从从而而得得出出香香农农第一定理。第一定理。3本讲稿第三页，共三十六页编码器的描述码元码字码码长 l码符号集4本讲稿第四页，共三十六页u信源编码器的信源编码器的主要任务主要任务：完成输入消息：完成输入消息集合与输出代码集合之间的集合与输出代码集合之间的映射映射。若要。若要实现无失真编码，则这种实现无失真编码，则这种映射必须是一映射必须是一一对应的、可逆的。一对应的、可逆的。5本讲稿第五页，共三十六页常用码型常用码型u1、二二元元码码：

3、若若信信道道码码符符号号集集A=0，1，编编码码输输出出的的码码字字都都是是二二元元码码，称称为为二二元元码。码。u2、等等长长码码：若若一一组组码码中中所所有有码码字字的的码码长长都相同，称为等长码。都相同，称为等长码。u3、变变长长码码：若若一一组组码码中中所所有有码码字字的的码码长长Ki各各不不相相同同，即即任任意意码码字字由由不不同同长长度度的的码符号序列组成，则称为变长码。码符号序列组成，则称为变长码。6本讲稿第六页，共三十六页常用码型常用码型u4 4、非非奇奇异异码码和和奇奇异异码码：若若一一组组分分组组码码中中的的所所有有码码字字都都不不相相同同，即即所所有有信信源源符符号号映映

4、射射到到不不同同的的码码字字。称称此此分分组组码码为为非非奇奇异码。否则为奇异码异码。否则为奇异码u5、同同价价码码和和非非同同价价码码：若若每每个个码码符符号号的的传传输输时时间间都都相相同同则则称称为为同同价价码码。否否则则为为非同价码非同价码7本讲稿第七页，共三十六页常用码型常用码型u6、码码的的N次次扩扩展展码码：假假使使某某分分组组码码W，把把信信源源X中中的的符符号号xi一一一一变变换换成成码码W中中的的码码字字Wi 字字，则则码码W的的N次次扩扩展展码码是是N个个码码字字组组成成的的码码字字序序列的集合。列的集合。8本讲稿第八页，共三十六页例：例：设信源设信源X的概率空间为的概率

5、空间为若若把把该该信信源源通通过过一一个个二二元元信信道道进进行行传传输输，为为适适合合信信道道传传输输，就就必必须须把把信信源源符符号号xi变变换换成成0、1符符号号组组成成的的码码序序列列（二二元元序序列列）。可可采采用用不不同同的的二二元元序序列列使使其其与与信信源源符符号号si一一一一对对应应，所所以以可可有有多多种种方方法法得得到到二二元元码码。如如表表4.1所所示示9本讲稿第九页，共三十六页表表5.1 5.1 信源信源X X的两种不同编码码字的两种不同编码码字 现求码现求码S2S2的二次扩展码。的二次扩展码。10本讲稿第十页，共三十六页常用码型常用码型u7、唯一可译码：唯一可译码：

6、若码的任意一串有限长的码符号序若码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此列只能被唯一地译成所对应的信源符号序列，则此码为唯一可译码。否则，称为非唯一可译码。码为唯一可译码。否则，称为非唯一可译码。u唯一可译码的物理含义：唯一可译码的物理含义：不仅要求不同的码字表示不仅要求不同的码字表示不同的信源符号，而且还进一步要求对由信源符不同的信源符号，而且还进一步要求对由信源符号构成的信息序列进行编码时，在接收端仍能正号构成的信息序列进行编码时，在接收端仍能正确译码，而不发生混淆。确译码，而不发生混淆。u本章主要研究的是同价唯一可译码。本章主要研究的是同价唯一可译码。11

7、本讲稿第十一页，共三十六页5.2 定长码定长码 u一一般般来来说说，若若要要实实现现无无失失真真的的编编码码，所所编编的的码码必必须须是是唯唯一一可可译译码码，否否则则，就就会会因因译译码码带带来来的的错误与失真。错误与失真。u非非奇奇异异定定长长码码的的N N次次扩扩展展码码一一定定也也是是非非奇奇异异定定长码。长码。u非奇异定长码一定是唯一可译码。非奇异定长码一定是唯一可译码。12本讲稿第十二页，共三十六页信源存在唯一可译定长码的条件：信源存在唯一可译定长码的条件：u对信源X 进行等长编码，必须满足 其中l 是等长码的码长,有 u例：英文电报有32个符号，即n=32。若对它进行二元编码，则

8、r=2，可得l=5。也就是说，每个英文电报符号至少要用5位二元符号编码才行。13本讲稿第十三页，共三十六页u实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，其信息熵约为1.4比特/符号，即平均每个英文符号所提供的信息量为1.4比特。u因此等长编码后5个二元符号只携带约1.4比特信息量。u对于无噪无损二元信道，每5个二元符号最大能载荷5比特的信息量。u因此，如此等长编码的信息传输效率极低。14本讲稿第十四页，共三十六页5.4等长信源编码定理u定理4.3一个熵为H(X)的离散无记忆信源，若对信源长为 N 的符号序列进行等长编码，设码字是从 r 个字母的码符号集中选取 l 个码元

9、组成。对于任意 0，只要满足u则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。15本讲稿第十五页，共三十六页编码信息率编码信息率编码效率编码效率举例：书145页例4.116本讲稿第十六页，共三十六页5.5 变长码u变长码也必须是唯一可译码，才能实现变长码也必须是唯一可译码，才能实现无失真编码。无失真编码。u定义：在唯一可译变长码中，有一类码，定义：在唯一可译变长码中，有一类码，它在译码时，无须参考后续的码符号就它在译码时，无须参考后续的码符号就能立即作出判断，译成对应的信源符号，能立即作出判断，译成对应的信源符号，则这类码称为则这类码称为即时码即时码17本讲稿第十七页，共三十六

10、页u一个唯一可译码成为即时码的充要条件是其一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。故中任何一个码字都不是其他码字的前缀。故即时码一定是唯一可译码，反之，唯一可译即时码一定是唯一可译码，反之，唯一可译码不一定是即时码。码不一定是即时码。u即时码可用即时码可用树图法来进行编码和译码树图法来进行编码和译码。18本讲稿第十八页，共三十六页u树码：树码：通过树图法构成的码叫树码通过树图法构成的码叫树码u对对r r进制树图，进制树图，有树根、树枝和节点有树根、树枝和节点。树图。树图最顶部的节点称为最顶部的节点称为树根树根。树枝树枝的尽头称为的尽头称为节节点点，每个节点生出

11、的树枝树目等于码符号树，每个节点生出的树枝树目等于码符号树r r。即时码的构造即时码的构造 19本讲稿第十九页，共三十六页20本讲稿第二十页，共三十六页u即时码可用即时码可用树图法来进行编码和译码树图法来进行编码和译码。u构造步骤：构造步骤：u 1、最上端为树根，从根出发向下伸出树枝，树枝总数等、最上端为树根，从根出发向下伸出树枝，树枝总数等于于m（码符号数）码符号数），树枝的尽头为节点。，树枝的尽头为节点。u 2、从每个节点再伸出、从每个节点再伸出m枝树枝，当某节点被安排为码枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的字后，就不再伸枝，这节点为终端节点。能再伸枝的

12、节点称为中间节点。一直继续进行，直到都不能伸枝节点称为中间节点。一直继续进行，直到都不能伸枝为止。为止。u 3、每个节点所伸出的树枝标上码符号，从根出发、每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节到终端节点所走路径对应的码符号序列则为终端节点的码字。点的码字。21本讲稿第二十一页，共三十六页u树树码码一一定定是是即即时时码码，任任一一即即时时码码都都可可用用上上述述树树图图法法来来表表示示。即即时时码码一一定定是是唯唯一一可可译译码码。唯一可译码，不一定是即时码。唯一可译码，不一定是即时码。22本讲稿第二十二页，共三十六页例：例：一信源一信源X(x1,

13、x2,x3,x4)经编码后得码字集合经编码后得码字集合S(1,01,001,0001)且一一对应。现接收码元序列为且一一对应。现接收码元序列为101110001001101011，试写出译码结果。，试写出译码结果。解解：该该 编编 码码 规规 则则 为为：x11,x201,x3001,x4001，每每一一码码字字均均以以1结结尾尾，见见1即即可可译译码码。对对所接收序列的译码结果为所接收序列的译码结果为u x1,x2,x1,x1,x4,x3,u这这种种编编码码，译译码码时时不不需需要要考考察察后后续续码码元元，故故又又称称之之为为即时码即时码。23本讲稿第二十三页，共三十六页编码的树图表示编码

14、的树图表示即时码一定是单义可译码即时码一定是单义可译码。24本讲稿第二十四页，共三十六页单义可译定理（即时码单义可译定理（即时码存在存在的充的充要条件）要条件）u对含有n个信源符号的信源用含r 个符号的码符号集进行编码，各码字的码长为 的唯一可译码存在的充要条件是，满足Kraft不等式u含义：25本讲稿第二十五页，共三十六页例：例：信源空间为信源空间为 X：x1,x2,x3,x4 P(X)：1/2，1/4，1/8，1/8 对其进行信源编码，信道基本符号集合为：对其进行信源编码，信道基本符号集合为：m=0,1；若若编编码码后后对对应应的的码码长长分分别别为为k1=1,k2=2,k3=3,k4=3

15、，问能否构造出一种即时码？问能否构造出一种即时码？解：解：将将m=2,n=4 和和ki的的4个值带入个值带入Kraft不等式得得满足满足Kraft不等式，所以一定能构成至少一种即时码不等式，所以一定能构成至少一种即时码 26本讲稿第二十六页，共三十六页27本讲稿第二十七页，共三十六页唯一可译码的判断法唯一可译码的判断法u应该注意的是克拉夫特（应该注意的是克拉夫特（Kraft）不等式只是给出来不等式只是给出来即时码或唯一可译码存在的充分必要条件，即时码或唯一可译码存在的充分必要条件，但该定但该定理并不能作为判别一种码是否为即时码或唯一可译理并不能作为判别一种码是否为即时码或唯一可译码的依据。码的

16、依据。u即唯一可译码（或即时码）一定满足不等式，反之，即唯一可译码（或即时码）一定满足不等式，反之，满足不等式的码不一定是唯一可译码。满足不等式的码不一定是唯一可译码。u例：例：码字（码字（0，10，010，111），满足克拉夫特不），满足克拉夫特不等式，但它不是唯一可译码。等式，但它不是唯一可译码。28本讲稿第二十八页，共三十六页唯一可译码的判断步骤：唯一可译码的判断步骤：u1、观察是否是非奇异码。若是奇异码则一定不是唯一、观察是否是非奇异码。若是奇异码则一定不是唯一可译码。可译码。u2、计算是否满足、计算是否满足Kraft不等式，若不满足一定不是唯不等式，若不满足一定不是唯一可译码。一可译

17、码。u3、将码画成一棵树图，观察是否满足即时码的、将码画成一棵树图，观察是否满足即时码的树图构造，若满足则是唯一可译码。树图构造，若满足则是唯一可译码。u4、直接用判别测试算法：、直接用判别测试算法：29本讲稿第二十九页，共三十六页5.6变长信源编码定理u设信源 有n个离散符号，编码后的码字为u其码长分别为u对于唯一可译码来说，信源符号与码字一一对应，所以有u则这个码的平均长度为30本讲稿第三十页，共三十六页u码的平均长度是每个信源符号平均需用的码元数。平均每个码元携带的信息量即编码后信道的信息传输率为u若要信息传输效率高，需寻求使平均码长最短的码，即紧致码，或称最佳码。31本讲稿第三十一页，

18、共三十六页平均码长可能达到的理论极限u定理：若一离散无记忆信源 X 具的熵为H(X)，并有 r 个码元的码符号，则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足u无失真变长信源编码定理香农第一定理32本讲稿第三十二页，共三十六页u编码效率：u码的剩余度：u二元无噪无损信道中信息传输率33本讲稿第三十三页，共三十六页u例：有一离散无记忆信源u其熵为H(X)=0.811比特/信源符号。u用二元码构造一个非续长码：x10，x21u这时平均码长 ，编码效率u信道信息传输率为34本讲稿第三十四页，共三十六页u对该信源的二次扩展信源进行编码如下u这个码的平均长度u得信源中每一个单个符号的平均码长u编码效率u信道信息传输率为u同样可得35本讲稿第三十五页，共三十六页u香农第一定理仅是一个存在性定理，指出了平香农第一定理仅是一个存在性定理，指出了平均码长与信源熵之间的关系，但没有给出如何均码长与信源熵之间的关系，但没有给出如何构造的信息。构造的信息。u用用前前述述例例子子的的编编码码方方法法虽虽然然可可以以得得到到即即时时码码，但但通通常常不不是是最最佳佳编编码码，故故有有必必要要寻寻求求更高效率的编码方法。更高效率的编码方法。36本讲稿第三十六页，共三十六页