无失真信源编码(1).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长信源序列的所包含的信息量lr表示码序列所能携带的最大信息量。由定理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的平均码长任意接近信源的熵,利用定理(5.3.5)的不等式，就可得到定理的结果,相关定义,编码速率：,编码效率：,信息传输速率：,编码剩余度：,对所有唯一可译码都要满足无需一定满足，但存在这种关系，通常希望越小越好,一些结论,平均码长的上、下界,时，此时：,各信源符号出现概率为 li为整数每码元平均所带信息量为,码元符号独立且等概,5.3.2,用例5.2.1的信源模型，i)对单信源符号进行二元编码，即，求平均码长和编码效率；ii）编成2次扩展码，信源序列与码序列的映射关系为：求平均码长和编码效率。,解：,1),信源序列的概率：,2),且：,与例5.2.1相比，可以看出，为得到同样编码效率所用的比定长码小得多。因此容易达到高的编码效率，是变长码的显著优点。,5.4 哈夫曼编码,本节主要内容,一、二元哈夫曼编码,二、多元哈夫曼编码,三、马氏源的编码,任意对于一个含q个符号的信源，存在最优的二进制码，其中有两个最长的码字有相同的长度且仅最后一个码位有别，即其中一个的最末尾是0，而另一个的最末尾是1（或者相反）,若一个唯一可译码的平均码长小于所有其它唯一可译码，则称该码为最优码(或紧致码)。应注意：最优是唯一可译码之间的比较，因此它的平均码长未必达到编码定理的下界。,5.4.1 二元哈夫曼编码,证明思路：,首先证明对于最优码，概率小的符号对应长度长的码字。,证明最长的码字有两个长度相同，且只有最后一位不同。,一个最优码唯一可译 满足Kraft不等式 存在与其同样码长的异前置码,二元最优异前置码的构造方法,设信源S为，对应的码字为,将概率最小的两个码符号 合并，从而产生新的信源S,设，对应的码字为。对新信源编码后，按下面的关系就可恢复原来信源的码字：,证明思路：,设,若 对信源 是最优的异前置码，则 对信源 也是最优的异前置码,对S，有,一些结论,我们可以采用合并两个最小概率符号的方法，逐步地按这样的路线去编码：,最后将2字母信源分配0、1符号；然后可逐步反推到原信源S，从而得到信源的最优编码。这种编码称做二元Huffman编码,5.4.1,一信源S的符号集A=，概率分别为：0.3，0.25，0.25，0.1，0.1；试对信源符号进行二元Huffman编码,解：,依次做信源SSS，最后将0、1符号分配给S，如下图：,将信源概率分布按大小依递减次序排列；合并两概率最小者，得到信新源；并分配 0,1 符号,新信源若包含两个以上符号返回（1），否则到（3）,从最后一级向前按顺序写出每信源符号所对应的码字,5.4.2,一信源S的符号集A=，概率分别为：0.4，0.2，0.2，0.1，0.1；试对信源符号进行二元Huffman编码，并计算平均码长和编码效率,解：,Huffman编码是最优码（或紧致码），是异前置码,编码结果并不唯一，例如0、1可换，相同概率符号码字可换，但平均码长不变,不一定达到编码定理下界，达下界条件为,通常适用于多元信源，对于二元信源，必须采用合并符号的方法，才能得到较高的编码效率,例5.4.2还可以用以下的方法编码：,不变,但码长的方差改变了,当码长的方差小时，编码器所需缓冲器容量小。因此要尽量减小码长的方差。方法是：在编码时，应使合并后的信源符号位于缩减信源符号尽可能高的位置上（减少合并次数）。,否则，就利用上式计算出大于q的最小正整数s。然后给信源增补零概率符号，使增补后的信源符号总数为s。编码后，去掉这些零概率符号所对应的码字，其余码字为所需码字,通过观察可知，要使编码的平均码长最短，对应的码树要构成满树是必要条件。对于r元哈霍夫曼编码，从第n阶的1个节点到n+1阶节点，增加的数目为r-1。因此，达到满树时，总的树叶数为：,5.4.2 多元哈夫曼编码,非负整数,5.4.3,一信源S的符号集A=概率分别为：0.4,0.2,0.1,0.1,0.05,0.05,0.05,0.05；试对信源符号进行3元哈夫曼编码，并计算平均码长和编码效率,解：,信源要增加1个零概率符号,如果有n个互斥随机事件，概率分别为pi,现用某种测试方法分步对所选择的目标事件进行识别，要求具有最小的决策平均次数，相当于对这些事件进行Huffman编码。,Huffman编码的应用,例如，甲手中有4张纸牌，点数分别为1、2、3、4，要求乙猜：乙可以向甲提问题，甲只能用是否来回答。求乙平均最少问几个问题可以猜到纸牌的点数和相应的策略。(1)1、2、3、4的概率均为1/4的决策树；(2)1、2、3、4的概率分别为1/2、1/4、1/8、1/8的决策树.首先Huffman编码；Huffman编码码树变成决策树。决策的设计：每步决策结果应该与节点分支的概率匹配。,根据马氏源的特性，当前发出的符号所含信息量取决于当前的状态。这个信息量可能很大也可能很小。例如，一个马氏源包含3个状态a，b，c，每个状态代表一个输出符号，状态转移矩阵如下：,马氏源可以采用按状态编码和多个符号合并编码,5.4.3 马氏源的编码,下一个字母b.c出现等概包含的信息量最大,下一个字母必然出现b包含的信息量为0,因此，采用一个符号用一个码字代替的方法会使编码效率降低,给定一个初始状态对每个状态,根据转移概率 进行最优编码，例如 Huffman编码.设 为对应的码表,其中规定信源符号 和码字 的对应关系，记为,给定一信源序列，设初始状态 用 码表，查出 对应的码字 作为编码器输出，同时根据 得到下一个状态 如此重复，直到处理完最后一个信源符号编码器输出为,根据译码器初始状态，用 码表查出其中的码字与序列 的前缀的相同部分,设，则 对应的 为译码器的输出根据 和 确定下一个状态，设为，则找到 码表中的码字与序列 中的前缀相同的部分，设，则 对应的 为译码器的输出如此重复，直到最后一个序列符号处理完。,5.4.4,对状态转移矩阵如下的马氏源进行哈夫曼编码，并计算编码效率。,解：,在3个状态下的Huffman编码如下,先求平稳分布,得到平均码长 为平稳分布的概率，为在每一个状态编 码的平均码长信源的熵 比特 编码效率,如果利用平稳分布编码结果为：用状态编码比利用平稳分布编码效率高。把信源的 N个符号合并成一个新符号再编码，会使编码效率提高。游程编码可使一阶马氏链的游程序列变为独立序列。,概率匹配编码（信源符号概率已知）-分组码：定长码，变长码-非分组码 通用编码（信源符号概率未知）,本章小结,信源编码的主要目的是提高信息传输的有效性，分为如下几类,典型序列的概率，个数 当序列长度N足够大时，有,本章小结,信源序列渐近均分特性,唯一可译码必须满足Kraft不等式,本章小结,无失真信源编码定理（仙农第一定理）,若对信源X的N次扩展源 进行编码，当N足够大时，总能找到唯一可译的r进编码，使得X的平均码长任意接近信源的熵,为编码信道信息传输速率 为无噪信道的容量,本章小结,关于信源编码定理的另一种描述,只要编码后，信息传输速率不大于无噪声信道的容量，就可实现无失真信源编码。,编码序列的特性 R的最大限制：编码符号独立且编码符号等概率无失真信源编码所采取的主要措施(1)概率匹配（Huffman编码等）使编码符号等概率(2)解除相关性，使信源变成无记忆,无失真信源编码的限制典型序列个数估计，若 则，即每个序列都是典型序列。要实现无失真，必须有。与无编码情况一样。当信源的熵接近 时，无失真信源编码的意义不大；此时信源冗余度，没有压缩的余地。,信源压缩编码的下限不采用信源编码时每信源符号的码长为，而通过压缩编码后的平均码长会减小，但大于等于 压缩编码的目的就是尽量降低传送每个信源符号时所需的比特数，而信源的熵 为无失真压缩码长的下限。,几种重要编码技术Huffman编码 算术编码游程编码 L-Z编码,Thank you!,