您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 企业财务 > 3.1离散无记忆信源等长编码
3.1离散无记忆信源等长编码⎥⎦⎤⎢⎣⎡=KKpppaaa,,,,,,2121A字母表信源输出序列),,,(21LLuuu=u{}Dbbb,,,21=B),,,(21NNvvv=v消息集码字集{}Lu{}Nv集合码字序列等长码不等长码D元码唯一可译码信源编码基本概念00011000011111p(a4)=1/8a4001100000010p(a3)=1/8a30110101101p(a2)=1/4a2110000p(a1)=1/2a1码4码3码2码1码0码表信源符号出现概率信源符号信源编码基本概念唯一可译码信源编码器码表信源信道XYL长序列N长码字无失真等长编码LNKD≥KLDNloglog≥LKND{}{}1212,,,,,,,LKLiiiAaaaLUaaa==信源符号序列长{}{}1212,,,,,,,NDNiiiBbbbNXbbb==码字符号码字序列长英文电报27个符号,K=27,L=1,D=2(二元编码)527logloglog222≈=≥DKLN每个英文电报符号至少要用5位二元符号编码实际英文电报符号信源,在考虑了符号出现的概率以及符号之间的依赖性后,平均每个英文电报符号所提供的信息量约等于1.4比特,即编码后5个二元符号只携带约1.4比特的信息量,远小于5比特(最大熵),可见编码后的信息传输效率极低。实例LNKD≥信源编码器码表信源信道XYL长序列N长码字无失真等长编码LNKD≥KLDNloglog≥)(logULHDN≥几乎无失真编码{}{}1212,,,,,,,LKLiiiAaaaLUaaa==信源符号序列长{}{}1212,,,,,,,NDNiiiBbbbNXbbb==码字符号码字序列长几乎无失真等长编码选择L足够长,使其中,为与L有关的正数,且当时有,才能不损失信息。然而这样的编码不总能保证单义可译,但非单义可译所引起的错误可渐近为任意小。反之,若,编码误差变得任意大。])([logLUHLDNε+≥Lε∞→L0→Lε])([logLUHLDNε−编码速率R=NlogD/LR=NlogD/L≥logK关于编码速率的说明:表示一个长度为N的D元码字给一个长度为L的消息的每个符号所提供的信息量。3.2离散无记忆(简单)信源的等长编码随机变量序列uL的概率为(无记忆源)序列的自信息量为()()()1212~KlKaaaupapapa⎡⎤⎢⎥⎣⎦3.2离散无记忆(简单)信源的等长编码),,,(21LLuuu=u()()Lllppu=∏u∑∑∏=−=−=−=llllllLLuIupuppI)()](log[)(log)(log)(uu一个消息序列UL每符号含有信息量算术平均为:信源的熵为H(U)设I(ul)的方差为3.2离散无记忆(简单)信源的等长编码()/()/LLllIILIuL==∑u()()()()()lkkkEIupaIaHU==∑2Iσ()()()()22()()IlkkkDIupaIaHUσ==−∑IL对于H(U)的方差为3.2离散无记忆(简单)信源的等长编码()()()222222122222()1[()][()()]1[()()]1[()](),()...()1*/LLlllLlIIIEHUEILHULLEIuLHULEIuHUIuIuIuLLLLσσ−=−=−=−==∑∑uu独立同分布3.2离散无记忆(简单)信源的等长编码例信源发出的消息序列长度L=8。长为8的序列是(a1+a2)8的展开式的所有项,共28个。消息序列的概率是(p1+p2)8的二项展开式中的各项。12~1/43/4laau⎛⎞⎜⎟⎝⎠()()()12~1/43/4lIaIaIu⎛⎞⎜⎟⎝⎠()0.81HUbit=()()()()22()()0.471IlkkkDIupaIaHUσ==−=∑()()()888111/8IaIaIa==()()()()358121235/8IaaIaIa=+{}()()()()()()21212212DD~(),,rKlKLllLIPEaaaupapapaIuILEHUDLLLξξξεξεσξξξ=−∞⎡⎤⎢⎥⎣⎦====∑u契比雪夫不等式3.2离散无记忆(简单)信源的等长编码3.2.2信源划分定理由契比雪夫大数定理可选,这可以通过适当选择L来实现,上式可以写成即当L足够大时,IL将以概率1取值为H(U)。0∀ε2222()()()()11LIrLIrIPHULLIPHULLσεδεσεδε⎡⎤−=⎢⎥⎣⎦⎡⎤−≤≥−=−⎢⎥⎣⎦uuεδ=3.2.2信源划分定理•典型序列集的定义•令H(U)是集的熵,,•定义为给定信源U输出长为L的典型序列集它称作弱ε典型序列集;相应地,的补集为非典型序列集。3.2离散无记忆(简单)信源的等长编码{})(,kapU0ε{}εεε+≤≤−=)()(:),(UHIUHLTLLUu()()/,LLLLIILU=∈uu),(εLTU3.2离散无记忆(简单)信源的等长编码令uL是信源的长为L的输出序列,其中,是序列中出现的次数。称为强典型序列集。例4次掷硬币试验强典型序列有{0011},{1001},{1100},{1100},{0011},{1010}.0ε{}(,):[()][()]ULkkkTLLpaLLpaεεε=−≤≤+ukLka{},()kUpa3.2离散无记忆(简单)信源的等长编码例信源发出的消息序列长度L=8,对其二元随机编码。I8的数值:2,1.80,1.60,1.41,1.21,1.01,0.811,0.61,0.41512~1/43/4aaU⎛⎞⎜⎟⎝⎠()0.81HUbit=87162534435261781121212121212122a,aa,aa,aa,aa,aa,aa,aa,a()()20.471IkDIaσ==()44352617812121212222aa,aa,aa,aa,a163/0.3679.ILσε=若对共个序列编码,错误概率上限是()()()()()()()87625301238888C1/4C1/43/4C1/43/4C1/43/40.027eP=+++=2617351212120.2aa,aa,aaε=弱典型序列是4435261781212121220.4aa,aa,aa,aa,aε=弱典型序列是87162531121212a,aa,aa,aa3.2.2信源划分定理3.2离散无记忆(简单)信源的等长编码()()(0)(0)(0)(0)(0)(0)1.0LL(0)1()(1)11log()log[(1)]11loglog(1)(0)(0)log(1)log(1)(0)lrLLLLLLLLLLLLLppLLPpLpppIpppLLppLLLLppLLLpIpLεδ−−−−⎡⎤−≤≥−⎢⎥⎣⎦=−=−=−−=−−−=−−−−→≈−uu例掷硬币正面概率,反面若用表示次试验中正面出现的次数。当足够大时og(1)log(1)()pppHp−−−=强典型序列必是弱典型序列3.2离散无记忆(简单)信源的等长编码3.2.2信源划分定理定理3.2.1(信源划分定理)给定信源对任意ε0,取L0使得则当L≥L0时总有{}εε−≥∈1),(LTPULru20ILσεε≤22()()11LIrIPHULLσεδε⎡⎤−≤≥−=−⎢⎥⎣⎦u3.2.2信源划分定理系3.2.1(特定典型序列出现的概率)若一个特定的事件(u1u2…uL)∈TU(L,ε),则2-L(H(U)+ε)≤P{(u1u2…uL)=(ai1ai2…aiL)}≤2-L(H(U)-ε)。证明设(u1u2…uL)∈TU(L,ε)。注意到此时H(U)-ε≤IL≤H(U)+ε,1212112121111loglog()()()()11log(()))lLLLLlliiiLiLiiiILPuaLPuaPuaPuaLPuuuaaa=========∑3.2.2信源划分定理所以121211()log()(()))LLiiiHUHULPuuuaaaεε−≤≤+=1212(())log(()))(())LLiiiLHUPuuuaaaLHUεε−+≤=≤−−12(())(())122(()))2LLHULHULiiiPuuuaaaεε−+−−≤=≤3.2离散无记忆(简单)信源的等长编码3.2.2信源划分定理系3.2.2(典型序列的数量)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。证明一方面,1212121212()(,)(())()(,)(())(())1(()(,))(()())212(,)(,)2LLUiiiULLULiiiuuuTLLHUaaaTLLHUULHUUPuuuTLPuuuaaaTLTLεεεεεεεε∈−+∈−++≥∈==≥=≤∑∑(由系)因此,3.2离散无记忆(简单)信源的等长编码3.2.2信源划分定理另一方面,1212121212()(,)(())()(,)(())(())1(()(,))(3.2.1)(()())2(1)2(,)(,)12LiiiULiiiULLULiiiaaaTLLHUaaaTLLHUULHUUPuuuTLPuuuaaaTLTLεεεεεεεεεε∈−−∈−−−−≤∈==≤=≥−∑∑由定理由系因此,()3.2离散无记忆(简单)信源的等长编码理解典型序列¾一个离散无记忆信源输出的消息序列可以分为两组,),(εLT),(εLT各序列出现的概率近于相等;每个序列平均符号的信息量接近于信源熵H(U);所有典型序列的概率和趋近于1。¾个别非典型序列的概率不一定比个别典型序列的概率低。¾虽然非典型序列集中序列的总概率很小,但是元素数目不一定小。理解典型序列¾个别非典型序列的概率不一定比个别典型序列的概率低。¾虽然非典型序列集中序列的总概率很小,但是元素数目不一定小。掷硬币试验:正面出现概率p,反面出现概率1-p典型序列非典型序列(全反)pLLpLpp−−)1(Lp)1(−LUHLLUKULT])([2),(εεα+≤=KLUHLlog])([22ε+=])([log2ε−−−=UHKL离散无记忆信源编码模型DMS)(LEu)(xDLuxxLuˆLLLUuuu∈=),,,(21u),,,(21Nxxx=xLLuu=ˆLLuu≠ˆ无错有错错误概率{}LLreppuu≠=ˆ3.2离散无记忆(简单)信源的等长编码3.2.3离散无记忆信源编码定理•编码速率•编码效率()1loglogNNRRMDMDLL====RUH/)(=η3.2离散无记忆(简单)信源的等长编码3.2.3离散无记忆信源编码定理•可达•对于给定的信源和编码速率R以及任意,若存在有,和,使当时,就称R是可达的,否则称此R不可达。例掷硬币实验R=1bit可达;R=0.5bit不可达。0ε0L()E()D0LLεep复习无失真等长编码的充要条件信源符号{a1,a2,…,aK}码字符号{0,1,…,D-1}长l的消息序列ai1ai2…ail长为N的码字n1n2…nNDN≥KLNlogD/L≥logK编码速率R=NlogD/LR≥logK复习由契比雪夫大数定理2222()()()()11LIrLIrIPHULLIPHULLσεδεσεδε⎡⎤−=⎢⎥⎣⎦⎡⎤−≤≥−=−⎢⎥⎣⎦uu()/()/LLllIILIuL==∑u()()()()()lkkkHUEIupaIa==∑()()()()22()()IlkkkDIupaIaHUσ==−∑典型序列集典型序列的数量(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)特定典型序列出现的概率若一个特定的事件(u1u2…uL)∈TU(L,ε),则2-L(H(U)+ε)≤P{(u1u2…uL)=(ai1ai2…aiL)}≤2-L(H(U)-ε)AsymptoticEquipartitionProperty{}εεε+≤≤−=)()(:),(UHIUHLTLLUu3.2.3离散无记忆信源编码定理定理3.2.2若,则R是可达;若则R是不可达的。)(UHR)(UHR()0[()](),,0(,)22(,)
本文标题:3.1离散无记忆信源等长编码
链接地址:https://www.777doc.com/doc-1507638 .html