信息论第二章节课件1章节

1、1,信源与信息熵,第二章,2,数字通信系统模型,加密密钥,解密密钥,u,x,y,k,z,v,z,y,x,3,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信息 2.5 冗余度,内容,4,重难点,本章重点 信源的统计特性和数学模型、离散信源熵及其性质、互信息,本章难点 马尔科夫信源、离散序列有记忆信源的熵,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信息 2.5 冗余度,5,2.1 信源的描述和分类,内容,2.1.1 无记忆信源 2.1.2 有记忆信源 2.1.3 马尔科夫信源,6,7,信源,信源 产生消息(符号)、消息序列和连续消息的来源 产生随机变量、随机序列和随机过程的源。 在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用随机变量、随机序列或随机过程来描述信源输出的消息,或者说用一个样本空间及其概率测度概率空间来描述信源 信源的基本特性：具有随机不确定性。,8,香农信息论的基本点,用随机变量或随机矢量来表示信源 用概率论和随机过程的

2、理论来研究信息,9,一、信源分类,2、离散信源：文字、数字、数据等符号,离散无记忆信源,离散有记忆信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,1、连续信源：语音、图像、图形,从信源发出的消息在时间上和幅度上的分布,10,根据人们对信源消息的感知 分为数据信源、文本信源、语音信源、图像信源等，其中文本信源和语音信源都是针对人类语言、文字、声乐等感知的，又通称为自然语信源。 从描述信源消息的随机过程的平稳性角度 分为平稳信源和非平稳信源,11,信源的分类方法可以有多种，但本质上主要基于两方面的考虑： 一是信源消息取值的集合以及消息取值时刻的集合，由此可分为离散信源、连续信源等； 二是信源消息的统计特性，由此可分为无记忆（Memoryless）信源、有记忆（Memory）源、平稳信源、非平稳信源、高斯信源、马尔可夫信源等。,12,2.1.1 无记忆信源,一、发出单个符号的无记忆离散信源： 发出的消息是离散的，且一个符号代表一条完整的消息。消息数为有限或无限可列。用一维离散变量X来描述。,例如扔骰子，每次试验结果必然是16点中

3、的某一个面朝上。,用一个离散型随机变量X来描述这个信源输出的消息。,13,在实际情况中，存在着很多这样的信源、例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。这些信源输出的都是单个符号（或代码）的消息，它们符号集的取值是有限的或可数的。,14,信源的描述,一个离散信源发出的各个符号消息的集合为：,它们的概率分别为,p(xi): xi的先验概率,单符号离散信源的数学模型概率空间,a,b,c,z,15,二、发出单个符号的连续无记忆信源： 输出是的单个符号的消息，消息的数量是无限的。可用一维连续型随机变量X描述,单符号连续无记忆信源的概率空间,消息的集合,随机取一节干电池测其电压值作为输出符号,符号取值为0,1.5之间的所有实数。 该信源就是发出单符号的连续无记忆信源,16,上述的离散信源和连续信源是最简单最基本的情况，信源输出只输出一个消息符号，所以可以用随机变量来描述。,信源的描述,17,三、发出符号序列的信源： 输出的消息由符号序列组成，用随机矢量X =(X1X2XlXL)描述。需要用联合概率分布表示信源特性。 L=2，X=(X1,X2)， 其信源的概率空间为,18,信

4、源的描述,随机序列的概率联合概率,当信源无记忆时 ，即 Xl(l=1,L)之间是无依赖的、统计独立的，则随机矢量的联合概率分布满足：,19,离散信源X(n个信源符号)的每次输出L长符号序列消息 x = (x1xlxL) x 共有 nL= nnn（共L个）种组合，即每个随机变量取值有n种，那么L个随机变量组成的随机序列，其样值共有nL种可能取值。 有时将这种由信源X输出的L长随机序列X所描述的信源叫做离散信源X的L次扩展信源。,L次扩展信源,20,一般情况下,信源在不同时刻发出的符号之间是相互依赖的，也就是信源输出的平稳随机序列X中，各随机变量Xl之间是有依赖的。 如在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。,2.1.2 有记忆信源,21,离散有记忆序列信源：当信源输出的随机矢量中各个分量之间不相互独立而可以是任意相关的,则称此类信源为有记忆信源。 布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。 若每次先取出一个球，记下颜色不放回布袋，再取第二个球。,22,表述有记忆信源要比表述无记忆信源困难得多 需在N维随机矢量的联合概率分布中，引入条件概率分

5、布来说明它们之间的关联。,23,2.1.3 马尔可夫信源,马尔可夫信源 一类相对简单的离散平稳有记忆信源 该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关 m阶马尔可夫信源： 信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。 条件概率,一阶马尔可夫信源：,24,马氏链的状态变量,若把前面有限个字母记作一个状态S，则信源某一时刻发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。 信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。 引入状态变量的好处：使得高阶马尔科夫过程可以转化为一阶马尔科夫过程处理。 假设m阶马尔可夫信源的一个状态含有m个字母,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 =2

6、2= 4 s1 = 00 s2 = 01 s3 = 10 s4 = 11 变换成对应的状态序列为 s2 s3 s2 s4 s4 s3 s1,0 1 0 1 1 1 0 0,26,转移概率,设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为： pij(m) = pSm+1=sj| Sm= si=psj | si pij(m)：基本转移概率（一步转移概率） 齐次马尔可夫链：pij(m)与m 的取值无关,则 pij= pSm+1=sj| Sm= si= pS2=sj| S1= si pij具有下列性质： pij0,27,若信源处于某一状态si ,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。 系统在任一时刻可处于状态空间S = s1,s2,sQ中的任意一个状态,状态转移时,转移概率矩阵,符号条件概率矩阵,区别,28,例2-1，如图所示是一个相对码编码器,输入的码Xr(r=1,2,)是相互独立的，取值0或1，且已知P(X=0)=p, P(X=1)=1p=q，输出的码是Yr。,Yr是一个二元一阶马氏链,Yr确定后,Yr+

7、1概率分布只与Yr有关,与Yr-1 、Yr-2 等无关。,注： 模2加,29,so,s1,p,q,q,p,p00= P(Y2=0/Y1=0)= P(X=0)= p,状态转移矩阵与时刻无关，所以是齐次的。,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,30,马尔可夫信源,状态转移图 齐次马尔可夫链可以用其状态转移图(香农线图)表示 每个圆圈代表一种状态 状态之间的有向线代表某一状态向另一状态的转移 有向线一侧的符号和数字分别代表发出的符号和条件概率,so,s1,1/0.6,0/0.3,0/0.4,s2,1/0.2,0/0.8,1/0.7,例2 设一个二元一阶马尔科夫信源，信源符号集X=0,1，信源输出符号的条件概率为 p(0|0)=0.25, p(0|1)=0.5, p(1|0)=0.75, p(1|1)=0.5 求状态转移概率，画出状态转移图。 解：,31,0,1,1/0.75,0/0.5,0/0.25,1/0.5,例3 设有一个二元二阶

8、马尔科夫信源，其信源符号集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 求状态转移概率矩阵，画出状态转移图 解：,32,33,00,01,10,11,0/0.8,0/0.5,1/0.2,0/0.5,1/0.5,1/0.5,0/0.2,1/0.8,34,齐次马尔可夫链中的状态可以根据其性质进行分类: 1、如状态si经若干步后总能到达状态sj，即存在k,使pij(k)0，则称si可到达sj; 若两个状态相互可到达,则称此二状态相通； 2、过渡态：一个状态经过若干步以后总能到达某一其他状态，但不能从其他状态返回； 3、吸收态：不能到达其他任何状态的状态； 4、常返态：经有限步后迟早要返回的状态； 5、周期性的：在常返态中，状态中仅当k能被某整数d1整除时才有pii(k)0； 6、非周期性的：对于pii(k)0的所有k值，其最大公约数为1。,

9、35,s3,s2,s4,s5,s1,s6,周期性的：在常返态中, 状态中仅当k能被某整数d1整除时才有pii(k)0,图中的周期为2；,x5:1,非周期性的：对于pii(k)0的所有k值，其最大公约数为1。,常返态：经有限步后迟早要返回的状态，,x4:1,x3:1/2,x2:1/2,x3:1/2,x2:1/2,x2:1/2,x4:1/4,x1:1/4,x6:1,x6:1/4,过渡态,吸收态,相通,36,马尔可夫信源,遍历状态： 非周期的常返状态,如图中的状态s2和s3 闭集： 状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态 不可约的： 闭集中除自身全体外再没有其他闭集,特殊结论,37,马尔可夫信源,一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k时趋于一个和初始状态无关的极限概率Wj，它是满足方程组 的唯一解； Wj ：马尔可夫链的一个平稳分布， Wj 或p(sj)就是系统此时处于状态sj的概率。,无论随机点从哪一个状态si出发，当转移的步数k足够大时，转移到状态sj的概率pij(k)都近似于一个常数Wj,38,so,s1,1/0.6,0/0.3,0/0.4,s2,1/0.2,0/0.8,1/0.7,例4：求马尔科夫链的稳态分布律,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 求： 信源全部状态及状态转移概率 画出完整的二阶马尔可夫信源状态转移图。 求稳定后的状态分布概率以及符号分布概率,40,状态转移概率矩阵,符号条件概率矩阵,(1)1/2,(0)1/2,41,稳态分布概率,稳态后的符号概率分布,42,例6 一个二元二阶马尔可夫信源,其信源符号集为0,1信源开始时：p(0) = p(1) = 0.5发出随机

《信息论第二章节课件1章节》由会员E****分享，可在线阅读，更多相关《信息论第二章节课件1章节》请在金锄头文库上搜索。