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

《无失真和限失真信源编码.ppt》由会员分享，可在线阅读，更多相关《无失真和限失真信源编码.ppt（66页珍藏版）》请在三一办公上搜索。

1、1,5.2 无失真信源编码,信源输出 X(X1X2XlXL)，Xla1，a2，ai，an编码为 Y(Y1Y2Yk YkL)，Ykb1，b2，bj，bm 要求能够无失真或无差错地译码，同时传送Y时所需要的信息率最小。,2,5.2 无失真信源编码,Yk平均每个符号的最大信息量为log m，KL长码字的最大信息量为KLlog m。用该码字表示L长的信源序列，则传送一个信源符号需要的信息率平均为,M为Y所能编成的码字的个数,3,5.2 无失真信源编码,信息率最小:就是找到一种编码方式使 最小。无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码。

2、,4,5.2 无失真信源编码,无失真的信源编码定理定长编码定理变长编码定理,K是定值 且惟一可译码 编码的目的：寻找最小K值。,5,5.2.1 定长编码定理,由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL个符号Y1，Y2，Yk，YKL(每个符号有m种可能值)进行定长编码。对任意0，0，只要 则当L足够大时，必可使译码差错小于；反之，当 时，译码差错一定是有限值，而L足够大时，译码几乎必定出错。,6,5.2.1 定长编码定理,定长编码定理说明：,码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。,7,5.2.1

3、 定长编码定理,反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，也可能有失真。,8,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种可能的码字,9,5.2.1 定长编码定理,在这种编码方式下，若差错概率为Pe，据切比雪夫不等式可导出,10,5.2.1 定长编

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

5、近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即,L取无限长,15,5.2.1 定长编码定理,例1设离散无记忆信源概率空间为,比特/符号,16,5.2.1 定长编码定理,对信源符号采用定长二元编码，要求编码效率为 90，若取L1，则可算出,2.55 90%=2.8比特/符号,Pe0.04 太大,17,5.2.1 定长编码定理,若要求译码错误概率,18,5.2.2 变长编码定理,变长编码定理在变长编码中，码长K是变化的 根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）,19,5.2.2 变长编码定理

6、,单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式,20,5.2.2 变长编码定理,离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中为任意小正数。,21,5.2.2 变长编码定理,用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。编码效率的下界:,22,5.2.2 变长编码定理,编码效率总是小于1，可以用它来衡量各种编码方法的优劣。为了衡量各种编码方法与最佳码的差距，定义码的剩余度

7、为,23,5.2.2 变长编码定理,例2设离散无记忆信源的概率空间为,24,5.2.2 变长编码定理,若用二元定长编码(0，1)来构造一个即时码：。平均码长 1二元码符号/信源符号,输出的信息效率为R0.811比特/二元码符号,编码效率为,25,5.2.2 变长编码定理,例3.长度为2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表,26,5.2.2 变长编码定理,二元码符号/信源序列,二元码符号/信源符号,编码效率,信息效率R20.961比特/二元码符号,27,5.2.2 变长编码定理,L3 R30.985比特/二元码符号 L4 R40.991比特/二元码符号,28,5.2.2 变

8、长编码定理,若对这个信源采用定长二元码编码，要求编码效率达到96时，允许译码错误概率,29,5.2.3 最佳变长编码,最佳变长编码 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。,30,5.2.3 最佳变长编码,能获得最佳码的编码方法主要有：香农（Shannon）费诺（Fano）哈夫曼（Huffman）等,31,5.2.3 最佳变长编码,一、香农（Shannon）编码1、将信源消息符号按其出现的概率大小依次排列2、确定满足下列不等式的整数码长Ki。,32,5.2.3 最佳变长编码,为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。

9、取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。,33,5.2.3 最佳变长编码,例4 设信源共7个符号消息，其概率和累加概率如下表所示。,34,5.2.3 最佳变长编码,设以i=4为例，求得,35,5.2.3 最佳变长编码,码元/符号,比特/码元,信源符号的平均码长为,平均信息传输率为,36,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,37,5.2.3 最佳变长编码,(0)10=(0)2，

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

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

12、应的码元序列，即相应的码字。,44,5.2.3 最佳变长编码,例7 对以下信源进行哈夫曼编码,45,5.2.3 最佳变长编码,46,5.2.3 最佳变长编码,码元/符号,bit/符号,信源符号的平均码长为,平均信息传输率为,47,5.2.3 最佳变长编码,哈夫曼编码方法得到的码并非唯一的每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。,48,5.2.3 最佳变长编码,对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼

13、码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。,49,5.2.3 最佳变长编码,50,5.2.3 最佳变长编码,例8 设有离散无记忆信源,51,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.1,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.20.1,52,53,5.2.3 最佳变长编码,哈夫曼编码,54,5.2.3 最佳变长编码,由此可见，第二种码的质量好。,码元/符号,两种编码方法的平均码长和编码效率都相等,但两种

14、码的质量不完全相同,可用码方差来表示。,55,5.2.3 最佳变长编码,进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。,56,5.2.3 最佳变长编码,哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。,57,m元霍夫曼码,前面讨论的二元霍夫曼码的编码方法,我们可以推广到m元编码中。不同的只是每次把概率最小的m个符号合并成一个新的信源符号，并分别用0，1，（m1）等码元表

15、示。为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此对于m元编码，信源U符号个数n必须满足：n（m1）Qm 式中：n信源符号个数；m进制数（码元数）；Q缩减次数。,58,下面给出m元霍夫曼编码步骤：,(1)验证所给n是否满足式n（m1）Qm，若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号；(2)取概率最小的m个符号合并成一个新结点，并分别用0，1，（m）给各分支赋值,把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复（2），如此下去直至树根。(4)取树根到叶子（信源符号对应结点）的各树枝上的赋值，得到各

16、符号码字。,59,【例9】已知离散无记忆信源,n=5，m=3，代入公式 n=(m-1)Q+m 得 Q=1,60,信源熵：,两种编码的平均码长分别为,因为lb31.58bit,lb42bit，所以其编码效率分别为,61,5.2.无失真信源编码,无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源（信道的输入信源）尽可能为等概率分布，以使新信源的每个码符号平均所包含的信息量达到最大，从而使信道的信息传输率和信道容量相等，实现信源与信道理想的统计匹配，这也是香农第一定理的物理意义。,62,5.3 限失真信源编码定理,信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；

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