信息论与编码第二章离散信源新.ppt

第二章 离散信源提纲l信源的数学模型及分类 l离散信源的自信息和信息熵l离散无记忆的扩展信源l离散平稳信源 l马尔可夫信源信源是产生消息的源，根据X的不同情况，信源可分为以下类型：根据信源的统计特性，离散信源又分为两种：离散信源离散信源 消息集X为离散集合。波形信源波形信源 时间连续的信源。连续信源连续信源 时间离散而空间连续的信源。无记忆信源无记忆信源 X的各时刻取值相互独立。有记忆信源有记忆信源 X的各时刻取值互相有关联。2.1信源的数学模型及分类 离散无记忆信源离散无记忆信源(Discrete Memoryless Source，简记为DMS)输出的是单个符号的消息，不同时刻发出的符号之间彼此统计独立，而且符号集中的符号数目是有限的或可数的。离散无记忆信源的数学模型为离散型的概率空间，即：p(xi)：信源输出符号消息xi的先验概率;满足：0 q(xi)1，1 i I 一 离散无记忆信源例1：掷骰子的结果作为信源消息，则就构成了一个这样的信源，其概率空间为：例2：箱中有赤、橙、黄、青、兰、紫六种颜色的32只彩球，其中赤16球，澄8球，黄4球，青2球，蓝、紫各1球。有放回抽取：一 离散无记忆信源（续）实际情况下，信源输出的消息往往不是单个符号，而是由许多不同时刻发出的符号所组成的符号序列。设序列由N个符号组成，若这N个符号取自同一符号集 a1,a2,ak，并且先后发出的符号彼此间统计独立，我们将这样的信源称作离散无记忆的离散无记忆的N维扩展信源维扩展信源。其数学模型为N维概率空间：x为各种长为N的符号序列，x=x1 x2 xN，xi a1,a2,ak，1 i N，序列集X=a1a1 a1,a1a1 a2,akak ak，共有kN种序列，x X。序列的概率p(x)=p(x1x2 xN)=二二 离散无记忆的扩展信源离散无记忆的扩展信源 例 如果X的的条件概率分布与时间起点无关，即任意两个不同时刻X的的概率分布都相同，概率分布都相同，则该信源为平稳信源平稳信源。对于离散平稳有记忆信源，在 t=i 时刻将要发出什么样的符号决定于两方面：(1)信源在 t=i 时刻随机变量Xi 取值的概率分布P(xi)。一般 P(xi)P(xj)(2)t=i 时刻以前信源发出的符号。即与条件概率P(xi/xi-1 xi-2)有关三三 离散平稳有记忆信源离散平稳有记忆信源 l若当t=i，t=j时(i,j 是大于1的任意整数)，P(xi)=P(xj)=P(x)，则序列是一维平稳的。具有这样性质的信源称为一维平稳信源。l除上述条件外，如果联合概率分布P(xixi+1)也与时间起点无关，即P(xixi+1)=P(xjxj+1)(i,j为任意整数且ij)，则信源称为二维平稳信源。它表示任何时刻信源发出二个符号的联合概率分布也完全相等。l如果各维联合概率分布均与时间起点无关，那么，信源是完全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源。这时有：P(xi)=P(xj)P(xi xi+1)=P(xj xj+1)P(xi xi+1 xi+N)=P(xj xj+1 xi+N)如如果在任何时刻其符号发生的概率只与前面已经发生的m个符号有关，而与更前面发生的符号无关，则称该信源为m价马尔可夫信源 四马尔可夫信源四马尔可夫信源 如果上述条件概率与时间起点i无关，则称为时齐马可夫信源。2.2 离散信源的自信息和信息熵l针对离散信源进行l基本概念样本空间：某一事物各种可能出现的不同状态，即所有可能选择的信息的集合概率测度：对每个可能选择的信息指定一个概率（非负，总和为1）概率空间：一个样本空间和他的概率测度先验概率：后验概率自信息：信息熵概率空间样本空间概率测度例1 如果将掷一次骰子的结果作为信源消息，则就构成了一个这样的信源，其概率空间为：例2 箱中有赤、橙、黄、青、兰、紫六种颜色的32只彩球，其中赤16球，澄8球，黄4球，青2球，蓝、紫各1球。现任取一球，将其色彩视为一个离散信源的输出，则该信源可用下列概率空间描述：发送端 接收端ai信道bj自信息l解决信息的度量问题 l信源发出的消息是随机的。未接收之前，收信者对信源发出的消息是不确定的。消息传到收信者后，才消除了不确定性，获得了信息。l某一消息发出的不确定性越大，一旦发生，接收者消除的不确定性就越大，获得的信息也就越大。一般而言，收信者所获取的信息量，在数量上等于通信前后不确定性消除（减少）的量。l获取信息量=收信前对某事件发生的不确定性-该事件发生后仍然存在的不确定性l假设发送符号为ai,，接收符号为收bj。可以直观地把信息量定义为：收到某消息bj后获得关于某事件ai发生的信息量=收到bj前、后对某事件ai存在的不确定性的消除=收信前关于某事件的不确定性（先验不定度）-收信后关于某事件发生的不确定性（后验不定度）先验概率越大，得到的信息量越小，反之信息量越大先验概率越大，得到的信息量越小，反之信息量越大中国足球队中国足球队3:0战胜巴西足球队战胜巴西足球队巴西足球队巴西足球队3:0战胜中国足球队战胜中国足球队注意l例例1 一个布袋内放一个布袋内放100个球，其中个球，其中80个球是红个球是红色的，色的，20个球是白色的，若随机摸取一个球，个球是白色的，若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信猜测其颜色，求平均摸取一次所能获得的自信息量。息量。解解:依据题意依据题意 这一随机事件的概率空间为这一随机事件的概率空间为 其中：其中：x1表示摸出的球为红球事件，表示摸出的球为红球事件，x2表示摸表示摸出的球是白球事件出的球是白球事件.1)如果摸出的是红球，则获得的信息量是如果摸出的是红球，则获得的信息量是 I（x1）=-log2p（x1）=-log20.8 bit 2)如果摸出的是白球，则获得的信息量是如果摸出的是白球，则获得的信息量是 I（x2）=-log2p（x2）=-log20.2 bit说明：说明：自信息量自信息量I(x1)和和I(x2)只是表征信源中各个符号的只是表征信源中各个符号的不确定度，一个信源总是包含着多个符号消息，不确定度，一个信源总是包含着多个符号消息，各个符号消息又按概率空间的先验概率分布，各个符号消息又按概率空间的先验概率分布，因而各个符号的自信息量就不同。所以因而各个符号的自信息量就不同。所以自信息自信息量不能作为信源总体的信息量量不能作为信源总体的信息量。信息熵l定义：例1续（3）如果每次摸出一个球后又放回袋中，如果每次摸出一个球后又放回袋中，再进行下一次摸取。则如此摸取再进行下一次摸取。则如此摸取n次，红球次，红球出现的次数为出现的次数为np（x1）次，白球出现的次）次，白球出现的次数为数为np（x2）次。随机摸取）次。随机摸取n次后总共所次后总共所获得的信息量为获得的信息量为l np（x1）I（x1）+np（x2）I（x2）4)则平均随机摸取一次所获得的信息量为则平均随机摸取一次所获得的信息量为 H（X）=1/nnp(x1)I(x1)+np(x2)I(x2)=-p(x1)log2p(x1)+p(x2)log2p(x2)=0.72比特比特/次次例例2 设甲地的天气预报为：晴设甲地的天气预报为：晴(占占48)、阴、阴(占占28)、大雨、大雨(占占18)、小雨、小雨(占占18)。又设乙地的天气预报为：晴。又设乙地的天气预报为：晴(占占78)，小雨，小雨(占占18)。试求两地天。试求两地天气预报各自提供的平均信息量。若甲地天气预报为两极端情况，一种是晴出现气预报各自提供的平均信息量。若甲地天气预报为两极端情况，一种是晴出现概率为概率为1而其余为而其余为0。另一种是晴、阴、小雨、大雨出现的概率都相等为。另一种是晴、阴、小雨、大雨出现的概率都相等为14。试求这两极端情况所提供的平均信息量。又试求乙地出现这两极端情况所提供试求这两极端情况所提供的平均信息量。又试求乙地出现这两极端情况所提供的平均信息量。的平均信息量。两个信源两个信源解：甲地天气预报构成的信源空间为解：甲地天气预报构成的信源空间为:则其提供的平均信息量即信源的信息熵则其提供的平均信息量即信源的信息熵则其提供的平均信息量即信源的信息熵则其提供的平均信息量即信源的信息熵:乙地天气预报的信源空间为乙地天气预报的信源空间为:n n结论结论结论结论：甲地：甲地：甲地：甲地天气预报天气预报提供的平均信息量大于乙地，因为乙地提供的平均信息量大于乙地，因为乙地提供的平均信息量大于乙地，因为乙地提供的平均信息量大于乙地，因为乙地比甲地的平均不确定性小。比甲地的平均不确定性小。比甲地的平均不确定性小。比甲地的平均不确定性小。甲地极端情况l极端情况极端情况1：晴天概率：晴天概率1n 结论结论：等概率分布等概率分布时信源的不确定性最大，时信源的不确定性最大，所以所以信息熵信息熵（平均信息量）平均信息量）最大最大。n极端情况极端情况2：各种天气等概率分布：各种天气等概率分布乙地极端情况l极端情况极端情况1：晴天概率：晴天概率1n 结论结论：在极端情况：在极端情况2下，甲地比乙地提供更多的信息量。下，甲地比乙地提供更多的信息量。因为，甲地可能出现的消息数比乙地可能出现的消息数多。因为，甲地可能出现的消息数比乙地可能出现的消息数多。n极端情况极端情况2：各种天气等概率分布：各种天气等概率分布说明：熵的基本性质（5）可加性 统计独立信源X和Y的联合信源的熵等于信源X和Y各自的熵之和。H(XY)=H(X)+H(Y)l可加性是熵函数的一个重要特性，正因具有可加性，才使熵函数的形式是唯一的。证明：证明：证明：证明：例如，甲信源为例如，甲信源为它们的联合信源是可计算得联合信源的联合熵：H(Z)=H(XY)=log(nm)=log m+log n=H(X)+H(Y)乙信源为乙信源为（6）强可加性l两个互相关联的信源X和Y的联合信源的熵等于信源X的熵加上在X已知条件下信源Y的条件熵。H（XY）=H（X）+H（Y/X）lH（Y/X）表示信源 X 输出一符号的条件下，信源Y再输出一符号所能提供的平均信息量，称为条件熵。H（XY）=H（X）+H（Y/X）的证明：）的证明：H（XY）=H（X）+H（Y/X）（7）递增性）递增性 若原信源若原信源 X 中中有一个符号分割成了有一个符号分割成了m个元素个元素(符号符号)，这，这m个元素的概率之和等于原元素的概率，而其个元素的概率之和等于原元素的概率，而其他符号的概率不变，则他符号的概率不变，则新信源的熵增加新信源的熵增加。熵的增加量等于由分割而产生的不确定性量。熵的增加量等于由分割而产生的不确定性量。证明可以从熵的定义或证明可以从熵的定义或强可加性强可加性得出：得出：因为因为因为因为而当而当而当而当inin时时时时p pij ij=0=0，所以，所以，所以，所以即得：即得：即得：即得：递增性的推广递增性的推广l它表示它表示n个元素的信源熵可以递推成个元素的信源熵可以递推成(n-1)个二元信个二元信源的熵函数的加权和。这样，可使源的熵函数的加权和。这样，可使多元信源的熵函多元信源的熵函数的计算简化成计算若干个二元信源的熵函数数的计算简化成计算若干个二元信源的熵函数。因。因此，熵函数的递增性又可称为递推性。此，熵函数的递增性又可称为递推性。（8）极值性）极值性l在离散信源情况下，信源各符号在离散信源情况下，信源各符号等概率分布等概率分布时，时，熵值达到最大。熵值达到最大。l性质表明性质表明等概率分布信源的平均不确定性为最大。等概率分布信源的平均不确定性为最大。l这是一个很重要的结论，称为这是一个很重要的结论，称为最大离散熵定理。最大离散熵定理。证明证明：因为对数是因为对数是型凸函数，满足詹森不等式型凸函数，满足詹森不等式Elog Y log EY，则有：，则有：二进制信源是离散信源的一个特例。二进制信源是离散信源的一个特例。该信源符号只有二个，设为该信源符号只有二个，设为“0”和和“1”。符号输出的概率分别为。符号输出的概率分别为“”和和“1-”，即信源的概率空间为：，即信源的概率空间为：H(X)=-log (1-)log(1-)=H()即信息熵即信息熵H(x)是是 的函数。的函数。取值于取值于0，1区间，可区间，可画出熵函数画出熵函数H()的曲线来，的曲线来，如右图所示。如右图所示。l熵函数熵函数H(P)是概率矢量是概率矢量P(p1，p2，pq)的严的严格格型凸函数型凸函数(或称上凸函数或称上凸函数)。l它表示：对任意概率矢量它表示：对任意概率矢量P1(p1,p2,pq)和和P2(p1,p2,pq)，和任意的，和任意的 0 1，有：有：H P1十十(1-)P2 H(P1)十十(1-)H(P2)l因为熵函数具有上凸性，所以熵函数具有极值，其因为熵函数具有上凸性，所以熵函数具有极值，其最大值存在。最大值存在。（9 9）上凸性）上凸性）上凸性）上凸性例题例4例5l当离散平稳无记忆信源发出固定长度的消息序列时，则得到原信源的扩展信源。l例如在电报系统中，若信源输出的是二个二元数字组成的符号序列，此时可认为是一个新的信源，它由四个符号（00，01，10，11）组成，我们把该信源称为二元无记忆信源的二次扩展信源。l如果把N个二元数字组成一组，则信源等效成一个具有2N个符号的新信源，把它称为二元无记信源的N次扩展信源。2.3 离散无记忆的扩展信源l一般情况下，对一个离散无记忆信源X，其样本空间为a1,a2,aq，对它的输出消息序列，可用一组组长度为N的序列来表示它。这时，它等效成一个新信源。l新信源输出的符号是N维离散随机矢量X=(X1，X2,XN)，其中每个分量Xi(i1,2,N)都是随机变量，它们都取值于同一信源符号集，并且分量之间统计独立，则由随机矢量X 组成的新信源称为离散无记忆信源X的N次扩展信源。单符号离散信源X的数学模型：lN次扩展信源与单符号离散信源比较：数学模型相同但输出不是单个符号，而是一串N个相互独立的符号序列：X(X1,X2,XN)，联合分布密度P(X)=P(X1X2XN)l把 X 等效为一个新信源，称为X的N次扩展信源，其数学模型：因为是无记忆的因为是无记忆的(彼此统计独立彼此统计独立)则：则：例6离散无记忆扩展信源的信息熵其中其中：同理计算式中其余各项，得到：同理计算式中其余各项，得到：H(XN)=H(X)+H(X)+H(X)=N H(X)证：证：例7一、离散平稳信源的数学定义一、离散平稳信源的数学定义二、二维平稳信源及其信息熵二、二维平稳信源及其信息熵三、三、离散平稳信源的极限熵离散平稳信源的极限熵2.4离散平稳信源 一、离散平稳信源的数学定义一、离散平稳信源的数学定义l 在一般情况下在一般情况下，信源在，信源在 t=i 时刻将要发出什么样的符号决时刻将要发出什么样的符号决定于两方面：定于两方面：(1)信源在信源在 t=i 时刻随机变量时刻随机变量Xi 取值的概率分布取值的概率分布P(xi)。一般一般 P(xi)P(xj)(2)t=i 时刻以前信源发出的符号。时刻以前信源发出的符号。即与条件概率即与条件概率P(xi/xi-1 xi-2)有关有关l对对平稳随机序列平稳随机序列，序列的统计性质与时间的推移无关，序列的统计性质与时间的推移无关，即信源发出符号序列的概率分布与时间起点无关。即信源发出符号序列的概率分布与时间起点无关。l平稳随机序列的数学定义如下：l若当t=i，t=j时(i,j 是大于1的任意整数)，P(xi)=P(xj)=P(x)，则序列是一维平稳的。具有这样性质的信源称为一维平稳信源。l除上述条件外，如果联合概率分布P(xixi+1)也与时间起点无关，即P(xixi+1)=P(xjxj+1)(i,j为任意整数且ij)，则信源称为二维平稳信源。它表示任何时刻信源发出二个符号的联合概率分布也完全相等。l如果各维联合概率分布均与时间起点无关，那么，信源是完全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源。这时有：P(xi)=P(xj)P(xi xi+1)=P(xj xj+1)P(xi xi+1 xi+N)=P(xj xj+1 xi+N)由于由于联合概率与条件概率联合概率与条件概率有以下关系：有以下关系：l结论：结论：对于平稳信源来说，其条件概率均与时间起点无关，对于平稳信源来说，其条件概率均与时间起点无关，只与关联长度只与关联长度N有关。有关。即平稳信源发出的平稳随机序列前即平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关后的依赖关系与时间起点无关。从从平稳性平稳性可得：可得：l对平稳信源对平稳信源如果如果某时刻发出什么符号只与前面发某时刻发出什么符号只与前面发出的出的N个符号有关个符号有关，那么，那么任何时刻任何时刻它们的依赖关它们的依赖关系都是一样的。即：系都是一样的。即：二、二维平稳信源及其信息熵二、二维平稳信源及其信息熵 最简单的平稳信源就是最简单的平稳信源就是二维平稳信源二维平稳信源。它。它满足一维和满足一维和二维概率分布与时间起点无关。二维概率分布与时间起点无关。同时已知：连续两个信源符号出现的联合概率分布为同时已知：连续两个信源符号出现的联合概率分布为同时已知：连续两个信源符号出现的联合概率分布为同时已知：连续两个信源符号出现的联合概率分布为P(ai aj)(i,j=1,q)，且：，且：，且：，且：l设有一个离散一维平稳信源，其概率空间为：设有一个离散一维平稳信源，其概率空间为：l由于只有两个符号有关联，且其关联与时间无关，则我们可把这个信源输出的随机序列分成每二个符号一组(因为相邻的两个符号才有关联)，每组构成新信源的一个符号，并假设组与组之间统计无关(实际上，组尾的符号与下一组组头的符号是有关的)。l这时，等效成一个新的信源X1X2，它们的联合概率空间为：根据信息熵的定义，得：根据信息熵的定义，得：H(XH(X1 1X X2 2)称为称为X X1 1X X2 2的联合熵的联合熵。关于离散二维平稳信源联合熵的说明lH(X1X2)表示原来信源X输出任意一对消息的共熵，即描述信源X输出长度为2的序列的平均不确定性（或所含有的信息量）。l可用H(X1X2)/2作为信源X的信息熵的近似值。从另一角度（从另一角度（来研究信源来研究信源X X的信息熵的近似值）：的信息熵的近似值）：（1 1）由由于于信信源源X X发发出出的的符符号号序序列列中中前前后后两两个个符符号号之之间间有有依依赖赖性性，可可以以先先求求出出在在已已知知前前面面一一个个符符号号X Xl la ai i时时，信信源源输输出出下下一个符号一个符号的平均不确定性：的平均不确定性：（2 2）前前面面一一个个符符号号X Xl l又又可可取取a ai i a a1 1，a a2 2，a aq q 中中任任一一个个，对对某某一一个个a ai i存存在在一一个个平平均均不不确确定定性性H(XH(X2 2/X/X1 1a ai i)，那那么么对对所所有有a ai i的的可可能能值值进进行行统统计计平平均均就就得得当当前前面面一一个个符符号号巳巳知知时时，再再输输出下一个符号的总的平均不确定性出下一个符号的总的平均不确定性H(XH(X2 2/X/X1 1)：（3 3）根据概率关系，可以得到）根据概率关系，可以得到）根据概率关系，可以得到）根据概率关系，可以得到联合熵与条件熵联合熵与条件熵联合熵与条件熵联合熵与条件熵的关系：的关系：的关系：的关系：（4）也可以得到条件熵和无条件熵的关系H(X2/X1)H(X2)（证明见（证明见p43）因此因此因此因此 H(XH(X1 1X X2 2)H(XH(X1 1)+H(X)+H(X2 2/X/X1 1)H(XH(X1 1)+H(X)+H(X2 2)=2H(X)=2H(X)所所所所以以以以，一一一一般般般般情情情情况况况况下下下下，输输输输出出出出二二二二个个个个符符符符号号号号的的的的联联联联合合合合熵熵熵熵总总总总是是是是小小小小于于于于二二二二倍倍倍倍信源的熵。信源的熵。信源的熵。信源的熵。例例8 8 某一离散二维平稳信源某一离散二维平稳信源某一离散二维平稳信源某一离散二维平稳信源其其其其发发发发出出出出的的的的符符符符号号号号只只只只与与与与前前前前一一一一个个个个符符符符号号号号有有有有关关关关，即即即即可可可可用用用用联联联联合合合合概概概概率率率率P(aP(ai ia aj j)给出它们的关联程度，如下表所示给出它们的关联程度，如下表所示给出它们的关联程度，如下表所示给出它们的关联程度，如下表所示 求信源的熵求信源的熵求信源的熵求信源的熵H(X)H(X)、条件熵条件熵条件熵条件熵H(XH(X2 2/X/X1 1)和联合熵和联合熵和联合熵和联合熵H(XH(X1 1X X2 2)。P(aP(ai ia aj j)a aj ja ai i0 01 12 20 01/41/41/181/180 01 11/181/181/31/31/181/182 20 01/181/187/367/36三、三、离散平稳信源的极限熵离散平稳信源的极限熵其中 的性质该性质表明联合熵等于起始时刻的无条件熵与各阶条件熵之和，并不随时间的推移而变化 该性质表明：在确知前面（N1）个时刻的符号的前提下，再发第N个符号提供的平均信息量，一定不超过每发一个符号提供的平均信息量（即平均符号熵）。表明，平均符号熵HN（X）的最大值就是原始信源X p的熵，而且它随N的增加是非递增的 2.5 马尔可夫信源一、马氏链的基本概念和主要特性二、马尔柯夫信源 三、马尔柯夫信源的信息熵一、马氏链的基本概念和主要特性l马尔可夫信源马尔可夫信源是一类相对简单的有记忆信源，信源在某一时刻发出某一符号的概率除与该符号有关外，只与此前发出的有限个符号有关。二、马尔柯夫信源l我们把前面若干个符号看作一个状态，可以认为信源在某一时刻发出某一符号的概率除了与该符号有关外，只与该时刻信源所处的状态有关，而与过去的状态无关。l信源发出一个符号后，信源所处的状态即发生改变，这些状态的变化组成了马氏链。马尔可夫信源状态转移图马尔可夫信源状态转移图 描述马尔可夫信源，我们可以用马尔可夫链的状态转移图。1、把每个可能出现的状态用一个圆圈表示；2、圆圈之间用有向线段连接，表示状态的迁移；3、在有向线段旁边，注明发出的符号 及在状态 下发出 的条件概率 马尔可夫信源状态转移图马尔可夫信源状态转移图 该马尔可夫信源有三个状态：，其中设为初始状态，初始概率为 ，等概率的转移到 这两个状态 例例一步转移概率矩阵一步转移概率矩阵m阶马尔可夫信源的条件概率阶马尔可夫信源的条件概率m阶马尔可夫信源的极限熵阶马尔可夫信源的极限熵三、马尔柯夫信源的信息熵例例 设有一个二元设有一个二元2阶马尔可夫信源，其信源符号集为阶马尔可夫信源，其信源符号集为解得解得计算极限熵计算极限熵