《无失真信源编码》PPT课件.ppt

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

1、第五章第五章 无失真信源编码无失真信源编码本章需要掌握的内容：本章需要掌握的内容：编码的目的编码的目的编码的目的编码的目的 离散无记忆信源的定长编码离散无记忆信源的定长编码离散无记忆信源的定长编码离散无记忆信源的定长编码 离散无记忆信源的变长编码定理离散无记忆信源的变长编码定理离散无记忆信源的变长编码定理离散无记忆信源的变长编码定理 变长编码的变长编码的变长编码的变长编码的HuffmanHuffman编码方法编码方法编码方法编码方法一一.信源编码信源编码第一节第一节 信源编码和码的类型信源编码和码的类型信源编码信源编码信源编码信源编码无失真信源编码无失真信源编码无失真信源编码无失真信源编码限失

2、真信源编码限失真信源编码限失真信源编码限失真信源编码1.1.1.1.信源编码的概念信源编码的概念信源编码的概念信源编码的概念编码：编码：编码：编码：将携带信息的一种符号序列按照一定规则映射成另将携带信息的一种符号序列按照一定规则映射成另将携带信息的一种符号序列按照一定规则映射成另将携带信息的一种符号序列按照一定规则映射成另一种符号序列的变换。一种符号序列的变换。一种符号序列的变换。一种符号序列的变换。信源编码信源编码信源编码信源编码:根据信源的统计特性对信源发出的信息进行编码。根据信源的统计特性对信源发出的信息进行编码。根据信源的统计特性对信源发出的信息进行编码。根据信源的统计特性对信源发出的

3、信息进行编码。3.3.3.3.编码器的数学模型编码器的数学模型编码器的数学模型编码器的数学模型信源编码器信源编码器 信源发出的消息符号集信源发出的消息符号集输出的码字集合输出的码字集合C C（代码组）（代码组）信道的基本符号集合信道的基本符号集合其中：其中：其中：其中：W W W Wi i i i称为称为称为称为码字码字码字码字，如果码字由，如果码字由，如果码字由，如果码字由N N N N个码元组成，则码长为个码元组成，则码长为个码元组成，则码长为个码元组成，则码长为N N N N。称为称为称为称为码元码元码元码元,或码符号或码符号或码符号或码符号2.2.信源编码目的信源编码目的信源编码目的信

4、源编码目的压缩信源剩余度，提高传输消息的有效性，把消息变成压缩信源剩余度，提高传输消息的有效性，把消息变成压缩信源剩余度，提高传输消息的有效性，把消息变成压缩信源剩余度，提高传输消息的有效性，把消息变成适合信道传输的信号。适合信道传输的信号。适合信道传输的信号。适合信道传输的信号。2.2.二元码：二元码：二元码：二元码：3.3.定长码：定长码：定长码：定长码：8.8.非同价码：非同价码：非同价码：非同价码：信道的基本符号集中码元个数为信道的基本符号集中码元个数为信道的基本符号集中码元个数为信道的基本符号集中码元个数为2 2 每个码元所占的传输时间不完全相同每个码元所占的传输时间不完全相同每个码

5、元所占的传输时间不完全相同每个码元所占的传输时间不完全相同7.7.同价码：同价码：同价码：同价码：每个码元所占的传输时间相同每个码元所占的传输时间相同每个码元所占的传输时间相同每个码元所占的传输时间相同6.6.奇异码：奇异码：奇异码：奇异码：码中码字至少有两个相同码中码字至少有两个相同码中码字至少有两个相同码中码字至少有两个相同5.5.非奇异码：非奇异码：非奇异码：非奇异码：码中所有的码字都不相同码中所有的码字都不相同码中所有的码字都不相同码中所有的码字都不相同4.4.变长码：变长码：变长码：变长码：码中的码字长短不一码中的码字长短不一码中的码字长短不一码中的码字长短不一码中所有码字的长度都相

6、同码中所有码字的长度都相同码中所有码字的长度都相同码中所有码字的长度都相同二二.码的类型码的类型1.1.1.1.分组码：分组码：分组码：分组码：将信源符号集中的每个信源组符号映射成一个固定的码字将信源符号集中的每个信源组符号映射成一个固定的码字将信源符号集中的每个信源组符号映射成一个固定的码字将信源符号集中的每个信源组符号映射成一个固定的码字 例例例例5-15-1：设有二元信道的信源编码器，其概率空间：设有二元信道的信源编码器，其概率空间：设有二元信道的信源编码器，其概率空间：设有二元信道的信源编码器，其概率空间编码后的结果：编码后的结果：编码后的结果：编码后的结果：信源符号信源符号Si Si

7、 码码1 1 码码2 2 码码3 3 码码4 4 S S1 1 00 0 0 0 00 0 0 0 S S2 2 01 01 11 1001 01 11 10 S S3 3 10 001 00 00 10 001 00 00 S S4 4 11 111 11 10 11 111 11 10定长码定长码定长码定长码非奇异码非奇异码非奇异码非奇异码非奇异非奇异非奇异非奇异码变长码变长码变长码变长码码码码变长码变长码变长码变长码奇异码奇异码奇异码奇异码次扩展码（类似次扩展码（类似次扩展码（类似次扩展码（类似N N次扩展信源）次扩展信源）次扩展信源）次扩展信源）举例：举例：举例：举例：10.10.10

8、.10.唯一可译码：唯一可译码：唯一可译码：唯一可译码：一个分组码若对任意有限的整数一个分组码若对任意有限的整数N,N,其其N N次扩展码均为非奇异码，次扩展码均为非奇异码，则称为唯一可译码。则称为唯一可译码。或每个信源符号序列映射成一个固定的码字，并且代码组中每或每个信源符号序列映射成一个固定的码字，并且代码组中每个码字只能唯一地被译成所对应的信源符号序列。个码字只能唯一地被译成所对应的信源符号序列。11.11.11.11.即时码：即时码：即时码：即时码：无需考虑后续的码符号即可从码符号序列中译出码字，这样无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码，又称非延时

9、码。的唯一可译码称为即时码，又称非延时码。*唯一可译码要成为即时码的条件：唯一可译码要成为即时码的条件：唯一可译码要成为即时码的条件：唯一可译码要成为即时码的条件：其中任一码字都不是其他码字的前缀其中任一码字都不是其他码字的前缀其中任一码字都不是其他码字的前缀其中任一码字都不是其他码字的前缀即时码可用树图构造：即时码可用树图构造：即时码可用树图构造：即时码可用树图构造：树根树根一阶节点一阶节点二阶节点二阶节点 三阶节点三阶节点(终端节点终端节点)A00011010111001000111110101100011010001(1)(1)(1)(1)树图的最顶部的节点称为树图的最顶部的节点称为树图

10、的最顶部的节点称为树图的最顶部的节点称为树根树根树根树根，树枝的尽头称为树枝的尽头称为树枝的尽头称为树枝的尽头称为节点节点节点节点(2)(2)(2)(2)每个节点的分支数等于码元数每个节点的分支数等于码元数每个节点的分支数等于码元数每个节点的分支数等于码元数，且各分支分别对应一个固定的码元，各分，且各分支分别对应一个固定的码元，各分，且各分支分别对应一个固定的码元，各分，且各分支分别对应一个固定的码元，各分支伸出方向所对应的码元是支伸出方向所对应的码元是支伸出方向所对应的码元是支伸出方向所对应的码元是统一统一统一统一的，如图向左伸出为的，如图向左伸出为的，如图向左伸出为的，如图向左伸出为0 0

11、 0 0，向右伸出为，向右伸出为，向右伸出为，向右伸出为1 1 1 1。(3)(3)各码字分布在码树的各码字分布在码树的各码字分布在码树的各码字分布在码树的终端节点终端节点终端节点终端节点(即不再分支的节点即不再分支的节点即不再分支的节点即不再分支的节点)。(4)(4)节点一旦被分配码字，后边的枝便要节点一旦被分配码字，后边的枝便要节点一旦被分配码字，后边的枝便要节点一旦被分配码字，后边的枝便要去掉去掉去掉去掉，否则成为非即时码。，否则成为非即时码。，否则成为非即时码。，否则成为非即时码。有一离散无记忆信源输出为有一离散无记忆信源输出为有一离散无记忆信源输出为有一离散无记忆信源输出为N N长符

12、号序列，信道基本符长符号序列，信道基本符长符号序列，信道基本符长符号序列，信道基本符号号号号r r个，信源输出符号个数为个，信源输出符号个数为个，信源输出符号个数为个，信源输出符号个数为q q，则，则，则，则存在存在存在存在唯一可译码的充要条唯一可译码的充要条唯一可译码的充要条唯一可译码的充要条件为：件为：件为：件为：第二节第二节 离散无记忆信源的定长编码离散无记忆信源的定长编码一一.离散无记忆信源的唯一可译码存在条件离散无记忆信源的唯一可译码存在条件结论结论结论结论:当码长为当码长为当码长为当码长为l l的码元序列的个数不小于信源输出的的码元序列的个数不小于信源输出的的码元序列的个数不小于信

13、源输出的的码元序列的个数不小于信源输出的N N长长长长序列的个数时序列的个数时序列的个数时序列的个数时,才存在唯一可译码才存在唯一可译码才存在唯一可译码才存在唯一可译码.由由表明表明表明表明:对于定长唯一可译码对于定长唯一可译码对于定长唯一可译码对于定长唯一可译码,每个信源输出的每个信源输出的每个信源输出的每个信源输出的符号序列符号序列符号序列符号序列经编经编经编经编码后的码字的码长至少为码后的码字的码长至少为码后的码字的码长至少为码后的码字的码长至少为Nlogq/logr,Nlogq/logr,如果小于如果小于如果小于如果小于Nlogq/logrNlogq/logr,则则则则唯一可译码不存在

14、唯一可译码不存在唯一可译码不存在唯一可译码不存在.表示平均每个信源符号至表示平均每个信源符号至表示平均每个信源符号至表示平均每个信源符号至少用少用少用少用logq/logrlogq/logr个码元来表示个码元来表示个码元来表示个码元来表示 例例例例5-25-25-25-2：英文电报有英文电报有英文电报有英文电报有3232个符号个符号个符号个符号(26(26个字母加上个字母加上个字母加上个字母加上6 6个字符个字符个字符个字符),),请问请问请问请问对对对对信源符号进行二进制编码，要想有唯一可译码，码长至少为信源符号进行二进制编码，要想有唯一可译码，码长至少为信源符号进行二进制编码，要想有唯一可

15、译码，码长至少为信源符号进行二进制编码，要想有唯一可译码，码长至少为多少？多少？多少？多少？解：解：解：解：r=2,q=32,N=1 r=2,q=32,N=1 r=2,q=32,N=1 r=2,q=32,N=1，要想有唯一可译码，则要想有唯一可译码，则要想有唯一可译码，则要想有唯一可译码，则二、定长编码定理二、定长编码定理进行长度为进行长度为 的的定长编码，定长编码，对对用码元集用码元集设离散无记忆信源设离散无记忆信源的熵为的熵为H(S)H(S)，其，其N N次扩展次扩展对于对于只要满足只要满足(正定理正定理)则当则当N N足够大时，几乎可实现无失真信源编码，此时译码差错足够大时，几乎可实现无

16、失真信源编码，此时译码差错小于小于。反之，若反之，若则当则当N N足够大时，译码错误概率趋于足够大时，译码错误概率趋于1(1(编码误差任意大编码误差任意大)（逆定理）（逆定理）信源为信源为例例例例5-35-35-35-3：仍以英文电报为例，当认为各符号是等概分布时的熵为仍以英文电报为例，当认为各符号是等概分布时的熵为仍以英文电报为例，当认为各符号是等概分布时的熵为仍以英文电报为例，当认为各符号是等概分布时的熵为 ，但是考虑相关性后英文信源的极限熵为，但是考虑相关性后英文信源的极限熵为，但是考虑相关性后英文信源的极限熵为，但是考虑相关性后英文信源的极限熵为 那么对它们进行定长编码时，那么对它们进

17、行定长编码时，那么对它们进行定长编码时，那么对它们进行定长编码时，各自需要的码长是多少？哪种情况的信息传输率高？各自需要的码长是多少？哪种情况的信息传输率高？各自需要的码长是多少？哪种情况的信息传输率高？各自需要的码长是多少？哪种情况的信息传输率高？解解解解：等概时所需的最少码符号：等概时所需的最少码符号：等概时所需的最少码符号：等概时所需的最少码符号5 5 5 5个，而考虑相关性时需要的最个，而考虑相关性时需要的最个，而考虑相关性时需要的最个，而考虑相关性时需要的最少码符号是少码符号是少码符号是少码符号是2 2 2 2个。后一种的信息传输率高个。后一种的信息传输率高个。后一种的信息传输率高个

18、。后一种的信息传输率高 三三.编码效率编码效率当允许错误概率小于当允许错误概率小于当允许错误概率小于当允许错误概率小于时，信源符号序列的长度时，信源符号序列的长度时，信源符号序列的长度时，信源符号序列的长度N N N N：为自信息的方差为自信息的方差如果为最佳编码，如果为最佳编码，则则例例5-4：设离散无记忆信源设离散无记忆信源设离散无记忆信源设离散无记忆信源求求信源序列的长度信源序列的长度。对对对对S S采取等长二元编码，要求编码效率采取等长二元编码，要求编码效率采取等长二元编码，要求编码效率采取等长二元编码，要求编码效率允许错误概率允许错误概率一一.变长编码的概念变长编码的概念 概念：概念

19、：通过编码后的代码组中的每个码字的码长不通过编码后的代码组中的每个码字的码长不通过编码后的代码组中的每个码字的码长不通过编码后的代码组中的每个码字的码长不尽相等。尽相等。尽相等。尽相等。要实现无失真信源编码，要实现无失真信源编码，要实现无失真信源编码，要实现无失真信源编码，变长码必须是唯一可译码变长码必须是唯一可译码变长码必须是唯一可译码变长码必须是唯一可译码第三节第三节 离散无记忆信源的变长编码离散无记忆信源的变长编码提问：提问：信源符号数和码字长度之间应该满足什么条信源符号数和码字长度之间应该满足什么条信源符号数和码字长度之间应该满足什么条信源符号数和码字长度之间应该满足什么条件才能构成唯

20、一可译码呢？件才能构成唯一可译码呢？件才能构成唯一可译码呢？件才能构成唯一可译码呢？二二.克拉夫特克拉夫特(Kraft)(Kraft)不等式不等式和和和和麦克米伦麦克米伦(McMillan)(McMillan)不等不等式式 设信源符号集为设信源符号集为其分别对应码长为其分别对应码长为l1 1,l2 2,lq q，则即时码存在的充要条件是：则即时码存在的充要条件是：对信源进行编码，相应的码字集为对信源进行编码，相应的码字集为码符号集为码符号集为不等式：不等式：不等式：不等式：不等式不等式不等式不等式 在满足在满足kraftkraft不等式的条件下，唯一可译码存在的充要条不等式的条件下，唯一可译码

21、存在的充要条件是：件是：设设S S0 0为原始码字的集合。再构造一系列集合为原始码字的集合。再构造一系列集合S S1 1,S,S2 2,Sn。构造构造S S1 1,S,S2 2,S,Sn n的方法：的方法：1 1、首先考察、首先考察S S0 0中所有的码字。若码字中所有的码字。若码字W Wj j是码字是码字W Wi i的前缀，的前缀，即即W Wi i=W=Wj jA A，则将后缀，则将后缀A A列为列为S S1 1中的元素，中的元素，S S1 1就是由所有具有就是由所有具有这种性质的这种性质的A A构成的集合。构成的集合。2 2、当、当n1n1，则将，则将S S0 0于于S Sn-1n-1比较

22、，看是否比较，看是否S S0 0中的码字是中的码字是S Sn-1n-1的前的前缀，如果是，则取后缀为缀，如果是，则取后缀为S Sn n中元素，且看中元素，且看S Sn-1n-1中码字是否为中码字是否为S S0 0中码字的前缀，如果是，则取后缀为中码字的前缀，如果是，则取后缀为S Sn n中元素，如此构成集中元素，如此构成集合合S Sn n。三三三三.唯一可译码判断准则唯一可译码判断准则唯一可译码判断准则唯一可译码判断准则准则：准则：准则：准则：一种码为唯一可译码的充要条件是一种码为唯一可译码的充要条件是一种码为唯一可译码的充要条件是一种码为唯一可译码的充要条件是S S1 1,S,S2 2,中没

23、有一中没有一中没有一中没有一个含有个含有个含有个含有S S0 0中的码字。中的码字。中的码字。中的码字。S0 S1 S2 S3 S4 S5 S6 S7 S8 S0 S1 S2 S3 S4 S5 S6 S7 S8 a d eb de b a d eb de b ad ad d eb 0 d eb 0 c bb cde bcde c bb cde bcde ad ad abb abb bad bad deb deb bbcde bbcde结论：结论：当当当当N7N7N7N7时，时，时，时，S S S Sn n n n为空集，而在为空集，而在为空集，而在为空集，而在S S S S5 5 5 5中包含

24、中包含中包含中包含S S S S0 0 0 0中的码字，中的码字，中的码字，中的码字，故而故而故而故而S S S S0 0 0 0不是唯一可译码。不是唯一可译码。不是唯一可译码。不是唯一可译码。例例例例5-55-55-55-5：设消息集合中共有设消息集合中共有设消息集合中共有设消息集合中共有7 7 7 7个消息，分别为个消息，分别为个消息，分别为个消息，分别为被编码成对应的码字被编码成对应的码字被编码成对应的码字被编码成对应的码字，判断是否，判断是否，判断是否，判断是否是唯一可译码。是唯一可译码。是唯一可译码。是唯一可译码。1.1.平均码长平均码长平均码长平均码长 ：四四.变长编码定理变长编码

25、定理表示编码时，平均每个信源符号需用的码元个数。表示编码时，平均每个信源符号需用的码元个数。表示编码时，平均每个信源符号需用的码元个数。表示编码时，平均每个信源符号需用的码元个数。平均每个码元载荷的信息量平均每个码元载荷的信息量=信道的信息传输率信道的信息传输率R R 信源编码目的：信源编码目的：信源编码目的：信源编码目的：提高信道信息传输率提高信道信息传输率提高信道信息传输率提高信道信息传输率R R R R，充分利用信道，充分利用信道，充分利用信道，充分利用信道信道的信息传输率信道的信息传输率信道的信息传输率信道的信息传输率R R=信道中平均每个符号所能传送的信息量信道中平均每个符号所能传送

26、的信息量2.2.2.2.最佳码最佳码最佳码最佳码 对于某一信源和某一码元集，若有一种唯一可译码，其平均对于某一信源和某一码元集，若有一种唯一可译码，其平均长度长度小于所有其他的唯一可译码，则称此码为最佳码小于所有其他的唯一可译码，则称此码为最佳码(紧致码紧致码)。请问请问:从提高无失真信源编码的有效性角度出发，当然希望从提高无失真信源编码的有效性角度出发，当然希望从提高无失真信源编码的有效性角度出发，当然希望从提高无失真信源编码的有效性角度出发，当然希望平均码长越小越好，但是平均码长越小越好，但是平均码长越小越好，但是平均码长越小越好，但是是否可以无限地小？有没有限度是否可以无限地小？有没有限

27、度是否可以无限地小？有没有限度是否可以无限地小？有没有限度？则总可以找到一种编码方法构成唯一可译码，使信源则总可以找到一种编码方法构成唯一可译码，使信源S S中的每中的每个信源符号所需的码字与平均长度满足个信源符号所需的码字与平均长度满足 有一离散无记忆信源有一离散无记忆信源S=SS=Si i(i=1,2,q)(i=1,2,q)，输出符号为，输出符号为q q个，其个，其熵为熵为H(S)H(S)，它的，它的N N次扩展信源次扩展信源其熵其熵,若用若用r r个码元对个码元对信源进行编码信源进行编码3.变长无失真信源编码定理变长无失真信源编码定理(香农第一定理香农第一定理)其中，其中，为为 中每个信

28、源符号序列中每个信源符号序列 编码所对应的码字的平编码所对应的码字的平均码长。均码长。变长编码定理说明：变长编码定理说明：若编码的平均码长小于信源的熵则唯一可译码不存在。同时指出：要做到无失真的信源编码，变换每个信源符号平均所需要最少的r进制码符号数，就是原始信源的熵值（以r为底的）；如果编码的平均码长小于原始信源的熵值，则唯一可译码不存在，此时，译码必然带来失真。当平均码长为时，编码后的信道的信息传输率此时有：比特/符号信道的信息传输率R=无损信道的信道容量C 可知此时：R达到最大值，实现信源与信道的统计匹配。变长编码定理还表明变长编码定理还表明：在无失真信源编码中，采用扩展信源的手段，虽然

29、可以减少每一个信源符号所需要的平均码符号数，使编码的有效性提高，但无论如何扩展，其有效性是有限度的，其极限值即是信源的熵值。对离散信源进行适当变换，使变化后的码符号信源对离散信源进行适当变换，使变化后的码符号信源对离散信源进行适当变换，使变化后的码符号信源对离散信源进行适当变换，使变化后的码符号信源(作作作作为信道的输入信源为信道的输入信源为信道的输入信源为信道的输入信源)尽可能等概分布尽可能等概分布尽可能等概分布尽可能等概分布，使每个码符号平均，使每个码符号平均，使每个码符号平均，使每个码符号平均含的信息量最大，从而使信道的信息传输率含的信息量最大，从而使信道的信息传输率含的信息量最大，从而

30、使信道的信息传输率含的信息量最大，从而使信道的信息传输率R R达到信道容量达到信道容量达到信道容量达到信道容量C C，实现信源与信道的统计匹配。，实现信源与信道的统计匹配。，实现信源与信道的统计匹配。，实现信源与信道的统计匹配。香农第一定理是香农信息论的主要定理之一，可以香农第一定理是香农信息论的主要定理之一，可以香农第一定理是香农信息论的主要定理之一，可以香农第一定理是香农信息论的主要定理之一，可以表达为：表达为：表达为：表达为：若信息传输率若信息传输率若信息传输率若信息传输率R R不大于信道容量不大于信道容量不大于信道容量不大于信道容量C C，总能对信源的输出，总能对信源的输出，总能对信源

31、的输出，总能对信源的输出进行适当的编码，使得在信道上能够无差错地以最大信息率进行适当的编码，使得在信道上能够无差错地以最大信息率进行适当的编码，使得在信道上能够无差错地以最大信息率进行适当的编码，使得在信道上能够无差错地以最大信息率C C传输信息。要使信息传输率传输信息。要使信息传输率传输信息。要使信息传输率传输信息。要使信息传输率R R大于大于大于大于C C而无差错地传输信息量而无差错地传输信息量而无差错地传输信息量而无差错地传输信息量是不可能的。是不可能的。是不可能的。是不可能的。无失真信源编码的实质是：无失真信源编码的实质是：4 4.编码效率编码效率编码效率编码效率和码的剩余度和码的剩余

32、度和码的剩余度和码的剩余度 码的剩余度码的剩余度=1-=1-编码效率编码效率编码效率编码效率:衡量各种码的优劣衡量各种码的优劣衡量各种码的优劣衡量各种码的优劣码的剩余度码的剩余度码的剩余度码的剩余度:衡量编码与最佳码的差距衡量编码与最佳码的差距衡量编码与最佳码的差距衡量编码与最佳码的差距例例5-6:5-6:有一离散无记忆信源有一离散无记忆信源 ,求对原始信源和二次扩展信源用求对原始信源和二次扩展信源用求对原始信源和二次扩展信源用求对原始信源和二次扩展信源用0000，1111码元集进行码元集进行码元集进行码元集进行编码后的信编码后的信编码后的信编码后的信息传输率以及编码效率息传输率以及编码效率息

33、传输率以及编码效率息传输率以及编码效率.解解:(1)(1)用用用用0000，1111对之进行编码，有对之进行编码，有对之进行编码，有对之进行编码，有 (2)(2)(2)(2)二次扩展信源为：二次扩展信源为：二次扩展信源为：二次扩展信源为：第四节第四节 变长编码的编码方法变长编码的编码方法一一.莫尔斯莫尔斯(Morse)(Morse)编码编码 二二.香农编码香农编码1.1.具体步骤具体步骤具体步骤具体步骤:将信源发出的将信源发出的将信源发出的将信源发出的q q q q个消息符号按其概率的逆减次序排列个消息符号按其概率的逆减次序排列个消息符号按其概率的逆减次序排列个消息符号按其概率的逆减次序排列计

34、算第计算第计算第计算第i i个消息的二进制码字的码长个消息的二进制码字的码长个消息的二进制码字的码长个消息的二进制码字的码长l li i,并取整并取整并取整并取整为了编成唯一可译码，首先计算第为了编成唯一可译码，首先计算第i i个消息的累加概率个消息的累加概率根据码长根据码长根据码长根据码长li li,对对对对的结果取小数点后的结果取小数点后的结果取小数点后的结果取小数点后li li位数作为第位数作为第位数作为第位数作为第i i i i个消息的码字个消息的码字个消息的码字个消息的码字将累加概率将累加概率将累加概率将累加概率PiPiPiPi变成二进制数变成二进制数变成二进制数变成二进制数利用利用

35、利用利用例例例例5-75-7：消息序号消息序号消息序号消息序号S Si i 概率概率概率概率p(Sp(Si i)logp(S)logp(Si i)码长码长码长码长L Li i 累加概率累加概率累加概率累加概率p pi i 二进制二进制二进制二进制码码码码 S1 0.40 1.32 2 0 00 S2 0.30 1.74 2 0.40 01 S3 0.20 2.32 3 0.70 101 S4 0.10 3.32 4 0.90 1110 用用0 0，1 1码符号分别代表概率最小的两个信源符号，并将这两码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含个概

36、率最小的信源符号合并成一个，从而得到只包含q-1q-1个符个符号的新信源号的新信源S S1 1,称为缩减信号源。称为缩减信号源。三三.二元二元Huffman编码编码1.1.编码步骤编码步骤编码步骤编码步骤将信源发出的将信源发出的将信源发出的将信源发出的q q个信源按其概率依次从大到小排列个信源按其概率依次从大到小排列个信源按其概率依次从大到小排列个信源按其概率依次从大到小排列把缩减信源把缩减信源把缩减信源把缩减信源S S1 1的符号按概率从大到小排列，再将其最后两个的符号按概率从大到小排列，再将其最后两个的符号按概率从大到小排列，再将其最后两个的符号按概率从大到小排列，再将其最后两个概率最小的

37、符号合并成一个符号，并分别用概率最小的符号合并成一个符号，并分别用概率最小的符号合并成一个符号，并分别用概率最小的符号合并成一个符号，并分别用0 0和和和和1 1码元表示，这码元表示，这码元表示，这码元表示，这样形成样形成样形成样形成q-2q-2个符号的新信源个符号的新信源个符号的新信源个符号的新信源S S2 2。依此类推，直至信源只剩两个符号为止，并分别用依此类推，直至信源只剩两个符号为止，并分别用依此类推，直至信源只剩两个符号为止，并分别用依此类推，直至信源只剩两个符号为止，并分别用“0”“0”和和和和“1”“1”表示。表示。表示。表示。从最后一级缩减信源开始，向前返回，得出各信源符号所对

38、从最后一级缩减信源开始，向前返回，得出各信源符号所对从最后一级缩减信源开始，向前返回，得出各信源符号所对从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即相应码字。应的码符号序列，即相应码字。应的码符号序列，即相应码字。应的码符号序列，即相应码字。例例5-85-8信源符号信源符号S Si i 概率概率p(p(Si)编码过程编码过程 码字码字W Wi i 码长码长li i S1 S2 S3 S1 0.4 S2 0.2 S3 0.2 S4 0.1 0.210101001编码过程：编码过程：编码过程：编码过程：1 1112 201012 23 30000003 34 400100

39、0104 45 5001100114 4用树图检验是否为即时码用树图检验是否为即时码用树图检验是否为即时码用树图检验是否为即时码0A01001110100000100011(1)(1)每次对信号缩减时，赋予最后两个概率最小的符号每次对信号缩减时，赋予最后两个概率最小的符号每次对信号缩减时，赋予最后两个概率最小的符号每次对信号缩减时，赋予最后两个概率最小的符号 用用用用“0”“0”和和和和“1”“1”是可任意的。是可任意的。是可任意的。是可任意的。(2)(2)对信源进行缩减时两个概率最小的符号合并后的概率与其对信源进行缩减时两个概率最小的符号合并后的概率与其对信源进行缩减时两个概率最小的符号合并

40、后的概率与其对信源进行缩减时两个概率最小的符号合并后的概率与其他符号概率相同时，可任意排序。他符号概率相同时，可任意排序。他符号概率相同时，可任意排序。他符号概率相同时，可任意排序。经哈夫曼编码方法得到的码并非是唯一的经哈夫曼编码方法得到的码并非是唯一的经哈夫曼编码方法得到的码并非是唯一的经哈夫曼编码方法得到的码并非是唯一的,造成非唯一造成非唯一造成非唯一造成非唯一的原因：的原因：的原因：的原因：码字码字W Wi i 码长码长l i S1 0.4 0.4 0.4 0.6 00 2 S2 0.2 0.2 0.4 0.4 10 2 S3 0.2 0.2 0.2 11 2 S4 0.1 0.2 01

41、0 3 S5 0.1 011 301010101例题例题例题例题5-85-8：A00111000101101010011即时码即时码即时码即时码由此可见：由此可见：由此可见：由此可见：结论：结论：当进行哈夫曼编码时，为了得到质量好的码，应使合当进行哈夫曼编码时，为了得到质量好的码，应使合当进行哈夫曼编码时，为了得到质量好的码，应使合当进行哈夫曼编码时，为了得到质量好的码，应使合并的信源符号位于缩减信源序列尽可能高的位置，这样可充分并的信源符号位于缩减信源序列尽可能高的位置，这样可充分并的信源符号位于缩减信源序列尽可能高的位置，这样可充分并的信源符号位于缩减信源序列尽可能高的位置，这样可充分利用

42、短码。利用短码。利用短码。利用短码。r r元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只是编码过程中构成缩减信源时，每次将是编码过程中构成缩减信源时，每次将r r个概率最小的符号合个概率最小的符号合并，并分别用并，并分别用0 0，1 1，r-1r-1码元表示。码元表示。为了充分利用短码，使哈夫曼码的平均码长最短，必须为了充分利用短码，使哈夫曼码的平均码长最短，必须是最后一个缩减信源有是最后一个缩减信源有r r个信源符号。因此，对于个信源符号。因此，对于r r元哈夫曼码，元哈夫曼码，信源信源S S的符号个数的符号个数q q必须满足必须满足 如果信

43、源如果信源S S的符号个数的符号个数q q不满足上式，则增补一些概率为不满足上式，则增补一些概率为0 0的信源符号。的信源符号。四四.r元哈夫曼码元哈夫曼码例例例例5-95-95-95-9：有一离散无记忆信源有一离散无记忆信源码元集码元集X=(0,1,2)X=(0,1,2)，对对S S进行进行3 3元哈夫曼编码元哈夫曼编码。解：解：解：解：信源符号信源符号 概率概率 编码过程编码过程 码字码字W Wi i 码长码长li Si p(Si)S1 S2 Wi li S1 0.4 0.4 0.4 0 1 S2 0.3 0.3 0.3 2 1 S3 0.2 0.2 0.3 10 2 S4 0.05 0.

44、05 12 2 S5 0.025 0.05 110 3 S6 0.025 111 3 S7 0 112 3210210210霍夫曼编码的特点：霍夫曼编码的特点：1）由于霍夫曼编码总是以最小概率相加的方法来缩减参与皮埃对的概率个数，因此概率越小，对缩减的贡献越大，其对应消息的码字也越长。2）最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几个消息符号有着相同概率的情况，将会有多种路径选择，即既具有多种可能的代码组集合。3）尽管对同一信源存在着多种结果的霍夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用最小概率相加的方法，其实质都是遵循最佳编码的原则，因此霍夫曼编码是最佳

45、编码。霍夫曼编码存在的问题霍夫曼编码存在的问题：1）霍夫曼编码要求信源消息概率已知或可估计。由于初始信源不可能总是统计好了概率，为此编码之前必须先估算信源的统计特性。在信源具有记忆性能并用霍夫曼编码来表示信源的扩展输出时，概率的估计很耗费时间。2）霍夫曼编码是建立在编码器和译码器都知道码树结构的基础上的，如果信源消息数目变大，则树型结构的大小和算法的复杂性会呈指数规律增加。五五.Lemple-Ziv编码编码 例例5-105-10：待编码的字符序列为：abaaaabaabaaabbbbbbbabbbbbaababaababa.,试用Lemple-Ziv方法给出编码结果。编码结果0a0b1a3b4

46、a4b2b7b1b8b5b11b地址123456789101112码段内容abaaaabaabaaabbbbbbbabbbbbaababaababa由此可知：Lemple-Ziv编码利用了已编码信息进行当前的编码，编码结果是等长码，编码过程就是建立码地址和将待编码消息序列分段的过程，所有的码段内容都是不同的。例例例例5-115-115-115-11：若有一信源：若有一信源：每每秒秒钟钟发发出出个个信信源源符符号号，将将此此信信源源的的输输出出符符号号送送入入某某一一个个二二元元信信道道中中进进行行传传输输（假假设设信信道道是是无无噪噪无无损损的的），而而信信道道每每秒秒钟钟只只传传递递2 2个

47、个二二元元符符号号。试试试试问问问问信信信信源源源源不不不不通通通通过过过过编编编编码码码码能能能能否否否否直直直直接接接接与与与与信信信信道道道道连连连连接接接接？若若若若通通通通过过过过适适适适当当当当编编编编码码码码能能能能否否否否在在在在此此此此信信信信道道道道中中中中进进进进行行行行无无无无失失失失真真真真传传传传输输输输？若若若若能连接，试说明如何编码并说明原因。能连接，试说明如何编码并说明原因。能连接，试说明如何编码并说明原因。能连接，试说明如何编码并说明原因。每秒发个信源符号，所以信源输出的信息速率为：每秒发个信源符号，所以信源输出的信息速率为：每秒发个信源符号，所以信源输出的

48、信息速率为：每秒发个信源符号，所以信源输出的信息速率为：Rt Rt Rt Rt比特比特比特比特/秒秒秒秒该信道是二元无噪无损信道，所以此信道的最大信息传输该信道是二元无噪无损信道，所以此信道的最大信息传输该信道是二元无噪无损信道，所以此信道的最大信息传输该信道是二元无噪无损信道，所以此信道的最大信息传输率（信道容量）率（信道容量）率（信道容量）率（信道容量）C=1 C=1 C=1 C=1比特比特比特比特/符号符号符号符号信道每秒只传送信道每秒只传送信道每秒只传送信道每秒只传送2 2 2 2个二元符号，所以信道的最大信息传输速个二元符号，所以信道的最大信息传输速个二元符号，所以信道的最大信息传输

49、速个二元符号，所以信道的最大信息传输速率：率：率：率：Ct=2*C=2 Ct=2*C=2 Ct=2*C=2 Ct=2*C=2比特比特比特比特/秒秒秒秒 RtCt RtCt RtCt RtCt根据无失真信源编码定理，因为根据无失真信源编码定理，因为根据无失真信源编码定理，因为根据无失真信源编码定理，因为RtCtRtCtRtCtRt2222二元符号二元符号二元符号二元符号/秒秒秒秒所以必须考虑所以必须考虑所以必须考虑所以必须考虑3 3 3 3次扩展信源，并对之编码次扩展信源，并对之编码次扩展信源，并对之编码次扩展信源，并对之编码.考虑考虑考虑考虑3 3 3 3次扩展信源，并对之编码，得：次扩展信源

50、，并对之编码，得：次扩展信源，并对之编码，得：次扩展信源，并对之编码，得：二元哈夫码：二元哈夫码：二元哈夫码：二元哈夫码：1 000 001 010 01100 01101 01110 01111平均码长：平均码长：平均码长：平均码长：送入信道的传输速率为送入信道的传输速率为送入信道的传输速率为送入信道的传输速率为 二元符号二元符号二元符号二元符号/秒秒秒秒2222二元符号二元符号二元符号二元符号/秒秒秒秒这时可在信道中进行无失真传输。这时可在信道中进行无失真传输。这时可在信道中进行无失真传输。这时可在信道中进行无失真传输。一一.游程编码游程编码1.1.游程编码的基本原理游程编码的基本原理 游