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

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

1、第第4章章 离散无记忆信源无失真编码离散无记忆信源无失真编码4.1 信源编码概论信源编码概论4.2 码的唯一可译性码的唯一可译性4.3 定长编码定理和定长编码方法定长编码定理和定长编码方法4.4 变长编码定理变长编码定理4.5 变长编码方法变长编码方法4.6 几种实用的无失真信源编码几种实用的无失真信源编码信源编码复习信源编码复习4.1 4.1 信源编码概论信源编码概论信源编码概论信源编码概论 传输之前的两次变换：传输之前的两次变换：传输之前的两次变换：传输之前的两次变换：信源编码信源编码信源编码信源编码、信道编码信道编码信道编码信道编码。传输之后的两次反变换：传输之后的两次反变换：传输之后的

2、两次反变换：传输之后的两次反变换：信道译码信道译码信道译码信道译码、信源译码信源译码信源译码信源译码。变换与反变换是成对出现的。变换与反变换是成对出现的。变换与反变换是成对出现的。变换与反变换是成对出现的。采采采采取取取取适适适适当当当当信信信信道道道道编编编编码码码码和和和和译译译译码码码码措措措措施施施施后后后后，可可可可使使使使信信信信道道道道传传传传送送送送的的的的差差差差错错错错率率率率降降降降到到到到允允允允许许许许的的的的范范范范围围围围之之之之内内内内，因因因因此此此此，图图图图中中中中虚虚虚虚框框框框部部部部分分分分可可可可近近近近似似似似地地地地视视视视为为为为一一一一个个

3、个个等等等等效效效效的的的的无无无无损损损损确确确确定定定定信信信信道道道道，简称为无噪信道，这一点是我们讨论信源编码的前提。简称为无噪信道，这一点是我们讨论信源编码的前提。简称为无噪信道，这一点是我们讨论信源编码的前提。简称为无噪信道，这一点是我们讨论信源编码的前提。1 1、基本概念、基本概念、基本概念、基本概念噪声噪声噪声噪声信信信信道道道道信源信源信源信源编码编码编码编码信信信信源源源源信信信信宿宿宿宿等效无噪信道等效无噪信道等效无噪信道等效无噪信道信源信源信源信源译码译码译码译码信道信道信道信道编码编码编码编码信道信道信道信道译码译码译码译码2 信源编码分类：信源编码分类：信源编码分类

4、：信源编码分类：无失真编码无失真编码无失真编码无失真编码、有失真编码有失真编码有失真编码有失真编码。无失真编码无失真编码无失真编码无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码冗余度压缩编码冗余度压缩编码冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源，它能保证码元序列经译码后能无失真地恢复成信源，它能保证码元序列经译码后能无失真地恢复成信源，它能保证码元序列经译码后能无失真地恢复成信源符号序列。符号序列。

5、符号序列。符号序列。有失真编码有失真编码有失真编码有失真编码：又称：又称：又称：又称熵压缩编码熵压缩编码熵压缩编码熵压缩编码，将在第，将在第，将在第，将在第6 6 6 6章讨论。章讨论。章讨论。章讨论。无损确定信道无损确定信道无损确定信道无损确定信道（等效）（等效）（等效）（等效）信源信源信源信源编码编码编码编码信信信信源源源源信信信信宿宿宿宿信源信源信源信源译码译码译码译码无失真信源编码的作用：无失真信源编码的作用：无失真信源编码的作用：无失真信源编码的作用：（1 1）符号变换）符号变换）符号变换）符号变换：使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；：

6、使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；（2 2）冗余度压缩）冗余度压缩）冗余度压缩）冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率：使编码之后的新信源概率分布均匀化，信息含量效率：使编码之后的新信源概率分布均匀化，信息含量效率：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于等于或接近于等于或接近于等于或接近于100%100%。32 2、编码器模型、编码器模型、编码器模型、编码器模型 码长码长码长码长l li i ：码字码字码字码字w wi i 所含码元的个数。单位：码元所含码元的个数。单位：码元所含码元的个数。单位：码元所含码

7、元的个数。单位：码元/符号，符号，符号，符号，r r进制单位进制单位进制单位进制单位/符号。符号。符号。符号。定长码定长码定长码定长码(FLCFLC，Fixed Length code)Fixed Length code)：码码码码中所有码字均有相同的码长中所有码字均有相同的码长中所有码字均有相同的码长中所有码字均有相同的码长l l；否则称为否则称为否则称为否则称为变长码变长码变长码变长码(VLCVLC，Variable Length code)Variable Length code)。平均码长：平均码长：平均码长：平均码长：码码码码WW码字集码字集码字集码字集WW 码字码字码字码字w wi

8、 i 码元集码元集码元集码元集 X X码元码元码元码元x xi i 编码器编码器编码器编码器f f信信信信源源源源信源编码信源编码信源编码信源编码 f f：一一对应的变换。：一一对应的变换。：一一对应的变换。：一一对应的变换。码元码元码元码元/符号符号符号符号 定长码：定长码：定长码：定长码：码元码元码元码元/符号符号符号符号 平平平平均均均均码码码码长长长长是是是是衡衡衡衡量量量量码码码码的的的的性性性性能能能能的的的的重重重重要要要要参参参参数数数数，“平平平平均均均均码码码码长长长长小小小小”说说说说明明明明平平平平均均均均一一一一个个个个码码码码元元元元所所所所携携携携带带带带的的的的

9、信信信信息息息息量量量量大大大大，信信信信息的冗余就小。息的冗余就小。息的冗余就小。息的冗余就小。4例：编码例：编码例：编码例：编码设设设设DMSDMS的概率空间为的概率空间为的概率空间为的概率空间为对其单个符号进行二进制编码。对其单个符号进行二进制编码。对其单个符号进行二进制编码。对其单个符号进行二进制编码。编码器编码器编码器编码器f f信信信信源源源源码元码元码元码元/符号符号符号符号 码元码元码元码元/符号符号符号符号 编码策略编码策略编码策略编码策略：经常出现（概率大）的符号：经常出现（概率大）的符号：经常出现（概率大）的符号：经常出现（概率大）的符号采用较短的码字，不经常出现（概率小

10、）采用较短的码字，不经常出现（概率小）采用较短的码字，不经常出现（概率小）采用较短的码字，不经常出现（概率小）的符号采用较长的码字的符号采用较长的码字的符号采用较长的码字的符号采用较长的码字。编码策略编码策略编码策略编码策略：采用等长的码字：采用等长的码字：采用等长的码字：采用等长的码字。53 3、编码器的输出、编码器的输出、编码器的输出、编码器的输出编码器编码器编码器编码器f f信信信信源源源源 f f 是一一对是一一对是一一对是一一对应的映射应的映射应的映射应的映射 bit/bit/码字码字码字码字或或或或bit/bit/符号符号符号符号 bit/bit/码元码元码元码元新信源新信源新信源

11、新信源X X ：编码后的信息率编码后的信息率编码后的信息率编码后的信息率R R ：平均一个码元携带的信息量。：平均一个码元携带的信息量。：平均一个码元携带的信息量。：平均一个码元携带的信息量。bit/bit/码元码元码元码元平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。信息。信息。信息。64 4、编码效率、编码效率、编码效率、编码效率 为了衡量编码效果，定义为了衡量

12、编码效果，定义为了衡量编码效果，定义为了衡量编码效果，定义编码效率编码效率编码效率编码效率：编码后的实际信息率与编码后：编码后的实际信息率与编码后：编码后的实际信息率与编码后：编码后的实际信息率与编码后的最大信息率之比。的最大信息率之比。的最大信息率之比。的最大信息率之比。注注注注：编码效率编码效率编码效率编码效率实际上也是新信源实际上也是新信源实际上也是新信源实际上也是新信源X X 的信息含量效率或熵的相对率。的信息含量效率或熵的相对率。的信息含量效率或熵的相对率。的信息含量效率或熵的相对率。编码器编码器编码器编码器f f信信信信源源源源新信源的冗余度新信源的冗余度新信源的冗余度新信源的冗余

13、度也是也是也是也是码的冗余度码的冗余度码的冗余度码的冗余度：74.2 4.2 码的唯一可译性码的唯一可译性码的唯一可译性码的唯一可译性 f f 为一一对应的变换，只是无失真编码的必要条件，并不充分为一一对应的变换，只是无失真编码的必要条件，并不充分为一一对应的变换，只是无失真编码的必要条件，并不充分为一一对应的变换，只是无失真编码的必要条件，并不充分;要保证将码元序列无失真地恢复成信源符号序列，还要求编要保证将码元序列无失真地恢复成信源符号序列，还要求编要保证将码元序列无失真地恢复成信源符号序列，还要求编要保证将码元序列无失真地恢复成信源符号序列，还要求编出的码自身具有独特的结构。出的码自身具

14、有独特的结构。出的码自身具有独特的结构。出的码自身具有独特的结构。有实用价值的码应该具有唯一可译性，即能从码字序列（也有实用价值的码应该具有唯一可译性，即能从码字序列（也有实用价值的码应该具有唯一可译性，即能从码字序列（也有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列。是码元序列）唯一地恢复成信源符号序列。是码元序列）唯一地恢复成信源符号序列。是码元序列）唯一地恢复成信源符号序列。举例：下雨天留客天留我不留举例：下雨天留客天留我不留举例：下雨天留客天留我不留举例：下雨天留客天留我不留无损确定信道无损确定信道无损确定信道无损确定信道（等效）（等效）（等效

15、）（等效）信源信源信源信源编码编码编码编码信信信信源源源源信信信信宿宿宿宿信源信源信源信源译码译码译码译码81 1、唯一可译码（、唯一可译码（、唯一可译码（、唯一可译码（UDCUDC，Uniquely Decodable CodeUniquely Decodable Code）唯一可译码（唯一可译码（唯一可译码（唯一可译码（UDCUDC）：该码的码字组成的任意有限长码字序列：该码的码字组成的任意有限长码字序列：该码的码字组成的任意有限长码字序列：该码的码字组成的任意有限长码字序列（也是码元序列）都能恢复成唯一的信源序列。否则称为（也是码元序列）都能恢复成唯一的信源序列。否则称为（也是码元序列）

16、都能恢复成唯一的信源序列。否则称为（也是码元序列）都能恢复成唯一的信源序列。否则称为非非非非唯一可译码唯一可译码唯一可译码唯一可译码。码是唯一可译码的码是唯一可译码的码是唯一可译码的码是唯一可译码的充分必要条件充分必要条件充分必要条件充分必要条件是：由码中的码字组成的任是：由码中的码字组成的任是：由码中的码字组成的任是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一意有限长的码字序列（也是码元序列），都能唯一划分成一意有限长的码字序列（也是码元序列），都能唯一划分成一意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。个

17、个的码字，且任一码字只与唯一一个信源符号对应。个个的码字，且任一码字只与唯一一个信源符号对应。个个的码字，且任一码字只与唯一一个信源符号对应。奇异码奇异码奇异码奇异码：含相同码字的码。否则称为：含相同码字的码。否则称为：含相同码字的码。否则称为：含相同码字的码。否则称为非奇异码非奇异码非奇异码非奇异码。非续长码非续长码非续长码非续长码：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。否则为否则为否则为否则为续长码续长码续长码续长码。非及时码非及时码非及时码非及时码：如果

18、接收端收到一个完整的码字后，不能立即译：如果接收端收到一个完整的码字后，不能立即译：如果接收端收到一个完整的码字后，不能立即译：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。码，还需等下一个码字开始接收后才能判断是否可以译码。码，还需等下一个码字开始接收后才能判断是否可以译码。码，还需等下一个码字开始接收后才能判断是否可以译码。否则为否则为否则为否则为及时码及时码及时码及时码或或或或立即码立即码立即码立即码。95种不同的码种不同的码W1：定长码。：定长码。W3：变长码。：变长码。奇异码。奇异码。定长非奇异码肯定是定长非奇异码肯定是UDC。W2：定

19、长码。：定长码。W4：变长码。：变长码。W5：变长码。：变长码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。续长码。续长码。非续长码。非续长码。续长码。续长码。及时码。及时码。非及时码。非及时码。奇异码肯定不是奇异码肯定不是UDC。不是不是UDC。非续长码肯定是非续长码肯定是UDC。是是UDC。非及时码。非及时码。非续长码。非续长码。10 唯一可译码唯一可译码唯一可译码唯一可译码 定长非奇异码定长非奇异码定长非奇异码定长非奇异码 非续长码非续长码非续长码非续长码非非非非奇奇奇奇异异异异码码码码码码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码

20、唯一可译码定长非奇异码定长非奇异码变长非续长码变长非续长码（部分）变长续长码（部分）变长续长码112 2、码树、码树、码树、码树 码树从码树从码树从码树从树根树根树根树根开始向上长出开始向上长出开始向上长出开始向上长出树枝树枝树枝树枝，树枝代表码元，树枝与树枝的交点叫，树枝代表码元，树枝与树枝的交点叫，树枝代表码元，树枝与树枝的交点叫，树枝代表码元，树枝与树枝的交点叫做做做做节点节点节点节点 。r r 进制码树进制码树进制码树进制码树：码元个数为：码元个数为：码元个数为：码元个数为r r，各节点（含树根）向上长出的树枝数不大，各节点（含树根）向上长出的树枝数不大，各节点（含树根）向上长出的树枝

21、数不大，各节点（含树根）向上长出的树枝数不大于于于于r r。l l 阶节点阶节点阶节点阶节点：经过：经过：经过：经过l l 根树枝才能到达的节点。根树枝才能到达的节点。根树枝才能到达的节点。根树枝才能到达的节点。终端节点终端节点终端节点终端节点或或或或端点端点端点端点：向上不长出树枝的节点。：向上不长出树枝的节点。：向上不长出树枝的节点。：向上不长出树枝的节点。整树整树整树整树：r r 进制码树各节点（包括树根）向上长出的树枝数均等于进制码树各节点（包括树根）向上长出的树枝数均等于进制码树各节点（包括树根）向上长出的树枝数均等于进制码树各节点（包括树根）向上长出的树枝数均等于r r。码字码字码

22、字码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该：与码树上的节点对应，组成该码字的码元就是从树根开始到该：与码树上的节点对应，组成该码字的码元就是从树根开始到该：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。节点所经过的树枝（或码元）。节点所经过的树枝（或码元）。节点所经过的树枝（或码元）。非续长码非续长码非续长码非续长码：所有码字均处于终端节点，即端点上。：所有码字均处于终端节点，即端点上。：所有码字均处于终端节点，即端点上。：所有码字均处于终端节点，即端点上。一阶节点一阶节点一阶节点一阶节点二阶节点二阶节点二阶节点二阶节点三阶节点三阶节点三

23、阶节点三阶节点WW1 1=00=00，0101，1010，1111WW4 4=0=0，1010，110110，111111WW5 5=0=0，0101，011011，111111123 3、KraftKraft不等式不等式不等式不等式 不满足不满足不满足不满足Kraft Kraft 不等式的码肯定不是非续长码；不等式的码肯定不是非续长码；不等式的码肯定不是非续长码；不等式的码肯定不是非续长码；满足满足满足满足Kraft Kraft 不等式的码也不一定是非续长码；不等式的码也不一定是非续长码；不等式的码也不一定是非续长码；不等式的码也不一定是非续长码；根据满足根据满足根据满足根据满足Kraft

24、Kraft 不等式的不等式的不等式的不等式的码长集合可构造出码长集合可构造出码长集合可构造出码长集合可构造出一个非续长码；一个非续长码；一个非续长码；一个非续长码；上述定理对唯一可译码仍然成立。上述定理对唯一可译码仍然成立。上述定理对唯一可译码仍然成立。上述定理对唯一可译码仍然成立。非续长非续长非续长非续长码码码码存在性定理存在性定理存在性定理存在性定理：对于任一：对于任一：对于任一：对于任一 进制进制进制进制非续长码非续长码非续长码非续长码，各码字的码长为，各码字的码长为，各码字的码长为，各码字的码长为 必须满足必须满足必须满足必须满足Kraft Kraft 不等式不等式不等式不等式：反过来

25、，若上式成立，就一定反过来，若上式成立，就一定反过来，若上式成立，就一定反过来，若上式成立，就一定能构造能构造能构造能构造一个一个一个一个 进制进制进制进制非续长码非续长码非续长码非续长码。WW4 4=0=0，1010，110110，111111WW5 5=0=0，0101，011011，111111例如：例如：例如：例如：13 Kraft Kraft 不等式是唯一可译码不等式是唯一可译码不等式是唯一可译码不等式是唯一可译码存在存在存在存在的充要条件；的充要条件；的充要条件；的充要条件；如果码是唯一可译码，则必定满足该不等式；如果码是唯一可译码，则必定满足该不等式；如果码是唯一可译码，则必定满

26、足该不等式；如果码是唯一可译码，则必定满足该不等式；如果满足如果满足如果满足如果满足Kraft Kraft 不等式，则这种码长的唯一可译码一定存在；不等式，则这种码长的唯一可译码一定存在；不等式，则这种码长的唯一可译码一定存在；不等式，则这种码长的唯一可译码一定存在；但不表示所有满足不等式的码一定是唯一可译码。但不表示所有满足不等式的码一定是唯一可译码。但不表示所有满足不等式的码一定是唯一可译码。但不表示所有满足不等式的码一定是唯一可译码。唯一可译唯一可译唯一可译唯一可译码码码码存在性定理存在性定理存在性定理存在性定理：对于任一：对于任一：对于任一：对于任一 进制进制进制进制唯一可译码（唯一可

27、译码（唯一可译码（唯一可译码（UDCUDC），各码，各码，各码，各码字的码长为字的码长为字的码长为字的码长为 ，必须满足，必须满足，必须满足，必须满足Kraft Kraft 不等式：不等式：不等式：不等式：反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个 进制进制进制进制唯一可译码（唯一可译码（唯一可译码（唯一可译码（UDCUDC）。WW1 1=0=0，1010，110110，111111WW2 2=1=1，1010，011011，111111例如：例如：例如：例如：对任意码字序列对任意码字序列对任

28、意码字序列对任意码字序列 101110111101110111，按按按按WW2 2中的码字，可以分割为中的码字，可以分割为中的码字，可以分割为中的码字，可以分割为1010，111111，011011，1 1 或者或者或者或者 1 1，011011，1010，111111144.3 4.3 定长编码定理和定长编码方法定长编码定理和定长编码方法定长编码定理和定长编码方法定长编码定理和定长编码方法1 1、对信源输出的符号序列进行编码、对信源输出的符号序列进行编码、对信源输出的符号序列进行编码、对信源输出的符号序列进行编码 DMSDMS编码器编码器编码器编码器f fDMSDMS编码器编码器编码器编码器

29、f f对信源对信源对信源对信源U U的的的的单个符号单个符号单个符号单个符号进进进进行编码行编码行编码行编码 对信源对信源对信源对信源U U的的的的N N长符号串长符号串长符号串长符号串进行编码进行编码进行编码进行编码 对扩展信源对扩展信源对扩展信源对扩展信源U UN N的的的的单个符单个符单个符单个符号号号号进行编码进行编码进行编码进行编码 152 2、定长编码定理、定长编码定理、定长编码定理、定长编码定理 DMSDMS编码器编码器编码器编码器f fr r 进制定长编码，码长为进制定长编码，码长为进制定长编码，码长为进制定长编码，码长为l lN N，可用的码字数目：可用的码字数目：可用的码字

30、数目：可用的码字数目：唯一可译唯一可译唯一可译唯一可译信息传输率信息传输率信息传输率信息传输率编码效率编码效率编码效率编码效率bit/bit/bit/bit/码元码元码元码元16 定长无失真编码定理定长无失真编码定理定长无失真编码定理定长无失真编码定理：用：用：用：用r r 元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源U U的的的的N N 长长长长符号序列符号序列符号序列符号序列进行定长编码，进行定长编码，进行定长编码，进行定长编码，N N 长符号序列对应的码长为长符号序列对应的码长为长符号序列对应的码长为长符号序列对应的码长为l lN N，

31、若对于任意小的正数，若对于任意小的正数，若对于任意小的正数，若对于任意小的正数 ，有不等式，有不等式，有不等式，有不等式 就几乎能做到无失真编码，且随着序列长度就几乎能做到无失真编码，且随着序列长度就几乎能做到无失真编码，且随着序列长度就几乎能做到无失真编码，且随着序列长度N N 的增大，译码的增大，译码的增大，译码的增大，译码差错率趋于差错率趋于差错率趋于差错率趋于0 0。反过来，若。反过来，若。反过来，若。反过来，若 就不可能做到无失真编码，且随着就不可能做到无失真编码，且随着就不可能做到无失真编码，且随着就不可能做到无失真编码，且随着N N 的增大，译码差错率趋的增大，译码差错率趋的增大

32、，译码差错率趋的增大，译码差错率趋于于于于1 1。173 3、定长编码方法（例）、定长编码方法（例）、定长编码方法（例）、定长编码方法（例）对对对对U U 的单个符号进行的单个符号进行的单个符号进行的单个符号进行2 2进进进进制定长编码。制定长编码。制定长编码。制定长编码。码元集码元集码元集码元集：X X=0,1=0,1取取取取l l=3=3bitbit/符号符号符号符号码元码元码元码元/符号符号符号符号码元码元码元码元/符号符号符号符号解：解：解：解：提高编码效率的方法提高编码效率的方法提高编码效率的方法提高编码效率的方法：对符号串进行编码；引入一定的失真。：对符号串进行编码；引入一定的失真

33、。：对符号串进行编码；引入一定的失真。：对符号串进行编码；引入一定的失真。P115 P115 184.4 4.4 变长编码定理变长编码定理变长编码定理变长编码定理(香农第一定理香农第一定理香农第一定理香农第一定理)无失真变长编码定理无失真变长编码定理无失真变长编码定理无失真变长编码定理：用：用：用：用 元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源 的的的的 长长长长符号串符号串符号串符号串进行变长编码，记进行变长编码，记进行变长编码，记进行变长编码，记 长符号串对应的平均码长为长符号串对应的平均码长为长符号串对应的平均码长为长符号串对应的平均

34、码长为 ，那么，要做到无失，那么，要做到无失，那么，要做到无失，那么，要做到无失真编码，平均码长真编码，平均码长真编码，平均码长真编码，平均码长 必须满足必须满足必须满足必须满足 另一方面，一定存在唯一可译码，其平均码长另一方面，一定存在唯一可译码，其平均码长另一方面，一定存在唯一可译码，其平均码长另一方面，一定存在唯一可译码，其平均码长 满足满足满足满足变长编码不要求所有码字长度相同，但要求平均码长最小。变长编码不要求所有码字长度相同，但要求平均码长最小。变长编码不要求所有码字长度相同，但要求平均码长最小。变长编码不要求所有码字长度相同，但要求平均码长最小。N N趋于无穷时平均码长和编码效率

35、的极限：趋于无穷时平均码长和编码效率的极限：趋于无穷时平均码长和编码效率的极限：趋于无穷时平均码长和编码效率的极限：随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的熵，编码效率提高，当然编码过程也愈复杂。熵，编码效率提高，当然编码过程也愈复杂。熵，编码效率提高，当然编码过程也愈复杂。熵，编码效率提高，当然编码过程也愈复杂。194.5 4.5 变长编码方法变长编码方法变长编码方法变长编码方法 变长编码采用变

36、长编码采用变长编码采用变长编码采用非续长码；非续长码；非续长码；非续长码；力求平均码长最小，此时编码效率最高，信源的冗余得到力求平均码长最小，此时编码效率最高，信源的冗余得到力求平均码长最小，此时编码效率最高，信源的冗余得到力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩；最大程度的压缩；最大程度的压缩；最大程度的压缩；对给定的信源，使平均码长达到最小的编码方法称为对给定的信源，使平均码长达到最小的编码方法称为对给定的信源，使平均码长达到最小的编码方法称为对给定的信源，使平均码长达到最小的编码方法称为最佳最佳最佳最佳编码编码编码编码，编出的码称为，编出的码称为，编出的码称为，编

37、出的码称为最佳码最佳码最佳码最佳码；三种变长编码方法：三种变长编码方法：三种变长编码方法：三种变长编码方法：霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码、费诺编码费诺编码费诺编码费诺编码以及以及以及以及香农编码香农编码香农编码香农编码；霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码是真正意义下的是真正意义下的是真正意义下的是真正意义下的最佳编码最佳编码最佳编码最佳编码。254.5.1 4.5.1 霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码 二进制霍夫曼编码过程如下：二进制霍夫曼编码过程如下：二进制霍夫曼编码过程如下：二进制霍夫曼编码过程如下：(1)(1)将信源符号按概率大小排序；将信源符号按概率大小排序；

38、将信源符号按概率大小排序；将信源符号按概率大小排序；(2)(2)对概率最小的两个符号求其概率之和，同时给两符号分对概率最小的两个符号求其概率之和，同时给两符号分对概率最小的两个符号求其概率之和，同时给两符号分对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元别赋予码元别赋予码元别赋予码元“0”0”和和和和“1”1”；(3)(3)将将将将“概率之和概率之和概率之和概率之和”当作一个新符号的概率，与剩下符号的当作一个新符号的概率，与剩下符号的当作一个新符号的概率，与剩下符号的当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到概率一起，形成一个缩减信源，再重复

39、上述步骤，直到概率一起，形成一个缩减信源，再重复上述步骤，直到概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和概率之和概率之和概率之和”为为为为1 1为止；为止；为止；为止；(4)(4)按上述步骤实际上构造了一个码树，从树根到端点经过按上述步骤实际上构造了一个码树，从树根到端点经过按上述步骤实际上构造了一个码树，从树根到端点经过按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。的树枝即为码字。的树枝即为码字。的树枝即为码字。26符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i11012001300014000015000001600

40、000062 2进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码。编码。编码。编码。码元集码元集码元集码元集：X X=0,1=0,1 27霍夫曼编码的基本特点霍夫曼编码的基本特点霍夫曼编码的基本特点霍夫曼编码的基本特点 编编编编出出出出的的的的码码码码是是是是非非非非续续续续长长长长码码码码：霍霍霍霍夫夫夫夫曼曼曼曼编编编编码码码码实实实实际际际际上上上上构构构构造造造造了了了了一一一一个个个个码码码码树树树树，码码码码树树树树从从从从最最最最上上上上层层层层的的的的端端端端点点点点开开开开始始始始构构构构造造造造，直直直直到到到到树树树树根根根根结结结结束束束束，最最最最后后后后得得得得到到到到

41、一个横放的码树，而且码字在终端节点上。一个横放的码树，而且码字在终端节点上。一个横放的码树，而且码字在终端节点上。一个横放的码树，而且码字在终端节点上。平平平平均均均均码码码码长长长长最最最最小小小小：霍霍霍霍夫夫夫夫曼曼曼曼编编编编码码码码采采采采用用用用概概概概率率率率匹匹匹匹配配配配方方方方法法法法来来来来决决决决定定定定各各各各码码码码字字字字的的的的码码码码长长长长，概概概概率率率率大大大大的的的的符符符符号号号号对对对对应应应应于于于于短短短短码码码码，概概概概率率率率小小小小的的的的符符符符号号号号对对对对应应应应于长码。于长码。于长码。于长码。码码码码字字字字不不不不唯唯唯唯一

42、一一一：每每每每次次次次对对对对概概概概率率率率最最最最小小小小的的的的两两两两个个个个符符符符号号号号求求求求概概概概率率率率之之之之和和和和形形形形成成成成缩缩缩缩减减减减信信信信源源源源时时时时，就就就就构构构构造造造造出出出出两两两两个个个个树树树树枝枝枝枝，由由由由于于于于给给给给两两两两个个个个树树树树枝枝枝枝赋赋赋赋码码码码元元元元时是任意的，码字不唯一。时是任意的，码字不唯一。时是任意的，码字不唯一。时是任意的，码字不唯一。28定长编码与变长编码冗余压缩效果比较定长编码与变长编码冗余压缩效果比较定长编码与变长编码冗余压缩效果比较定长编码与变长编码冗余压缩效果比较定长编码定长编码

43、定长编码定长编码变长编码变长编码变长编码变长编码码元码元码元码元/符号符号符号符号码元码元码元码元/符号符号符号符号bit/bit/符号符号符号符号bit/bit/码元码元码元码元bit/bit/码元码元码元码元定长编码：定长编码：001，010，011，100，101，110，111变长编码：变长编码：1，01，001，0001，00001，000001，000000cc29码字不唯一码字不唯一30上例另一种霍夫曼编码：上例另一种霍夫曼编码：31符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i0.350.35110.300.300120.200.2000

44、130.100.10000140.040.040000150.0050.00500000160.0050.00500000062 2进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码。编码。编码。编码。码元集码元集码元集码元集：X X=0,1=0,1 码元码元码元码元/符号符号符号符号32符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i0.350.351120.300.301020.200.200120.100.1000130.040.04000140.0050.0050000150.0050.0050000052 2进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码

45、。编码。编码。编码。码元集码元集码元集码元集：X X=0,1=0,1 码元码元码元码元/符号符号符号符号33码字码字码字码字WWi i码长码长码长码长l li i1101200130001400001500000160000006码字码字码字码字WWi i码长码长码长码长l li i112102012001300014000015000005码方差：码方差：码字不同，码长也不同，但码字不同，码长也不同，但平均码长相同，因此编码效平均码长相同，因此编码效率相同。率相同。34r r进制霍夫曼编码进制霍夫曼编码进制霍夫曼编码进制霍夫曼编码 每次求缩减信源时，求每次求缩减信源时，求每次求缩减信源时，求

46、每次求缩减信源时，求r r个最小概率之和，即将个概率最个最小概率之和，即将个概率最个最小概率之和，即将个概率最个最小概率之和，即将个概率最小的小的小的小的r r符号缩减为一个新符号，并分别用符号缩减为一个新符号，并分别用符号缩减为一个新符号，并分别用符号缩减为一个新符号，并分别用1,2,r-11,2,r-1码元表码元表码元表码元表示，直到最后一次缩减时，示，直到最后一次缩减时，示，直到最后一次缩减时，示，直到最后一次缩减时，r r个概率之和为个概率之和为个概率之和为个概率之和为1 1终止。终止。终止。终止。新问题新问题新问题新问题：缩减到最后时剩下不到：缩减到最后时剩下不到：缩减到最后时剩下不

47、到：缩减到最后时剩下不到r r个符号了。个符号了。个符号了。个符号了。为保证平均码长最小，希望缩减到最后刚好还剩下为保证平均码长最小，希望缩减到最后刚好还剩下为保证平均码长最小，希望缩减到最后刚好还剩下为保证平均码长最小，希望缩减到最后刚好还剩下r r个符个符个符个符号。为达到此目的，可给信源号。为达到此目的，可给信源号。为达到此目的，可给信源号。为达到此目的，可给信源添加几个无用的符号添加几个无用的符号添加几个无用的符号添加几个无用的符号（概率（概率（概率（概率为为为为0 0的符号），使得信源符号数的符号），使得信源符号数的符号），使得信源符号数的符号），使得信源符号数q q满足满足满足满足

48、:q=(r-1)q=(r-1)+r+r 信源缩减的次数信源缩减的次数信源缩减的次数信源缩减的次数35符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i0.320.32210.220.22110.180.180220.160.160120.080.0800230.040.0400130.000.003 3进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码。编码。编码。编码。码元集码元集码元集码元集：X X=0,1,2=0,1,2 码元码元码元码元/符号符号符号符号 q q=7=736符号串的霍夫曼编码符号串的霍夫曼编码符号串的霍夫曼编码符号串的霍夫曼编码例：对如下例

49、：对如下例：对如下例：对如下DMSDMS进行进行进行进行2 2进制霍夫曼编码，分别对单个符号和二进制霍夫曼编码，分别对单个符号和二进制霍夫曼编码，分别对单个符号和二进制霍夫曼编码，分别对单个符号和二元符号串进行编码。元符号串进行编码。元符号串进行编码。元符号串进行编码。bit/bit/符号符号符号符号符号符号符号符号概率概率概率概率码字码字码字码字码长码长码长码长u u1 10.450.451 1 1 11 1 1 1u u u u2 2 2 20.350.35010101012 2 2 2u u u u3 3 3 30.200.20000000002 2 2 2码元码元码元码元/符号符号符号

50、符号对对对对单单单单个个个个符符符符号号号号进进进进行行行行编编编编码码码码37符号符号符号符号概率概率概率概率码字码字码字码字码长码长码长码长u u1 1u u1 10.20250.202511112 2u u1 1u u2 20.15750.15750110113 3u u2 2u u1 10.15750.15750010013 3u u2 2u u2 20.12250.12250000003 3u u1 1u u3 30.090.091011013 3u u3 3u u1 10.090.09010101014 4u u2 2u u3 30.070.07010001004 4u u3 3u