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

离散无记忆信源不等长编码第7讲消息集码字集LuNvLNKDKRKLDNlogloglog)(UHR)(logULHDN等长编码无失真几乎无失真loglog,NMNDRMDLL编：码速率对典型序列无误编码Review掷硬币：正面出现p=0.25，这时信源熵H(U)=0.811比特。1logDLNR()/81.1%HUR（1）若采用等长二元无错编码时，510ep95.0/)(RUH（2）若采用只对典型序列编码，要求译码错误概率，求L95.0])(/[)(UHUH0427.095.0)(05.0UH471.0]81.075.01[log75.0]81.025.01[log25.0222I7221058.2eIpL由可得又可得例题要求长度达到2580万以上，难以实现。Review出路：不等长编码Morse电码特点：经常出现的字母变换为较短的数字序列，不经常出现的字母变换为较长的数字序列。ABCDEFGHI·––···–·–·–·····–·––·······JKLMNOPQR·––––·–·–··–––·–––·––·––·–·–·STUVWXYZ···–··–···–·–––··––·––––··设信源随机变量U的概率分布为若事件ak对应的码字长度为nk，则平均码字长度为Kkkkapnn1)(n平均码长)(,),(),(,,,2121KKaPaPaPaaaPU希望小。解决方案：概率大的事件用短码字。1）每个消息都至少有一个码字与之对应，且不同的消息对应不同的码字；2）对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列，即码字的分点唯一确定。不等长编码的唯一可译性解决方案：适当地编码，使得每个码字都具有识别标记。事件概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.12510111110111不等长码实例码C：异字头码码D：逗点码码C的平均码长小于码D的平均码长若①事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。唯一可译的两种解决方法逗点码若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位。则称这个字母串为逗号，称此码为逗点码。异字头码见到逗号就识别为一个码字的开始。见到一个码字就立即识别。事件概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.12510111110111不等长码实例码C的平均码长为1×0.5+2×0.25+3×0.125+3×0.125=1.75码D的平均码长为1×0.5+2×0.25+3×0.125+4×0.125=1.875CnDn()0.5*10.25*20.125*3*21.75HUbits异字头码异字头码可用树图表示。异字头码是唯一可译的。异字头码具有即时性。A01000000000000011111111111二进制码树树根—码字的起点分成D个树枝—码的进制数端节点—码字1101中间节点—码字的一部分节数—码长码树满树：端节点均为N节节点——等长码，码长为N端节点数目ND非满树：?01200112222三进制码树全树：每个节点上都有D个分枝的树D元全树的端节点数目为D+m(D-1)，m为非负整数。0001112码树异字头码（译码）异字头码的树图表示。异字头码是唯一可译的。异字头码具有即时性事件概率码Ca10.50a20.2510a30.125110a40.125111异字头码（译码）异字头码的树图表示。异字头码是唯一可译的。异字头码具有即时性。事件概率码Ca10.50a20.2510a30.125110a40.125111000111a1a2a3a4111100a4a2a100001110101101110（2）当码字长度给定，异字头码不是唯一的。任意给定的n1,n2,…,nK和D，是否总能存在满足条件的D元异字头码？（1）若选定某一节点表示消息，则该节点不再延伸。这是为了保证异字头条件。11111000100100010（3）若要构造有K个码字的D元异字头码，其码长分别为n1,n2,…,nK，则只需画出一个有K个端节点分别处于n1,n2,…,nK级的D元树图即可。异字头码（编码）Kraft不等式定理•任一长度为n1，n2，…，nK的D-元异字头码必满足Kraft不等式•反之，若给定满足Kraft不等式的一组码字长度，则可以构造出具有同样长度的异字头码。KkknD11Kraft不等式•必须注意：–Kraft不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据；如码字{0，10，010，111}虽然满足Kraft不等式，但它不是唯一可译码。122222332141knk010可译码为010，或0,10不妨设n1≤n2≤…≤nK，则n1级节点中的任何一个作端点即占去了满树中所有可能nK级节点的Kraft不等式充分性证明证明:11/nnnnDDDKK依次进行下去，当为第K个消息选择码字时，若有111KknnkKDD就能保证为第K个消息能够选择一个nK级端点作为码字，从而构造了异字头码。设有一个异字头码存在，它的各码字长度为n1≤n2≤…≤nK。Kraft不等式必要性证明knD证明：KknkD11每个码字对应的节点占去码树的。根据异字头条件，我们可以将K个码字和树中的某一级节点相对应，即将码字嵌入树中。由异字头条件知，这K个码字至多覆盖整个码树，因而有唯一可译码必要条件唯一可译码必满足Kraft不等式定理：证明对任意的正整数r，有KknKknKknrKknrrkkkkDDDD11112211KkKknnnKkrrkkkD11)(12211Kaaa,,,21BbbbK,,,2112,,,Knnnnr长码字序列rxxx,,,21Bxirkkknnn,,,21nikn总共个序列，对其进行重新组合rKiA表示含有i个码元的序列总数则],[maxminrnrniKnnnn,,,max21maxKnnnn,,,min21min消息集码字集唯一可译码必要条件唯一可译码必满足Kraft不等式定理证明对任意的正整数r，有KknKknKknrKknrrkkkkDDDD11112211KkKknnnKkrrkkkD11)(12211maxminnrnriiiDA由码的唯一可译性，可知长度为i含r个码字的序列必不相同，于是，则iiDAminmax2maxminlog11minmax112)(1nnrrrrrnrnkKknrnrnDk当时，上式右边指数项趋于0，因而右边趋于1。rKknkD11由此得maxmin1nrnriiirKknDADK任一满足Kraft不等式的非异字头码都可以找到一个码字长度不变的异字头码。DUHnlog)(1log)(DUHn任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足不等长编码定理01log)1(loglnlogloglog1loglog1loglog)(11111111KknKkknkKkknkKkknkKknkKkkkKkkkKkkkkkkkkDepDpepDpepDpDpppDnpppDnUH不等长编码定理证明DUHnlog)((),1~logknkHUpDkKnD注意：证明于是有Kraft不等式DUHnlog)(选n1、n2、…、nK，使KkDpDkknkn~1,)1(111KkkKknpDk不等长编码定理证明DnDnpDpppUHKkkkKknkKkkkklog)1(log)1(log1log)(11111log)(DUHn另外，对上式右边求倒数取对数并进行概率加权得则有，所以必存在码字长度为n1、n2、…、nK的唯一可译D元不等长码。于是有任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足DUHnLLlog)(1log)(DUHnLL不等长编码定理推论)(log)(DMSDUHnDLUHnLlog)(LDLUHnL1log)()(1log)(DMSLDUHn若对L长消息符号序列进行编码，相当于对源中的元素进行编码)(,LLpUu任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足DUHnlog)(LDUHn1log)(Shannon第一编码定理DnRlogRUH)(编码速率与编码效率——离散无记忆信源任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足DUHnlog)(LDUHn1log)(Shannon第一编码定理任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足)(UHRLDUHRlog)(——离散无记忆信源例题作二元编码4143~21aaUU概率码字平均码长Rηa13/401×3/4+1×1/4=1a21/41U2概率码字平均码长Rηa1a19/1601×9/16+2×3/16+3×3/16+3×1/16=27/1627/320.961a1a23/1610a2a13/16110a2a21/16111H(U)=0.811DnRlogRUH)(10.811Shannon-Fano-Elias编码Shannon-Fano-Elias编码方法采用信源符号的累积分布函数来分配码字。12{,,,}KAaaa设信源符号集，其相应的概率分布为P(ak)0(k=1,2,…,K)。定义信源符号的累积分布函数为其中。11()(),kkikiiFaPaaaA111()()(),2kkikkiiFaPaPaaaA1()0Fa又定义修正累积分布函数：将区间分为了K个子区间，每个区间的宽度为P(ak)。ka()kFa修正累积分布函数值处于对应ak台阶的中点。编码方法？因为所有概率都大于0，所有当。时当)()(bFaFba)(kaFka)(kaFka问题：的数值取多少位能保证唯一可译？)(kaF一般为一实数，若用二进制数表示，可能为无限位数。)(kaF二元编码方法：消息ak的码字为实数的二元数字表示序列的截短，保留的截短序列长度nk是大于或等于I(ak)的最小整数加1。）（kFa即1)(1lognkkap如知道，就能确定处在累积分布函数图中那个区间，就能确定信源符号。因此，可采用的数值作为符号的码字。可证明：该码是满足异字头码条件，并且2)(n1)(XHXH唯一可译码？kknnaa2FFkk）（）（若选取1)(1lognkkap得)()(2)(2FFkkkkknnaFaFapaakk）（）（可见，与它的近似值之差小于该台阶的一半。唯一可译！)(kaFkna）（kF根据二进制小数截去位数的影响，得异字头码？用对编码，得的码字为此码字对应的区间为。由和可知，此区间的下界处于累积分布函数台阶的中点以下，以上，而这区间的上界处于以下。也就是，每个码字对应的区间完全处于累积分布函数中该信源符号对应的台阶宽度内。所以，不同码字对应的区域是不同的，没有重叠，该码满足异字头条件。lnzzzk21k.0aF