第二章随机过程的信息度量和渐近等分性.

1§2.1信源和随机过程的基本概念§2.2随机过程的信息度量§2.3渐近等分性质§2.4渐近等分在数据压缩中的应用§2.5Shannon-McMillan-Breiman定理第二章2信源：是信息的来源,是产生消息(符号)、消息序列(符号序列)以及时间连续的消息的来源.(1)在一个固定的时刻,信源发出的是一个随机变量.(2)随着时间的延续，信源发出的是一个随机过程.信源的主要问题如何描述信源的输出（信源的建模问题）怎样确定信源产生的信息量信源编码第二章1.信源的分类及其数学模型312()()NPXPXXX),(teX时间（空间）取值信源种类举例消息的数学描述离散离散离散信源(数字信源)文字、数据离散化图象离散随机变量序列离散连续连续信源连续连续波形信源(模拟信源)语音、音乐、热噪声、图形、图象随机过程连续离散不常见根据信源输出消息在时间和取值上是离散或连续分类4信号取值离散：信源输出的消息是有限或可数的，而且每次只输出其中一个消息.如：抛硬币！其数学模型是离散型的概率空间：1212,(),(),()()qqxxxXPxPxPxPx()1iipa,(,)()()XabPxPx信号取值连续：信源输出的是单个符号，但符号集的取值是连续的，或实数集.如：语音信号某时间的连续数据！其数学模型是离散型的概率空间：()1bapxdx5波形信源：输出的消息是时间连续，且符号集的取值也连续.如：多媒体通信系统的信号！一般用平稳遍历的随机过程来描述波形信源的输出.平稳：在任意两个不同时刻随机变量的各维概率分布相同.如：自然英文字母！11(,,,,,)nnnpxxtt11(,,,,,)nnnpxxtt6离散信源信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列…U-2U-1U0U1U2…，其中(1)Uk为第k个时间段发出的随机变量；(2)每个Uk都是一个离散型的随机变量.信源的分类及其数学模型71)根据信源发出的消息序列之间是否有统计依赖关系，信源可分为有记忆信源、无记忆信源.离散无记忆信源：随机变量…、U-2、U-1、U0、U1、U2、…相互独立.简单信源：信源在不同时刻发出的随机变量有相同的概率分布.离散无记忆简单信源：离散无记忆信源发出的随机变量具有相同的概率分布.信源的分类及其数学模型8注意：有记忆信源：信源在不同时刻发出的随机变量相互依赖.有限记忆信源：在有限时间差内的信源随机变量相互依赖.信源的分类及其数学模型9()离散无记忆信源记忆长度无限长离散平稳信源平稳信源离散有记忆信源记忆长度有限随机序列马尔可夫信源连续平稳信源非平稳信源随机过程：波形信源2)根据信源发出的消息序列中的消息统计特性是否保持不变，信源可分为平稳信源、非平稳信源.信源的分类及其数学模型102.离散信源•离散信源（1）单符号离散信源：信源输出的消息是离散消息，且每个符号表示一条消息。•用离散随机变量表示。记作：大写字母。（2）多符号离散信源：信源输出的消息是离散消息，且多个符号表示一条消息。•用随机矢量表示。（3）连续信源：信源输出的消息是连续消息。•用随机过程表示。11离散单符号信源：输出离散取值的单个符号的信源.离散单符号信源是最简单、最基本的信源，是组成实际信源的基本单元，可以用一个离散随机变量来表示.离散单符号信源X的概率空间1212...()()()...()qqxxxXPXpxpxpx()0ipx1()1niipx2.离散信源12信源输出的所有消息的自信息的统计平均值，定义为信源的平均自信息（信息熵）1()log()()log()niiiiHXEpxpxpx信息熵表示离散单符号信源的平均不确定性.离散单符号信源13实际信源往往输出的消息是时间和空间上的一系列符号.例如电报系统,这类信源每次输出的不是一个单个的符号，而是一个符号序列.通常一个消息序列的每一位出现哪个符号都是随机的,而且一般前后符号之间的出现是有统计依赖关系的,这种信源称为多符号离散信源.为了便于研究,假设随机变量序列中随机变量的各维联合概率分布(统计特性)均不随时间的推移而变化,即信源所发出的符号序列的概率分布与时间的起点无关,这种信源称为多符号离散平稳信源.多符号离散信源可以用随机变量序列来描述，即12nXXXX离散多符号信源14定义对于离散随机变量序列，若任意两个不同时刻i和j(大于1的任意整数)信源发出消息的概率分布完全相同，即对于任意的,和具有相同的概率分布，也就是各维联合概率分布均与时间起点无关的信源称离散平稳信源。nXXX21,2,1,0N1iiiNXXX1jjjNXXX)()(jiXPXP)()(11jjiiXXPXXP11()()iiiNjjjNPXXXPXXX离散平稳信源15对离散平稳信源，由联合概率与条件概率的关系可以推出)|()|(11jjiiXXPXXP1111(|)(|)iNiiiNjNjjjNPXXXXPXXXX因此)()()(21NXHXHXH)|()|()|(12312NNXXHXXHXXH31242321(|)(|)(|)NNNHXXXHXXXHXXX离散平稳信源16如果一个信源序列是平稳遍历过平稳程,遍称信源为历信源.平稳遍历信源1223(,,...)(,,...),.设为一个实数序列，用表示移位算子，称实数列的集合为，如果当且定平移不变义当集仅xxxTTxxxATxAxA12{(,,...)}01.称一个平稳过程为，如果对任何平移不变集定遍历的有或义rAPxxA,直观地说一个遍历的马氏过程从任何一个状态出发可以正概率在有限步到达任何其它状态.17随机变量是定义在概率空间上取值为实数的函数。因此我们可以像数学分析讨论函数序列逐点收敛性那样去讨论随机变量序列在每个样本点处的值的收敛性。然而,由于随机变量取值的随机性,我们常常不可能期望随机变量序列在所有点处都存在极限。现在的问题是研究极限是否在一个概率为1的点集上存在。由于随机变量序列向常数的收敛有多种不同的形式,按其收敛为依概率收敛,依概率1收敛,相对应分别有弱大数定律、强大数定律。1812111{,,...,...1,0,1lim{||}1.:,,1.nniiinrininiiXXXXEXaXanPXannXan设,}为相互独立的随机变量序列,并且服从相同的分布,有有限数学期望=,则依概率收敛到即对任意的有直观的理解除去极小的可能性只要充定理(弱大数定律)分大与可任意接近弱大数定律191211{,,...,...1,1{lim}1.{},.nniiinrinikXXXXEXaXnaPXanX定理(强大数定律)设,}为相互独立的随机变量序列,并且服从相同的分布,有有限数学期望=,则依概率1收敛到即一个信源序列如果使定义强大数定律成立称为平均遍历强大数定律20121212(,)()(),(,,...,)(,,...,)(,,...,).,0,()()().mnmmmmnHXYHXHYHXXXHXXXHXXXmnhmnhmhn因为所以对任意的整数满足的定义半可列称加数列数()()()()11,lim()inf().设是满足的半可加数列引则理nnfnfmnfmfnfnfnnn2.2随即过程的总度量3.随机过程的信息度量211{,1,2,...}lim,1lim.设实数列有极引限则理nnnnknkanaaaan定义随机变量序列中，对前N个随机变量的联合熵求平均称为平均符号熵.121()(,,,)NNHHXXXNX随机过程的信息度量2212121()lim()lim(,,,)1inf(,,,)()defNNNNNNHXHHXXXNHXXXXN是平稳信源X如果当时上式极限存在，则被称为熵率，或极限熵，记为Nlim()NNHX随机过程的信息度量2312,.{,,...,...},nXXXX为了便于计算我们给出熵定理率的另一个等价形式设,是平稳信源121(1)'()lim(|,,...,)存在;defnnnHXHXXXX(2)()'().HXHX随机过程的信息度量24（2）对于收敛的实数列，即如果是一个收敛于a的实数列，那么123,,,aaa11limlimNkNNNkaaaN利用上述结论及熵的链法则可以推出121lim(|)'()NNNHXXXXHX121lim()lim(,,,)()NNNNHHXXXHXNX1111lim(|,,)NkkNkHXXXN1213121211lim(()(|)(|)(|))NNNHXHXXHXXXNHXXXX25121{,,...,...}()()nXXXXHXHX设,是无记忆信源,则熵率推论1.随机过程的信息度量1211221{,,...,...}()(|,,...,,1,()(|2nkkXXXXHXHXXXXkHXHXX设,是k-阶平稳马氏信源,则熵率);特别地时推论).26为了研究离散平稳无记忆信源的极限熵，把信源输出的符号序列看成是一组一组发出的。例1电报系统中,可以认为每2个二进制数字组成一组。这样信源输出的是由2个二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源，它由四个符号00，01，10，11组成，把该信源称为二进制无记忆信源的二次扩展。例2如果把每三个二进制数字组成一组，这样长度为3的二进制序列就有8种不同的符号，可等效成一个具有8个符号的信源，把它称为二进制无记忆信源的三次扩展信源。4.离散平稳无记忆信源27假定信源输出的是N长符号序列，把它看成是一个新信源，称为离散平稳无记忆信源的N次扩展信源，用N维离散随机变量序列来表示：12NNXXXXX1212()()()()()NiqNiqNXppppPXi是一个长为N的序列，12Niiiiaxxx离散平稳无记忆信源N次扩展信源的概率空间为28N次扩展信源的熵离散平稳无记忆信源的N次扩展信源的熵等于离散单符号信源熵的N倍1()()()log()NqNiiiHHXppX()()()NHHXNHXX离散平稳无记忆信源的熵率1()lim()lim()()NNNHXHNHXHXNX离散平稳无记忆信源29例设有一离散无记忆信源X，其概率空间为求该信源的熵率及二次扩展信源的熵。123111244xxxXPX解离散单符号信源熵321()()log()1.5iiiHXpxpx比特/符号()1.5/HHX＝比特符号熵率30二次扩展信源的概率空间二次扩展信源的熵921()()()log()3iiiHHXppX比特/符号21112123134215226237318329332()()()()()()()()()1/41/81/81/81/161/161/81/161/16()xxxxxxxxxxxxxxxxxxXPX31实际信源常常是有记忆信源.设信源输出N长的符号序列，则可以用N维随机变量序列来表示信源，其中每个随机变量之间存在统计依赖关系.N维随机变量序列的联合熵为12NXXXX12()(,,,)NHHXXXX121312121()(|)(|)(|)NNHXHXXHXXXHXXXX离散平稳有记忆信源3212314114936xxxXPX