信息论与编码原理-信源编码ppt课件.ppt
( 4.5 )《信息论与编码原理-信源编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码原理-信源编码ppt课件.ppt（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第5章信源编码章信源编码 编码分为信源编码和信道编码，其中信源编码分为信源编码和信道编码，其中信源编码又分为编码又分为无失真和限失真无失真和限失真。一般称一般称u无失真信源编码定理无失真信源编码定理为第一极限定理；为第一极限定理；u信道编码定理信道编码定理（包括离散和连续信道）称为第（包括离散和连续信道）称为第 二极限定理；二极限定理；u限失真信源编码定理限失真信源编码定理称为第三极限定理。称为第三极限定理。1普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著第第5章信源编码章信源编码由于信源符号之间存在分布由于信源符号之间存在分布不均匀和相关不均匀和相关性性，使得信源存在，使得信
2、源存在冗余度冗余度，信源编码的主，信源编码的主要任务就是减少冗余，提高编码效率。要任务就是减少冗余，提高编码效率。2普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著第第5章信源编码章信源编码信源编码的基本途径有两个：信源编码的基本途径有两个：n使序列中的各个符号尽可能地互相独立，使序列中的各个符号尽可能地互相独立，即解除相关性；即解除相关性；n使编码中各个符号出现的概率尽可能地使编码中各个符号出现的概率尽可能地相等，即概率均匀化。相等，即概率均匀化。3普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著第第5章信源编码章信源编码信源编码的基础是信息论中的两个编码定理：信源编
3、码的基础是信息论中的两个编码定理：n无失真编码定理无失真编码定理n限失真编码定理限失真编码定理 无失真编码无失真编码只适用于离散信源只适用于离散信源 对于连续信源，只能在失真受限制的情况下进对于连续信源，只能在失真受限制的情况下进行行限失真编码限失真编码 4普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著第第5章信源编码章信源编码本章讨论本章讨论离散信源编码离散信源编码，首先从，首先从无失真编无失真编码定理码定理出发，重点讨论以出发，重点讨论以香农码香农码、费诺码费诺码和和霍夫曼码霍夫曼码为代表的最佳无失真码。然后为代表的最佳无失真码。然后介绍了介绍了限失真编码定理限失真编码定理。
4、最后简单介绍了。最后简单介绍了一些其它常用的信源编码方法。一些其它常用的信源编码方法。5普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义信源信源编码器编码器信道信道码表码表图图5-1 信源编码器示意图信源编码器示意图6普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义信源编码信源编码是指信源输出符号经信源编码器是指信源输出符号经信源编码器编码后转换成另外的压缩符号编码后转换成另外的压缩符号无失真信源编码无失真信源编码：可精确无失真地复制信：可精确无失真地复制信源输出地消息源输出地消息7普通高等教育“十五”国家级规划教
5、材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义将信源消息分成若干组，即符号序列将信源消息分成若干组，即符号序列xi，xi(xi1xi2xilxiL)，xil A=a1，a2，ai，an每个符号序列每个符号序列xi依照固定码表映射成一个码字依照固定码表映射成一个码字yi，yi(yi1yi2yilyiL)，yil B=b1，b2，bi，bm这这样样的的码码称称为为分分组组码码，有有时时也也叫叫块块码码。只只有有分分组组码码才才有有对对应的码表应的码表，而非分组码中则不存在码表。，而非分组码中则不存在码表。8普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码
6、的定义如如图图5-1所所示示，如如果果信信源源输输出出符符号号序序列列长长度度L1，信源符号集信源符号集A(a1，a2，an)信源概率空间为信源概率空间为 若若将将信信源源X通通过过二二元元信信道道传传输输，就就必必须须把把信信源源符符号号ai变变换换成成由由0，1符符号号组组成成的的码码符符号号序序列列，这这个个过程就是信源编码过程就是信源编码 9普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义码可分为两类：码可分为两类：一一、固固定定长长度度的的码码，码码中中所所有有码码字字的的长长度度 都相同，如表都相同，如表5-1中的码中的码1就是就是定长码定长
7、码二二、可可变变长长度度码码，码码中中的的码码字字长长短短不不一一，如表中码如表中码2就是就是变长码变长码。10普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义不同的码符号序列，如表不同的码符号序列，如表5-1所示。所示。表表5-1 变长码与定长码变长码与定长码信信源源符符号号ai信源信源符号符号出现出现概率概率p(ai)码表码表码码1码码2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)1111111普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义（1）奇异码和非奇异码）奇异码和非
8、奇异码 若若信信源源符符号号和和码码字字是是一一一一对对应应的的，则则该该码为码为非奇异码非奇异码。反之为奇异码。反之为奇异码。如如表表5-2中中的的码码1是是奇奇异异码码，码码2是是非非奇奇异异码。码。12普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义表表5-2 码的不同属性码的不同属性信源符号信源符号ai符号出符号出现现概率概率p(ai)码码1码码2码码3码码4a11/20011a21/411101001a31/80000100001a41/811011000000113普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义
9、编码的定义（2）唯一可译码唯一可译码 任意有限长的码元序列，只能被唯一地任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译分割成一个个的码字，便称为唯一可译码码 14普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义唯唯一一可可译译码码中中又又分分为为非非即即时时码码和和即即时时码码：如如果果接接收收端端收收到到一一个个完完整整的的码码字字后后，不不能能立立即即译译码码，还还需需等等下下一一个个码码字字开开始始接接收收后后才才能能判判断断是是否否可可以以译译码码，这这样样的的码码叫叫做做非非即时码。即时码。15普通高等教育“十五”国家级规
10、划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义即即时时码码：只只要要收收到到符符号号就就表表示示该该码码字字已已完完整，可以立即译码。整，可以立即译码。即即时时码码又又称称为为非非延延长长码码，任任意意一一个个码码字字都都不不是是其其它它码码字字的的前前缀缀部部分分，有有时时叫叫做做异异前前缀码缀码。16普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义码码奇异码奇异码非分组码非分组码分组码分组码非奇异码非奇异码非唯一可译码非唯一可译码非即时码非即时码即时码即时码(非延长码非延长码)唯一可译码唯一可译码17普通高等教育“十五”国家级规划教材信
11、息论与编码 曹雪虹等编著5.1 编码的定义编码的定义通常可用通常可用码树码树来表示各码字的构成来表示各码字的构成 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1二进制码树二进制码树18普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三进制码树三进制码树19普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义唯一可译码唯一可译码存在存在的充分和必要条件的充分和必要条件 各码字的长度各
12、码字的长度Ki 应符合应符合克劳夫特不等式克劳夫特不等式：20普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义例例：设二进制码树中设二进制码树中X (a1，a2，a3，a4 )，K11，K22，K32，K43，应，应用上述判断定理：用上述判断定理：因此不存在满足这种因此不存在满足这种Ki的唯一可译码的唯一可译码。21普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义a1=1 0 1 0 1 0 1a2=01a3=011a4=0001，01，001，000 惟一可译码；惟一可译码；1，01，101，000 不是惟一可译
13、码；不是惟一可译码；均满足克劳夫特不等式均满足克劳夫特不等式22普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.1 编码的定义编码的定义克克劳劳夫夫特特不不等等式式只只是是用用来来说说明明唯唯一一可可译译码码是否是否存存在，并不能作为唯一可译码的判据。在，并不能作为唯一可译码的判据。23普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码信源输出信源输出X(X1X2XlXL)，Xl a1，a2，ai，an编码为编码为Y(Y1Y2Yk YkL)，Yk b1，b2，bj，bm。要求能够要求能够无失真或无差错无失真或无差错地译码，同
14、时传地译码，同时传送送Y时所需要的时所需要的信息率最小信息率最小 24普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码Yk平均每个符号平均每个符号的最大信息量为的最大信息量为log mKL长码字的最大信息量为长码字的最大信息量为KLlog m则传送一个信源符号需要的信息率平均为则传送一个信源符号需要的信息率平均为 25普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码所所谓谓信信息息率率最最小小，就就是是找找到到一一种种编编码码方方式使式使 最小。最小。无失真信源编码无失真信源编码定理
15、研究的内容定理研究的内容:最最小小信信息息率率为为多多少少时时，才才能能得得到到无无失失真真的的译译码码？若若小小于于这这个个信信息息率率是是否否还还能能无无失真地译码失真地译码 26普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码无失真的信源编码定理无失真的信源编码定理n定长定长编码定理编码定理n变长变长编码定理编码定理 27普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码n定长定长编码定理编码定理K是定值是定值 且惟一可译码且惟一可译码28普通高等教育“十五”国家级规划教材信息论
16、与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码由由L个个符符号号组组成成的的、每每个个符符号号的的熵熵为为HL(X)的的无无记记忆忆平平稳稳信信源源符符号号序序列列X1X2XlXL，可可用用KL个个符符号号Y1，Y2，Yk，（每每个个符符号号有有m种种可可能值）进行能值）进行定长编码定长编码。对任意。对任意 0，0，只要，只要则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于；反之，当反之，当 时，译码差错一时，译码差错一定是有限值，而定是有限值，而L足够大时，译码几乎必定出错足够大时，译码几乎必定出错 29普通高等教育“十五”国家级规划教材信息论与编码 曹雪
17、虹等编著5.2 5.2 无失真信源编码无失真信源编码定长编码定理说明，定长编码定理说明，码字所能携带的信息量码字所能携带的信息量大于大于信源序列输出信源序列输出的信息量，则可以使传输几乎无失真，当的信息量，则可以使传输几乎无失真，当然条件是然条件是L L足够大足够大。30普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码反之，当反之，当 时，不可能构成无失时，不可能构成无失真的编码，也就是不可能做一种编码器，真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，时，则为
18、临界状态，可能无失真，也可能有失真。也可能有失真。31普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码式中式中 为自信息方差为自信息方差 为为一一正正数数。当当 和和 均均为为定定值值时时，只只要要L足够大，足够大，Pe可以小于任一正数可以小于任一正数。即，。即，32普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码当信源序列长度当信源序列长度L满足满足 时，时，能达到差错率要求能达到差错率要求 33普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源
19、编码无失真信源编码在在连连续续信信源源的的情情况况下下，由由于于信信源源的的信信息息量量趋趋于于无无限限，显显然然不不能能用用离离散散符符号号序序列列Y来来完完成无失真编码，而只能进行成无失真编码，而只能进行限失真编码限失真编码。34普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码定义定义为为编编码码效效率率，即即信信源源的的平平均均符符号号熵熵为为H(X)，采采用用平平均均符符号号码码长长为为 来来编编码码，所所得得的的效率。效率。编码效率总是小于编码效率总是小于1，且最佳编码效率为，且最佳编码效率为 35普通高等教育“十五”国家级规划
20、教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码编编码码定定理理从从理理论论上上阐阐明明了了编编码码效效率率接接近近1的的理理想想编编码码器器的的存存在在性性，它它使使输输出出符符号号的的信息率与信源熵之比接近于信息率与信源熵之比接近于1，即，即 L取无限长取无限长36普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码例例设离散无记忆信源概率空间为设离散无记忆信源概率空间为 比特比特/符号符号 37普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码对对信信源源符
21、符号号采采用用定定长长二二元元编编码码，要要求求编编码码效率为效率为 90，若取，若取L1，则可算出，则可算出2.55 90%=2.8比特比特/符号符号Pe0.04 太大太大38普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码若要求译码错误概率若要求译码错误概率 39普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码变长变长编码定理编码定理在变长编码中，码长在变长编码中，码长K是变化的是变化的根根据据信信源源各各个个符符号号的的统统计计特特性性，如如概概率率大大的的符符号号用用短短码码
22、，概概率率小小的的用用较较长长的的码码，使使得得编编码码后后平平均均码码长长降降低低，从从而而提提高高编编码码效效率。（统计匹配）率。（统计匹配）40普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码单单个个符符号号变变长长编编码码定定理理：若若离离散散无无记记忆忆信信源源的的符符号号熵熵为为H(X)，每每个个信信源源符符号号用用m进进制制码码元元进进行行变变长长编编码码，一一定定存存在在一一种种无无失失真真编编码码方方法法，其其码码字字平平均均长长度度满满足足下下列列不不等式等式41普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等
23、编著5.2 5.2 无失真信源编码无失真信源编码 离离散散平平稳稳无无记记忆忆序序列列变变长长编编码码定定理理：对对于于平平均均符符号号熵熵为为HL(X)的的离离散散平平稳稳无无记记忆忆信信源源，必必存存在在一一种种无无失失真真编编码码方方法法，使使平平均均信息率满足不等式信息率满足不等式其中其中 为任意小正数。为任意小正数。42普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码用用变变长长编编码码来来达达到到相相当当高高的的编编码码效效率率，一一般般所所要要求求的的符符号号长长度度L可可以以比比定定长长编编码码小小得得多。多。43普通高等
24、教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码编编码码效效率率总总是是小小于于1 1，可可以以用用它它来来衡衡量量各各种种编码方法的优劣。编码方法的优劣。为为了了衡衡量量各各种种编编码码方方法法与与最最佳佳码码的的差差距距，定义码的剩余度为定义码的剩余度为 44普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码例例设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为45普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码若用二元定长编码
25、若用二元定长编码(0，1)来构造一个即来构造一个即时码：时码：。平均码长平均码长 1二元码符号二元码符号/信源符号信源符号46普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码编码效率为编码效率为输出的信息效率为输出的信息效率为R0.811比特比特/二元码符号二元码符号47普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5.2 5.2 无失真信源编码无失真信源编码长度为长度为2的信源序列进行的信源序列进行变长编码变长编码（编码方（编码方法后面介绍），其即时码如下表法后面介绍），其即时码如下表 aip(ai)即时码a1a19/16
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 信息论 编码 原理 信源 ppt 课件
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内