信息论——chapter5.ppt

第五章 无失真信源编码,－－北京邮电大学 信息工程学院,,,,一、概述,二、定长码,三、变长码,四、哈夫曼编码,主要内容,本章主要介绍无失真信源编码定理与一些重要的无失真信源编码方法,五、几种实用的信源编码方法,,信源编码：,将信源符号序列按一定的数学规律映射成由码符号组成的码序列的过程信源译码：,根据码序列恢复信源序列的过程无失真信源编码：,即信源符号可以通过编码序列无差错地恢复适用于离散信源的编码）,限失真信源编码：,信源符号不能通过编码序列无差错地恢复可以把差错限制在某一个限度内）,,信源编码的目的：提高传输有效性，即用尽可能短的码符号序列来代表信源符号无失真信源编码定理证明，如果对信源序列进行编码，当序列长度足够长时 ，存在无失真编码使得传送每信源符号所需的比特数接近信源的熵因此，采用有效的信源编码会使信息传输效率得到提高§5.1 概述,本节主要内容,一、信源编码器,二、信源编码的分类,三、分组码,§5.1.1 信源编码器,,编码器,信源序列,,,码符号集,码字集合,,信源译码器,译码器,信源序列,,,码符号集,码字集合,,信源编码器 （1）,,,,信源符号 {英文字母},码符号集点、划、字母间隔、单词间隔,信道基本符号{0，1},简单信源编码器,信源编码器 （2）,,,二进信道,,将英文字母变成摩尔斯电码,,将摩尔斯电码变成二进码,摩尔斯信源编码器,,原信源的N次扩展码,将N个信源符号编成一个码字。

相当于对原信源的N次扩展源的信源符号进行编码信源X={0,1}的二次扩展源X2的符号集为：{00,01,10,11}对X2编码，即为原信源X的二次扩展码§5.1.2 信源编码的分类,,概率匹配编码：信源符号的概率已知通用编码：信源符号的概率未知分组码：先分组再编码在分组码中，每一个码字仅与当前输入的信源符号组有关，与其他信源符号无关包括：定长码、变长码（Huffman编码、费诺编码） 非分组码：码序列中的符号与信源序列中的符号无确定的对应关系例如算术编码按信源序列和编码器输出的关系,先分组再编码,,,每一个码字仅与当前输入的信源符号组有关,编码器,,信源序列,,编码序列,例如算术编码就是非分组码,,无确定的对应关系,§5.1.3 分组码,,与非分组码的显著区别：分组码中包含码字,,各码字 都不相同？,,,Y,N,,不同的消息序列不会生成相同的码序列,,,无失真编码,必要条件,,,即时码与非即时码,只要接收到 每个码字的 最后一个符 号可立即将 该码字译出？,,,Y,N,优点：译码延迟小,,异前置码,设 为长度为 的码字，即 ， 称 为 的前置。

一个码中无任何码字是其他码字的前置异前置码是唯一可译码异前置码与即时码是等价的,,逗号码,用一个特定的码符号表示所有码字的结尾逗号码是唯一可译码,设信源符号集为{a,b,c,d}, 采用6种分组编码如下表，分析每一个码的唯一可译性,5.1,,非奇异 唯一可译,,,10,,ba,c,,,,,,等长,,,异前置码,,,逗号码,,,0表示开头,即时码,,一些结论,,,变长码,定长码,只要非奇异，就唯一可译,非奇异且异前置就唯一可译,速率变化设置缓冲器,速率恒定不需缓冲器,受误码影响大,逗号码除外,码长已知容易同步,容易产生差错传播,无差错传播,,,,,码树,,码树是表示信源编码码字的重要工具之一,,叶子,根节点,,一个码C包含4个码字：{1,01,000,001}, 试用码树来表示,5.2,采用二进制码树,解：,,,,,,R,,,,,,,1,0,0,0,1,1,（1）,（01）,（001）,（000）,一些结论,,,非奇异码字总能与码树建立一一对应的关系,在码树中，n阶节点的个数最多为,例：2进码树中，r阶节点数目最多为,,§5.2 定长码,本节主要内容,一、无失真编码条件,二、信源序列分组定理,§5.2.1 无失真编码条件,,对于定长码, 只要非奇异就唯一可译。

这就要求码字的数目不少于被编码的信源序列的个数,设信源X包含q个符号，码符号集包含的符号数为r,,,单信源符号编码：,码长,,,,N长信源符号序列编码（N次扩展码）,平均每个信源符号所需码符号数,,,,英文字母26个加1个空格可看成共27个符号的信源 如对单符号进行编码：,但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数可以远小于上面的值， 在理想情况下可以压缩到接近信源的熵1.4左右本节就是从理论上证明这种压缩是可以实现的§5.2.2 信源序列分组定理,,定理5.2.1,离散无记忆信源,{,,,使得,{,①,②,所有符号序列出现概率之和小于,序列 出现的概率 满足：,,(5.2.3),证： 我们先证明（5. 2. 3）式 设信源符号集 为 ， 各符号出现的概率分别为 ，为长度为 的序列， 为 中符号 出现的次数 将信源序列按下列原则分成两 ： 、，其中，： （5. 2.4）： 其它}根据大数定律，当序列足够长时，信源符号 出现的次数接近 。

因此， 中的序列的符号出 现的次数符合大数定律，称典型序列从（5. 2. 4）中可以看出， 随 的不同而改变设 ，则对于 中的信源符号 ，有或 ，其中由于信源是无记忆的，所以 的概率为 ＝ ， 的自信息负值为：,,,,,,,,,,,,,,,,所以选择 ，使得（5. 2. 5） 则式（5. 2. 3）成立下面证明定理的后半部分设 ， 根据（5. 2. 3）式，有（5. 2.6） 因为信源是无记忆的，所以 ， 得到（5. 2. 7） 将（5. 2. 7）代入（5. 2. 6），得 （5. 2. 8）,,,,,令 , 可得 , 所以根据Chebyshev不等式： ，其中为随机变量；这样就得到：（5. 2. 9）其中 ， ， 所以，（5. 2. 10）,,,,,,,,,其中，自信息的方差 （5. 2. 11）取 ，则当 ，,,,,,,总结,,,定理说明，当N足够大时，典型序列 的 的值接近信源的熵,,对于有记忆的马氏源，定理5.2.1也成立,渐进均分特性,,典型序列的概率估计,设取2为底,简记为:,,当 足够小时，每个典型序列的概率 接近， 其偏差不大于 ； 此时序列的长度需要很大,,典型序列的个数估计,设 为 中序列的个数,先估计上界：,利用概率估计的下界,再估计下界：,利用概率估计的上界,,,渐近均分特性,当 取值很小时（N要求很大），对于典型序列,含意：,当长度N足够大时：,典型序列接近等概率 ，数目近似于 非典型序列出现的概率接近为零（以概率收敛）,结论,,设信源序列数为 ，编码序列数为 。

如果每个信源序列都至少要有一个码字，即需要 但是，随着信源序列长度的增加，基本上是典型序列出现，这样我们仅考虑对典型序列的编码，所以实际需要 个码字而当信源的熵小于 时，就会使得码字的长度减小§5.2.3 定长码信源编码定理,,离散无记忆信源的熵为H(X)，码符号集的符号数为r，将长度为N的信源序列编成长度为l的码序列只要满足：,,则当N足够大时，译码差错可以任意小( ）；若上述不等式不满足，肯定会出现译码差错在编码时，可以使所有典型序列都有对应的码字，而最坏的情况是所有的非典型序列无对应的码字典型序列的个数小于,,,,正定理,,若不满足上式,,,逆定理,,=,已知编码序列条件下信源序列的不确定性，如果无差错译码,该不确定性为零相关定义,,定长码编码速率,,它表示编码后，一个信源符号平均所携带的最大信息量，也可以理解为传送一个信源符号平均所需的比特数 压缩码率实际就是减小编码速率编码效率,,NH(X)表示N长信源序列的所包含的信息量 l㏒r表示码序列所能携带的最大信息量 由定理5.3.2可知，当N足够大时， 可以接近1 由渐近均分特性，当 减小时， 增加。

压缩码率和提高编码效率是同样的含义信息传输速率：每个传输符号所含信息量,,对于二进编码，编码效率与信息传输速率数值相同相关结论,,无失真信源信源编码的另一种表述,如果编码速率 ，则存在无失真编码反之，肯定有失真编码效率与熵的关系,,信源给定后，若要求编码效率越高，N 越大，要求译码差错越低，N值也越大5.2.1,一离散无记忆信源的模型如下，要求用二元编码，已知 ，试估计信源序列的最小长度N信源的熵,解：,自信息方差,{,结论,要达到一定误码要求，信源序列长度需很长，所以编码器难于实现§5.3 变长码,本节主要内容,一、异前置码的性质,二、变长码信源编码定理,§5.3.1 异前置码的性质,,变长码可用非全码树来描述下图就是一个异前置码的码树只有端点（树叶）对应码字对应码字的端点与根之间不能有其它的节点作为码字 端点不能向上延伸再构成新码字,,,若信源符号数为q，码符号数为r，对信源符号进行编码，相应码长度为 ，则异前置码存在的充要条件是：,,,,,,,,,,,充分性：,做一个 阶全树，树叶总数,取 阶的任一节点作为第一个码字，去掉的树叶,,,,,,,,,,,,必要性：,构造一个码全树，最高阶为码字最大长度,,对于阶为 的节点，占用的树叶数为,当码满足 Kraft 不等式时，未必就是异前置码,异前置码并不唯一，例如 0,1 交换。

5.4.1,下表列出了3种变长码的编码，并给出了对应每个码的所有的码长 和具有同一码长的码字的个数，其中码符号集为{0,1,2,3}试问对每个码是否存在相应的异前置码？,解：,利用 Kraft 不等式来验证对于码1：,存在相应的异前置码,同理： 码2不存在相应的异前置码；码3存在相应的异前置码实际上，可以用码树来验证，方法更简单证明略,若一个码是唯一可译码且码字长为 则必满足Kraft不等式，即：,q：信源符号数 r：码符号数,,任意唯一可译码都可用异前置码代替，而不改变码字的任一长度结论,满足kraft不等式并不一定唯一可译，因为奇异码可能满足kraft不等式§5.3.2 变长码信源编码定理,,单信源符号编码的平均码长：,,,表示平均每个信源符号所需码符号的个数,对于N次扩展源编码，原信源符号平均码长为,,,,给定熵为H(X)的离散无记忆信源X，用r元码符号集对单信源符号进行编码， 则存在唯一可译码，其平均码长满足：,(1)证明不等式前半部,,,,,,,等式成立条件,即,(2)证明不等式后半部,,,,,,,{,,,证明略,若对长度为N的离散无记忆信源序列进行编码，则存在唯一可译码，且使每信源符号平均码长满足：,且对任何唯一可译码左边不等式都要满足。

证明略,对于离散平稳遍历马氏源，有：,,证明思路：,若对任意信源X的N次扩展源 进行编码，当N足够大时，总能找到唯一可译的r进编码，使得X的平均码长任意接近信源的熵,。