第四章：无失真信源编码.

《第四章：无失真信源编码.》由会员分享，可在线阅读，更多相关《第四章：无失真信源编码.（113页珍藏版）》请在金锄头文库上搜索。

1、第四章：无失真信源编码,无失真信源编码,无失真编码概述 定长信源编码 变长信源编码 实用的无失真信源编码方法举例,4.1无失真编码概述1,离散、无失真、无记忆信源编码的一般模型：,总组合数：,总码组合数：,入,出,取值于同一个符号集， 符号集大小为n,取值于同一个符号集， 符号集大小为m,4.1无失真编码概述2,问题：能否进行无失真编码?怎样进行无失真编码? (前提：不考虑信源统计特性),应满足条件：,无失真条件变换,相互矛盾！,结论：当 n = m 时，KL 不有效。 当K = L 时，mn，亦不满足有效性,解决办法： 引入信源统计特性。,无失真：,有效：,4.1无失真编码概述3,考察无失真

2、条件：,等概条件下的消息符号熵,等概条件下的码字符号熵,考虑信源的实际统计特性（非等概），实际消息熵为：,代入无失真条件得：,结论：即使m=n,只要 就有可能实现KL。 即无失真与有效性同时满足。,具体实现方法：定长与变长编码,4.2定长编码定理1-描述,定长（等长）码信源编码定理： 对离散，无记忆、平稳、遍历信源其符号序列：S =(S1S2 SL)， 可用K个符号C =(C1C2CK) 进行等长编码，对任意0,0， 只要满足： 则：当L足够大时，可使译码差错小于， 反之，当 时，译码一定出错。,解释： 定长编码定理给出了信源进行等长编码所需码长的理论极限值。,结论：对信源进行二元等长编码时，

3、每个信源符号所需码长的极限值为,结论：对于唯一可译码，每个信源符号至少需要用 个码符号来变换。,4.2定长编码定理2-进一步理解,若要求所得的等长码是唯一可译的，则必须：,若L1，则：,当采用二元码编码时，m2，则：,4.2定长编码定理2-进一步理解,每个码字（码序列）所能携带的平均信息量,每个源序列所包含的平均不确定性。即：信源序列携带的信息量,等长有效性的无失真编码的条件：,码长下限：,为实现有效：,误码率任意小的方向：?,结论：只要码字能够携带的信息量大于信源序列携带的信息 量，总可以实现几乎无失真编码,考虑信源统计特性,讨论：第三章：在考虑符号出现的概率和符号间相关性前提下,每个 英文

4、符号平均携带的信息量是1.4bit/符号5bit/码符号。,4.2 定长编码定理3-举例,例1：英文电报有32个符号（266），即n=32， 若m=2，L1（即对信源的逐个符号进行二元编码）， 则：,bit,解释：每个英文电报符号至少需要用5位二元符号编码 （每位二元符号可以携带1bit信息，即每个英文电报符号用了可以携带 5bit信息的码符号即5位二元码表示）,问题：如何提高效率？如何体现有效性？,结论：若不考虑信源统计特性等长编码效率极低!,4.2定长编码定理4-进一步理解,解决方法：,字母个数为n，字母之间相关长度为L的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字

5、母组合，而且随着L的增加，这种无意义序列的总数越来越大。,进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 ,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。,考察：,方法：,问题：,会引入一定的误差！但当L足够长后，误差可以任意小。,4.2定长编码定理5证明,考察离散、随机序列信源的统计特性 渐进等分割性（AEP） AEP描述： 渐进等分割定理： （熵定理，遍历性定理） 设 是离散无记忆信源输出的一个特定序列，则任给 和 ，总可以找到一个整数 ，使当 时，有：,引入：渐进等分割性（AEP: Asymptotic Equipartit

6、ion Property ）,特定序列的平均符号自信息,随机矢量的平均符号熵,任何一个离散随机序列信源当序列长度L时,信源序列会产 生两极分化.小概率事件集合 与大概率事件集合 ,即nL= 对于 有性质: 对于 有性质:,由此可见，信源编码只需对信源中少数落入典型大概率事件的集合的符号进行编码即可。而对大多数属于非典型小概率事件集合中的信源符号无需编码.,4.2定长编码定理6 AEP物理意义,信源熵,大概率事件熵,4.2定长编码定理7 AEP证明,集合 和 中的序列分别称为 典型序列和 非典型序列,表示 中所有 典型序列的集合,表示 集合中序列的个数,可以证明：对于任意小的正数 ， ，当L足够

7、大时，,4.2定长编码定理7 AEP证明,还可以证明：对于任意小的正数 ， ，当L足够大时，,表示序列 出现的概率,由切比雪夫不等式可得：,表示S中每个符号携带的信息量的方差,例2 p(1)=p,p(0)=q,统计独立L长的序列: 当L8时，序列11000101和序列011100101 的概率为 和 显然，这两个序列不等概, 当L 时，有一些序列1出现的次数接近Lp，这些序列的概率为 且这些序列近似等概分布。,4.2定长编码定理8 AEP举例,L长的序列 ，对于任意小的正数 满足式 的序列称为 典型序列 即：典型序列集是哪些平均自信息任意小地接近信源熵的N长序列的集合,4.2定长编码定理9-

8、AEP应用,AEP结论：当L足够大时， 所有 典型序列出现的概率近似相等，即 典型序列为渐进等概序列 可粗略认为 典型序列出现的概率为 所有 典型序列的概率和接近为1，即 典型序列总数占信源序列的总数,4.2定长编码定理9- AEP应用,AEP应用： 提出、证明都是基于离散无记忆序列信源 平稳遍历信源有类似结果 体现信源统计特性 用以证明定长编码定理,4.2定长编码定理10 证明,定长编码定理证明思路： 将取自S，长为L的信源符号序列分为集合 和,几个概念：,编码信息率：,编码后对应于每个信源符号平均能载荷的最大信息量,编码效率：,编码前后平均每个信源符号能载荷的最大信息量之比,只对集合 中的

9、序列进行一一对应的等长编码,此时的误差为 ，计算误差,证明当 ，且 (K/L)log mH(S)+ 时，,4.2定长编码定理11（物理意义）,结论： 可推广至离散、非平稳无记忆信源和有记忆信源（即H(S)=H (S)）情况 只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码,二元码时，m2：,最佳等长码时：,4.2定长编码定理12（实际应用问题）,编译码同步问题 问题：如何使译码端知道码字起点 解决办法：1、每个码字加短同步前缀 2、每若干码字加较长同步前缀,分组长度与编译码复杂性、编译码延时等的关系 问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加 解决办法：

10、目前没有理想的解决办法,定长信源编码的理论意义远大于其实用价值,4.2定长编码定理13（举例),例3：设有一简单离散信源：L=1,n=2 对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低 于10-5，试求符号联合编码长度L=？,解：,由编码效率：,而：,则：,且：,则：,结论：可见,需要4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的.,一般来说：当L有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码,改变信源,定长编码,无失真信源编码实现方法一,无失真信源编码实现方法二,适应信源,变长编码,大概率短码；小概率长

11、码,4.3变长信源编码-1,几个码类的概念 非奇异码（单义码） 唯一可译码 前缀码（即时码、非延长码、异前置码） 最佳码（紧致码） Kraft定理即时码码长必须满足的条件 唯一可译码存在定理 变长编码定理（香农第一定理）,4.3变长信源编码-2(几个码类的概念),非奇异码（单义码）： 每一个码字仅对应信源中的一个信源符号（序列）。 编码是单义的。 反之为奇异码或非单义码。,4.3变长信源编码-3(几个码类的概念),唯一可译码 编码单义、译码单义 对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。 非奇异码=唯一可译码？,4.3变长信源编码

12、-4(几个码类的概念),前缀码 是唯一可译码中的一类 在一个变长码中，没有任何一个码字是其他码字的前缀。 译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。 又称即时码、非延时码 例如逗点码：1，01，001，0001,4.3变长信源编码-5(几个码类的概念),最佳码 唯一可译码的一类 其平均码长小于其他唯一可译码的平均长度,所有的码,非奇异码,唯一可译码,前缀码,最佳码,4.3变长信源编码-6（几种类型的信源编码举例） 例4：,定长 唯一可译,奇异,非奇异,前缀,唯一可译,4.3变长信源编码-7(Kraft定理),引出 码树构造即时码方法 Kraft定理描述即时码码长须满足的条件

13、Kraft定理证明略,实时唯一可译、可分离,A,B,A,B,B,B,B,B,A,A,C,D,D,E,D,100010111010111101010111001001101110,要求：须严格同步,4.3变长信源编码-8(Kraft定理引出),问题：寻求实时唯一可译码 方法：研究实时唯一可译码的码字可分离条件 简单信源：“码树”概念（直观） 一般信源：通过Kraft定理给出实时唯一可译码（前缀码）存在 的条件,码树变长码的树图表示,将变长码与码树建立“一一对应”关系： 树根码字起点 树枝数码的进制数 节点码字或码字的一部分 终止节点码字 节数码长 非满树变长码 满树等长码,利用码树构造前缀码,s

14、1,s2,s3,s4,0,1,1,1,0,0,0,10,110,111,s1,0.04,s4,s3,0.16,0.64,s2,0.16,4.3变长信源编码-9(Kraft定理),问题： 比较简单信源，码树方法可直接且直观构造前缀码 较复杂信源，直接画码树复杂且困难 解决方法： 为便于分析，特别对含有很多符号种类的复杂信源，寻找一种与上述“树图”等效的解析式表达式-Kraft不等式。 结论： Kraft定理给出码字可分离或前缀码存在的充要条件,4.3变长信源编码-10(Kraft定理),kraft定理：长度为Ki（i=1,2,n）的m （码字母表长度）进制前缀码存在的充要条件为： 证明：略 物理

15、意义： 给定信源个数N和码字母数m，只要允许码字长度可以足够长，就总可以满足Kraft不等式，从而得到前缀码。 只要适当选取码长，码字一定可以即时分离。,例5：,3 2 1 0,4 个叶子: 代表序列 1, 01, 001 和 000是前缀码,4.3变长信源编码-11(唯一可译码定理),Kraft不等式给出的限制也是所有唯一可译码都必须满足的。 定理描述： 任何唯一可译码均满足Kraft不等式。 结论： 唯一可译码一定满足kraft不等式 满足kraft不等式的码不一定是唯一可译码，但一定存在至少一种唯一可译码 对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码,4.3变长编码定理12,问题： 对于已知信源S可用码符号集X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择准则。 引入：码的平均长度。 离散无记忆平稳信源,信源熵