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

离散无记忆信源不等长编码第九讲消息集码字集LuNvLNKDKLDNloglog)(UHR)(logULHDN等长编码无失真几乎无失真LDNRlog典型序列Review掷硬币：正面出现p=0.25，这时信源熵H(U)=0.81。1logDLNR()/0.81HUR（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由可得又可得22()()LIreIPHUpLLu例题也就是长度要达到2580万以上。Morse电码特点：经常出现的字母变换为较短的数字序列，不经常出现的字母变换为较长的数字序列。ABCDEFGHI·––···–·–·–·····–·––·······JKLMNOPQR·––––·–·–··–––·–––·––·––·–·–·STUVWXYZ···–··–···–·–––··––·––––··E对应1000J对应1011101110111000设信源随机变量U的概率分布为若事件ak对应的码字长度为nk，则平均码字长度为Kkkkapnn1)(n平均码长)(,),(),(,,,2121KKaPaPaPaaaPU希望小。解决方案：概率大的事件用短码字。1）每个消息都至少有一个码字与之对应，且不同的消息对应不同的码字；2）对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列，即码字的分点唯一确定。不等长编码的唯一可译性解决方案：适当地编码，使得每个码字都具有识别标记。事件概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.12510111110111不等长码实例若①事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。唯一可译的两种解决方法逗点码若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。异字头码见到逗号就识别为一个码字的开始。见到一个码字就立即识别。事件概率码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异字头码异字头码的树图表示。异字头码是唯一可译的。异字头码具有即时性。A01000000000000011111111111二进制码树树根—码字的起点分成r个树枝—码的进制数端节点—码字1101中间节点—码字的一部分节数—码长码树满树：每个节点上都有2个分枝的树——等长码非满树：不等长码01200112222三进制码树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元树图即可。异字头码（编码）长度分别为n1、n2、…、nK的D元异字头码存在的充分必要条件是Kraft不等式11KknkD•必须注意：–Kraft不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据；如码字{0，10，010，111}虽然满足Kraft不等式，但它不是唯一可译码。122222332141knk不妨设n1≤n2≤…≤nK，则n1级节点中的任何一个作端点即占去了满树中所有可能nK级节点的Kraft不等式充分性证明证明:11/nnnnDDDKK依次进行下去，当为第K个消息选择码字时，若有111KknnkKDD就能保证为第K个消息能够选择一个nK级端点作为码字，从而构造了异字头码。设有一个异字头码存在，它的各码字长度为n1≤n2≤…≤nK，则可作一个nK级满树，根据异字头条件，我们可以将K个码字和树中的某一级节点相对应，即将码字嵌入树中。每个码字对应的节点占去码树的，由异字头条件知，这K个码字至多覆盖整个码树，因而有Kraft不等式必要性证明knD证明：KknkD11唯一可译码必要条件唯一可译码必满足Kraft不等式定理证明对任意的正整数r，有KknKknKknrKknrrkkkkDDDD11112211KkKknnnKkrrkkkD11)(12211Kaaa,,,21BbbbK,,,21nnnnK,,,21r长码字序列rxxx,,,21Bxirkkknnn,,,21nnik总共个序列，对其进行重新组合rKiA表示含有i个码元的序列总数则],[maxminrnrniKnnnn,,,max21maxKnnnn,,,min21min消息集码字集唯一可译码必要条件唯一可译码必满足Kraft不等式定理证明对任意的正整数r，有KknKknKknrKknrrkkkkDDDD11112211KkKknnnKkrrkkkD11)(12211maxminrnrniiiDA由码的唯一可译性，可知长度为i含r个码字的序列必不相同，于是，则iiDAminmax2maxminlog11minmax112)(1nnrrrrrnrnkKknrnrnDk当时，上式右边指数项趋于0，因而右边趋于1。rKknkD11由此得maxmin1rnrniiirKknDADK任一满足Kraft不等式的非异字头码都可以找到一个码字长度不变的异字头码。DUHnlog)(1log)(DUHn任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足不等长编码定理01log)1(loglnlogloglog1loglog1loglog)(11111111KknKkknkKkknkKkknkKknkKkkkKkkkKkkkkkkkkDepDpepDpepDpDpppDnpppDnUH不等长编码定理证明DUHnlog)()log)(~1,(DUHnKkDpknk，则若证明于是有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不等长编码定理推论DUHnlog)(DLUHnLlog)(LDLUHnL1log)(LDUHn1log)(若对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.811本节小结基本概念Shannon第一编码定理（本节内容见课本62-69页）–平均码长、唯一可译码、异字头码–Craft不等式、唯一可译码的必要条件()1logHUnDLnDUHlog)(1log)U(log)(LDHnDUHLL离散无记忆信源一般离散信源作业3.13.23.4