2008-应用信息论基础-张林-Chap-2-339504607

1第二章信源与信源无失真编码InformationSourceandLosslessCoding©THU2008–Allrightsreserved清华大学电子系－张林2008年10月15日2008年10月22日2008年10月29日2.0引子„让我们再次从系统的视角回顾一下整个通信流程信源信源编信道编信道信道译信源译信宿©THU2008–Allrightsreserved2源码器码器道码器码器宿解密干扰源加密编码侧的考虑„信源输出的序列具有随机性，如何刻画？…可以将信源看作一个随机过程…“Wecanthinkofadiscretesourceasgeneratingthemessage,symbolbysymbol...amathematicalmodelofssystem...isknownasastochasticprocess.”„要将信源输出的信息进行最有效的表示，如何进行？…离散随机变量的熵在什么情况下可以获得最大？©THU2008–Allrightsreserved3…离散随机变量的熵在什么情况下可以获得最大？…通过什么方法可以逼近这个极限？信源信源编码器X0～p0(x)X’～p(x’)解码侧的考虑„是否可以唯一的恢复原来的序列？„恢复原来序列的计算复杂度„实际设计的编码方法与理论极限的差距©THU2008–Allrightsreserved4信源译码器…0100101010…ThisisBY1QH.本章脉络©THU2008–Allrightsreserved52.1渐进等同分割性质„是什么导致我们研究渐进等同分割性质？…回想：最大离散熵原理…定理：等概分布时，离散熵最大化…但是：信源输出的一般不是等概分布的…问题：如何将非等概输出的信源变成等概？©THU2008–Allrightsreserved6信源输出序列将序列进行分割S1S2S3S4…2古典概率理论中大数定律的回顾„伯努利在1713年首先给出了频率稳定性的一种数学表述方法，并证明了结论。„该结论是一系列大数定理（LawofLargeNumber）的第一个110,1,2,...nniipiAiASXnNnNεδ=⎧=⎨⎩==∑n在一个“成功”概率为的伯努利试验序列中，，第次试验发生X，第次试验不发生对于任意正数和存在正整数当时伯努利大数定律©THU2008–Allrightsreserved7„伯努利大数定律说的是1nnNnNSPpnSPpnεδεδεδ⎛⎞−≥⎜⎟⎝⎠⎛⎞−≥−⎜⎟⎝⎠对于任意正数和，存在正整数，当时，有:，或等价地:，PnSpn→古典概率理论中大数定律的回顾„博雷尔（Borel）给出了更强的数学表达形式„博雷尔强大数定律（StrongLawofLargeNumber）说的是a.e.nSp→10piAiA⎧=⎨⎩n在一个“成功”概率为的伯努利试验序列中，，第次试验发生X，第次试验不发生博雷尔强大数定律©THU2008–Allrightsreserved8„回顾：…依概率收敛到X…几乎处处收敛到Xpn→1,1,2,...1lim1.nniinnSXnnSPpn=→∞==≥⎛⎞==⎜⎟⎝⎠∑当时，则古典概率理论中大数定律的回顾„博雷尔大数定律比伯努利大数定律强，因此后者也常常被称为弱大数定律„更一般的弱大数定律表述为：X设为独立同分布的随机变量则弱大数定律©THU2008–Allrightsreserved9111EinPiiXXXn=→∑设为独立同分布的随机变量，则渐进等同分割性质的评述„渐进等同分割性质：AsymptoticEquipartitionProperty„差不多所有的事件都是等概出现的：Almostalleventsarealmostequallysurprising„可以简单地由弱大数定理推出„对于数据压缩的贡献©THU2008–Allrightsreserved10„对于数据压缩的贡献：…等同分割→等概率→最大离散熵→定长编码定理…暗示了一种定长编码的方法渐进等同分割性质定理定理2.12.1如果X1,X2，…是独立同分布的离散随机变量，分布服从p(x)，则121log(,,...,)()PnpXXXHXn−→证明见板书证明见板书©THU2008–Allrightsreserved11证明见板书证明见板书渐进等同分割性质的另外一种表述„朱书定理3.2pp.82„请大家自学书中的证明，在这里不赘述„特别要注意以概率收敛的概念在该表述中的体现离散忆稳恒信输出的个特定序列©THU2008–Allrightsreserved121200...00log(){()}1nxxxNnNpPHXnεδεδ∞=≥+−xx设离散无记忆稳恒信源输出的一个特定序列。则任给和，可以找到一个整数，使当时，有3典型序列定义定义2.12.1相对于分布p(x)和序列(x1,x2,…,xn)∈Xn，典型序列集合定义为满足下列不等式约束的所有序列x的集合。()nAε(())(())122()(,,...,)2nHXnHXnppxxxεε−+−−≤=≤x对于典型序列的直观理解©THU2008–Allrightsreserved139典型序列是全部可能序列的子集9给定特定的误差范围ε和序列长n，离散无记忆信源输出Bb序列的集中程度9若固定ε，n越大，典型序列中元素个数越多9若固定n，ε越大，典型序列中元素个数越多典型序列的性质定理定理2.22.2典型序列具有以下性质：()()()(())11.,()log()()2.Pr{}13.2nnnnHXAHXpHXnnAAεεεεεε+∈−≤−≤+−≤xx若则若足够大，©THU2008–Allrightsreserved14()(())3.24.(1)2nnHXAAεεεε−≤≥−证明见板书证明见板书对于定理2.2的物理解释9对于足够大的n，典型序列中的序列几乎等概9对于足够大的n，典型序列集合几乎可以从概率上覆盖所有序列9对于足够大的n，典型序列集合中的元素个数大约为2nH个2.2定长编码定理„问题的提出：…设X1,X2,…Xn...是服从分布p(x)的离散无记忆信源的输出序列…我们的目标是寻找尽量短的编码方案，来描述这一随机序列„直观的分析：…p(x)一般不是均匀分布，因此，针对每一个字母的定长码不合算…AEP告诉我们，若分割的段足够长，各段分布呈现等概趋势©THU2008–Allrightsreserved15…AEP告诉我们，若分割的段足够长，各段分布呈现等概趋势„直观的解决：…利用典型序列集合的性质来进行编码回顾：典型序列集合„长度为n的离散无记忆信源输出序列，其典型序列集合有以下性质：…对于足够大的n，典型序列中的序列几乎等概…对于足够大的n，典型序列集合在概率意义上几乎可以覆盖所有可能…对于足够大的n，典型序列集合中的元素个数大约为2nH个©THU2008–Allrightsreserved16构造一种定长编码的方案„分别对典型序列和非典型序列进行编码„针对典型序列，加1比特用于识别，加1比特浮点补偿，码长小于n(H+ε)+2„针对非典型序列，加1比特用©THU2008–Allrightsreserved17„针对非典型序列，加1比特用于识别，加1比特浮点补偿，码长小于nlog|X|+2„编码映射是一对一的定长编码定理定理定理2.32.3设Xn是由独立同分布离散随机变量x~p(x)构成的序列。对于任意正数ε，总有足够大的n，可以找到一个一一映射，将Xn映射为二进制序列，且满足：©THU2008–Allrightsreserved18证明见板书证明见板书4定长编码定理的另一种表述定理定理2.42.4对于独立同分布离散随机序列XN，用长度为M的码进行编码，码字母表大小为J。对任意正数ε和δ，只要N足够大，且满足不等式ε+)(logXHJNM©THU2008–Allrightsreserved19则源字母组没有自己特定码字的概率P0小于ε。证明见朱书证明见朱书pp.85pp.85例2.1典型序列一个离散无记忆信源生成二元消息，其概率分布为：p(A)=0.3,p(B)=0.7，令ε=0.01，分析典型序列。1.该离散信源的熵为H(0.3)=0.88bits。2.如果直接针对原序列编码，则码长为1bits。研究进行不同长度分组后典型序列的分布情©THU2008–Allrightsreserved203.研究进行不同长度分组后，典型序列的分布情况。©THU2008–Allrightsreserved21©THU2008–Allrightsreserved22©THU2008–Allrightsreserved23定长编码定理的评注„香农最早给出了针对离散无记忆信源的AEP„McMillan和Breiman证明了有限各态历经信源的AEP，扩展了AEP的适用范围©THU2008–Allrightsreserved24•B.McMillan.Thebasictheoremsofinformationtheory.Ann.Math.Stat.,24:196–219,1953.•L.Breiman.Theindividualergodictheoremsofinformationtheory.Ann.Math.Stat.,28:809–811,1957.52.3离散信源的熵率„什么是信源？…产生消息或消息序列的源…信源的例子：烟（烽火台），语言，图片，电视„信息论关心的是信源输出的消息的统计特性，而非信息本身„信源输出可能出现的状态（输出的消息）是随机的不确©THU2008–Allrightsreserved25„信源输出可能出现的状态（输出的消息）是随机的、不确定的，但表现出一定的规律性„如何用统计数学的方法描述信源？…用随机过程加以描述…{}Tttx∈),(信源的分类„按取值集合与取值时刻的连续与离散划分，简单直观信号取值信号取值时刻信源种类离散离散数字信源（DigitalSource）连续连续模拟信源（AnalogSource）©THU2008–Allrightsreserved26连续离散连续信源（ContinuousSource）离散连续信源的分类„按刻画信源的随机过程的性质划分…无记忆信源…有记忆信源…平稳信源…非平稳信源随机过程在时间上是否独立？随机过程是否平稳©THU2008–Allrightsreserved27„由此产生出的特殊的信源…马尔可夫信源…高斯信源„我们在本章的其余部分，将主要针对离散信源进行研究随机过程的不确定性„我们已经针对一个随机变量定义了熵，如果是一个随机过程，如何扩展这个概念，以描述其不确定性？„直觉思考：…如果随机过程是无记忆过程，那么应该与描述随机变量没有什么区别。…如果有记忆，那么较晚生成的消息提供的信息量应该比稍早产生©THU2008–Allrightsreserved28如果有忆那较晚成的消息提供的信息应该稍早产的消息提供的信息量来得小。„如果用平均值来表示随机过程的信息量，当样本轨道长度趋近无穷的时候，熵率存在吗？熵率的定义定义定义2.22.2当极限存在时，随机过程{Xi}的熵率定义为：或者，也可以定义为©THU2008–Allrightsreserved29若极限存在。定义2.2给出了对于熵率的两种不同视角的理解9前者是序列趋近于无穷长时每个消息提供的信息量9后者是在了解历史的条件下，最后一个消息提供的信息量例2.2随机过程的熵率„打字机：假定打字机等概地输出m个字母，则它可以等概地输出mn个序列，因此H(X1,X2,…Xn)=logmn，熵率是H(X)=logmbits/字符„平稳无记忆信源：设X1,X2,…为iid随机变量，则©THU2008–Allrightsreserved30„非平稳无记忆信源：对于这种情况，我们可以找到一个Xi的分布，使极限不存在。具体见板书具体见板书6稳恒信源的熵率定理定理2.52.5对于稳恒信源，条件熵H(Xn|Xn-1,…,X1)是n的减函数，并且存在极限H’(X)。定理定理2626对于稳恒信源两种方式定义的