信息论与编码第四章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,高传输率与抗干扰是一对矛盾,，,但可以从理论上证明，至少存在某种最佳的编码或信息处理方法，能解决这一矛盾。,4.1 编码器,变换,（数学规则）,：,将信源符号用由码元组成的序列（长度为,l,i,）来表示,若通过一个二进制信道进行传输，为使信源适合信道的传输，将用0,1符号序列表示，码符号集为 ，序列与,s,i,的对应形式可有多种，得不同的码。,第四章 无失真信源编码,码的基本分类：,固定长度码（等长码）,变长码：各码字的码长不等,非奇异码：码中所有码字都不相同,奇异码：有同码,码的N次扩展：,码2的二次扩展码为：,同价码：每个码符号（元）所占的传输时间都相同,4.2 等长码和等长信源编码定理,实现无失真编码的条件：,1、信源符号与码字一一对应,2、任意一串有限长的码符号序列与信源s的符号序列也是一一对应，即N次扩展后仍满足一一对应关系。,同时满足上述条件称为,唯一可译码,有重码，非唯一可译码,等长非奇异码一定单义可译,等长编码条件,：，,满足此条件，才有可能无重码（非奇异）；扩展后：,：平均每个信源符号所需要的码符号（元）个数,考虑到符号出现的概率以及符号之间的依赖性,。,再去除一些无效字符组合，扩展信源中的符号总数 所需编码的码字个数可大大下降。,设离散无记忆信源：,由切贝雪夫不等式,：,方差为定值 表明,依概率收敛于,上界,下界,我们可以只对集G中M,G,个信源序列进行一一对应的等长编码，这就要求码字总数不小于M,G,就行，即,满足式的条件下，时，译码错误概率,但当,由M,G,的下界式可知，这种情况下选取的码字总数小于集G中可能有的信源序列数，将有相应码字对应的信源序列的概率和记作 ，它必然满足：,造成有些序列没有码字对应，译码时必出错，其中正确的译码概率：,等长信源编码定理,一个熵为H（S）的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中选取,l,个字母组成，对于任意 ，只要满足 ，当 时，几乎可实现无失真编码，即译码错误概率能为任意小。,反之，若 ，则不可能实现无失真编码，时，。,可改写：,只要码字载荷的信息量大于信源序列携带的信息量，总可实现几乎无失真编码，而且传输效率接近于1,例：0 1 扩展N2 00 01 10 11 0.9 0.1 0.81 0.09 0.09 0.01,如取00，01，10编码，概率和为：0.99,扩展N3 000 001 010 100 101 110 111,0.729 0.081 0.081 0.081 0.009 0.009 0.001,取,两位0的编码，概率为0.972；取前7个编码，概率为：0.999,扩展N4,0000 0001 0010 0011 0100 0101 0110 0111,0.6561 0.0729 0.0729 0.0081 0.0729 0.0081 0.0081 0.0009,1001 1010 1011 1100 1101 1110 1111,0.0729 0.0081,0.0081,0.0009 0.0081 0.0009,0.0009,0.0001,取,3,个,0,的编码,(05,个,),，概率为,0.9477,；,取,2,个,0,的编码,(11,个,),，概率为,0.9963,；,取,1,个,0,的编码,(15,个,),，概率为,0.9999,4.3 变 长 码,变长码可以在N不很大时就可编出效率很高而且无失真的码；变长码也必须是唯一可译码才能实现无失真编码。,例：码1 码2,设：是码C中的任一码字，而其它码字,都不是码字W,i,的前缀，则此码为,即时码，亦称非延长码。,即时码是唯一可译码的一类子码,。,树图法构造即时码：,根、枝、节点,码树图也可以用来译码,单义（唯一）可译定理,：设信源符号集为：，码符号集为：，又设码字为 ，其分别对应的码长为；，则存在唯一可译码的充分必要条件是：,码长,l,i,，码符号集中符号个数r，信源符号个数q，称作kraft不等式。,说明,：唯一可译码一定满足不等式，反之，满足不等式的码不一定是唯一可译码。,充分性证明：,假定满足不等式的码长为 ，在q个码字中可能有长度相同的码字。设码长为1的有n,1,个，长度为2的有n,2,个，长度为j的有n,j,个，最大长度为,l,的有n,l,个，此处n为节点的阶数，（即n次扩展），此节点中的码字长度为n,i,；n,i,为长度为i的码字个数。有：,一共q个码字，全为1时，满足不等式,：,考虑有码长相等的情况，合并同类项后得：,两边同乘以 ：,移项后为：,由于都为正整数，将,左边去掉一项（等号去掉），有：,同理得：,由 与最大长度,l,之间的关系，上述不等式系列给我们带来了结构上的构码条件。显然可证明：如满足kraft不等式，则一定能构成至少一种结构为 的即时码，如最长码数 取不等式中的等号，则为用尽即时码，如取不等号，则为非用尽的即时码，即时码是唯一可译码的一类子码，所以定理的充分性也就得到了证明。,必要性证明：已知唯一可译码的码长为 ，设n是一个任意的正整数，考虑等式：,右边共有 项，代表了n个码字组成的码字序列的总数。每项均对应于n个码字组成的一个码字序列，如下图，图中1、2、n表明码字的序号，分别为对应的码长。,令：,j,的值是个码字组成的码字序列的总长，也就是n个信源符号组成的序列所对应的码符号序列的总长度。因为讨论的是变长码，所以设 的取值范围为：,则j的取值范围为,式,为各 项之和，都可取 而 又都可取值为 ，所以相同数值j的出现不止一次，也就是在 个码字序列中码符号总长相等的码字序列不止一个，令为 个，换句话说，就是把总长度为j的序列的数目记为 ，例如由唯一可译码 三个码字所组合成的长度 的序列共有7种：,1 01 001，1 001 01，01 1 001，01 001 1，001 1 01，001 01 1，01 01 01,a,1,a,2,a,3,，a,1,a,3,a,2,，,a,2,a,1,a,3,，,a,2,a,3,a,1,，,a,3,a,1,a,2,，a,3,a,2,a,1,，a,2,a,2,a,2,因此：式（19）可以合并：将 代入上式：,对于所有正整数n，上式都要成立，当 时,所以必须有：证毕,4.4 变长信源编码定理,平均码长：,一个信源符号所需的平均码符号数为：,可见：越短，越大，信息传输效率就越高，因此，我们总希望编出来的码平均码长 最短，可作为衡量唯一可译码的有效性高低的一个标准。,定理4.3,，若一个离散无记忆信源具有熵为 ，并有r个码符号的符号集，则总可找到一种无失真编码方法，构成唯一可译码，使其平均码长满足：,下界证明：,由证明过程知，上述等式成立的充要条件是：,可见，只有当选择每个码长：时，才能达到这个下界值,式中 必须为正整数，每个 必须呈现 的形式（是正整数）。,上界证明：只需证明 在上界与下界中间可以找到一种唯一可译码就行。在如下区间取之整数,证毕,信源给定，H（S）确定，那么，该信源的唯一可译码的平均码长 的下界值也就随之确定，信源编码的有效性的限度也就确定了，在不改变编码的对象，即信源本身的统计特性的情况下，单靠改变编码方法来继续提高有效性是无潜力可挖了。,定理4.4,离散无记忆信源S的N次扩展信源 ，熵为 ，并有码符号集 。对信源 进行编码，总可以找到一种编码方法，构成唯一可译码，使信源中每个信源S中每隔信源符号所需的码字平均长度满足：,或者,且 式中：令N1就是定理4.3,证明：,用S,N,替代定理4.3中的S，得：，其中 是以r进制为单位的扩展信源S,N,的熵。,代入上式,结论可推广到平稳遍历的有记忆信源（如马尔可夫信源）,以上分析表明，要进一步提高编码的有效性，必须考虑到信源符号间的依赖性，以减少信源每发一个符号所携带的平均信息量，缩短平均码长的长度。考虑的依赖性越仔细，即记忆长度越长，平均码长就可能越短，编码就越有效。,如前所述，我们还可以用扩展信源的手段，达到数据压缩的目的，扩展的程度越高，压缩的效果越好。但增加了编码的复杂性（代价）。,变长无失真信源编码定理（香农第一定理）也可这样来描述：设信源S的熵为H（S），无噪离散信道容量为C，于是，信源的输出可以进行这样的编码，使得在信道上传输的平均速率为每秒 个信源符号，其中 可以是任意小的正数，要使传输的平均速率大于 是不可能的。,编码效率：码的剩余度：,4.5 变长码的编码方法,香农编码,：，,可使不超过上界，但不一定保证是紧效码,哈夫曼编码,：1、,将信源消息（符号）按概率大小顺序排队。,2、从最小概率的两个消息开始编码，并给予一定的编码规则，如小概率的下支络编为1（或0），大概率的上支络编为0（或1），两相等，也按上、下支络给值。,3、将已编码的两个消息对应概率合并，并重新按概率大小排队，重复2,4、重复3，直至剩两个符号为止。,5、编成的变长码按后出先编的方法，从树根沿编码路线逆行至对应的消息（从最后级向前返回），得出各信源符号所对应的码符号序列。,Huffman码一定是紧效码,证明,：由H氏编码方法最后一步得到的缩减信源Sa必定只有r个符号.这r个符号的概率和必为1，且这r个符号分别只授于一个码符号(1,2,3r)，所以缩减信源Sa对应的单义可译码Ca的平均码长 一定等于1，平均码长等于1的单义可译码当然是最佳码。,设某一缩减信源S,j,，已找到一个最佳码C,j,，其平均码长为 ，由编码方法，对于S,j,中某一元素Sa（由前一个缩减信源中 概率最小的r个符号 合并而来的，且 ，对于 信源的码 ，其平均码长为 。由于在 中除了 这r个符号相应的r个码字比缩减信源S,j,中的符号Sa相应的码字多一个r进制码符号外，其余码字长度都是相同的。所以 满足以下关系：,用反证法来证明：假设找到另一个码 的最佳码，即其平均码长 ，设 的码字为 ，各码字的长度分别为 ，再假设这些码字的排列次序是按照码字概率递减的次序，得 （可以通过改变码字的标号来达到这一要求）。而在这些码中 除了最后一个码符号不同外，其它码符号全部相同，也就是说有本层的码字长度相等 如我们在 中。,，与上式相比由假设，应有：也就是说C,j,不是最佳码，非最佳信符，这与假设矛盾.说明不存在 ，反过来说，霍夫曼码是最佳码，因为 至最前一级都是最佳码，所以：H氏编码方法是最佳编码方法。,对信源的N次扩展信源同样可以采取霍夫曼编码，因为霍夫曼码是最佳码，所以编码后单个信源符号所编得的平均码长随N的增加很快接近于极限值信源的熵。,r进制霍夫曼码：,二进制H氏码常用于数字通信，计算机每次将两个最小概率的信源合并。如码符号集为个（进制），则每次为个符号合并成一个新的信源，为了充分利用短码，最后应该也必须将码符全用上，这样才能使平均码长最短，这就需要信源S的符号数q必须满足 ，表示缩减的次数，(r-1）为每次缩减所减少的信源个数，二进制时 ，为整数，上式有时与实际不吻合，不满足上述条件时，可以补充信源个数使其满足，但令其概率为0，当然，补充信源的个数应 。,费诺（Fano）码：,与Hoffman码稍有区别，不是最佳的编码方法，但有时也可得到紧效码的性能。,将信源符号以概率递减的次序排列起来；将排列好的信源符号划分成两大组，使每组的概率和近于相同，并各赋予一个二进制码无“0”或“1”；再得各组分为2组，概率和相近，赋值，直至每小组只剩一个信符号为止。,Fano码的编码方法实际上是构造码树的一种方法，所以是即时码，且考虑信源的统计特性，概率大的信源符号对应短码字，如全部分组都相等，则为紧效码，否则不是。,