第3章 无失真信源编码.ppt

第3章 无失真信源编码,第1节 几个概念 第2节 单义可译码 第3节 非延长码及其构造 第4节 单义可译性定理 第5节 编码长度和编码效率 第6节 平均码长的界限定理 第7节 Huffman编码 第8节 香农编码 第9节 费诺编码 第10节 行程编码 Lemple_Ziv编码,1 信源符号的码字：用来表示信源符号的数字序列W,如在ASCII码中，a编码成：,2 信源符号码字长度：用来表示信源符号的数字序列长度,如：,第1节 几个概念,4 变长码：各符号用不同长度的码字表示,第1节 几个概念,3 定长码：所有的符号用相同长度的码字表示,第1节 几个概念,5 信源码符号：信源编码中构成信源码字的符号集,A={0,1},A={0,1,2},,,信源,编码器,信道,1、编码原理方框图,设信源发出的符号集S={s1,s2,…,sq}，每个信源符号编码成一个信源码字，对应的码字集为W={w1,w2,…,wq}，每个码字均由信源码符号集A={a1,a2,…,ar}中的元素组成第2节 单义可译码,如,2、单义可译码,如果所有的码字与信源符号一一对应，并且连续的码字符号 也与连续的信源符号一一对应，则称编码为单义可译编码。

定义：,第2节 单义可译码,第2节 单义可译码,例：若信源符号为：A BAD CAB，则可编码为：,FLC,VLC,这两种编码都是单义可译码 VLC比FLC效率高,0 1 0 01 00 0 1 A B A D C A B 01 00 10 00 1 D C E C B 01 00 1 000 1 D C B G B,若接收符号序列为：010010001，则可能有很多种可能的译码如：,3) 例子,第2节 单义可译码,第2节 单义可译码,说明： 1、单义可译码的要求一定：信源码字与信源符号一一对应；信源符号序列与信源码字序列一一对应 2、通常情况下，变长码具有较高的效率（平均码字程度小）问题： 如何判断及构造单义可译码？,第2节 单义可译码,1) 前缀编码条件：任何一个有效信源码字不可能是其它有效码字的前缀3、前缀编码：是一种单义可译码,2) 前缀编码：满足前缀编码条件的信源编码称为前缀编码,问题：前缀编码,1、非延长码定义,第3节 非延长码及其构成,这两种编码都是单义可译码,第3节 非延长码及其构成,例：1001011001101……,非延长码：也叫即时码，是指接收到码字后能立刻确定对应的符号。

编码1：100,10,1,100,1,10,1……,编码2：1,001,01,1,001,1,01……,第3节 非延长码及其构成,2 说明： 1、非延长码也叫即时码，是一种单义可译码 2、非延长码也是前缀编码，满足前缀编码条件 3、任何一种单义可译码总可以找到一种对应的具有相同码字长度的非延长码,任何一个有效码字所对应的点，不能经过另外一个有效码字对应的点第3节 非延长码及其构成,3、非延长码的树图构造法,1、Kraft不等式,若ni代表一种单义可译信源编码中信源符号si对应的码字wi的长度，r代表信源码符号数则下面不等式一定成立,如信源码符号集,则,如信源码符号集,则,第4节 单义可译定理,第4节 单义可译定理,2、单义可译性定理,任何一种单义可译编码，必满足克拉夫不等式；同样，只要码字长度满足克拉夫不等式，至少可以找到一种单义可译编码说明：满足kraft不等式的编码不一定为非延长码第4节 单义可译定理,第4节 单义可译定理,3、图解,第4节 单义可译定理,例题：,1、已知信源码字长度分别为以下各值，至少能够找到一种单义可译码的是 （ ） A 1，1，3，4 B 1，2，2，3 C 1，3，3，2 D 1，2，2，2,2、下面哪种说法是不正确的 （ ） A 任何满足Kraft不等式的编码一定是前缀编码。

B 任何前缀编码一定满足Kraft不等式 C 前缀编码条件是：任何一个有效信源码字不能是其它有效信源码字的前缀 D 若某信源编码要求的编码长度满足Kraft不等式，则至少可以找到一种前缀编码第4节 单义可译定理,2、平均码字长度，平均每个信源符号对应码字的长度,1、模型,第5节 平均码长与编码有效性,信源码符号/信源码字,平均每个信源码字由几个信源码符号组成,第5节 平均码长与编码有效性,3、码率,1) 信源的熵,平均每个信源符号所携带的信息量,2) 信息率,平均每个信源信源码符号携带多少比特的信息量,第5节 平均码长与编码有效性,4、说明,1) 假设信道码符号集为A={0,1}，则每个信源码符号最多携带1比特的信息量2) 假设信道码符号集为A={0,1,2}，则每个信源码符号最多携带log3比特的信息量例：p373,已知信源空间为,信道符号空间,对应的码字长度分别为n1, n2,,n3, n4写出一种有效编码，并求对应的信息率,第5节 平均码长与编码有效性,1) 利用二叉树单义可译码,2) 信源的熵,3) 平均码字长度,4) 信息率,第5节 平均码长与编码有效性,讨论：,平均码字长度,信息率,第5节 平均码长与编码有效性,P408 T4 P409 T6,作业：,平均码字长度越小越好，但是对于一种给定信源，其平均码字长度是受到该信源的熵影响的。

1、平均码字长度的界限定理,第6节 平均码长的界限定理,2、证明下界,1) 分析,,第6节 平均码长的界限定理,2) 证明：,第6节 平均码长的界限定理,3、上界证明,取码字wi长度为ni，满足：,因为,，满足克拉夫不等式所以满足条件的单义可译码总可以找到第6节 平均码长的界限定理,第6节 平均码长的界限定理,第6节 平均码长的界限定理,说明：平均码字长度×平均每个码符号最多携带的信息量≤平均每个信源符号携带的信息量,说明：平均码字长度小于该量的单义可译码一定可以找到，平均码字大于该量的信源编码效率低例 考虑一个信源 X， 发出四种符号的概率分别为：p1=0.5, p2=0.3, p3=0.1 ， p4=0.1其非延长码编码为 {0,10,110,111}找出这种编码的平均码字长度及信道的信息率第6节 平均码长的界限定理,第6节 平均码长的界限定理,比特/信源符号,信源码符号/信源码字,比特/信源码符号,4、推广到一般情况,假设同时对N个信源符号编码，则得到：,,当,时，有：,第6节 平均码长的界限定理,1、说明,Huffman编码是1952年由Huffman提出的一种变长码，它的基本假设前提是：我们事先知道信源发送每种符号的概率。

第7节 Huffman 编码,2、模型,第7节 Huffman 编码,3、二进制Huffman编码步骤,1) 将信源符号按概率的降序排列,2) 将最底端的两个符号连接起来，上面一支标注“0”，下面一支标注“1”先假设信源码符号为二进制符号，即：,3) 将两个符号的和的概率作为一个新的合成符号的概率，并将合成符号与剩余的符号按降序排列,第7节 Huffman 编码,4) 重复步骤2)和3)，直到只剩下一个合成符号,5) 从每个符号出发，按顺序读出到末端的所有标注，并将标注序列的逆序作为该信源符号的编码第7节 Huffman 编码,第7节 Huffman 编码,例：考虑一个DMS信源，其概率空间为：,信道符号集为X={0,1}.写出这个信源的Huffman编码并求码率1) Huffman编码,,,,,,,,1.0,第7节 Huffman 编码,2) 信息率,讨论1：若将两个符号连接起来后，将上支标注“1”而将下支标注“0”编码是否仍为非延长码？编码效率有何变化？,第7节 Huffman 编码,结论： 1、将两个符号连接起来后，将上支标注“1”而将下支标注“0”。

编码仍为非延长码，编码效率不变 2、Huffman编码不唯一第7节 Huffman 编码,例：,信道符号集为X={0,1}.写出这个信源的Huffman编码并求码率例：考虑一个DMS信源，其概率空间为：,1) Huffman编码,第7节 Huffman 编码,第7节 Huffman 编码,2) 信息率,第7节 Huffman 编码,讨论2：若有两个信源符号概率相同，该如何编码？,原则： 1、一般情况下相等概率信源符号之间的顺序可随意，得到的编码效率相同 1、最好将合成符号放在最上面，这样编码得到的码长方差最小第7节 Huffman 编码,说明： 信源编码平均码字长度越小越好，平均码长方差越小越好码长方差定义为：,第7节 Huffman 编码,例：考虑一个DMS信源，其概率空间为：,信道符号集为X={0,1}.写出这个信源的Huffman编码并求码率第7节 Huffman 编码,1) Huffman编码,,1.0,编码一：将合成符号放在最上面,第7节 Huffman 编码,第7节 Huffman 编码,2) 信息率,第7节 Huffman 编码,1) Huffman编码,,1.0,,编码二：将合成符号放在最下面,第7节 Huffman 编码,第7节 Huffman 编码,2) 信息率,第7节 Huffman 编码,说明：,两种编码的码率相同，但码长方差不同。

第7节 Huffman 编码,4、r进制Huffman编码步骤,1) 将信源符号按降序排列，若信源符号个数q=α(r-1)+r,则直接到步骤2)；若信源符号个数不满足q=α(r-1)+r,则适当增加几个概率为0的虚拟符号，使得总信源符号数满足q´=α(r-1)+r,先假设信道符号为r进制符号，即：,第7节 Huffman 编码,2) 将最底端的r个符号连接起来，各支按照从上到下的顺序标注0，1，…，(r-1)3) 将r个符号的和的概率作为一个新的合成符号的概率，并将合成符号与剩余的符号按降序排列,4) 重复步骤2)和3)，直到只剩下一个合成符号,5) 从每个符号出发，按顺序读出到末端的所有标注，并将标注序列的逆序作为该信源符号的编码第7节 Huffman 编码,第7节 Huffman 编码,例：P409 T10 英文字母A,B,C,D,E,F表示不同的颜色，组成以下的图形,试用符号集X＝{0,1,2}对A,B,C,D,E,F进行编码第7节 Huffman 编码,1) 信源符号概率分布:,2) Huffman编码,第7节 Huffman 编码,3) 平均码字长度,第7节 Huffman 编码,讨论：,若不增加虚拟符号，会怎么样？,第7节 Huffman 编码,平均码字长度,5、扩展信源符号编码,一种更有效的编码方法是同时对N个信源符号进行编码。

例：考虑一个信源，各符号及相应的概率如下所示，信道符号集为X＝{0，1},第7节 Huffman 编码,第7节 Huffman 编码,信源的熵为：,平均码字长度为：,信息率,第7节 Huffman 编码,如果同时对两个符号进行编码，其概率密度及Huffman编码如下图所示：,平均每个信源符号对应的信源码符号数,信息率,第7节 Huffman 编码,信源的熵为：,结论：,同时对N个符号进行编码，编码效率更高Huffman编码小结 1、二进制编码讨论：0，1互换时情况几个符号具有相同概率情况 2、多进制情况 3、扩展信源符号同时编码第7节 Huffman 编码,作业：,P410 T11 P409 T5 (1) (2)N=2,第8节 香农编码,1、信源,按降序排列得到，因此该假设不失一般性。