3.2不等长编码

消息集码字集{}Lu{}NvLNKD≥KLDNloglog≥)(UHR)(logULHDN等长编码无失真几乎无失真LDNRlog=典型序列Morse电码特点：经常出现的字母变换为较短序列，不经常出现的字母变换为较长序列。JKLMNOPQR·––···–·–·–·····–·––·······STUVWXYZ···–··–···–·–––··––·––––···––––·–·–··–––·–––·––·––·–·–·ABCDEFGHI设信源随机变量U的概率分布为若事件ak对应的码字长度为nk，则平均码字长度为∑==Kkkkapnn1)(n平均码长⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡)(,),(),(,,,2121KKaPaPaPaaaPU希望小。解决方案：概率大的事件用短码字。011111111100.125a40111100010.125a30110100.25a200000.5a1码D码C码B码A概率事件不等长码实例奇异码：码A非奇异码非奇异的必要条件：D元编码中，长度为m的码字数不超过Dm个3.3离散无记忆信源的不等长编码例扩展编码0010Ca3a2a1U000000100010011100000100C2a3a3a3a2a3a1a2a3a2a2a2a1a1a3a1a2a1a1U23.3离散无记忆信源的不等长编码定义一个编码的扩展编码非奇异，则该码称为唯一可译码。如图的非唯一可译编码，3次扩展编码奇异。0110Ca3a2a1U3.3离散无记忆信源的不等长编码定义3.3.2若逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。等长码是唯一可译的。①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；称此码为逗点码。定义3.3.4若①事件与码字一一对应；②每个码字都不是另一个码字的字头(前缀)。则称此码为异字头码。异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。判断码的唯一可译性的方法：Sardinas-Patterson测试可将码作所示的分类011111111100.125a40111100010.125a30110100.25a200000.5a1码D码C码B码A概率事件不等长码实例码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码树异字头码（译码）异字头码的树图表示。异字头码是唯一可译的。异字头码具有即时性1110.125a41100.125a3100.25a200.5a1码C概率事件异字头码（译码）异字头码的树图表示。异字头码是唯一可译的。异字头码具有即时性。1110.125a41100.125a3100.25a200.5a1码C概率事件000111a1a2a3a4111100a4a2a100001110101101110（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异字头码存在的充分必要条件码字最大长度为4的3元码。C1长度为1，占有满树的1/3；C2长度为2，占有满树的1/9；C3长度为3，占有满树的1/27。码字最大长度为nk的D元码，码字C长度为n1，占有nk阶满树的比例:1nD−Kraft不等式长度n1,n2,…,nK的D元异字头码存在的充分必要条件为:a)若异字头码存在，则b)若上式成立，由式可知，给最后一个消息序列可安排一个码字。1nD−2nD−KnD−1KnD−−∑−=−−−≤111KknnkKDD12...1KnnnDDD−−−+++≤()12Knnn≤≤…≤Kraft不等式3.3离散无记忆信源的不等长编码定理2唯一可译码满足Kraft不等式证明思路：由唯一可译性可知，该码的n次扩展Cn是非奇异的。在码的扩展中，长度为m的码序列的数目必定不超过Dm.由此来证明Kraft不等式。3.3离散无记忆信源的不等长编码设消息所对应的码字长度记为l(ak)。对于扩展码，码字序列的长度为要证明的不等式为考虑上式左边的n次幂。于是得到kaU∈()()121,...,niiinijjlaaala==∑()1iilaaUD−∈≤∑3.3离散无记忆信源的不等长编码()()()()()()()()()1211221212............iiiiiniiinniiinniiinninninlaaUlalalaaUaUaUlalalaaaaUlaaUDDDDDD−∈−−−∈∈∈−+++∈−∈⎛⎞⎜⎟⎝⎠===∑∑∑∑∑∑3.3离散无记忆信源的不等长编码各项按码字长度合并同类项，得()()max1ninninllammaUDAmD−−=∈=∑∑(){}()(){}maxmax::iinniillaaUAmalam=∈==3.3离散无记忆信源的不等长编码由于要求编码C唯一可译∑=−≤KknkD11()()maxmax11maxiinnllamaUmnlmmmDAmDDDnl−−∈=−=⎛⎞=⎜⎟⎝⎠≤=∑∑∑()mAmD≤n→∞()1/max1nnl→()1iilaaUD−∈≤∑复习•等长编码定理:RH(U)可达;RH(U)不可达•基础：切比晓夫大数定理典型序列出现的概率1-ε特定典型序列概率上限2-L(H(U)-ε)特定典型序列的数目上限2L(H(U)+ε)复习•异字头码存在的充分必要条件：基础：异字头码与码树端节点对应•唯一可译码存在的必要条件：Kraft不等式基础：m长码字对应的消息序列§Dm•反例:(a1+a2+a3)6码字长度7的消息有6.25个；长度7码字有27个12...1KnnnDDD−−−+++≤0110Ca3a2a1U3.3离散无记忆信源的不等长编码3.3.3不等长编码定理(Shannon第一编码定理)DUHnlog)(≥1log)(+DUHn定理任一唯一可译码满足存在有D元唯一可译码，其平均长度3.3离散无记忆信源的不等长编码证明：1()log(loglog)KkkkkkHUnDpppnD=−=−+∑1logknKkkkDpp−==∑1loglnknKkkkDepp−==∑()11logln(log)1ln1kknnKKkkkkkkDDepepxxpp−−==⎛⎞≤−≤−⎜⎟⎝⎠∑∑()1(log)10kKnkeDKraft−=⎛⎞=−≤⎜⎟⎝⎠∑唯一可译，不等式()logHUnD∴≥()()1,2,,logknkHUpDkKD−==时取等号，此时平均码长达到了下限值3.3离散无记忆信源的不等长编码给定信源，选使则由最后一式左边得{}kpU,kn111=≤∑∑==−KkkKknpDk()()1log,loglog1,log1,kkkkkkpppkDDkDnpnkDkknnnnDpD−−−⎡⎤=−−≤−+⎢⎥−≤−−≤()()11,2,...,kknnkDpDkK−−−≤=（*）3.3离散无记忆信源的不等长编码（*）Knnn,,,21∑∑==−−KkkkKkkkDnppp11log)1(log()loglogHUnDD−()1logHUnD∴+()()11,2,...,kknnkDpDkK−−−≤=所以必存在有码长为的异字头码。对（*）式右边取对数并进行概率平均得3.3离散无记忆信源的不等长编码则一个原消息符号的平均编码长度{})(,LLpUu1log)()(log)(+≤DUHUnDUHLLL()()()1loglogLLLLHUnUHUnLDLLDL≤=+若对信源输出的L长消息符号序列进行编码，这相当于对源中的元素进行编码3.3离散无记忆信源的不等长编码若源是由简单无记忆源扩展而成,则有从而当L加大时，就逐渐趋近于。{})(,LLpUu)()(ULHUHL=()()1loglogLHUHUnDDL≤+DUHlog)(3.3离散无记忆信源的不等长编码不等长编码的编码速率定义为上述定理可描述为：不等长码的编码效率定义码的多余度DnRlog=()()HURHUε≤+()RHURUH)(=ηnDUHnlog/)(1−=−η若，就存在唯一可译的不等长编码；若，则不存在唯一可译的不等长码。3.3离散无记忆信源的不等长编码⎟⎟⎠⎞⎜⎜⎝⎛05.005.02.03.04.0:54321aaaaaU1logkDknp⎡⎤=⎢⎥⎢⎥1234500011001010010101aaaaa→→→→→()()1.95log2.5bit/78%kkHUbitsRnDpnHURη======∑1a2a3a4a0000111105a011例题DMSShannon编码n1=2,n2=2,n3=3,n4=n5=53.3离散无记忆信源的不等长编码Shannon-Fano编码⎟⎟⎠⎞⎜⎜⎝⎛05.005.02.03.04.0:54321aaaaaU51111a→()/92.9%HURη==345aaa1a2a2a3a5a00001111log2.1bitkkRnDpn===∑10a→210a→3110a→41110a→例题作二元编码⎥⎥⎦⎤⎢⎢⎣⎡4143~21aaUR11/4a21×3/4+1×1/4=103/4a1η平均码长码字概率U1111/16a2a21103/16a2a127/32R103/16a1a20.9611×9/16+2×3/16+3×3/16+3×1/16=27/1609/16a1a1η平均码长码字概率U2H(U)=0.811DnRlog=RUH)(=η10.811本节小结基本概念Shannon第一编码定理（本节内容见课本62-69页）–平均码长、唯一可译码、异字头码–Craft不等式、唯一可译码的必要条件()1logHUnDL+nDUH≤log)(1log)U(log)(LDHnDUHLL+≤离散无记忆信源一般离散信源作业3.13.23.4