第4章信源无失真编码讲义课件

信源的主要问题：信源的主要问题：信源的描述（数学建模）；信源的描述（数学建模）；信源输出信息能力的定量分析（信源熵）；信源输出信息能力的定量分析（信源熵）；信源信息的有效表示（信源编码）。信源信息的有效表示（信源编码）。信源信息的有效表示（信源编码）。信源信息的有效表示（信源编码）。（发送者）（发送者）信道信道信宿信宿信源信源干扰或噪声干扰或噪声消息消息（接收者）（接收者）信源编码信源编码由于信源符号之间存在分布由于信源符号之间存在分布不均匀和相关性不均匀和相关性，使得信源存在，使得信源存在冗余度冗余度，信，信源编码的主要任务就是减少冗余，提高编码效率。源编码的主要任务就是减少冗余，提高编码效率。信源编码的基本途径有两个：信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。使编码中各个符号出现的概率尽可能地相等，即概率均匀化。信源编码分类：信源编码分类：信源编码分类：信源编码分类：无失真编码无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符，它能保证码元序列经译码后能无失真地恢复成信源符，它能保证码元序列经译码后能无失真地恢复成信源符，它能保证码元序列经译码后能无失真地恢复成信源符号序列。号序列。号序列。号序列。有失真编码有失真编码：会改变信源的熵，不可逆压缩，又称：会改变信源的熵，不可逆压缩，又称：会改变信源的熵，不可逆压缩，又称：会改变信源的熵，不可逆压缩，又称熵压缩编码熵压缩编码。无失真信源编码的作用：无失真信源编码的作用：无失真信源编码的作用：无失真信源编码的作用：符号变换符号变换：使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；冗余度压缩冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等：使编码之后的新信源概率分布均匀化，信息含量效率等：使编码之后的新信源概率分布均匀化，信息含量效率等：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于于或接近于于或接近于于或接近于100%100%100%100%。单符号信源无失真编码器模型单符号信源无失真编码器模型单符号信源无失真编码器模型单符号信源无失真编码器模型编码器编码器编码器编码器f f信信信信源源源源f f 是一一对是一一对是一一对是一一对应的映射应的映射应的映射应的映射 bit/bit/bit/bit/码字或码字或码字或码字或bit/bit/bit/bit/符号符号符号符号 bit/bit/bit/bit/码元码元码元码元新信源新信源X ：编码后的信息率编码后的信息率R R ：平均一个码元：平均一个码元：平均一个码元：平均一个码元携带的信息量。携带的信息量。携带的信息量。携带的信息量。bit/bit/bit/bit/码元码元码元码元平均码长越小，每个码元携带的信息平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较量就越多，传输一个码元就传输了较多的信息。多的信息。码元码元码元码元/符号符号符号符号 编码效率编码效率：编码后的实际信息率与编：编码后的实际信息率与编：编码后的实际信息率与编：编码后的实际信息率与编码后的最大信息率之比。码后的最大信息率之比。码后的最大信息率之比。码后的最大信息率之比。新信源的冗余度新信源的冗余度也是也是也是也是码的冗余度码的冗余度码的冗余度码的冗余度：唯一可译码（唯一可译码（唯一可译码（唯一可译码（UDCUDCUDCUDC）：该码的码字组成的任意有限长码字序列：该码的码字组成的任意有限长码字序列：该码的码字组成的任意有限长码字序列：该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列。否则称为都能恢复成唯一的信源序列。否则称为都能恢复成唯一的信源序列。否则称为都能恢复成唯一的信源序列。否则称为非唯一可译码非唯一可译码非唯一可译码非唯一可译码。码是唯一可译码的码是唯一可译码的码是唯一可译码的码是唯一可译码的充分必要条件充分必要条件充分必要条件充分必要条件是：由码中的码字组成的任是：由码中的码字组成的任是：由码中的码字组成的任是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一意有限长的码字序列（也是码元序列），都能唯一划分成一意有限长的码字序列（也是码元序列），都能唯一划分成一意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。个个的码字，且任一码字只与唯一一个信源符号对应。个个的码字，且任一码字只与唯一一个信源符号对应。个个的码字，且任一码字只与唯一一个信源符号对应。奇异码奇异码奇异码奇异码：含相同码字的码。否则称为：含相同码字的码。否则称为：含相同码字的码。否则称为：含相同码字的码。否则称为非奇异码非奇异码非奇异码非奇异码。非续长码非续长码非续长码非续长码：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。否则为否则为否则为否则为续长码续长码续长码续长码。非即时码非即时码非即时码非即时码：如果接收端收到一个完整的码字后，不能立即译：如果接收端收到一个完整的码字后，不能立即译：如果接收端收到一个完整的码字后，不能立即译：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。码，还需等下一个码字开始接收后才能判断是否可以译码。码，还需等下一个码字开始接收后才能判断是否可以译码。码，还需等下一个码字开始接收后才能判断是否可以译码。否则为否则为否则为否则为即时码即时码即时码即时码。举例：下雨天留客天留我不留举例：下雨天留客天留我不留举例：下雨天留客天留我不留举例：下雨天留客天留我不留第第4 4章章 离散无记忆信源无失真编码离散无记忆信源无失真编码4.1 4.1 信源编码概论信源编码概论4.2 4.2 码的唯一可译性码的唯一可译性4.3 4.3 定长编码定理和定长编码方法定长编码定理和定长编码方法4.4 4.4 变长编码定理变长编码定理4.5 4.5 变长编码方法变长编码方法4.6 4.6 几种实用的无失真信源编码几种实用的无失真信源编码4.1 4.1 4.1 4.1 信源编码概论信源编码概论信源编码概论信源编码概论 采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范围之内，因此，图中虚框部分可近似地视为一个等效的围之内，因此，图中虚框部分可近似地视为一个等效的围之内，因此，图中虚框部分可近似地视为一个等效的围之内，因此，图中虚框部分可近似地视为一个等效的无损确定信道无损确定信道无损确定信道无损确定信道，简称为无噪信道，这一点是我们讨论信源编码的前提。简称为无噪信道，这一点是我们讨论信源编码的前提。简称为无噪信道，这一点是我们讨论信源编码的前提。简称为无噪信道，这一点是我们讨论信源编码的前提。1 1 1 1、基本概念、基本概念、基本概念、基本概念噪声噪声噪声噪声信信信信道道道道信源信源信源信源编码编码编码编码信信信信源源源源信信信信宿宿宿宿等效无噪信道等效无噪信道等效无噪信道等效无噪信道信源信源信源信源译码译码译码译码信道信道信道信道编码编码编码编码信道信道信道信道译码译码译码译码无损确定信道无损确定信道无损确定信道无损确定信道（等效）（等效）（等效）（等效）信源信源信源信源编码编码编码编码信信信信源源源源信信信信宿宿宿宿信源信源信源信源译码译码译码译码信源编码分类：信源编码分类：信源编码分类：信源编码分类：无失真编码无失真编码无失真编码无失真编码、有失真编码有失真编码有失真编码有失真编码。无失真编码无失真编码无失真编码无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码冗余度压缩编码冗余度压缩编码冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源，它能保证码元序列经译码后能无失真地恢复成信源，它能保证码元序列经译码后能无失真地恢复成信源，它能保证码元序列经译码后能无失真地恢复成信源符号序列。符号序列。符号序列。符号序列。有失真编码有失真编码有失真编码有失真编码：又称：又称：又称：又称熵压缩编码熵压缩编码熵压缩编码熵压缩编码，将在第，将在第，将在第，将在第6 6 6 6章讨论。章讨论。章讨论。章讨论。无失真信源编码的作用：无失真信源编码的作用：无失真信源编码的作用：无失真信源编码的作用：（1 1 1 1）符号变换）符号变换）符号变换）符号变换：使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；：使信源的输出符号与信道的输入符号相匹配；（2 2 2 2）冗余度压缩）冗余度压缩）冗余度压缩）冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率：使编码之后的新信源概率分布均匀化，信息含量效率：使编码之后的新信源概率分布均匀化，信息含量效率：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于等于或接近于等于或接近于等于或接近于100%100%100%100%。2 2 2 2、编码器模型、编码器模型、编码器模型、编码器模型 码长码长码长码长l li i ：码字码字码字码字w wi i 所含码元的个数。单位：码元所含码元的个数。单位：码元所含码元的个数。单位：码元所含码元的个数。单位：码元/符号，符号，符号，符号，r r r r进制单位进制单位进制单位进制单位/符号。符号。符号。符号。定长码定长码定长码定长码(FLCFLCFLCFLC，Fixed Length code)Fixed Length code)Fixed Length code)Fixed Length code)：码：码：码：码中所有码字均有相同的码长中所有码字均有相同的码长中所有码字均有相同的码长中所有码字均有相同的码长l l；否则称为否则称为否则称为否则称为变长码变长码变长码变长码(VLCVLCVLCVLC，Variable Length code)Variable Length code)Variable Length code)Variable Length code)。平均码长：平均码长：平均码长：平均码长：码码码码WW码字集码字集码字集码字集WW 码字码字码字码字w wi i 码元集码元集码元集码元集 X X码元码元码元码元x xi i 编码器编码器编码器编码器f f信信信信源源源源信源编码信源编码信源编码信源编码f f：一一对应的变换。：一一对应的变换。：一一对应的变换。：一一对应的变换。码元码元码元码元/符号符号符号符号 定长码：定长码：定长码：定长码：码元码元码元码元/符号符号符号符号 平均码长是衡量码的平均码长是衡量码的平均码长是衡量码的平均码长是衡量码的性能的重要参数，性能的重要参数，性能的重要参数，性能的重要参数，“平均平均平均平均码长小码长小码长小码长小”说明平均一个码说明平均一个码说明平均一个码说明平均一个码元所携带的信息量大，信元所携带的信息量大，信元所携带的信息量大，信元所携带的信息量大，信息的冗余就小。息的冗余就小。息的冗余就小。息的冗余就小。例：编码例：编码例：编码例：编码设设设设DMSDMSDMSDMS的概率空间为的概率空间为的概率空间为的概率空间为对其单个符号进行二进制编码。对其单个符号进行二进制编码。对其单个符号进行二进制编码。对其单个符号进行二进制编码。编码器编码器编码器编码器f f信信信信源源源源码元码元码元码元/符号符号符号符号 码元码元码元码元/符号符号符号符号 编码策略编码策略编码策略编码策略：经常出现（概率大）的符号：经常出现（概率大）的符号：经常出现（概率大）的符号：经常出现（概率大）的符号采用较短的码字，不经常出现（概率小）采用较短的码字，不经常出现（概率小）采用较短的码字，不经常出现（概率小）采用较短的码字，不经常出现（概率小）的符号采用较长的码字的符号采用较长的码字的符号采用较长的码字的符号采用较长的码字。编码策略编码策略编码策略编码策略：采用等长的码字：采用等长的码字：采用等长的码字：采用等长的码字。3 3 3 3、编码器的输出、编码器的输出、编码器的输出、编码器的输出编码器编码器编码器编码器f f信信信信源源源源f f 是一一对是一一对是一一对是一一对应的映射应的映射应的映射应的映射 bit/bit/bit/bit/码字码字码字码字或或或或bit/bit/bit/bit/符号符号符号符号 bit/bit/bit/bit/码元码元码元码元新信源新信源新信源新信源X X ：编码后的信息率编码后的信息率编码后的信息率编码后的信息率R R ：平均一个码元携带的信息量。：平均一个码元携带的信息量。：平均一个码元携带的信息量。：平均一个码元携带的信息量。bit/bit/bit/bit/码元码元码元码元平均码长越小，每个码元携带的信息量就越多，传输一个平均码长越小，每个码元携带的信息量就越多，传输一个平均码长越小，每个码元携带的信息量就越多，传输一个平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。码元就传输了较多的信息。码元就传输了较多的信息。码元就传输了较多的信息。4 4 4 4、编码效率、编码效率、编码效率、编码效率 为了衡量编码效果，定义为了衡量编码效果，定义为了衡量编码效果，定义为了衡量编码效果，定义编码效率编码效率编码效率编码效率：编码后的实际信息：编码后的实际信息：编码后的实际信息：编码后的实际信息率与编码后的最大信息率之比。率与编码后的最大信息率之比。率与编码后的最大信息率之比。率与编码后的最大信息率之比。注注注注：编码效率编码效率编码效率编码效率实际上也是新信源实际上也是新信源实际上也是新信源实际上也是新信源X X的信息含量效率或熵的相的信息含量效率或熵的相的信息含量效率或熵的相的信息含量效率或熵的相对率。对率。对率。对率。编码器编码器编码器编码器f f信信信信源源源源新信源的冗余度新信源的冗余度新信源的冗余度新信源的冗余度也是也是也是也是码的冗余度码的冗余度码的冗余度码的冗余度：4.2 4.2 4.2 4.2 码的唯一可译性码的唯一可译性码的唯一可译性码的唯一可译性举例：举例：举例：举例：1 1）下雨天留客天留我不留）下雨天留客天留我不留）下雨天留客天留我不留）下雨天留客天留我不留2 2）明年逢春好不晦气）明年逢春好不晦气）明年逢春好不晦气）明年逢春好不晦气 终年倒运少有余财终年倒运少有余财终年倒运少有余财终年倒运少有余财 此地安能居住此地安能居住此地安能居住此地安能居住 其人好不伤悲其人好不伤悲其人好不伤悲其人好不伤悲无损确定信道无损确定信道无损确定信道无损确定信道（等效）（等效）（等效）（等效）信源信源信源信源编码编码编码编码信信信信源源源源信信信信宿宿宿宿信源信源信源信源译码译码译码译码4.2 4.2 4.2 4.2 码的唯一可译性码的唯一可译性码的唯一可译性码的唯一可译性 f f为一一对应的变换只是无失真编码的必要条件，并不充分为一一对应的变换只是无失真编码的必要条件，并不充分为一一对应的变换只是无失真编码的必要条件，并不充分为一一对应的变换只是无失真编码的必要条件，并不充分;要保证将码元序列无失真地恢复成信源符号序列，还要求编要保证将码元序列无失真地恢复成信源符号序列，还要求编要保证将码元序列无失真地恢复成信源符号序列，还要求编要保证将码元序列无失真地恢复成信源符号序列，还要求编出的码自身具有独特的结构。出的码自身具有独特的结构。出的码自身具有独特的结构。出的码自身具有独特的结构。有实用价值的码应该具有唯一可译性，即能从码字序列（也有实用价值的码应该具有唯一可译性，即能从码字序列（也有实用价值的码应该具有唯一可译性，即能从码字序列（也有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列。是码元序列）唯一地恢复成信源符号序列。是码元序列）唯一地恢复成信源符号序列。是码元序列）唯一地恢复成信源符号序列。无损确定信道无损确定信道无损确定信道无损确定信道（等效）（等效）（等效）（等效）信源信源信源信源编码编码编码编码信信信信源源源源信信信信宿宿宿宿信源信源信源信源译码译码译码译码1 1 1 1、唯一可译码（、唯一可译码（、唯一可译码（、唯一可译码（UDCUDCUDCUDC，Uniquely Decodable CodeUniquely Decodable CodeUniquely Decodable CodeUniquely Decodable Code）唯一可译码（唯一可译码（唯一可译码（唯一可译码（UDCUDCUDCUDC）：该码的码字组成的任意有限长码字序：该码的码字组成的任意有限长码字序：该码的码字组成的任意有限长码字序：该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列。否则称为列都能恢复成唯一的信源序列。否则称为列都能恢复成唯一的信源序列。否则称为列都能恢复成唯一的信源序列。否则称为非唯一可译码非唯一可译码非唯一可译码非唯一可译码。码是唯一可译码的码是唯一可译码的码是唯一可译码的码是唯一可译码的充分必要条件充分必要条件充分必要条件充分必要条件是：由码中的码字组成的是：由码中的码字组成的是：由码中的码字组成的是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分任意有限长的码字序列（也是码元序列），都能唯一划分任意有限长的码字序列（也是码元序列），都能唯一划分任意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。成一个个的码字，且任一码字只与唯一一个信源符号对应。成一个个的码字，且任一码字只与唯一一个信源符号对应。成一个个的码字，且任一码字只与唯一一个信源符号对应。奇异码奇异码奇异码奇异码：含相同码字的码。否则称为：含相同码字的码。否则称为：含相同码字的码。否则称为：含相同码字的码。否则称为非奇异码非奇异码非奇异码非奇异码。非续长码非续长码非续长码非续长码：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。：码中任一码字都不是另一码字的续长（延长）。否则为否则为否则为否则为续长码续长码续长码续长码。非即时码非即时码非即时码非即时码：如果接收端收到一个完整的码字后，不能立即：如果接收端收到一个完整的码字后，不能立即：如果接收端收到一个完整的码字后，不能立即：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译译码，还需等下一个码字开始接收后才能判断是否可以译译码，还需等下一个码字开始接收后才能判断是否可以译译码，还需等下一个码字开始接收后才能判断是否可以译码。否则为码。否则为码。否则为码。否则为即时码即时码即时码即时码。5 5种不同的码种不同的码W1：定长码。：定长码。W3：变长码。：变长码。奇异码。奇异码。定长非奇异码肯定是定长非奇异码肯定是UDCUDC。W2：定长码。：定长码。W4：变长码。：变长码。W5：变长码。：变长码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。续长码。续长码。非续长码。非续长码。续长码。续长码。即时码。即时码。非即时码。非即时码。奇异码肯定不是奇异码肯定不是UDCUDC。不是不是UDCUDC。非续长码肯定是非续长码肯定是UDCUDC。是是UDCUDC。非即时码。非即时码。唯一可译码唯一可译码唯一可译码唯一可译码定长非奇异码定长非奇异码定长非奇异码定长非奇异码非续长码非续长码非续长码非续长码非非非非奇奇奇奇异异异异码码码码码码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码定长非奇异码定长非奇异码变长非续长码变长非续长码（部分）变长续长码（部分）变长续长码非分组码非分组码分组码分组码Sardinas Patterson判断法对信源对信源对信源对信源U U U U编出编出编出编出6 6 6 6种不同的码，如下表所示。种不同的码，如下表所示。种不同的码，如下表所示。种不同的码，如下表所示。1 1 1 1）这）这）这）这6 6 6 6种码分别是什么码？哪些是种码分别是什么码？哪些是种码分别是什么码？哪些是种码分别是什么码？哪些是UDCUDCUDCUDC？2 2 2 2）分别求出各码的平均码长。）分别求出各码的平均码长。）分别求出各码的平均码长。）分别求出各码的平均码长。2 2 2 2、码树、码树、码树、码树 码树从码树从码树从码树从树根树根树根树根开始向上长出开始向上长出开始向上长出开始向上长出树枝树枝树枝树枝，树枝代表码元，树枝与树枝的交点叫，树枝代表码元，树枝与树枝的交点叫，树枝代表码元，树枝与树枝的交点叫，树枝代表码元，树枝与树枝的交点叫做做做做节点节点节点节点 。r r r r进制码树进制码树进制码树进制码树：码元个数为：码元个数为：码元个数为：码元个数为r r r r，各节点（含树根）向上长出的树枝数不大，各节点（含树根）向上长出的树枝数不大，各节点（含树根）向上长出的树枝数不大，各节点（含树根）向上长出的树枝数不大于于于于r r r r。l l阶节点阶节点阶节点阶节点：经过：经过：经过：经过l l 根树枝才能到达的节点。根树枝才能到达的节点。根树枝才能到达的节点。根树枝才能到达的节点。终端节点终端节点终端节点终端节点或或或或端点端点端点端点：向上不长出树枝的节点。：向上不长出树枝的节点。：向上不长出树枝的节点。：向上不长出树枝的节点。码字码字码字码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该：与码树上的节点对应，组成该码字的码元就是从树根开始到该：与码树上的节点对应，组成该码字的码元就是从树根开始到该：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。节点所经过的树枝（或码元）。节点所经过的树枝（或码元）。节点所经过的树枝（或码元）。非续长码非续长码非续长码非续长码：所有码字均处于终端节点，即端点上。：所有码字均处于终端节点，即端点上。：所有码字均处于终端节点，即端点上。：所有码字均处于终端节点，即端点上。整树整树整树整树：r r r r进制码树各节点（包括树根）向上长出的树枝数均等于进制码树各节点（包括树根）向上长出的树枝数均等于进制码树各节点（包括树根）向上长出的树枝数均等于进制码树各节点（包括树根）向上长出的树枝数均等于r r r r。一阶节点一阶节点一阶节点一阶节点二阶节点二阶节点二阶节点二阶节点三阶节点三阶节点三阶节点三阶节点WW1 1=00=00，0101，1010，1111WW4 4=0=0，1010，110110，111111WW5 5=0=0，0101，011011，1111113 3 3 3、KraftKraftKraftKraft不等式不等式不等式不等式 不满足不满足不满足不满足KraftKraftKraftKraft不等式的码肯定不是非续长码；不等式的码肯定不是非续长码；不等式的码肯定不是非续长码；不等式的码肯定不是非续长码；满足满足满足满足KraftKraftKraftKraft不等式的码也不一定是非续长码；不等式的码也不一定是非续长码；不等式的码也不一定是非续长码；不等式的码也不一定是非续长码；根据满足根据满足根据满足根据满足KraftKraftKraftKraft不等式的码长集合可构造出一个非续长码；不等式的码长集合可构造出一个非续长码；不等式的码长集合可构造出一个非续长码；不等式的码长集合可构造出一个非续长码；上述定理对唯一可译码仍然成立。上述定理对唯一可译码仍然成立。上述定理对唯一可译码仍然成立。上述定理对唯一可译码仍然成立。非续长非续长非续长非续长码码码码存在性定理存在性定理存在性定理存在性定理：对于任一：对于任一：对于任一：对于任一 进制进制进制进制非续长码非续长码非续长码非续长码，各码字的码长为，各码字的码长为，各码字的码长为，各码字的码长为 必须满足必须满足必须满足必须满足KraftKraftKraftKraft不等式：不等式：不等式：不等式：反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个 进制进制进制进制非续长码非续长码非续长码非续长码。WW1 1=0=0，1010，110110，111111WW2 2=0=0，0101，011011，111111例如：例如：例如：例如：KraftKraftKraftKraft不等式是惟一可译码不等式是惟一可译码不等式是惟一可译码不等式是惟一可译码存在存在存在存在的充要条件；的充要条件；的充要条件；的充要条件；如果码是唯一可译码，则必定满足该不等式；如果码是唯一可译码，则必定满足该不等式；如果码是唯一可译码，则必定满足该不等式；如果码是唯一可译码，则必定满足该不等式；如果满足如果满足如果满足如果满足KraftKraftKraftKraft不等式，则这种码长的惟一可译码一定存在；不等式，则这种码长的惟一可译码一定存在；不等式，则这种码长的惟一可译码一定存在；不等式，则这种码长的惟一可译码一定存在；但不表示所有满足不等式的码一定是惟一可译码。但不表示所有满足不等式的码一定是惟一可译码。但不表示所有满足不等式的码一定是惟一可译码。但不表示所有满足不等式的码一定是惟一可译码。唯一可译唯一可译唯一可译唯一可译码码码码存在性定理存在性定理存在性定理存在性定理：对于任一：对于任一：对于任一：对于任一 进制进制进制进制唯一可译码（唯一可译码（唯一可译码（唯一可译码（UDCUDC），各码，各码，各码，各码字的码长为字的码长为字的码长为字的码长为 ，必须满足，必须满足，必须满足，必须满足KraftKraft不等式：不等式：不等式：不等式：反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个反过来，若上式成立，就一定能构造一个 进制进制进制进制唯一可译码（唯一可译码（唯一可译码（唯一可译码（UDCUDC）。WW1 1=0=0，1010，110110，111111WW2 2=1=1，1010，011011，111111例如：例如：例如：例如：对任意码字序列对任意码字序列对任意码字序列对任意码字序列 101110111101110111，按按按按WW2 2中的码字，可以分割为中的码字，可以分割为中的码字，可以分割为中的码字，可以分割为1010，111111，011011，1 1或者或者或者或者1 1，011011，1010，1111114.3 4.3 4.3 4.3 定长编码定理和定长编码方法定长编码定理和定长编码方法定长编码定理和定长编码方法定长编码定理和定长编码方法1 1 1 1、对信源输出的符号序列进行编码、对信源输出的符号序列进行编码、对信源输出的符号序列进行编码、对信源输出的符号序列进行编码 DMSDMSDMSDMS编码器编码器编码器编码器f fDMSDMSDMSDMS编码器编码器编码器编码器f f对信源对信源对信源对信源U U的的的的单个符号单个符号单个符号单个符号进进进进行编码行编码行编码行编码 对信源对信源对信源对信源U U的的的的N N长符号串长符号串长符号串长符号串进行编码进行编码进行编码进行编码 对扩展信源对扩展信源对扩展信源对扩展信源U UN N的的的的单个符单个符单个符单个符号号号号进行编码进行编码进行编码进行编码 2 2 2 2、定长编码定理、定长编码定理、定长编码定理、定长编码定理 DMSDMSDMSDMS编码器编码器编码器编码器f fr r进制定长编码，码长为进制定长编码，码长为进制定长编码，码长为进制定长编码，码长为l lN N，可用的码字数目：可用的码字数目：可用的码字数目：可用的码字数目：唯一可译唯一可译唯一可译唯一可译信息传输率信息传输率信息传输率信息传输率编码效率编码效率编码效率编码效率bit/bit/bit/bit/码元码元码元码元 定长无失真编码定理定长无失真编码定理定长无失真编码定理定长无失真编码定理：用：用：用：用r r元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源U U的的的的N N长符号序列进行定长编码，长符号序列进行定长编码，长符号序列进行定长编码，长符号序列进行定长编码，N N N N长符号序列对应的码长为长符号序列对应的码长为长符号序列对应的码长为长符号序列对应的码长为l lN N，若对于任意小的正数，若对于任意小的正数，若对于任意小的正数，若对于任意小的正数 ，有不等式，有不等式，有不等式，有不等式 就几乎能做到无失真编码，且随着序列长度就几乎能做到无失真编码，且随着序列长度就几乎能做到无失真编码，且随着序列长度就几乎能做到无失真编码，且随着序列长度N N的增大，译码的增大，译码的增大，译码的增大，译码差错率趋于差错率趋于差错率趋于差错率趋于0 0 0 0。反过来，若。反过来，若。反过来，若。反过来，若 就不可能做到无失真编码，且随着就不可能做到无失真编码，且随着就不可能做到无失真编码，且随着就不可能做到无失真编码，且随着N N的增大，译码差错率趋的增大，译码差错率趋的增大，译码差错率趋的增大，译码差错率趋于于于于1 1 1 1。3 3 3 3、定长编码方法（例）、定长编码方法（例）、定长编码方法（例）、定长编码方法（例）对对对对U U的单个符号进行的单个符号进行的单个符号进行的单个符号进行2 2 2 2进制编码。进制编码。进制编码。进制编码。码元集码元集码元集码元集：X X=0=0，11 取取取取l l=3=3bit/bit/bit/bit/符号符号符号符号码元码元码元码元/符号符号符号符号码元码元码元码元/符号符号符号符号解：解：解：解：提高编码效率的方法提高编码效率的方法提高编码效率的方法提高编码效率的方法：对符号串进行编码，同时引入一定的失真。：对符号串进行编码，同时引入一定的失真。：对符号串进行编码，同时引入一定的失真。：对符号串进行编码，同时引入一定的失真。P115 P115 P115 P115 4.4 4.4 4.4 4.4 变长编码定理变长编码定理变长编码定理变长编码定理(香农第一定理香农第一定理香农第一定理香农第一定理 )无失真变长编码定理无失真变长编码定理无失真变长编码定理无失真变长编码定理：用：用：用：用 元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源元符号表对离散无记忆信源 的的的的 长符号串长符号串长符号串长符号串进行变长编码，记进行变长编码，记进行变长编码，记进行变长编码，记 长符号串对应的平均码长为长符号串对应的平均码长为长符号串对应的平均码长为长符号串对应的平均码长为 ，那么，要做到无失，那么，要做到无失，那么，要做到无失，那么，要做到无失真编码，平均码长真编码，平均码长真编码，平均码长真编码，平均码长 必须满足必须满足必须满足必须满足 另一方面，一定存在唯一可译码，其平均码长另一方面，一定存在唯一可译码，其平均码长另一方面，一定存在唯一可译码，其平均码长另一方面，一定存在唯一可译码，其平均码长 满足满足满足满足变长编码不要求所有码字长度相同，但要求平均码长最小。变长编码不要求所有码字长度相同，但要求平均码长最小。变长编码不要求所有码字长度相同，但要求平均码长最小。变长编码不要求所有码字长度相同，但要求平均码长最小。N N N N趋于无穷时平均码长和编码效率的极限：趋于无穷时平均码长和编码效率的极限：趋于无穷时平均码长和编码效率的极限：趋于无穷时平均码长和编码效率的极限：随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的熵，编码效率提高，当然编码过程也愈复杂。熵，编码效率提高，当然编码过程也愈复杂。熵，编码效率提高，当然编码过程也愈复杂。熵，编码效率提高，当然编码过程也愈复杂。例：对二元例：对二元DMS进行无失真编码：进行无失真编码：N=1若用二元码符号若用二元码符号(0，1)进行定长编码：进行定长编码：。平均码长平均码长 1 码元码元/信源符号信源符号编码效率为编码效率为输出的信息效率输出的信息效率要求：对比定长编码与变长编码的编码效率（要求：对比定长编码与变长编码的编码效率（N=2,3,4）。）。练习题对对U的二次扩展信源进行定长编码，码表如下表的二次扩展信源进行定长编码，码表如下表：uip(ui)码字u1u19/1600u1u23/1601u2u13/1610u2u21/1611编码效率为编码效率为码字平均长度码字平均长度单个符号的平均码长单个符号的平均码长N=2N=3,4时，对对U的二次扩展信源进行变长编码，码表如下表的二次扩展信源进行变长编码，码表如下表：uip(ui)码字u1u19/160u1u23/1610u2u13/16110u2u21/16111N=2编码效率为编码效率为码字平均长度码字平均长度单个符号的平均码长单个符号的平均码长N=3,4时，分析：分析：1、比较定长编码与变长编码的编码效率可知，尤其在、比较定长编码与变长编码的编码效率可知，尤其在N较大时变长编码的效率远大于定长编码。较大时变长编码的效率远大于定长编码。N定长变长20.8110.96130.8110.98540.8110.9912、若对定长编码与变长编码同样要求编码效率达到、若对定长编码与变长编码同样要求编码效率达到96%，允许的译码错误概率允许的译码错误概率 时，定长编码所需序列长度时，定长编码所需序列长度N：所需的信源序列长度：所需的信源序列长度：同样的编码效率，变长编码信源序列长度同样的编码效率，变长编码信源序列长度N=2时即可满足时即可满足编码效率达到编码效率达到96%的要求。随着的要求。随着N的增加，编码效率趋近的增加，编码效率趋近于于1。4.5 4.5 4.5 4.5 变长编码方法变长编码方法变长编码方法变长编码方法 变长编码采用变长编码采用变长编码采用变长编码采用非续长码；非续长码；非续长码；非续长码；力求平均码长最小，此时编码效率最高，信源的冗余得到力求平均码长最小，此时编码效率最高，信源的冗余得到力求平均码长最小，此时编码效率最高，信源的冗余得到力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩；最大程度的压缩；最大程度的压缩；最大程度的压缩；对给定的信源，使平均码长达到最小的编码方法称为对给定的信源，使平均码长达到最小的编码方法称为对给定的信源，使平均码长达到最小的编码方法称为对给定的信源，使平均码长达到最小的编码方法称为最佳最佳最佳最佳编码编码编码编码，编出的码称为，编出的码称为，编出的码称为，编出的码称为最佳码最佳码最佳码最佳码；三种变长编码方法：三种变长编码方法：三种变长编码方法：三种变长编码方法：霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码、费诺编码费诺编码费诺编码费诺编码以及以及以及以及香农编码香农编码香农编码香农编码；霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码是真正意义下的是真正意义下的是真正意义下的是真正意义下的最佳编码最佳编码最佳编码最佳编码。1 1 1 1、霍夫曼编码、霍夫曼编码、霍夫曼编码、霍夫曼编码 二进制霍夫曼编码过程如下：二进制霍夫曼编码过程如下：二进制霍夫曼编码过程如下：二进制霍夫曼编码过程如下：（1 1 1 1）将信源符号按概率大小排序；）将信源符号按概率大小排序；）将信源符号按概率大小排序；）将信源符号按概率大小排序；（2 2 2 2）对概率最小的两个符号求其概率之和，同时给两符号）对概率最小的两个符号求其概率之和，同时给两符号）对概率最小的两个符号求其概率之和，同时给两符号）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元分别赋予码元分别赋予码元分别赋予码元“0 0 0 0”和和和和“1 1 1 1”；（3 3 3 3）将）将）将）将“概率之和概率之和概率之和概率之和”当作一个新符号的概率，与剩下符号当作一个新符号的概率，与剩下符号当作一个新符号的概率，与剩下符号当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到的概率一起，形成一个缩减信源，再重复上述步骤，直到的概率一起，形成一个缩减信源，再重复上述步骤，直到的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和概率之和概率之和概率之和”为为为为1 1 1 1为止；为止；为止；为止；（4 4 4 4）按上述步骤实际上构造了一个码树，从树根到端点经）按上述步骤实际上构造了一个码树，从树根到端点经）按上述步骤实际上构造了一个码树，从树根到端点经）按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。过的树枝即为码字。过的树枝即为码字。过的树枝即为码字。符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i11012001300014000015000001600000062 2 2 2进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码。编码。编码。编码。码元集码元集码元集码元集：X X=0=0，11 霍夫曼编码的基本特点霍夫曼编码的基本特点霍夫曼编码的基本特点霍夫曼编码的基本特点 编出的码是非续长码编出的码是非续长码编出的码是非续长码编出的码是非续长码：霍夫曼编码实际上构造了一个码树，：霍夫曼编码实际上构造了一个码树，：霍夫曼编码实际上构造了一个码树，：霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到码树从最上层的端点开始构造，直到树根结束，最后得到码树从最上层的端点开始构造，直到树根结束，最后得到码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树。一个横放的码树。一个横放的码树。一个横放的码树。平均码长最小平均码长最小平均码长最小平均码长最小：霍夫曼编码采用概率匹配方法来决定各码：霍夫曼编码采用概率匹配方法来决定各码：霍夫曼编码采用概率匹配方法来决定各码：霍夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应字的码长，概率大的符号对应于短码，概率小的符号对应字的码长，概率大的符号对应于短码，概率小的符号对应字的码长，概率大的符号对应于短码，概率小的符号对应于长码。于长码。于长码。于长码。码字不唯一码字不唯一码字不唯一码字不唯一：每次对概率最小的两个符号求概率之和形成：每次对概率最小的两个符号求概率之和形成：每次对概率最小的两个符号求概率之和形成：每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元缩减信源时，就构造出两个树枝，由于给两个树枝赋码元缩减信源时，就构造出两个树枝，由于给两个树枝赋码元缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，码字不唯一。时是任意的，码字不唯一。时是任意的，码字不唯一。时是任意的，码字不唯一。定长编码与变长编码冗余压缩效果比较定长编码与变长编码冗余压缩效果比较定长编码与变长编码冗余压缩效果比较定长编码与变长编码冗余压缩效果比较定长编码定长编码定长编码定长编码(P115)(P115)变长编码变长编码变长编码变长编码码元码元码元码元/符号符号符号符号码元码元码元码元/符号符号符号符号bit/bit/bit/bit/符号符号符号符号bit/bit/bit/bit/码元码元码元码元bit/bit/bit/bit/码元码元码元码元定长编码：定长编码：001，010，011，100，101，110，111变长编码：变长编码：1，01，001，0001，00001，000001，000000符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i0.350.350.350.35110.300.300.300.300120.200.200.200.2000130.100.100.100.10000140.040.040.040.040000150.0050.0050.0050.00500000160.0050.0050.0050.00500000062 2 2 2进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码。编码。编码。编码。码元集码元集码元集码元集：X X=0=0，11 码元码元码元码元/符号符号符号符号符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i0.350.350.350.351120.300.300.300.301020.200.200.200.200120.100.100.100.1000130.040.040.040.04000140.0050.0050.0050.0050000150.0050.0050.0050.0050000052 2 2 2进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码。编码。编码。编码。码元集码元集码元集码元集：X X=0=0，11 码元码元码元码元/符号符号符号符号码字码字码字码字WWi i码长码长码长码长l li i1101200130001400001500000160000006码字码字码字码字WWi i码长码长码长码长l li i112102012001300014000015000005码方差：码方差：码字不同，码长也不同，但码字不同，码长也不同，但平均码长相同，因此编码效平均码长相同，因此编码效率相同。率相同。r r r r进制霍夫曼编码进制霍夫曼编码进制霍夫曼编码进制霍夫曼编码 每次求缩减信源时，求每次求缩减信源时，求每次求缩减信源时，求每次求缩减信源时，求r r r r个最小概率之和，即将概率最小个最小概率之和，即将概率最小个最小概率之和，即将概率最小个最小概率之和，即将概率最小的的的的r r r r符号缩减为一个新符号，直到概率之和为符号缩减为一个新符号，直到概率之和为符号缩减为一个新符号，直到概率之和为符号缩减为一个新符号，直到概率之和为1 1 1 1终止。终止。终止。终止。新问题新问题新问题新问题：缩减到最后时剩下不到：缩减到最后时剩下不到：缩减到最后时剩下不到：缩减到最后时剩下不到r r r r个符号了。个符号了。个符号了。个符号了。为保证平均码长最小，希望缩减到最后刚好还剩下为保证平均码长最小，希望缩减到最后刚好还剩下为保证平均码长最小，希望缩减到最后刚好还剩下为保证平均码长最小，希望缩减到最后刚好还剩下r r r r个符个符个符个符号。为达到此目的，可给信源号。为达到此目的，可给信源号。为达到此目的，可给信源号。为达到此目的，可给信源添加几个无用的符号添加几个无用的符号添加几个无用的符号添加几个无用的符号（概率（概率（概率（概率为为为为0 0 0 0的符号），使得信源符号数的符号），使得信源符号数的符号），使得信源符号数的符号），使得信源符号数q q q q满足满足满足满足:q+i=(r-1)q+i=(r-1)q+i=(r-1)q+i=(r-1)+r+r+r+r 信源缩减的次数信源缩减的次数信源缩减的次数信源缩减的次数增加无用符号增加无用符号增加无用符号增加无用符号的个数的个数的个数的个数符号符号符号符号概率概率概率概率码字码字码字码字WWi i码长码长码长码长l li i0.320.320.320.32210.220.220.220.22110.180.180.180.180220.160.160.160.160120.080.080.080.0800230.040.040.040.0400130.000.000.000.003 3 3 3进制进制进制进制霍夫曼霍夫曼霍夫曼霍夫曼编码。编码。编码。编码。码元集码元集码元集码元集：X X=0=0，1 1，22 码元码元码元码元/符号符号符号符号符号串的霍夫曼编码符号串的霍夫曼编码符号串的霍夫曼编码符号串的霍夫曼编码例：对如下例：对如下例：对如下例：对如下DMSDMSDMSDMS进行进行进行进行2 2 2 2进制霍夫曼编码，分别对单个符号和二进制霍夫曼编码，分别对单个符号和二进制霍夫曼编码，分别对单个符号和二进制霍夫曼编码，分别对单个符号和二元符号串进行编码。元符号串进行编码。元符号串进行编码。元符号串进行编码。bit/bit/bit/bit/符号符号符号符号符号符号符号符号概率概率概率概率码字码字码字码字码长码长码长码长u u1 10.450.450.450.451 1 1 11 1 1 1u u u u2 2 2 20.350.350.350.35010101012 2 2 2u u u u3 3 3 30.200.200.200.20000000002 2 2 2码元码元码元码元/符号符号符号符号对对对对单单单单个个个个符符符符号号号号进进进进行行行行编编编编码码码码符号符号符号符号概率概率概率概率码字码字码字码字码长码长码长码长u u1 1u u1 10.20250.20250.20250.202511112 2u u1 1u u2 20.15750.15750.15750.15750110113 3u u2 2u u1 10.15750.15750.15750.15750010013 3u u2 2u u2 20.12250.12250.12250.12250000003 3u u1 1u u3 30.090.090.090.091011013 3u u3 3u u1 10.090.090.090.09010101014 4u u2 2u u3 30.070.070.070.07010001004 4u u3 3u u2 20.070.070.070.07100110014 4u u3 3u u3 30.040.040.040.04100010004 4码元码元码元码元/符号符号符号符号对二元符号串进行编码对二元符号串进行编码对二元符号串进行编码对二元符号串进行编码2 2 2 2、费诺（、费诺（、费诺（、费诺（FanoFanoFanoFano）编码）编码）编码）编码 费诺（费诺（费诺（费诺（FanoFanoFanoFano）编码也是构造一个码树，因此，编出的码是）编码也是构造一个码树，因此，编出的码是）编码也是构造一个码树，因此，编出的码是）编码也是构造一个码树，因此，编出的码是非续长码，但不一定是最佳码。非续长码，但不一定是最佳码。非续长码，但不一定是最佳码。非续长码，但不一定是最佳码。费诺编码步骤费诺编码步骤费诺编码步骤费诺编码步骤(以二进制编码为例以二进制编码为例以二进制编码为例以二进制编码为例)：（1 1 1 1）将信源符号按概率从大到小的排序；）将信源符号按概率从大到小的排序；）将信源符号按概率从大到小的排序；）将信源符号按概率从大到小的排序；（2 2 2 2）将信源符号分成）将信源符号分成）将信源符号分成）将信源符号分成2 2 2 2组，使组，使组，使组，使2 2 2 2组信源符号的概率之和近组信源符号的概率之和近组信源符号的概率之和近组信源符号的概率之和近似相等，并给似相等，并给似相等，并给似相等，并给2 2 2 2组信源符号分别赋码元组信源符号分别