第5章 无失真信源编码精选文档.ppt

第5章 无失真信源编码中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT,本讲稿第一页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 第第五五章章 无失真信源编码无失真信源编码5.1 信源编码的相关概念信源编码的相关概念5.2 定长码及定长编码定理定长码及定长编码定理5.3 变长码及变长编码定理变长码及变长编码定理5.4 变长码的编码方法变长码的编码方法5.5 实用的无失真信源码方法实用的无失真信源码方法本讲稿第二页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1 信源编码的相关概念信源编码的相关概念5.1.1 编码器编码器 信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为码序列码序列，对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码编码，完成编码功能的器件，称为编码器编码器。接收端有一个译码器译码器完成相反的功能。讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。本讲稿第三页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 图5.1是一个信源编码器，它的输入是信源符号（字母）集 ，同时存在另一符号（码字母）集 ，一般来说，元素 是适合信道传输的，称为码符号（或者码元）。编码器的功能就是将信源符号集中的符号 （或者长为N的信源符号序列 ）变换成由 组成 ，其的长度为 的一一对应的序列。5.1.1 编码器编码器 本讲稿第四页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 编 码 器输出图图5.1 无失真信源编码器无失真信源编码器码字母表码字母表码序列码序列信源符号序列信源符号序列5.1.1 编码器编码器本讲稿第五页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT BCD码（码（8421码）码）0 00001 00012 00103 00114 01005 01016 01107 01118 10009 10015.1.1 编码器编码器本讲稿第六页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.1 编码器编码器本讲稿第七页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.1 编码器编码器本讲稿第八页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.1 编码器编码器本讲稿第九页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 可见，编码就是从信源符号到码符号的一种映射，编码就是从信源符号到码符号的一种映射，即若 ，称f为定长编码；否则，f为变长编码。平均码长：平均码长：若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。5.1.1 编码器编码器本讲稿第十页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.1 编码器编码器信源编码有以下3种主要方法：(1)匹配编码匹配编码根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。将要讲述的香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。(2)变换编码变换编码 先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。(3)识别编码识别编码识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如中文文字和语音的识别。后两种信源编码均为有失真的信源编码。无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。本讲稿第十一页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 下面，我们给出这些码的定义。1.二元码二元码若码符号集为 ，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。2.等长码等长码若一组码中所有码字的码长都相同，即 ，则称为等长码。3.变长码变长码若一组码组中各码字的码长长短不一，则称为变长码。5.1.2 码的分类码的分类本讲稿第十二页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.2 码的分类码的分类4.分组码和非分组码分组码和非分组码 定义定义5.1 将信源符号集中的每个信源符号 固定地映射成一个码字 ，这样的码称为分组码。分组码。用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非非分组码分组码，又称为树码树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。5.奇异码与非奇异码奇异码与非奇异码 定义定义5.2 若一种分组码中的所有码字都不相同，则称此分组码为非奇异码非奇异码，否则称为奇异码奇异码。本讲稿第十三页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.2 码的分类码的分类奇异码与非奇异码奇异码与非奇异码 信源符号信源符号符号出现概率符号出现概率码码1 1码码2 2码码3 3码码4 41/21/20 00 01 11 11/41/411111010101001011/81/8000000001001000010011/81/8111101011000100000010001注释注释变长、奇变长、奇异码异码变长，非变长，非奇奇异异码，非唯码，非唯一可译码一可译码变长，非变长，非奇异、唯奇异、唯一可译一可译、非即时码非即时码变长，非变长，非奇异、唯奇异、唯一可译、一可译、即时码即时码本讲稿第十四页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.2 码的分类码的分类6.唯一可译码与非唯一可译码唯一可译码与非唯一可译码 定义定义5.3 任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码唯一可译码。唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。下雨天，留客，天留我不留。下雨天，留客，天留我不留。下雨天，留客天，留我不？留。下雨天，留客天，留我不？留。7.即时码与非即时码即时码与非即时码 定义定义5.4 无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码即时码。本讲稿第十五页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.2 码的分类码的分类 下面讨论唯一可译码成为即时码的条件。定义定义5.5 设 为一码字，对于任意的 ，称码符号序列的前j个元素 为码字的前缀。按照上述的前缀的定义，有下述结论：定理定理5.1 一个唯一可译码成为即时码 的充要条件是其中任何一个码字都不是 其他码字的前缀。即时码可以用树图来构造图5.2是一个 二元即时码的树图图5.2 二元即时码的树图本讲稿第十六页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.1.2 码的分类码的分类 树是没有回路的图，所以它也是由节点和弧构成的树中最顶部的节点称为根节点根节点，没有子节点的节点称为叶子节点叶子节点。所有根节点的子节点称为一阶节点一阶节点，所有一阶节点的子节点称为二阶节点二阶节点，依此类推。阶节点最多有 个。节点的阶次又称为节点的深度深度。综上所述，可将信源编码作如下分类：码非分组码（树码）分组码（块码）奇异码非奇异码非唯一可译码唯一可译码即时码非即时码本讲稿第十七页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。设信源输出符号序列长度为N，码字的长度为 ，编码的目的，就是要使信源的信息率最小，也就是说，要用最少的符号来代表信源。5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第十八页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.2 定长码及定长编码定理定长码及定长编码定理 若对一个有q个信源符号的信源X进行定长编码，那么信源X存在唯一可译定长码的条件是 (5.1)其中，r是码符号集中的码元数，l是定长码的码长。如果对信源S的N次扩展信源 进行定长编码，若要编得的定长码是唯一可译码，则必须满足 (5.2)其中，q是信源X的符号个数，是信源X的N次扩展信源 的符号个数，r是码符号集B的码符号数。本讲稿第十九页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 一、基本概念一、基本概念若信源符号序列，共 个变换成定长码序列，共 个1、编码速率：、编码速率：码序列最大信息量与信源序列长度N平均最大信息量（信息传输率信息传输率），单位bit/符号。5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 2、信息传输率：、信息传输率：编码后平均每个码元携带的信息量，即二、定长编码定理二、定长编码定理由N个符号组成的、每个符号熵为 的无记忆平稳信源符号序列 ，可用 个符号（每个符号有r中可能值）进行定长变码。对任意 ，只要5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十一页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 则当N足够大时，必可使译码差错小于 ；反之，当时，译码差错一定是有限值，即当N足够大时，译码几乎必定出错。5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十二页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件是所取得信源序列长度N足够大。设差错概率为 ，信源序列的自方差为则有：5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十三页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 当 和 均为定值时，只要N足够大，可一小于任一正数 ，即此时要求：5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十四页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 只要 足够小，就可以几乎无差错地译码，当然代价是N变得更大。令为码字最大平均符号信息量。三、三、编码效率编码效率1、定义、定义5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十五页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 2、最佳编码效率为、最佳编码效率为四、指导意义四、指导意义无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的N非常大进行统一编码才行，这往往是不现实的。5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十六页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 例题：设离散无记忆信源概率空间为信源熵为自信息方差为五、应用举例五、应用举例5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十七页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十八页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 对信源符号采用定长二元编码，要求编码效率 ，无记忆信源有 ，因此可以得到如果要求译码错误概率 ，则5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第二十九页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要 个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。如果用3比特来对上述信源的8个符号进行定长二元编码，N=1，此时可实现译码无差错，但编码效率只有2.55/3=85%。5.2 定长码及定长编码定理定长码及定长编码定理本讲稿第三十页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.2 定长码及定长编码定理定长码及定长编码定理 定长编码的信息传输效率是很低的。提高信息传输效率的方法有：方法方法1 考虑符号之间的依赖关系，对信源S的扩展信源进行编码。方法方法2对于概率等于0或非常小的符号序列不予编码。因此，一般说来，当N有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。本讲稿第三十一页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3 变长码及变长编码定理变长码及变长编码定理5.3.1 Kraft不等式和不等式和McMillan不等式不等式 定理定理5.3 设信源符号集为 ，码符号集为 ，对信源进行编码，得到的码为 ，码长分别为 。即时码存在的充要条件是 这称为Kraft不等式不等式。由Kraft不等式可知，给定r和q，只要允许码字长度可以足够长，则码长总可以满足Kraft不等式而得到即时码，Kraft不等式指出了即时码的码长必须满足的条件(5.11)本讲稿第三十二页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.1 Kraft不等式和不等式和McMillan不等式不等式 对于唯一可译码，该不等式又称为McMillan不等式。定理定理5.4 唯一可译码存在的充要条件是 r为码符号个数，为码字长度，q为信源符号个数。定理5.4指出了唯一可译码中r、q、之间的关系，如果满足这个不等式的条件，则一定能够构成至少一种唯一可译码，否则，无法构成唯一可译码它给出了唯一可译变长码的存在性。另外，从定理5.3和定理5.4可以得到一个重要的结论，即任何一个唯一可译码均可用一个相同码长的即时码来代替，因为即时码很容易用树图法构造，因此要构造唯一可译码，只要构造即时码就可以了。(5.12)本讲稿第三十三页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.2 唯一可译码的判别准则唯一可译码的判别准则 A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判断码C的唯一可译性此算法的原理如下所示：其中 都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时 一定是 的前缀，而 的尾随后缀一定是另一码字 的前缀；而 的尾随后缀又是其他码字的前缀最后，码符号序列的尾部一定是一个码字。本讲稿第三十四页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.2 唯一可译码的判别准则唯一可译码的判别准则 设C为码字集合，按以下步骤构造此码的尾随后缀集合F：(1)考查C中所有的码字，若 是 的前缀，则将相应的后缀作为一个尾随后缀码放入集合 中；(2)考查C和 两个集合，若 是 的前缀或 是 的前缀，则将相应的后缀作为尾随后缀码放入集合 中；(3)即为码C的尾随后缀集合；(4)若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。定理定理5.5 一个码是唯一可译码的充要条件是的 并集中没有C中的码字。本讲稿第三十五页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.2 唯一可译码的判别准则唯一可译码的判别准则例题：例题：设码C=0,10,1100,1110,1011,1101，根据上述测试方法，判断是否是唯一可译码。解：1.先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀。2.再观察码字“10”，它是码字“1011”的前缀，因此有尾随后缀：1011001001所以，对于10码：集合F=11，00，10，01，其中“10”为码字，故码C不是唯一可译码。也可以看出码元序列 10111010，11101011，10显然不是唯一可译的。本讲稿第三十六页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.3 无失真变长编码定理无失真变长编码定理一、基本概念一、基本概念 在变长编码中，码长是变化的。对同一信源，其即时码或唯一可译码可以有许多种。究竟哪一种好呢？从高速传输信息的观点来考虑，当然 希望选择由短的码符号组成的码字，就是用码长来作为选择准则，为此我们引入码的平均长度。它是每个信源符号平均需用的码元数。对某一信源来说，若有一个唯一可译码，其平均长度小于所有其它的唯一可译码的平均长度，则该码称为紧致码，或称最佳码。无失真变长信源编码的基本问题就是要找最佳码。本讲稿第三十七页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 1、平均码长、平均码长（1）单符号（）单符号（L=1）设信源为编码后的码字为其码长分别为因为对唯一可译码来说，信源符号与码字是一一对应的，所以有则这个码的平均长度为5.3.3 无失真变长编码定理无失真变长编码定理本讲稿第三十八页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT（2）序列符号（）序列符号（N1 ）编码后的码字分别为对应的码字长度分别为则平均码长为5.3.3 无失真变长编码定理无失真变长编码定理本讲稿第三十九页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 2 2、编码速率：、编码速率：码序列最大信息量与信源序列长度N之比值，实际表示单个信源符号经编码后能够达到平均最大信息量，单位bit/符号。5.3.3 无失真变长编码定理无失真变长编码定理本讲稿第四十页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.3 无失真变长编码定理无失真变长编码定理 3、信息传输率：信息传输率：编码后平均每个码元携带的信息量，如果传输一个码符号平均需要t秒时间，则编码后信源每秒钟提供的信息量为 可以看出，越小，则 越大，信息传输率就越高，因此我们感兴趣的码是使平均码长 最短的码。4、最佳码：最佳码：对于给定的信源和码符号集，若有一个唯一可译码，其平均码长 小于所有其他唯一可译码，则称这种码为紧致码紧致码或最佳码最佳码。无失真信源编码的核心问题就是寻找紧致码比特/码符号本讲稿第四十一页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.3 无失真变长编码定理无失真变长编码定理 下面的定理给出了紧致码的平均码长可能达到的理论极限 定理定理5.6 若一个离散无记忆信源X，熵为H(X)，用拥有r个码符号的码符号集 对X进行无失真编码，则总可以找到一种唯一可译码，其平均码长满足 若用编码速率表示，上式可写成 另外还可以看到平均码长的极限值与无失真定长信源编码定理中的极限值是一致的。(5.23)(5.33)二、单个符号变长编码定理二、单个符号变长编码定理本讲稿第四十二页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.4 香农第一编码定理香农第一编码定理 定理定理5.7 设离散无记忆信源X的信源熵H(X)，它的N次扩展信源 ，其熵 。并用码符号 对信源 进行编码，总可以找到一种唯一可译码，使信源X中每个信源符号所需的平均码长满足 或者写成 进一步写成 定理5.6可以看作定理5.7在N=1时的特殊情况。定理5.7是香农信息论的主要定理之一。(5.34)(5.35)三、离散平稳无记忆序列变长编码定理三、离散平稳无记忆序列变长编码定理本讲稿第四十三页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.4 香农第一编码定理香农第一编码定理四、指导意义 香农第一编码定理给出了码字的平均长度的下界和上界。但并不是说大于这上界不能构成唯一可译码，而是因为我们总是希望 尽可能短。定理说明当平均码长小于上界时，唯一可译码也存在。也就是说，定理给出的是最佳码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源(信道的输入)尽可能为等概率分布，使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到信道容量，实现信源与信道理想的统计匹配。这就是香农第一定理的物理意义。本讲稿第四十四页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.4 香农第一编码定理香农第一编码定理 为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。定义定义5.12 定义 为编码效率编码效率，对同一信源来说，码的平均码长 越短，越接近极限 ，信道的信息传输率越高，越接近无噪无损信道的信道容量，这时也越接近于1，所以用码的效率来衡量各种编码的优劣。(5.44)五、编码效率与五、编码效率与剩余度剩余度本讲稿第四十五页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.3.4 香农第一编码定理香农第一编码定理 另外，为了衡量各种编码与最佳码的差距，引入码的剩余度的概念。定义定义5.13 定义 为码的剩余度剩余度。在二元无噪无损信道中r=2，所以在二元无噪无损信道中信息传输率 注意它们数值相同，单位不同是个无单位的比值，而R的单位是比特/码符号。(5.45)本讲稿第四十六页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 六、应用举例六、应用举例例题：设离散无记忆信源的概率空间为5.3.4 香农第一编码定理香农第一编码定理本讲稿第四十七页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 其信源熵为若用二元定长编码（0，1）来构造一个即时码：，这时平均码长为编码效率为 5.3.4 香农第一编码定理香农第一编码定理本讲稿第四十八页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 输出的信息率为再对长度为2的信源序列进行变长编码，其即时码如下表所示：序列序列概率即时码 序列序列概率即时码 9/16 0 3/16 110 3/16 10 1/16 1115.3.4 香农第一编码定理香农第一编码定理本讲稿第四十九页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 这个码的平均长度为：编码速率为：其编码效率和信息传输率为：5.3.4 香农第一编码定理香农第一编码定理本讲稿第五十页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 编码复杂了，但信息传输率和效率有了提高。同样可以求得信源序列长度增加到3和4时，进行变长编码所得的编码效率和信息传输率分别为如果对这一信源采用定长二元码编码，要求编码效率达到96%，允许译码错误概率 ，则5.3.4 香农第一编码定理香农第一编码定理本讲稿第五十一页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 可以算出自信息方差为 为需要的信源序列长度为5.3.4 香农第一编码定理香农第一编码定理本讲稿第五十二页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 可以看出，使用定长编码时，为了使编码效率较高（96%），需要对非常长的信源序列进行编码，且总存在译码差错。而使用变长编码，为了使编码效率达到96%，只要N=2就行了，且可以实现无失真编码。当然，变长编码的译码相对来说要复杂一些。5.3.4 香农第一编码定理香农第一编码定理本讲稿第五十三页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.4 变长码的编码方法变长码的编码方法 本章介绍的变长码的常见编码方法，如香农编码、香农-费诺-埃利斯编码、霍夫曼编码、费诺编码均为匹配编码，也称统计编码统计编码，都是通过使用较短的码字来给出现概率较高的信源符号编码。而出现概率较小的信源符号用较长的码字来编码，从而使平均码长最短，达到最佳编码的目的。下面介绍这几种方法：5.4.1 香农编码香农编码 香农码的方法是选择每个码字长度 满足 按照香农编码方法构造的码，其平均码长 不超过上界，即本讲稿第五十四页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.4.1 香农编码香农编码其具体方法如下：(1)将信源发出的q个消息符号按其概率的递减次序排列(2)计算出各个信源符号的累加概率(3)按下式计算第i个消息的二元代码组的码长(4)将累加概率 (十进制小数)变换成二进制小数。根据码长 取小数点后 个二进制符号作为第i个消息的码字。本讲稿第五十五页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 例例1 1：设信源共有设信源共有7 7个符号组成，个符号组成，其概率如表所示，其概率如表所示，求其香农码。求其香农码。信源消息符号信源消息符号符号概率符号概率 0.20 0.19 0.18 0.17 0.15 0.10 0.015.4.1 香农编码香农编码本讲稿第五十六页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 符号概率累加概率码字长度 码 字0.2002.3430000.190.22.4130010.180.392.4830110.170.572.5631000.150.742.7431010.100.893.34411100.010.996.66711111105.4.1 香农编码香农编码本讲稿第五十七页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 以 为例，累加概率 ，变成二进制数，为0.1001，转换的方法是：用 乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到了满足要求的位数，或者没有小数部分了为止。5.4.1 香农编码香农编码本讲稿第五十八页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 例如现在 ，乘以2为1.14，整数部分有进位，所以小数点后第一位为1，将小数部分即0.14再乘以2，得0.28，没有整数进位，所以小数点后第二位为0，依此类推，可得到其对应的二进制数为0.1001。可以看出，编码所得的码字，没有相同的，所以是非奇异码，也没有一个码字是其它码字的前缀，所以是即时码。唯一可译码。平均码长为：5.4.1 香农编码香农编码本讲稿第五十九页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 平均信息传输率为香农编码的效率不高，实用意义不大，但对其它编码方法有很好的理论指导意义。5.4.1 香农编码香农编码本讲稿第六十页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.4.2 香农香农-费诺费诺-埃利斯编码埃利斯编码 将香农编码中的累加概率换成修正累加概率即可得到相应的香农-费诺-埃利斯编码：(1)计算出各个信源符号的修正累加概率 (2)按下式计算第i个消息的二元代码组的码长 (3)将累加概率 (十进制小数)变换成二进制小数根据码长 取小数点后 个二进制符号作为第i个消息的码字本讲稿第六十一页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.4.3 霍夫曼编码霍夫曼编码这是霍夫曼于1952年提出的一种构造紧致码的方法具体方法如下：(1)q将个信源符号按概率大小递减排列 (2)用“0，1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源，称为缩减信源 ；(3)把缩减信源 的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2个信源符号的缩减信源 ；(4)依次继续下去，直至信源最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；(5)然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即相应的码字。本讲稿第六十二页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 5.4.3 霍夫曼编码霍夫曼编码霍夫曼编码方法得到的码并非是唯一的。造成非唯一的原因有两个：(1)每次对信源缩减时，赋予最后两个概率最小的信源符号的码符号“0”和“1”是可以互换的，所以可得到不同的霍夫曼码；(2)对信源进行缩减时，如果两个概率最小的信源符号合并后的概率与其他信源符号的概率相同，则在进行概率排序时的次序可以是任意的，因此会得到不同的霍夫曼码。霍夫曼码是用概率匹配的方法进行信源编码它有两个明显特点：(1)霍夫曼码的编码方法保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码；(2)每次缩减信源的最长两个码字有相同的码长，并且仅仅只有最后一位码符号不同。定理定理5.8 霍夫曼码是紧致码。本讲稿第六十三页，共八十七页中国矿业大学信电学院中国矿业大学信电学院School of Information and Electrical Engineering,CUMT 例例4：下表是一个哈夫曼编码的整个过程。其平均码长为信息传输率为5.4.3 霍夫曼编码霍夫曼编码本讲稿第六十四页，共八十七页中国矿业大学信电学院