第三章：信源、熵率及冗余度PPT课件

1,.,第三章：信源、熵率及冗余度,.,2,问题一,信息论对信源的研究内容包括哪几个方面？,.,3,信息论对信源研究的内容,信源的建模：用恰当的随机过程来描述信号关心角度：信号中携带的信息信源输出信号中携带信息的效率的计算熵率、冗余度信源输出信息的有效表示信源编码,.,4,问题二,从信息论的角度如何为信源建模？信源的统计特性如何？如何对信源分类？各类信源如何建模？,.,5,信源特性,信源的统计特性1）什么是信源？信源是信息的来源，实际通信中常见的信源有：语音、文字、图像、数据。在信息论中，信源是产生消息（符号）、消息（符号）序列以及连续消息的来源，数学上，信源是产生随机变量X，随机序列和随机过程X(t,)的源。2）信源的主要特性信源的最基本的特性是具有统计不确定性，它可用概率统计特性来描述。,.,6,信源的分类,离散信源与连续信源离散信源单符号信源序列信源平稳&非平稳有记忆&无记忆连续信源连续信源波形信源,.,7,离散信源单符号离散信源（1）,它是最简单也是最基本的信源，是组成实际信源的基本单元。这类信源可能输出的消息数是有限的或可数的，而且每次只输出其中一个消息。因此，可以用一个离散型随机变量X来描述这个信源输出的消息。这个随机变量X的样本空间就是符号集A；而X的概率分布就是各消息出现的先验概率，信源的概率空间必定是一个完备集。,.,8,离散信源单符号离散信源（2）,当信源给定，其相应的概率空间就已给定；反之，如果概率空间给定，这就表示相应的信源已给定。所以，概率空间能表征离散信源的统计特性，因此有时也把这个概率空间称为信源空间。在实际情况中，存在着很多这样的信源。例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。这些信源输出的都是单个符号(或代码)的消息，它们符号集的取值是有限的或可数的。我们可用一维离散型随机变量X来描述这些信源的输出。它的数学模型就是离散型的概率空间：,.,9,离散信源单符号离散信源的数学描述,对单符号离散信源U有：例31：对于二进制数字信源：U=0,1，则有,.,10,离散信源离散多符号信源,实际的信源输出的消息是时间或空间上离散的一系列随机变量。这类信源每次输出的不是一个单个的符号，而是一个符号序列。在信源输出的序列中，每一位出现哪个符号都是随机的，而且一般前后符号的出现是有统计依赖关系的。这种信源称为多符号离散信源。例32：THEYAREMYFRIENDS.,.,11,离散信源多符号离散信源的数学描述,多符号离散信源可用随机矢量/随机变量序列描述，即X=X1X2X3信源在不同时刻的随机变量Xi和Xi+r的概率分布P(Xi)和P(Xi+r)一般来说是不相同的，即随机变量的统计特性随着时间的推移而有所变化。,.,12,离散信源离散平稳信源,若信源输出的随机序列X=(，)中，每个随机变量Xi(i=1,2,，N)都是取值离散的离散型随机变量，即每个随机变量Xi的可能取值是有限的或可数的。而且随机矢量X的各维概率分布都与时间起点无关，也就是在任意两个不同时刻随机矢量X的各维概率分布都相同。这样的信源称为离散平稳信源。如中文自然语言文字，离散化平面灰度图像都是这种离散型平稳信源。一般来说，信源输出的随机序列的统计特性比较复杂，分析起来也比较困难。为了便于分析，我们假设信源输出的是平稳的随机序列，也就是序列的统计性质与时间的推移无关。很多实际信源也满足这个假设。,.,13,离散信源平稳信源的数学模型（二维）,最简单的离散平稳信源：二维平稳信源X=X1X2每两个符号看做一组，每组代表信源X=X1X2的一个消息；每组中的后一个符号和前一个符号有统计关联，这种概率性的关系与时间起点无关；假定符号序列的组与组之间是统计独立的。,设X1,X2x1,x2,xn,矢量Xx1x1,x1xn,x2x1,x2xn,xnx1,xnxn令,.,15,X的数学模型,.,16,离散信源离散平稳无记忆信源,在某些简单的离散平稳信源情况下，信源先后发出的一个个符号彼此是统计独立的。也就是说信源输出的随机矢量X=(XXX）中，各随机变量Xi(i=1,2,N)之间是无依赖的、统计独立的，则N维随机矢量的联合概率分布满足P(X)=P（）P（）P（）我们称由信源空间X，P(x)描述的信源X为离散无记忆信源。这信源在不同时刻发出的符号之间是无依赖的，彼此统计独立的。,.,17,离散信源离散无记忆信源的N次扩展信源,离散无记忆信源X=x1,x2,xn，对它的输出消息序列，可以用一组组长度为N的序列来表示它。这时它就等效成了一个新信源；新信源输出的符号是N长的消息序列，用N维离散随机矢量来描述。ai=(xi1xi2xiN)i=1,2,n每个分量xik(k=1,2,N)都是随机变量，都取值于同一信源X，并且分量之间统计独立。由随机矢量X组成的新信源称为离散无记忆信源X的N次扩展信源。离散无记忆信源的N次扩展信源的数学模型是X信源空间的N重空间。,ABDACBBACCDX100000000000X211111111111X300000000000X400000000000X500000000000X600100000001X701001110110X810011001110X1、X2、X8,均为单符号随机变量信源X=0,1，P(X1X2X8)与时间起点无关平稳P(X1X2X8)P(X1)P(X2)P(X8)无记忆信源,例33：,电文：女孩儿在哭XCHUYJKOIUYHSFRTNHYTFSGTRWX1CKHNSX2H0SHGX3UIFYTX4YURTRX5JYTFWX1,X2,X3,X4,X5均为单符号随机变量XA、B、CZP(X1X2X3X4X5)=P(X1)P(X2)P(X3)P(X4)P(X5)且与时间起点无关，X为一无记忆平稳信源,例34：,.,20,离散信源二进制无记忆信源的N次扩展信源,把信源输出的序列看成是一组一组发出的。电报系统中，可以认为每二个二进制数字组成一组。这样信源输出的是由二个二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源，它由四个符号00，01，10，11组成，把该信源称为二进制无记忆信源的二次扩展。如果把每三个二进制数字组成一组，这样长度为3的二进制序列就有8种不同的序列，可等效成一个具有8个符号的信源，把它称为二进制无记忆信源的三次扩展信源。二进制无记忆信源的N次扩展：把每N个二进制数字组成一组，则信源等效成一个具有2N个符号的新信源，把它称为二进制无记忆信源的N次扩展信源。,.,21,离散信源离散平稳有记忆信源,一般情况下，信源在不同时刻发出的符号之间是相互依赖的。也就是信源输出的平稳随机序列X中，各随机变量Xi之间是有依赖的。例如，在汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。其他如英文，德文等自然语言都是如此。这种信源称为有记忆信源。我们需在N维随机矢量的联合概率分布中，引入条件概率分布来说明它们之间的关联。,女孩儿在哭XTHISGIRLISCRYINGX1TGICX2HISRX3IRYX4SLIX5NX6GX1,X2,X3,X4,X5均为单符号随机变量XA、B、CZP(X1X2X3X4X5)P(X1)P(X2)P(X3)P(X4)P(X5)与时间起点无关，X是一有记忆平稳信源,例35：,.,23,离散信源马尔可夫信源,表述有记忆信源要比表述无记忆信源困难得多。实际上信源发出的符号往往只与前若干个符号的依赖关系强，而与更前面的符号依赖关系弱。为此，可以限制随机序列的记忆长度。当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关。,.,24,离散信源时齐马尔可夫信源,设马尔可夫信源各时刻随机变量的取值为xk，xkXk，k=1,2,，i-1,i,i+1,N，则描述随机序列中各随机变量之间依赖关系的条件概率为P(xi|xi+2xi+1xi-1xi-2xi-3xi-mx1）=（xi|xi-1xi-2x-3xi-m）（i=1,2,N）如果上述条件概率与时间起点i无关，即信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐马尔可信源。,.,25,1.各字母等概、字母间不相关（字符独立）XFOMLRXKHRJFFJUJLPWCFWKCYFFJEYVKCQSGHYDQPAAMKBZAACIBZLHJQD.2.字母出现概率按照英文文本统计，字母间不相关（字符独立）OCROHLIRGWRNMIELWISEULLNBNESEBYATHEEIALHENHTTPAOOBTTVANAH3.字母出现概率按照英文文本统计，字母间存在二维相关性（两两相邻字母相关）ONIEANTSOUTINYSARETINCTORESTBESDEAMYACHINDILONASIVETUCOOWEATTEASONAREFUSOTIZINANDYTOBESEACECTISBE.,信源建模,信源建模,4.字母出现概率按照英文文本统计，字母间存在三维相关性INNOISTLATWHEYCRATICTFROUREBIRSGROCIDPONDENOMEOFDEMONSTURESOFTHEREPTAGINISREGOACTIONAOFCRE.5.字母出现概率按照英文文本统计，字母间存在N维相关性REPRESENTINGANDSPEEDILYISANGOODAPTORCOMECANDIFFERENTNATURALHEREHETHEAINCAMETHETOOFTOEXPERTGRAYCOMETOFURNISHESTHELINEMESSAGEHADBETHESE.6.单词间存在相关性（依据语法）.THEHEADANDINFRONTALATTACKONANENGLISHWRITERTHATTHECHARACTEROFTHISPOINTISTHEREFOREANOTHERMETHODFORTHELETTERSTHATTHETIMEOFWHOEVERTOLDTHEPROBLEMFORANUNEXPECTED.,模型复杂度越高，越逼近实际。,一个足够复杂的随机序列模型能够满意地表示自然语言的信源。,.,27,离散序列信源总结,.,28,模拟信源,模拟信源又可根据时间是否离散分为连续信源和波形信源。连续信源是时间离散而取值连续的一类信源，波形信源是指取值连续时间也连续的一类信源。由于模拟信源的情况比较复杂，限于学时，我们只对单变量连续信源的信息测度进行讨论。,.,29,连续信源单变量连续信源（1）,有的信源虽输出是单个符号(代码)的消息，但其可能出现的消息数是不可数的无限值，即输出消息的符号集A的取值是连续的，或取值是实数集(-，)。例如，遥控系统中有关电压、温度、压力等测得的连续数据。这些数据取值是连续的，但又是随机的。我们可用一维的连续型随机变量X来描述这些消息。这种信源称为连续信源，其数学模型是连续型的概率空间。,.,30,连续信源单变量连续信源的描述,单变量连续信源的输出是取值连续的随机变量。可用变量的概率密度、变量间的条件概率密度和联合概率密度描述。一维概率密度函数条件概率密度和联合概率密度函数,其中：,波形信源,更一般地说，实际信源输出的消息常常是时间和取值都是连续的。例如，语音信号X(t)、热噪声信号n(t)、场景图像信号X(x0,y0,t)等时间连续函数。在某一固定时间t，它们的可能取值又是连续的和随机的。对于这种信源输出的消息，可用随机过程来描述。称这类信源为随机波形信源。,.,32,波形信源,分析一般随机波形信源比较复杂和困难。常见的随机波形信源输出的消息是时间、频带受限的随机过程。,根据取样定理，可以把这样的随机过程用一系列时间(或频率)域上离散的取样值来表示，而每个取样值都是连续型随机变量。,随机过程转换成时间(或频率)上离散的随机序列。在某种条件下可以转换成随机变量间统计独立的随机序列。,平稳的随机过程可转换成平稳的随机序列。随机波形信源转换成连续平稳信源。若对每个取样值(连续型的)经过分层(量化)，就可将连续的取值转换成有限的或可数的离散值。连续信源转换成了离散信源。,波形信源（时间连续、取值连续）连续信源（时间离散、取值连续）离散信源（时间离散、取值离散）,采样,量化,.,34,实际信源,实际信源在离散情况下是消息序列信源，在连续情况下是随机过程信源，它们分别代表数字与模拟信源。,.,35,实际信源离散序列信源(1),其中，i=1,2,n为每个消息（符号）取值的种类数l=1,2,L为消息（符号）序列的长度应注意的是i和l是代表两个不同范畴的变量，表示不同的概念，切勿混淆。如：五码英文报：i=26+1，l=5,i=1,2,n,l=1,2,L,.,36,实际信源离散序列信源(2),信源输出是一组随机序列（矢量）：其样值为：对应概率为：由于每个随机变量U=1,2,n有n种取值，则有种可能取值。如：五码英文报：i=26+1，l=5，共有275种取值,.,37,实际信源离散序列信源(3),例36：最简单L=3的三位PCM信源：这时L=3,n=2,即i=0,1，则有：,实际信源连续波形信源（1）,在实际的连续波形信源中，可以采用两种方法进行分析一类是将连续波形信源转化为随机序列信源另一类是仍然采用随机过程来分析,什么样的信源可以进行离散化处理？,实际上，只要满足一个非常宽松的条件，即满足限时(T)、限频(F)的连续消息信源，即满足物理可实现条件下，均可离散化为随机序列。,.,39,实际信源连续波形信源（2）,图像信源图像信源一般可以引用一个四元的随机场来表示：（简化）主要统计特性：初步可以认为是一个近似的平稳遍历过程,.,40,实际信源连续波形信源（3）,语音信源语音信源可以近似用一个一维随机过程U(,t)表示。严格的讲，它是一个非平稳过程，但是对于短时段(5-50ms)可认为是平稳的，且某些是随机噪声（清辅音），而某些时段则呈现周期性特征（浊音），还有一些短时段是二者的混合，但是对于短时段(5-50ms)可认为是平稳的。,.,41,信源输出信号中携带信息如何度量？（以离散信源为例）,问题三,.,42,信源输出信号中携带信息的度量,单符号信源的熵离散无记忆平稳信源的熵无记忆平稳信源的N次扩展信源的熵有记忆平稳信源的熵率,离散无记忆平稳信源的N次扩展信源的熵,因为是无记忆的/统计独立若ai=(xi1xi2xi3xiN)则p(ai)=p(xi1)p(xi2)p(xiN)其中i1,i2,iN1,2,n根据信息熵的定义，N次扩展信源的熵可以证明：离散无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍，即H(X)=H(XN)=NH(X),例37,有一离散无记忆信源求这个离散无记忆信源的二次扩展信源，扩展信源的每个符号是信源X的输出长度为2的符号序列。因为信源X共有3个不同符号，所以由信源X中每两个符号组成的不同排列共有32=9种，得二次扩展信源共有9个不同的符号。因为信源X是无记忆的，则有,可以算得H(X)=1.5比特/符号（此处的符号是指X信源的输出符号xi）H(X)=H(X2)=H(A)=3比特/符号（此处的符号是指扩展信源的输出符号ai，它是由二个xi符号组成）所以H(X)=2H(X)对上述结论的解释：因为扩展信源XN的每一个输出符号ai是由N个xi所组成的序列，并且序列中前后符号是统计独立的。现已知每个信源符号xi含有的平均信息量为H(X)，那么，N个xi组成的无记忆序列平均含有的信息量就为NH(X)（根据熵的可加性）。因此信源XN每个输出符号含有的平均信息量为NH(X)。,.,46,离散无记忆平稳信源的熵,当随机变量X1和X2相互统计独立时，则因此,.,47,结论：随机变量X1和X2统计独立时，二维离散平稳无记忆信源X=X1X2的熵H(X)等于X1的熵H(X1)和X2的熵H(X2)之和。当X1和X2取值于同一集合时，H(X1)=H(X2)=H(X)，H(X)=H(X2)=2H(X)，与离散无记忆信源二次扩展信源的情况相同。可以把离散无记忆平稳信源的二次扩展信源看成是二维离散无记忆平稳信源的特例；,.,48,离散平稳有记忆信源的信源熵,N维离散平稳有记忆信源的熵H(X)=H(X1)+H(X2/X1)+H(X3/X1X2)+H(XN/X1X2XN-1)证明：（略）结论：多符号离散平稳有记忆信源X的熵H(X)是X中起始时刻随机变量X1的熵与各阶条件熵之和。由于信源是平稳的，这个和值与起始时刻无关。,离散平稳有记忆信源的条件熵的非递增性,条件熵H(XN/X1X2XN-1)随N的增加是非递增的，即H(XN/X1X2XN-1)H(XN/X1X2XN-2)证明前面已证明：H(X2/X1)H(X2)，同理可证：H(X3/X1X2)H(X3/X2)，由于信源是平稳的，所以H(X3/X2)=H(X2/X1)，故得H(X3/X1X2)H(X2/X1)H(X1)对于平稳信源递推H(XN/X1X2XN-1)H(XN-1/X1X2XN-2)H(XN-2/X1X2XN-3)H(X3/X1X2)H(X2/X1)H(X1),.,50,离散平稳有记忆信源的平均符号熵,H(X)/矢量熵=H(X1X2XN-1XN)/联合熵表示平均发一个消息（由N个符号组成）提供的信息量。平均符号熵：信源平均每发一个符号提供的信息量为,离散平稳有记忆信源的熵率（极限熵）,对于离散平稳信源，考察其输出信息量例38,P(ai,aj),P(ai/aj),当信源符号间无依赖性时：,当考虑信源符号间的一维依赖性时：,条件熵：,联合熵：,可见：,且：,考察信源符号间有依赖性时联合信源的平均符号熵：,可见：,比特/符号,比特/符号,比特/二个符号,比特/符号,分析：,结论：符号间的相关性使得信源的平均符号熵减少，即每个符号平均携带的信息量减少。,问题：H2(X)和H(X2|X1)哪一个值更能接近实际二维平稳信源的熵？即：用哪一个值来表示二维平稳信源每个符号平均携带的信息量比特/符号,考察：离散平稳有记忆信源符号之间的依赖长度为N的信源,定义：N长的信源符号序列的平均符号熵即平均每个信源符号所携带的信息量为,比特/符号,当时，存在以下性质：条件熵随N的增加是非递增的平均符号熵随N的增加是非递增的N给定时，平均符号熵=条件熵。即：存在，且：,结论：对于有限记忆长度的平稳信源可用有限记忆长度的条件熵来对平稳信源进行信息测度。,.,55,熵率,对于离散平稳信源，考察其输出信息量假设字母序列长度为N，则有限长度的序列的熵可看成随机矢量（）的熵，可用联合熵表示，平均每个字母的熵可以表示为当时，若存在，则：定义：为该平稳信源的熵率，又称平稳信源的极限熵或极限信息量对于一般的平稳信源，可以证明，极限一定存在。,结论,熵率的含义：代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。多符号离散平稳信源实际上就是原始信源在不断地发出符号，符号之间的统计关联关系也并不仅限于长度N之内，而是伸向无穷远。所以要研究实际信源，必须求出熵率H，才能确切地表达多符号离散平稳有记忆信源平均每发一个符号提供的信息量。熵率的计算：必须测定信源的无穷阶联合概率和条件概率分布，这是相当困难的。有时为了简化分析，往往用条件熵或平均符号熵作为熵率的近似值。在有些情况下，即使N值并不大，这些熵值也很接近H，例如马尔可夫信源。,.,57,问题四,信源输出信号的信息携带效率如何表示？,.,58,信源输出信号的信息携带效率的表示,冗余度与信源效率,它表征信源信息率的多余程度，是描述信源客观统计特性的一个物理量。由广义Shannon不等式有：,冗余度1,可见对于有记忆信源，最小单个消息熵应为，即从理论上看，对有记忆信源只需传送即可。,但是这必需要掌握信源全部概率统计特性。这显然是不现实的。实际上，往往只能掌握有限的维，这时需传送，那么与理论值相比，就多传送了。,冗余度2,为了定量描述信源有效性，可定义：信源效率：信源冗余度：（相对剩余）或者定义：冗余度：信源效率：相对冗余度：,.,61,冗余度3,正由于信源存在着冗余度，即存在着不必要传送的信息，因此信源也就存在进一步压缩信息率的可能性。冗余度越大，压缩潜力也就越大。可见它是信源编码、数据压缩的前提与理论基础。,冗余度4,例39：计算英文文字信源的冗余度）首先给出英文字母（含空格）出现概率如下：,冗余度5,首先求得独立等概率情况H0，即,其次，计算独立不等概率情况H1，,再次，若仅考虑字母有一维相关性，求H2，,最后实际熵H，利用统计推断方法求出。由于采用的逼近的方法和所取的样本的不同，推算值也有不同，这里采用Shannon的推断值。,.,64,冗余度6,这一结论说明，英文信源，从理论上看71是多余成分。直观地说100页英文书，理论上看仅有29页是有效的，其余71页是多余的。正是由于这一多余量的存在，才有可能对英文信源进行压缩编码。,冗余度7,对于其它文字，也有不少人作了大量的统计工作，简述如下：英文法文德文西班牙文中文（按8千汉字计算）,.,66,问题五,如何有效表示信源输出信号？