信息论与编码.ppt_第1页
信息论与编码.ppt_第2页
信息论与编码.ppt_第3页
信息论与编码.ppt_第4页
信息论与编码.ppt_第5页
已阅读5页,还剩31页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第2章 信源与信息熵,2.1 信源的描述与分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信息 2.5 冗余度,2.1.1 信源的分类,按照信源的特性对信源进行分类: 根据信源发出的消息在时间上和幅度上是否连续 连续信源:发出的消息在时间上和幅度上都是连续分布 离散信源:发出的消息在时间上和幅度上都是离散分布 根据信源发出的符号之间的相关性 无记忆信源:信源符号之间不相关 有记忆信源:信源符号之间具有某种相关性,2.1.1 信源的分类,离散信源又可进一步细分为: 单符号离散信源:信源发出的每个符号都代表一个消息 符号序列离散信源:信源发出的消息由一组含二个以

2、上 符号构成的序列表示 离散无记忆信源 离散有记忆信源(马尔可夫信源:某一个符号出 现的概率只与前面一个或有限个符号有关,而不 依赖更前面的那些符号) 也可以对连续信源进行以上细分,2.1.2 信源的描述 信源的统计特性和数学模型,在信息论中,信源产生消息符号、消息序列和连续消息,由于消息的不确定性,从数学上看,信源可以用随机变量、随机序列和随机过程表示。 消息符号随机变量(袋中摸球、掷骰子、十进制数字、字母等;干电池的电压,语音信号,图像信号等) 消息序列随机序列 连续消息随机过程,2.1.2 信源的描述,1. 消息符号(举例) 单符号离散信源:用一维离散随机变量X表示,它 对应的概率空间为

3、: 式(2-1-1) 单符号连续信源:用一维连续随机变量X表示,它 对应的概率空间为: 式(2-1-2),2.1.2 信源的描述,用概率空间表示单符号离散信源时涉及的概念: 样本空间:X的符号集合A=a1,a2,an称作随机变量X 的样本空间,XA 先验概率:X的概率分布P(X=a1), P(X=a2), , P(X=an) 分别记作p(a1), p(a2 ) , ,p(an), 这就是各符 号出现的先验概率,它满足完备性:,2.1.2 信源的描述,用概率空间表示单符号连续信源所涉及的概念: 信源输出的消息也是单个符号,但消息的数量是无 限的,即随机变量X的取值是无限的: pX(x)为符号分布

4、的概率密度函数,且满足 将幅度连续的连续信源进行量化可以转换为 离散信源,2.1.2 信源的描述,2. 消息序列:信源输出的消息由一系列符号组成 消息序列用随机序列(随机矢量多维随机变量)X表示,X= (X1, X2, XL),L是消息序列的长度,XiAi,Ai =ai1, ai2, , ain 信源特性用联合概率分布表示 以L=2,A1= A2 =a1, a2 , an为例,信源X= (X1, X2)的概率空间为: 式(2-1-3),2.1.2 信源的描述,(1) 离散无记忆消息序列(摸球放回去模型) 信源发出的符号序列中各符号之间相互独立,各符号出现的概率是其自身的先验概率,即p(X1,

5、X2, XL)= p(X1) p(X2) p(XL); 如果离散无记忆信源发出的序列为平稳随机序列(序列的统计特性即随机矢量的任意维概率分布与时间起点无关),则每个变量的一维概率分布相同,即p(X1)= p(X2) =p(XL),且取值于同一概率空间(2-1-1),则 上述信源又称为为离散无记忆信源X的L次扩展信源。若XlA有n种可能的取值,则长度为L的随机序列X有nL种可能的取值。L次扩展信源也满足完备性。,2.1.2 信源的描述,一般情况下,信源发出的符号之间是互相依赖、互相关联的,这种信源即有记忆信源。例如: 中文字母组成的中文消息 英文字母组成的英文消息 采样后的话音序列,2.1.2

6、信源的描述,(2) 有记忆信源(摸球不放回去模型) 时间离散的有记忆信源用随机序列表示 幅度离散的有记忆符号序列条件概率 幅度连续的有记忆符号序列条件概率密度函数 时间连续的有记忆信源用随机过程表示 将连续信源离散化为随机序列信源 直接分析连续模拟信源(由于数学上的困难,目前只能分析单个连续消息变量的信源),2.1.2 信源的描述,离散有记忆随机序列信源的描述方法条件概率 条件概率能够反映信源发出的符号序列各个符号 之间的记忆特性(相关特性),2.1.2 信源的描述,实际上信源发出的符号往往只与前面几个符号的依赖关系较强,而与更前面的符号依赖关系较弱。 为此可以限制随机序列的记忆长度。 当记忆

7、长度为m+1时,称这种有记忆信源为m阶马尔可夫(Markov)信源。也就是说信源所发出的符号只与前m个符号有关,与更前面的符号无关。,2.1.2 信源的描述,描述符号之间依赖关系的条件概率为 m阶马尔可夫信源的联合概率密度可表示为: 如果条件概率与时间起点i无关,即信源输出的消息可看成为齐次(时齐)马尔可夫链,则此信源称为齐次马尔可夫信源。,2.1.2 信源的描述,一种最简单的马尔可夫信源是m=1的信源:,2.1.2 信源的描述,高阶马尔可夫过程分析: 采用矢量进行分析,过程复杂 将矢量转化为状态变量,分析系统在输入符号下的转移情况,转化成一阶马尔可夫过程分析,2.1.2 信源的描述,与高阶马

8、尔可夫过程(m阶)相关的概念: 符号集: A=a1,a2,an 状态si :当前时刻出现以前出现的m个符号组成的序列, 状态集S:状态si 的集合,共有Q=nm种组合 S=s1,s2,sQ 符号条件概率p(xj|si):表示信源在某一时刻出现符号xj的 概率与信源所处的状态si有关 状态转移概率p(sj|si):当信源符号xj出现后,信源由状 态si转移到状态sj的概率,2.1.2 信源的描述,状态转移概率pij(m,n):系统在时刻m系统处于状态si(i) 的条件下,转移到在时刻n系统处于状态sj(j)的条件概率 其性质如下: 特别地,关心n-m=1的情况,即pij(m,m+1),记为pij

9、(m), 称为一步转移概率(基本转移概率),即,2.1.2 信源的描述,对于齐次马尔可夫链,其转移概率具有时移不变性,即 只与状态有关,与时刻m无关,状态转移概率可表示为: 显然pij具有如下性质: k步转移概率:,2.1.2 信源的描述,转移概率矩阵: 。特别地,对于齐次 马氏链一步转移概率矩阵: 或: 行元素之和为1 列元素之和不一定为1 且普曼-柯尔莫郭洛方程: 特别地,当l=1时,,2.1.2 信源的描述,若用矩阵表示,有: 结论:对于齐次马尔可夫链,一步转移概率(矩阵)完 全决定了k步转移概率(矩阵) 初始概率: 无条件概率: 二者关系:,2.1.2 信源的描述,稳定马尔可夫链: 若

10、 存在,且等于与初始状态i无关的稳态分布 ,即 ,此马尔可夫最后达 到稳定,其所有变量Xk的概率分布不变。 怎样求Wj? (2-1-7) 可见(2-1-7)式有非零解,且满足,2.1.2 信源的描述,例1:设一个二元二阶马尔可夫信源,信源符号集 为X =0,1,输出符号的条件概率为: 求该信源的状态转移图、状态转移矩阵及稳态分 布概率。,2.1.2 信源的描述,状态转移图: 状态转移矩阵:,2.1.2 信源的描述,稳态分布概率满足: 0.8W1+0.5W3=W1 0.2W1+0.5W3=W2 0.5W2+0.2W4=W3 0.5W2+0.8W4=W4 W1+W2+W3+W4=1 求解方程组求得

11、: W1=5/14, W2=5/14, W3=2/14, W4=2/14,2.1.2 信源的描述,遍历马尔可夫链: 不可约性: 对任一对i和j,至少存在一个k,使 ,即从si开 始,总有可能到达sj;反之,对所有k, ,即一 旦出现si以后就不可能到达sj,即状态具有可约性 非周期性:即所有 的n中没有比1大的公因子,2.1.2 信源的描述,例2:判断下列马尔可夫链的周期性: 因为从s1出发再回到s1所需的步数为2,4,6,故 其转移矩阵的周期为2。,2.1.2 信源的描述,这里,转移矩阵为: 可以验证,当k为奇数时,2.1.2 信源的描述,当k为偶数时, 若初始状态为s1,经奇数步后,Sk=

12、sj的概率为: 而经偶数步后, 这样就达不到稳定状态,但(2-1-7)有解(必要条件), Wj=1/4,2.1.2 信源的描述,遍历的直观意义:不论信源从哪一状态si出发,当转移步数k足够大时,转移到状态sj的概率pij(k)都近似为某个常数Wj。即马尔可夫信源在初始时刻可以处在任意状态,而信源之间可以进行状态转移,经过足够长时间之后,信源达到一种稳定分布(与初始状态无关)。,2.1.2 信源的描述,例2-1(p-14):下图所示是一相对编码器,输入的码Xr, r=1,2,相互独立,取值为0或1,且已知P(X=0)=p, P(X=1)=1-p=q,输出的码是Yr,判断Yr是不是一马尔可 夫链;若是,判断它是不是遍历的,并求稳态分布概率。,例2-2:有一个二元二阶马尔可夫信源,其信源符号集为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(

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论