第7讲离散无记忆信源不等长编码2014

离散无记忆信源不等长编码,第7讲,等长编码,无失真,几乎无失真,对典型序列无误编码,掷硬币：正面出现p=0.25，这时信源熵H(U)=0.811比特。,（1）若采用等长二元无错编码时，,（2）若采用只对典型序列编码，要求译码错误概率,，求L,由,可得,又,可得,例题,要求长度达到2580万以上，难以实现。,出路：不等长编码,Morse电码,特点：经常出现的字母变换为较短的数字序列，不经常出现的字母变换为较长的数字序列。,设信源随机变量U的概率分布为若事件ak对应的码字长度为nk，则平均码字长度为,平均码长,希望小。,解决方案：概率大的事件用短码字。,1）每个消息都至少有一个码字与之对应，且不同的消息对应不同的码字；2）对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列，即码字的分点唯一确定。,不等长编码的唯一可译性,解决方案：适当地编码，使得每个码字都具有识别标记。,不等长码实例,码C：异字头码,码D：逗点码,码C的平均码长小于码D的平均码长,若事件与码字一一对应；每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。,唯一可译的两种解决方法,逗点码,若事件与码字一一对应；每个码字的开头部分都是一个相同的字母串；这个字母串仅仅出现在码字的开头，不出现在码字的其它部位。则称这个字母串为逗号，称此码为逗点码。,异字头码,见到逗号就识别为一个码字的开始。,见到一个码字就立即识别。,不等长码实例,码C的平均码长为10.5+20.25+30.125+30.125=1.75码D的平均码长为10.5+20.25+30.125+40.125=1.875,异字头码,异字头码可用树图表示。,异字头码是唯一可译的。,异字头码具有即时性。,A,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,二进制码树,树根码字的起点,分成D个树枝码的进制数,端节点码字1101,中间节点码字的一部分,节数码长,码树,满树：端节点均为N节节点等长码，码长为N端节点数目,非满树：?,0,1,2,0,0,1,1,2,2,2,2,三进制码树全树：每个节点上都有D个分枝的树D元全树的端节点数目为D+m(D-1)，m为非负整数。,0,0,0,1,1,1,2,码树,异字头码（译码）,异字头码的树图表示。,异字头码是唯一可译的。,异字头码具有即时性,异字头码（译码）,异字头码的树图表示。,异字头码是唯一可译的。,异字头码具有即时性。,0,0,0,1,1,1,a1,a2,a3,a4,111100,a4,a2,a1,（2）当码字长度给定，异字头码不是唯一的。,任意给定的n1,n2,nK和D，是否总能存在满足条件的D元异字头码？,（1）若选定某一节点表示消息，则该节点不再延伸。这是为了保证异字头条件。,（3）若要构造有K个码字的D元异字头码，其码长分别为n1,n2,nK，则只需画出一个有K个端节点分别处于n1,n2,nK级的D元树图即可。,异字头码（编码）,Kraft不等式,定理任一长度为n1，n2，nK的D-元异字头码必满足Kraft不等式反之，若给定满足Kraft不等式的一组码字长度，则可以构造出具有同样长度的异字头码。,Kraft不等式,必须注意：Kraft不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据；如码字0，10，010，111虽然满足Kraft不等式，但它不是唯一可译码。,010可译码为010，或0,10,不妨设n1n2nK，则n1级节点中的任何一个作端点即占去了满树中所有可能nK级节点的,Kraft不等式充分性证明,证明:,依次进行下去，当为第K个消息选择码字时，若有,就能保证为第K个消息能够选择一个nK级端点作为码字，从而构造了异字头码。,设有一个异字头码存在，它的各码字长度为n1n2nK。,Kraft不等式必要性证明,证明：,每个码字对应的节点占去码树的。,根据异字头条件，我们可以将K个码字和树中的某一级节点相对应，即将码字嵌入树中。,由异字头条件知，这K个码字至多覆盖整个码树，因而有,唯一可译码必要条件,唯一可译码必满足Kraft不等式,定理：,证明,对任意的正整数r，有,r长码字序列,总共个序列，对其进行重新组合,表示含有i个码元的序列总数,则,消息集,码字集,唯一可译码必要条件,唯一可译码必满足Kraft不等式,定理,证明,对任意的正整数r，有,由码的唯一可译性，可知长度为i含r个码字的序列必不相同，于是，则,当时，上式右边指数项趋于0，因而右边趋于1。,由此得,任一满足Kraft不等式的非异字头码都可以找到一个码字长度不变的异字头码。,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,不等长编码定理,不等长编码定理证明,证明,于是有,Kraft不等式,选n1、n2、nK，使,不等长编码定理证明,另外，对上式右边求倒数取对数并进行概率加权得,则有，所以必存在码字长度为n1、n2、nK的唯一可译D元不等长码。,于是有,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,不等长编码定理推论,若对L长消息符号序列进行编码，相当于对源中的元素进行编码,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,Shannon第一编码定理,编码速率与编码效率,离散无记忆信源,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,Shannon第一编码定理,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,离散无记忆信源,例题,作二元编码,H(U)=0.811,1,0.811,Shannon-Fano-Elias编码,Shannon-Fano-Elias编码方法采用信源符号的累积分布函数来分配码字。,设信源符号集，其相应的概率分布为P(ak)0(k=1,2,K)。定义信源符号的累积分布函数为其中。,又定义修正累积分布函数：,将区间分为了K个子区间，每个区间的宽度为P(ak)。,修正累积分布函数值处于对应ak台阶的中点。,编码方法？因为所有概率都大于0，所有当,问题：的数值取多少位能保证唯一可译？,一般为一实数，若用二进制数表示，可能为无限位数。,二元编码方法：消息ak的码字为实数的二元数字表示序列的截短，保留的截短序列长度nk是大于或等于I(ak)的最小整数加1。,即,如知道，就能确定处在累积分布函数图中那个区间，就能确定信源符号。因此，可采用的数值作为符号的码字。,可证明：该码是满足异字头码条件，并且,唯一可译码？,若选取,得,可见，与它的近似值之差小于该台阶的一半。唯一可译！,根据二进制小数截去位数的影响，得,异字头码？用对编码，得的码字为此码字对应的区间为。由和可知，此区间的下界处于累积分布函数台阶的中点以下，以上，而这区间的上界处于以下。也就是，每个码字对应的区间完全处于累积分布函数中该信源符号对应的台阶宽度内。所以，不同码字对应的区域是不同的，没有重叠，该码满足异字头条件。,注意：在这种编码方法中没有要求信源符号的概率按照大小次序排列。,习题3-7（Shannon编码）令离散无记忆信源，且。,定义累积分布函数:,而Ql=0。,今按下述方法进行二元编码：消息ak的码字为实数Qk的二元数字表示序列的截短，保留的截短序列长度nk是大于或等于I(ak)的最小整数,如有尾数进位。,(a)证明这样编得到的码满足异字头条件，且平均码长满足,Fano编码,为选出的码集合的平均长度最小，自然想到:从每个节点出发的D种可能的分支出现的概率近于相等，这将给出一种近于最佳的编码方法Fano编码。例：设信源U的9个消息a1，a2，a9的概率分别为1/3，1/9，1/9，1/9，1/9，1/9，1/27，1/27，1/27。为了使平均码长尽可能地短，我们将消息划分成近于等概的3个子集a1，a2，a3，a4，a5，a6，a7，a8，a9，分别与码树的一级节点对应。对于第二个子集，我们