信息论基础2010-第三章new

《信息论基础2010-第三章new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息论基础浙江大学信息与通信工程研究所张朝阳2010夏学期第三章离散无记忆信源（DMS）的无损编码DMS的编码目标：在代价最小的意义上来最有效地表达一个信源。包括量化、压缩、映射、变换、自然语言翻译等许多具体和抽象的过程。绝对无差(n)P=0,∀ne错编码无损编码信源编码渐进无差(n)n→∞P→0e错编码有损编码（限失真编码）DMS编解码系统概念框图uLxN无扰xNu^DMSΧ(uL)D(xN)L信宿信道绝对无差错等长编码DMSa1a2aKU1,U2,U3ULUi~,∀ippp12

2、K编码符号集={b,b,,b}12D对源U的任意L长序列进行绝对无差错等长编码，则必有NLD≥K即编码速率NlogDR∆≥logKL渐进无差错等长编码KH(U)=H(p1,p2,,pk)=−∑pklogpkk=1NlogDR=？→H(U)LAEP性质（I）LuL=(u,u,,u),p(uL)=∏p(u)12Lll=1LI(uL)=−logp(uL)=∑I(u)ll=1∆I(uL)1LIL==∑I(ul)LLl=1AEP性质（II）L1E(IL)=E{∑I(ul)}=E(I(u))=H(U)Ll=1

3、Var(I(u))lVar(I)=LLK12=∑Pr(ul=ai)[−logPr(ul=ai)−E(I(ul))]Li=11K∆σ22I=∑p(ai)[logp(ai)+H(U)]=Li=1LAEP性质（III）由契比雪夫不等式Var(ξ)P{

4、ξ−E(ξ)

5、>ε}≤,∀随机变量ξ和ε2ε可得2σ{}IPI−H(U)>ε≤L2Lε2σI给定ε，当L充分大时2<εLε故P{I−H(U)>ε}≤ε,L或P{I−H(U)<ε}≥1−ε.L典型列集合令H(U)是为一个离散无记忆信源DMS{U，p(⋅)}的熵，ε为任意正

6、数，则称(L)L1LAε(U)=u:−logp(u)−H(U)<εLLL为给定DMS输出长度为L的ε典型列集合，简称典型列集，其中u∈U。典型列性质（1）：当L足够大时，L(L)Pr(u∈A(U))>1−εε(L)LLL(L)Pr(Aε(U))=∑p(u)=∑p(u)I(u∈Aε(U))L(L)LLu∈Aε(U)u∈U[L(L)](L(L))=EI(u∈Aε(U))=Pru∈Aε(U)>1−ε典型列性质典型列性质（2）：−L[H(U)+ε]L−L[H(U)−ε]L(L)2≤p(u)≤2,ifu∈A(

7、U)ε典型列性质（3）：L[H(U)−ε](L)L[H(U)+ε](1−ε)2≤A(U)≤2ε证明：LLL1=∑p(u)≥∑p(u)1−ε≤∑p(u)LLL(L)u∈Uu∈Aε(U)uL∈A(L)(U)ε−L[H(U)+ε]−L[H(U)−ε]≥∑2≤∑2L(L)L(L)u∈Aε(U)u∈Aε(U)(L)−L[H(U)+ε](L)−L[H(U)−ε]=A(U)⋅2=

8、A(U)

9、2εε(L)L[H(U)−ε]∴

10、A(L)(U)

11、≤2L[H(U)+ε]∴

12、A(U)

13、≥(1−ε)2εεDMS编码定理对熵为H(U)的离

14、散无记忆信源所输出的L长序列进行等长编码，编码序列长为N，编码符号表包括D个可用编码符号。则当平均NlogD每信源符号所耗用的编码比特数（编码速率）R∆满足LR>H(U)+εL(L)L→∞时，可实现渐进无差错的编码（P→0）；e反之，若RH(

15、U)+ε<(L)L(H(U)−ε)A(U)(1−ε)2LRL(H(U)+ε)(L)ε2>2>A(U)εL(ε−ε′)2L→∞Pr(Aε(L)(U))>1−ε⇒P(L)<ε=→0e1−εDMS的不等长编码消息集概率分布码字码长apbbbn1111121n11a2p2b21b22b2n2n2apbbbKKK1K2KnKnKKn=∑pknkk=1不等长码的例子信源消息出现概率码A码B码C码Da0.500001a0.250101102a0.1251000111103a0.12510110111

16、11104不等长码的基本要求唯一可译性即时可译性={101，00110，10111，11001}10111，00110，11001，101101，11001，10110，00110唯一可译性非奇异性x≠x⇒C(x)≠C(x)ijij码扩展*C(xxxx)=C(x)C(x)C(x)C(x)123n123n定义：码的任意扩展都是非奇异的，则称码是唯一可译的。唯一可译性的Sardi