无失真和限失真信源编码.ppt

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

1、5.2 5.2 无失真信源编码无失真信源编码信源输出信源输出 X(X1X2XlXL)，Xl a1，a2，ai，an编码为编码为 Y(Y1Y2Yk YkL)，Yk b1，b2，bj，bm 要求能够要求能够无失真或无差错无失真或无差错地译码，同时传送地译码，同时传送Y时所需要的时所需要的信息率最小信息率最小。15.2 5.2 无失真信源编码无失真信源编码 Yk平均每个符号平均每个符号的最大信息量为的最大信息量为log m，KL长码字的最大信息量为长码字的最大信息量为KLlog m。用该。用该码字表示码字表示L长的信源序列，则传送一个信源长的信源序列，则传送一个信源符号需要的信息率平均为符号需要的信

2、息率平均为 M为Y所能编成的码字的个数25.2 5.2 无失真信源编码无失真信源编码信息率最小信息率最小:就是找到一种编码方式使就是找到一种编码方式使 最小。最小。无失真信源编码无失真信源编码定理研究的内容定理研究的内容:最最小小信信息息率率为为多多少少时时，才才能能得得到到无无失失真真的的译译码码？若若小小于于这这个个信信息息率率是是否否还还能能无无失真地译码。失真地译码。35.2 5.2 无失真信源编码无失真信源编码无失真的信源编码定理无失真的信源编码定理n定长定长编码定理编码定理n变长变长编码定理编码定理 K是定值是定值 且惟一可译码且惟一可译码 编码的目的：寻找最小编码的目的：寻找最小

3、K K值。值。45.2.1 5.2.1 定长编码定理定长编码定理 由由L个个符符号号组组成成的的、每每个个符符号号的的熵熵为为HL(X)的的无无记记忆忆平平稳稳信信源源符符号号序序列列X1X2XlXL，可可用用KL个个符符号号Y1，Y2，Yk，YKL(每个符号有每个符号有m种可能值种可能值)进行进行定长编码定长编码。对任意对任意 0，0，只要，只要 则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于；反之，当反之，当 时，时，译译码码差差错错一一定定是是有有限限值值，而而L足足够够大大时时，译译码码几几乎乎必必定出错。定出错。55.2.1 5.2.1 定长编码定理定长编码定理定

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

5、种等概率符号,L=1,信源序列熵达到最大值,H(x)=3bit/符号,即K=3bit/符号=H(x).n当信源符号输出概率不相等时,若p(ai)=0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04,则H(x)=2.55bit/符号n用22.55=5.856种可能的码字85.2.1 5.2.1 定长编码定理定长编码定理 在这种编码方式下，若差错概率为Pe，据切比雪夫不等式可导出95.2.1 5.2.1 定长编码定理定长编码定理式式中中 为为自自信信息息方方差差,为为一一正正数数。当当 和和 均均为为定定值值时时，只只要要L足足够够大，大，Pe可以小于任一正数可以小于任一正数

6、。即，。即，在这种编码方式下，若差错概率为Pe，据切比雪夫不等式可导出105.2.1 5.2.1 定长编码定理定长编码定理当信源序列长度当信源序列长度L满足满足 时，时，能达到差错率要求能达到差错率要求 115.2.1 5.2.1 定长编码定理定长编码定理 在在连连续续信信源源的的情情况况下下，由由于于信信源源的的信信息息量量趋趋于于无无限限，显显然然不不能能用用离离散散符符号号序序列列Y来来完完成成无无失失真真编编码码，而而只只能能进进行行限限失失真真编编码码。125.2.1 5.2.1 定长编码定理定长编码定理定义定义为为编编码码效效率率，即即信信源源的的平平均均符符号号熵熵为为H(X)，

7、采采用用平平均均符符号号码码长长为为 来来编编码码，所所得得的的效率。效率。编码效率总是小于编码效率总是小于1，且最佳编码效率为，且最佳编码效率为 135.2.1 5.2.1 定长编码定理定长编码定理 编编码码定定理理从从理理论论上上阐阐明明了了编编码码效效率率接接近近1的的理理想想编编码码器器的的存存在在性性，它它使使输输出出符符号号的的信息率与信源熵之比接近于信息率与信源熵之比接近于1，即，即 L取无限长取无限长145.2.1 5.2.1 定长编码定理定长编码定理例例1 设离散无记忆信源概率空间为设离散无记忆信源概率空间为 比特比特/符号符号 155.2.1 5.2.1 定长编码定理定长编

8、码定理 对对信信源源符符号号采采用用定定长长二二元元编编码码，要要求求编编码码效效率为率为 90，若取，若取L1，则可算出，则可算出2.55 90%=2.8比特比特/符号符号Pe0.04 太大太大165.2.1 5.2.1 定长编码定理定长编码定理若要求译码错误概率若要求译码错误概率 175.2.2 5.2.2 变长编码定理变长编码定理变长变长编码定理编码定理在变长编码中，码长在变长编码中，码长K是变化的是变化的 根根据据信信源源各各个个符符号号的的统统计计特特性性，如如概概率率大大的的符符号号用用短短码码，概概率率小小的的用用较较长长的的码码，使使得得编编码码后后平平均均码码长长降降低低，从

9、从而而提提高高编编码码效率。（统计匹配）效率。（统计匹配）185.2.2 5.2.2 变长编码定理变长编码定理单个符号单个符号变长编码定理：变长编码定理：若若离离散散无无记记忆忆信信源源的的符符号号熵熵为为H(X)，每每个个信信源源符符号号用用m进进制制码码元元进进行行变变长长编编码码，一一定定存存在在一一种种无无失失真真编编码码方方法法，其其码码字字平平均长度满足下列不等式均长度满足下列不等式195.2.2 5.2.2 变长编码定理变长编码定理 离散平稳无记忆序列离散平稳无记忆序列变长编码定理：变长编码定理：对对于于平平均均符符号号熵熵为为HL(X)的的离离散散平平稳稳无无记记忆忆信信源源，

10、必必存存在在一一种种无无失失真真编编码码方方法法，使平均信息率满足不等式使平均信息率满足不等式其中其中 为任意小正数。为任意小正数。205.2.2 5.2.2 变长编码定理变长编码定理 用用变变长长编编码码来来达达到到相相当当高高的的编编码码效效率率，一一般般所所要要求求的的符符号号长长度度L可可以以比比定定长长编编码码小小得得多。多。编码效率的下界编码效率的下界:215.2.2 5.2.2 变长编码定理变长编码定理 编编码码效效率率总总是是小小于于1 1，可可以以用用它它来来衡衡量量各种编码方法的优劣。各种编码方法的优劣。为为了了衡衡量量各各种种编编码码方方法法与与最最佳佳码码的的差差距，定

11、义码的剩余度为距，定义码的剩余度为 225.2.2 5.2.2 变长编码定理变长编码定理例例2设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为235.2.2 5.2.2 变长编码定理变长编码定理 若用二元定长编码若用二元定长编码(0，1)来构造一个来构造一个即时码：即时码：。平均码长平均码长 1二元码符号二元码符号/信源符号信源符号输出的信息效率为输出的信息效率为R0.811比特比特/二元码符号二元码符号编码效率为编码效率为245.2.2 5.2.2 变长编码定理变长编码定理例例3.长度为长度为2的信源序列进行的信源序列进行变长编码变长编码（编（编码方法后面介绍），其即时码如下表码方法

12、后面介绍），其即时码如下表 aip(ai)即时码a1a19/160a1a23/1610a2a13/16110a2a21/16111255.2.2 5.2.2 变长编码定理变长编码定理二元码符号二元码符号/信源序列信源序列二元码符号二元码符号/信源符号信源符号编码效率编码效率信息效率信息效率R20.961比特比特/二元码符号二元码符号 265.2.2 5.2.2 变长编码定理变长编码定理L3 R30.985比特比特/二元码符号二元码符号 L4 R40.991比特比特/二元码符号二元码符号 275.2.2 5.2.2 变长编码定理变长编码定理 若对这个信源采用定长二元码编码，若对这个信源采用定长二

13、元码编码，要求编码效率达到要求编码效率达到96时，允许译码错误时，允许译码错误概率概率 285.2.3 5.2.3 最佳变长编码最佳变长编码最佳变长编码最佳变长编码 凡凡是是能能载载荷荷一一定定的的信信息息量量，且且码码字字的的平平均均长长度度最最短短，可可分分离离的的变变长长码码的的码码字字集集合合称为称为最佳变长码最佳变长码。295.2.3 5.2.3 最佳变长编码最佳变长编码能能获得最佳码的编码方法主要有：获得最佳码的编码方法主要有：n香农（香农（Shannon）n费诺（费诺（Fano）n哈夫曼（哈夫曼（Huffman）等）等 305.2.3 5.2.3 最佳变长编码最佳变长编码一、香农

14、一、香农（Shannon）编码）编码1、将信源消息符号按其出现的概率大小依次、将信源消息符号按其出现的概率大小依次排列排列2、确定满足下列不等式的整数码长、确定满足下列不等式的整数码长Ki。315.2.3 5.2.3 最佳变长编码最佳变长编码3.为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息个消息的累加概率的累加概率4.将累加概率将累加概率Pi变换成二进制数。变换成二进制数。5.取取Pi二进数的小数点后二进数的小数点后Ki位即为该消息位即为该消息符号的二进制码字。符号的二进制码字。325.2.3 5.2.3 最佳变长编码最佳变长编码信源消息信源消息符号符号ai符号概符号概率率(a

15、i)累加概累加概率率Pi-log p(ai)码码字字长长度度Ki码码字字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110例例4 设信源共设信源共7个符号消息，其概率和累加概率如下表所示。个符号消息，其概率和累加概率如下表所示。335.2.3 5.2.3 最佳变长编码最佳变长编码设以i=4为例，求得345.2.3 5.2.3 最佳变长编码最佳变长编码码元码元/符号符号比特比特/码元码元 信源符

16、号的平均码长为平均信息传输率为355.2.3 5.2.3 最佳变长编码最佳变长编码例5 设信源有3个符号,概率分布为(0.5,0.4,0.1)，写出其香农编码。解：由于p1=0.5，p2=0.4，p3=0.1 由 得 K1=1，K2=2，K3=4 累加概率为P1=0，P2=0.5，P3=0.9365.2.3 5.2.3 最佳变长编码最佳变长编码(0)10=(0)2，(0.5)10=(0.10)2(0.9)10=(0.1110)2，01010101101110K1=1，K2=2，K3=4得编码码字分别为0，10，1110。375.2.3 5.2.3 最佳变长编码最佳变长编码二、费诺二、费诺编码方

17、法编码方法费诺编码属于概率匹配编码费诺编码属于概率匹配编码(1)将将信信源源消消息息符符号号按按其其出出现现的的概概率率大大小小依次排列：依次排列：。(2)将将依依次次排排列列的的信信源源符符号号按按概概率率值值分分为为两两大大组组，使使两两个个组组的的概概率率之之和和近近于于相相同同，并并对对各各组组赋赋予予一一个个二二进进制制码码元元“0”和和“1”。385.2.3 5.2.3 最佳变长编码最佳变长编码(3)将每一大组的信源符号进一步再分成两将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号相同，并又赋予

18、两个组一个二进制符号“0”和和“1”。(4)如此重复，直至每个组只剩下一个信源如此重复，直至每个组只剩下一个信源符号为止。符号为止。(5)信源符号所对应的码字即为费诺码。信源符号所对应的码字即为费诺码。395.2.3 5.2.3 最佳变长编码最佳变长编码例例6 对以下信源进行费诺编码对以下信源进行费诺编码。消消息息符符号号ai各各 个个 消消息息概概率率 p(ai)第一次第一次分分组组第二次第二次分分组组第三次第三次分分组组第四次第四次分分组组二元二元码码字字码长码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.1

19、01011104a70.01111114405.2.3 5.2.3 最佳变长编码最佳变长编码 码元码元/符号符号 bit/符号符号 信源符号的平均码长为平均信息传输率为415.2.3 5.2.3 最佳变长编码最佳变长编码 三、哈夫曼哈夫曼编码方法编码方法(1)将信源消息符号按其出现的概率大小依次排将信源消息符号按其出现的概率大小依次排列，列，(2)取两个概率最小的字母分别配以取两个概率最小的字母分别配以0和和1两个码两个码元，并将这两个概率相加作为一个新字母的概元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。率，与未分配的二进符号的字母重新排队。425.2.3 5

20、.2.3 最佳变长编码最佳变长编码(3)对对重重排排后后的的两两个个概概率率最最小小符符号号重重复复步步骤骤(2)的的过程。过程。(4)不不断断继继续续上上述述过过程程，直直到到最最后后两两个个符符号号配配以以0和和1为止。为止。(5)从从最最后后一一级级开开始始，向向前前返返回回得得到到各各个个信信源源符符号所对应的码元序列，即相应的码字。号所对应的码元序列，即相应的码字。435.2.3 5.2.3 最佳变长编码最佳变长编码例例7 对以下信源进行哈夫曼编码对以下信源进行哈夫曼编码 信源符号信源符号ai概率概率p(ai)码码字字Wi码长码长Kia10.20102a20.19112a30.180

21、003a40.170013a50.150103a60.1001104a70.0101114445.2.3 5.2.3 最佳变长编码最佳变长编码0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.010101010101010.200.190.180.170.150.100.01101100000101001100111455.2.3 5.2.3 最佳变长编码最佳变长编码 码元码元/符号符号

22、 bit/符号符号 信源符号的平均码长为平均信息传输率为465.2.3 5.2.3 最佳变长编码最佳变长编码哈夫曼编码方法得到的码并非唯一的哈夫曼编码方法得到的码并非唯一的n每每次次对对信信源源缩缩减减时时，赋赋予予信信源源最最后后两两个个概概率率最最小小的的符符号号，用用0和和1是是可可以以任任意意的的，所所以以可可以以得得到到不不同同的的哈哈夫夫曼曼码码，但但不不会会影影响码字的长度。响码字的长度。475.2.3 5.2.3 最佳变长编码最佳变长编码n对对信信源源进进行行缩缩减减时时，两两个个概概率率最最小小的的符符号号合合并并后后的的概概率率与与其其它它信信源源符符号号的的概概率率相相同

23、同时时，这这两两者者在在缩缩减减信信源源中中进进行行概概率率排排序序，其其位位置置放放置置次次序序是是可可以以任任意意的的，故故会会得得到到不不同同的的哈哈夫夫曼曼码码。此此时时将将影影响响码码字字的的长长度度，一一般般将将合合并并的的概概率率放放在在上上面面，这样可获得，这样可获得较小的码方差较小的码方差。485.2.3 5.2.3 最佳变长编码最佳变长编码香农编码3.140.831费诺编码费诺编码2.740.953哈夫曼编码哈夫曼编码2.720.96495.2.3 5.2.3 最佳变长编码最佳变长编码例例8 设有离散无记忆信源设有离散无记忆信源505.2.3 5.2.3 最佳变长编码最佳变

24、长编码0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.1010101010101010151525.2.3 5.2.3 最佳变长编码最佳变长编码信源符号信源符号ai概率概率p(ai)码码字字Wi1码长码长Ki1码码字字Wi2码长码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113哈夫曼编码535.2.3 5.2.3 最佳变长编码最佳变长编码由

25、此可见，第二种码的质量好。码码元元/符号符号 两种编码方法的平均码长和编码效率都相等,但两种码的质量不完全相同,可用码方差来表示。545.2.3 5.2.3 最佳变长编码最佳变长编码 进进行行哈哈夫夫曼曼编编码码时时，为为得得到到码码方方差差最最小小的的码码，应应使使合合并并的的信信源源符符号号位位于于缩缩减减信信源源序序列列尽尽可可能能高高的的位位置置上上，以以减减少少再再次次合合并的次数，充分利用短码。并的次数，充分利用短码。555.2.3 5.2.3 最佳变长编码最佳变长编码哈夫曼码是用哈夫曼码是用概率匹配概率匹配方法进行信源编码。方法进行信源编码。n哈哈夫夫曼曼码码的的编编码码方方法法

26、保保证证了了概概率率大大的的符符号号对对应应于于短短码码，概概率率小小的的符符号号对对应应于于长长码码，充分利用了短码；充分利用了短码；n缩缩减减信信源源的的最最后后二二个个码码字字总总是是最最后后一一位位不同，从而保证了不同，从而保证了哈夫曼码是即时码哈夫曼码是即时码。56m元霍夫曼码 前面讨论的二元霍夫曼码的编码方法,我们可以推广到m元编码中。不同的只是每次把概率最小的m个符号合并成一个新的信源符号，并分别用0，1，（m1）等码元表示。为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此对于m元编码，信源U符号个数n必须满足：n（m1）Qm 式中：n信源符号

27、个数；m进制数（码元数）；Q缩减次数。57下面给出m元霍夫曼编码步骤：(1)验证所给n是否满足式n（m1）Qm，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号；(2)取概率最小的m个符号合并成一个新结点，并分别用0，1，（m）给各分支赋值,把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复（2），如此下去直至树根。(4)取树根到叶子（信源符号对应结点）的各树枝上的赋值，得到各符号码字。58n【例9】已知离散无记忆信源 n=5，m=3，代入公式 n=(m-1)Q+m 得 Q=159信源熵：两种编码的平均码长分别为 因为lb31.58bit,

28、lb42bit，所以其编码效率分别为605.2.5.2.无失真信源编码无失真信源编码 无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源（信道的输入信源）尽可能为等概率分布，以使新信源的每个码符号平均所包含的信息量达到最大，从而使信道的信息传输率和信道容量相等，实现信源与信道理想的统计匹配，这也是香农第一定理的物理意义。615.3 限失真信源编码定理限失真信源编码定理 信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D。625.3 限失真信源编码定理限失真信源编码定理限失真信源编码定理：设离散

29、无记忆信源X的信息率失真函数R(D)，则当信息率RR(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D，为任意小的正数。反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于D。635.3 限失真信源编码定理限失真信源编码定理 如果是二元信源，对于任意小的，每一个信源符号的平均码长满足如下公式 645.3 限失真信源编码定理限失真信源编码定理 在失真限度内使信息率任意接近R(D)的编码方法存在。然而，要使信息率小于R(D)，平均失真一定会超过失真限度D。对于连续平稳无记忆信源，无法进行无失真编码，在限失真情况下，有与上述定理一样的编码定理。655.3 限失真信源编码定理限失真信源编码定理 限失真信源编码定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知。因而就不能象无损编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上迄今尚无合适的可实现的编码方法可接近R(D)这个界。66