信息论第二章优秀PPT.ppt

《信息论第二章优秀PPT.ppt》由会员分享，可在线阅读，更多相关《信息论第二章优秀PPT.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论第二章信息论第二章第1页，本讲稿共46页2数字通信系统模型数字通信系统模型信道信源信源编码加密信道编码干扰源信宿信源解码解密信道解码加密密钥解密密钥uxykzvzyx第2页，本讲稿共46页32.1 2.1 信源的描述和分类信源的描述和分类2.2 2.2 离散信源熵和互信息离散信源熵和互信息2.3 2.3 离散序列信源的熵离散序列信源的熵2.4 2.4 连续信源的熵和互信息连续信源的熵和互信息2.5 2.5 冗余度冗余度内容内容第3页，本讲稿共46页4重难点重难点本章重点 信源的统计特性和数学模型、离散信源熵及其性质、互信息本章难点本章难点 马尔科夫信源、离散序列有记忆信源的熵2.1 2.

2、1 信源的描述和分类信源的描述和分类2.2 2.2 离散信源熵和互信息离散信源熵和互信息2.3 2.3 离散序列信源的熵离散序列信源的熵2.4 2.4 连续信源的熵和互信息连续信源的熵和互信息2.5 2.5 冗余度冗余度第4页，本讲稿共46页52.1 2.1 信源的描述和分类信源的描述和分类第5页，本讲稿共46页内容内容2.1.1 无记忆信源2.1.2 有记忆信源2.1.3 马尔科夫信源6第6页，本讲稿共46页7信源信源信源产生消息(符号)、消息序列和连续消息的来源产生随机变量、随机序列和随机过程的源。在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用随机变量、

3、随机序列或随机过程来描述信源输出的消息,或者说用一个样本空间及其概率测度概率空间来描述信源信源的基本特性：具有随机不确定性。第7页，本讲稿共46页8香农信息论的基本点香农信息论的基本点用随机变量或随机矢量来表示信源用概率论和随机过程的理论来研究信息第8页，本讲稿共46页9一、信源分一、信源分类类 2、离散信源：文字、数字、数据等符号离散无记忆信源离散有记忆信源发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源1、连续信源：语音、图像、图形从信源发出的消息在时间上和幅度上的分布第9页，本讲稿共46页10根据人们对信源消息的感知 分为数据信源、文本信

4、源、语音信源、图像信源等，其中文本信源和语音信源都是针对人类语言、文字、声乐等感知的，又通称为自然语信源。从描述信源消息的随机过程的平稳性角度 分为平稳信源和非平稳信源第10页，本讲稿共46页11信源的分类方法可以有多种，但本质上主要基于两方面的考虑：一是信源消息取值的集合以及消息取值时刻的集合，由此可分为离散信源、连续信源等；二是信源消息的统计特性，由此可分为无记忆（Memoryless）信源、有记忆（Memory）源、平稳信源、非平稳信源、高斯信源、马尔可夫信源等。第11页，本讲稿共46页122.1.1 2.1.1 无无记忆信源记忆信源一、发出单个符号的无记忆离散信源：发出的消息是离散的，

5、且一个符号代表一条完整的消息。消息数为有限或无限可列。用一维离散变量X来描述。例如扔骰子，每次试验结果必然是16点中的某一个面朝上。用一个离散型随机变量X来描述这个信源输出的消息。第12页，本讲稿共46页13在实际情况中，存在着很多这样的信源、例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。这些信源输出的都是单个符号（或代码）的消息，它们符号集的取值是有限的或可数的。第13页，本讲稿共46页14信源的描述信源的描述一个离散信源发出的各个符号消息的集合为：它们的概率分别为p(xi):xi的先验概率先验概率单符号离散信源的数学模型概率空间a,b,c,z第14页，本讲稿共46页15二

6、、发出单个符号的连续无记忆信源：输出是的单个符号的消息，消息的数量是无限的。可用一维连续型随机变量X描述 单符号连续无记忆信源的概率空间消息的集合 随机取一节干电池测其电压值作为输出符号,符号取值为0,1.5之间的所有实数。该信源就是发出单符号的连续无记忆信源第15页，本讲稿共46页16上述的离散信源和连续信源是最简单最基本的情况，信源输出只输出一个消息符号，所以可以用随机变量来描述。信源的描述信源的描述第16页，本讲稿共46页17三、发出符号序列的信源：输出的消息由符号序列组成，用随机矢量X=(X1X2XlXL)描述。需要用联合概率分布表示信源特性。L=2，X=(X1,X2)，其信源的概率空

7、间为第17页，本讲稿共46页18信源的描述信源的描述随机序列的概率联合概率当信源无记忆时，即 Xl(l=1,L)之间是无依赖的、统计独立的，则随机矢量的联合概率分布满足：第18页，本讲稿共46页19离散信源X(n个信源符号个信源符号)的每次输出L长符号序列消息x=(x1xlxL)x 共有共有 nL=nnn（共L个）种组合，即每个随机变量取值有n种，那么L个随机变量组成的随机序列，其样值共有nL种可能取值。有时将这种由信源X输出的L长随机序列X所描述的信源叫做离散信源X的L次扩展信源。L次扩展信源次扩展信源第19页，本讲稿共46页20一般情况下,信源在不同时刻发出的符号之间是相互依赖的，也就是信

8、源输出的平稳随机序列X中，各随机变量Xl之间是有依赖的。如在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。2.1.22.1.2 有记忆信源有记忆信源第20页，本讲稿共46页21离散有记忆序列信源：当信源输出的随机矢量中离散有记忆序列信源：当信源输出的随机矢量中各个分量各个分量之间不相互独立之间不相互独立而可以是任意相关的而可以是任意相关的,则称此类信源为则称此类信源为有记忆信源。有记忆信源。布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若每次先取出一个球，记下颜色不放回布袋，再取第二个球。第21页，本讲稿共46页22表述有记忆信源要比表述无记忆信源困难得多需

9、在N维随机矢量的联合概率分布中，引入条件概率分布来说明它们之间的关联。第22页，本讲稿共46页232.1.3 2.1.3 马尔可夫信源马尔可夫信源马尔可夫信源一类相对简单的离散平稳有记忆信源该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关m阶马尔可夫信源：信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。条件概率一阶马尔可夫信源：第23页，本讲稿共46页24马氏链的状态变量马氏链的状态变量 若把前面有限个字母记作一个状态S，则信源某一时刻发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。信源将来的状态及其送出的字母将只与信源现在的状

10、态有关，而与信源过去的状态无关。引入状态变量的好处：使得高阶马尔科夫过程可以转化为一阶马尔科夫过程处理。假设m阶马尔可夫信源的一个状态含有m个字母第24页，本讲稿共46页25马氏链的基本概念马氏链的基本概念 令si=(xi1,xi2,xim)xi1,xi2,xim a1,a2,an状态集S=s1,s2,sQ Q=nm（状态数目）信源输出的随机符号序列为：x1,x2,xi-1,xi 信源所处的随机状态序列为：s1,s2,si-1,si 例：二元序列为01011100 考虑m=2，Q=nm=22=4 s1=00 s2=01 s3=10 s4=11 变换成对应的状态序列为 s2 s3 s2 s4 s

11、4 s3 s10 1 0 1 1 1 0 0第25页，本讲稿共46页26转移概率转移概率设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为：pij(m)=pSm+1=sj|Sm=si=psj|sipij(m)：基本转移概率（一步转移概率）齐次马尔可夫链：pij(m)与m 的取值无关,则 pij=pSm+1=sj|Sm=si=pS2=sj|S1=sipij具有下列性质：pij0第26页，本讲稿共46页27若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。系统在任一时刻可处于状态空间S=s1,s2,sQ

12、中的任意一个状态,状态转移时,转移概率矩阵符号条件概率矩阵区区区区别别别别第27页，本讲稿共46页28例2-1，如图所示是一个相对码编码器,输入的码Xr(r=1,2,)是相互独立的，取值0或1，且已知P(X=0)=p,P(X=1)=1p=q，输出的码是Yr。TXrYrYr-1+Yr是一个二元一阶马氏链,Yr确定后,Yr+1概率分布只与Yr有关,与Yr-1、Yr-2 等无关。注：注：注：注：模模模模2 2加加加加第28页，本讲稿共46页29sos1pqqpp00=P(Y2=0/Y1=0)=P(X=0)=p 状态转移矩阵与状态转移矩阵与状态转移矩阵与状态转移矩阵与时刻无关，所以时刻无关，所以时刻无

13、关，所以时刻无关，所以是齐次的。是齐次的。是齐次的。是齐次的。Yr的状态转移概率：p01=P(Y2=1/Y1=0)=P(X=1)=q p10=P(Y2=0/Y1=1)=P(X=1)=q p11=P(Y2=1/Y1=1)=P(X=0)=p 第29页，本讲稿共46页30马尔可夫信源马尔可夫信源状态转移图齐次马尔可夫链可以用其状态转移图(香农线图)表示每个圆圈代表一种状态 状态之间的有向线代表某一状态向另一状态的转移有向线一侧的符号和数字分别代表发出的符号和条件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.7第30页，本讲稿共46页例2 设一个二元一阶马尔科夫信源，信源符

14、号集X=0,1，信源输出符号的条件概率为 p(0|0)=0.25,p(0|1)=0.5,p(1|0)=0.75,p(1|1)=0.5 求状态转移概率，画出状态转移图。解：311/0.750/0.51/0.5第31页，本讲稿共46页例3 设有一个二元二阶马尔科夫信源，其信源符号集X=0,1.状态变化如下：在状态为01时，若出现0，将零附到01后将第一位0挤出，状态变为10.其他状态变化过程类似。信源输出符号的条件概率为 P(0|00)=p(1|11)=0.8,p(1|00)=p(0|11)=0.2，p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5 求状态转移概率矩阵，画出状

15、态转移图解：32第32页，本讲稿共46页3301010/0.80/0.51/0.20/0.51/0.51/0.50/0.21/0.8第33页，本讲稿共46页34 齐次马尔可夫链中的状态可以根据其性质进行分类:1、如状态si经若干步后总能到达状态sj，即存在k,使pij(k)0，则称si可到达sj;若两个状态相互可到达,则称此二状态相通；2、过渡态：一个状态经过若干步以后总能到达某一其他状态，但不能从其他状态返回；3、吸收态：不能到达其他任何状态的状态；4、常返态：经有限步后迟早要返回的状态；5、周期性的：在常返态中，状态中仅当k能被某整数d1整除时才有pii(k)0；6、非周期性的：对于pii

16、(k)0的所有k值，其最大公约数为1。第34页，本讲稿共46页35s3s2s4s5s1s6周期性的：在常返态中,状态中仅当k能被某整数d1整除时才有pii(k)0,图中的周期为2；x5:1非周期性的：对于pii(k)0的所有k值，其最大公约数为1。常返态：经有限步后迟早要返回的状态，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4过渡态过渡态吸收态吸收态相通相通第35页，本讲稿共46页36马尔可夫信源马尔可夫信源遍历状态：非周期的常返状态,如图中的状态s2和s3闭集：状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态不

17、可约的：闭集中除自身全体外再没有其他闭集特殊结论第36页，本讲稿共46页37马尔可夫信源马尔可夫信源一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k时趋于一个和初始状态无关的极限概率Wj，它是满足方程组 的唯一解；Wj：马尔可夫链的一个平稳分布，Wj 或或p(sj)就是系统此时处于状态sj的概率。无论随机点从哪一个无论随机点从哪一个状态状态si出发，当转移出发，当转移的步数的步数k足够大时，足够大时，转移到状态转移到状态sj的概率的概率pij(k)都近似于一个常都近似于一个常数数Wj第37页，本讲稿共46页38sos11/0.60/0.30/0.4s21/0.20/0

18、.81/0.7例4：求马尔科夫链的稳态分布律第38页，本讲稿共46页39例5：有一个二元二阶马尔可夫信源,其信源符号集为0，1，已知符号条件概率：p(0|00)=1/2 p(1|00)=1/2 p(0|01)=1/3 p(1|01)=2/3 p(0|10)=1/4 p(1|10)=3/4 p(0|11)=1/5 p(1|11)=4/5求：信源全部状态及状态转移概率画出完整的二阶马尔可夫信源状态转移图。求稳定后的状态分布概率以及符号分布概率 第39页，本讲稿共46页40状态转移概率矩阵符号条件概率矩阵(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0

19、)1/4(0)1/5(1)4/5第40页，本讲稿共46页41稳态分布概率稳态后的符号概率分布第41页，本讲稿共46页44练习练习2-12-2第44页，本讲稿共46页45马尔可夫链马尔可夫链马尔可夫链，因安德烈马尔可夫（A.A.Markov，18561922）得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。马尔可夫链是随机变量X_1,X_2,X_3.的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而X_n的值则是在时间n的状态。如果X_n+1对于过去状态的

20、条件概率分布仅是X_n的一个函数，则P(X_n+1=x|X_0,X_1,X_2,ldots,X_n)=P(X_n+1=x|X_n).这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。第45页，本讲稿共46页46 马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）。马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。马尔可夫链最近的应用是在地理统计学（geostatistics）中。其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟。这一应用类似于“克里金”地理统计学（Kriging geostatistics），被称为是“马尔可夫链地理统计学”。这一马尔可夫链地理统计学方法仍在发展过程中。第46页，本讲稿共46页