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

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

1、15.2 5.2 无失真信源编码 Yk平均每个符号的最大信息量为log m，KL长码字的最大信息量为KLlog m。用该码字表示L长的信源序列，则传送一个信源符号需要的信息率平均为 M为Y所能编成的码字的个数第1页/共66页25.2 5.2 无失真信源编码信息率最小:就是找到一种编码方式使 最小。无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码。第2页/共66页35.2 5.2 无失真信源编码无失真的信源编码定理定长编码定理变长编码定理 K是定值 且惟一可译码 编码的目的：寻找最小K K值。第3页/共66页45.2.1 5.2.1 定

2、长编码定理 由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL个符号Y1，Y2，Yk，YKL(每个符号有m种可能值)进行定长编码。对任意 0，0，只要 则当L足够大时，必可使译码差错小于；反之，当 时，译码差错一定是有限值，而L足够大时，译码几乎必定出错。第4页/共66页55.2.1 5.2.1 定长编码定理定长编码定理说明：码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L L足够大。第5页/共66页65.2.1 5.2.1 定长编码定理反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错

3、概率趋于零。时，则为临界状态，可能无失真，也可能有失真。第6页/共66页75.2.1 5.2.1 定长编码定理例:信源有8种等概率符号,L=1,信源序列熵达到最大值,H(x)=3bit/符号,即K=3bit/符号=H(x).当信源符号输出概率不相等时,若p(ai)=0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04,则H(x)=2.55bit/符号用22.55=5.856种可能的码字第7页/共66页85.2.1 5.2.1 定长编码定理 在这种编码方式下，若差错概率为Pe，据切比雪夫不等式可导出第8页/共66页95.2.1 5.2.1 定长编码定理式中 为自信息方差,为一

4、正数。当 和 均为定值时，只要L足够大，Pe可以小于任一正数。即，在这种编码方式下，若差错概率为Pe，据切比雪夫不等式可导出第9页/共66页105.2.1 5.2.1 定长编码定理当信源序列长度L满足 时，能达到差错率要求 第10页/共66页115.2.1 5.2.1 定长编码定理 在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。第11页/共66页125.2.1 5.2.1 定长编码定理定义为编码效率，即信源的平均符号熵为H(X)，采用平均符号码长为 来编码，所得的效率。编码效率总是小于1，且最佳编码效率为 第12页/共66页135

5、.2.1 5.2.1 定长编码定理 编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即 L取无限长第13页/共66页145.2.1 5.2.1 定长编码定理例1设离散无记忆信源概率空间为 比特/符号 第14页/共66页155.2.1 5.2.1 定长编码定理 对信源符号采用定长二元编码，要求编码效率为 90，若取L1，则可算出2.55 90%=2.8比特/符号Pe0.04 太大第15页/共66页165.2.1 5.2.1 定长编码定理若要求译码错误概率 第16页/共66页175.2.2 5.2.2 变长编码定理变长编码定理在变长编码中，码长K

6、是变化的 根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）第17页/共66页185.2.2 5.2.2 变长编码定理单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式第18页/共66页195.2.2 5.2.2 变长编码定理 离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中 为任意小正数。第19页/共66页205.2.2 5.2.2 变

7、长编码定理 用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。编码效率的下界:第20页/共66页215.2.2 5.2.2 变长编码定理 编码效率总是小于1 1，可以用它来衡量各种编码方法的优劣。为了衡量各种编码方法与最佳码的差距，定义码的剩余度为 第21页/共66页225.2.2 5.2.2 变长编码定理例2设离散无记忆信源的概率空间为第22页/共66页235.2.2 5.2.2 变长编码定理 若用二元定长编码(0，1)来构造一个即时码：。平均码长 1二元码符号/信源符号输出的信息效率为R0.811比特/二元码符号编码效率为第23页/共66页245.2.2 5.2

8、.2 变长编码定理例3.长度为2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表 aip(ai)即时码a1a19/160a1a23/1610a2a13/16110a2a21/16111第24页/共66页255.2.2 5.2.2 变长编码定理二元码符号/信源序列二元码符号/信源符号编码效率信息效率R20.961比特/二元码符号 第25页/共66页265.2.2 5.2.2 变长编码定理L3 R30.985比特/二元码符号 L4 R40.991比特/二元码符号 第26页/共66页275.2.2 5.2.2 变长编码定理 若对这个信源采用定长二元码编码，要求编码效率达到96时，允许译码错

9、误概率 第27页/共66页285.2.3 5.2.3 最佳变长编码最佳变长编码 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。第28页/共66页295.2.3 5.2.3 最佳变长编码能获得最佳码的编码方法主要有：香农（Shannon）费诺（Fano）哈夫曼（Huffman）等 第29页/共66页305.2.3 5.2.3 最佳变长编码一、香农（Shannon）编码1、将信源消息符号按其出现的概率大小依次排列2、确定满足下列不等式的整数码长Ki。第30页/共66页315.2.3 5.2.3 最佳变长编码3.为了编成唯一可译码，计算第i个消息的累加概率4.

10、将累加概率Pi变换成二进制数。5.取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。第31页/共66页325.2.3 5.2.3 最佳变长编码信源消息信源消息符号符号ai符号概符号概率率(ai)累加概累加概率率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个符号消息，其概率和累加概率如下表所示。第32页/共66页33

11、5.2.3 5.2.3 最佳变长编码设以i=4为例，求得第33页/共66页345.2.3 5.2.3 最佳变长编码码元/符号比特/码元 信源符号的平均码长为平均信息传输率为第34页/共66页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.9第35页/共66页365.2.3 5.2.3 最佳变长编码(0)10=(0)2，(0.5)10=(0.10)2(0.9)10=(0.1110)2，010101

12、01101110K1=1，K2=2，K3=4得编码码字分别为0，10，1110。第36页/共66页375.2.3 5.2.3 最佳变长编码二、费诺编码方法费诺编码属于概率匹配编码(1)将信源消息符号按其出现的概率大小依次排列：。(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。第37页/共66页385.2.3 5.2.3 最佳变长编码(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4)如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码

13、字即为费诺码。第38页/共66页395.2.3 5.2.3 最佳变长编码例6 对以下信源进行费诺编码。消消息息符符号号ai各各 个个 消消息息概概率率 p(ai)第一次第一次分组分组第二次第二次分组分组第三次第三次分组分组第四次第四次分组分组二元二元码字码字码长码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114第39页/共66页405.2.3 5.2.3 最佳变长编码 码元/符号 bit/符号 信源符号的平均码长为平均信息传输率为第40页/共66页415.2.3 5.2.3

14、 最佳变长编码 三、哈夫曼编码方法(1)将信源消息符号按其出现的概率大小依次排列，(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。第41页/共66页425.2.3 5.2.3 最佳变长编码(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。第42页/共66页435.2.3 5.2.3 最佳变长编码例7 对以下信源进行哈夫曼编码 信源符号信源符号ai概率概率p(ai)码字码字Wi码长码长

15、Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114第43页/共66页445.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.01101100000101001100111第44页/共

16、66页455.2.3 5.2.3 最佳变长编码 码元/符号 bit/符号 信源符号的平均码长为平均信息传输率为第45页/共66页465.2.3 5.2.3 最佳变长编码哈夫曼编码方法得到的码并非唯一的每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。第46页/共66页475.2.3 5.2.3 最佳变长编码对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较

17、小的码方差。第47页/共66页485.2.3 5.2.3 最佳变长编码香农编码3.140.831费诺编码费诺编码2.740.953哈夫曼编码哈夫曼编码2.720.96第48页/共66页495.2.3 5.2.3 最佳变长编码例8 设有离散无记忆信源第49页/共66页505.2.3 5.2.3 最佳变长编码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.10101010101010101第50页/共66页51第51页/共6

18、6页525.2.3 5.2.3 最佳变长编码信源符号信源符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113哈夫曼编码第52页/共66页535.2.3 5.2.3 最佳变长编码由此可见，第二种码的质量好。码元/符号 两种编码方法的平均码长和编码效率都相等,但两种码的质量不完全相同,可用码方差来表示。第53页/共66页545.2.3 5.2.3 最佳变长编码 进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置

19、上，以减少再次合并的次数，充分利用短码。第54页/共66页555.2.3 5.2.3 最佳变长编码哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。第55页/共66页56m元霍夫曼码 前面讨论的二元霍夫曼码的编码方法,我们可以推广到m元编码中。不同的只是每次把概率最小的m个符号合并成一个新的信源符号，并分别用0，1，（m1）等码元表示。为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此对于m元编码，信源U符号个数n必须

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

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

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