第二章 离散信源及其信息测度 2.1 信源的数学模型及分类 2.2 离散信源的信息熵 2.3 信息熵的基本性质 2.4 离散无记忆的扩展信源

Presentation on theme: "第二章 离散信源及其信息测度 2.1 信源的数学模型及分类 2.2 离散信源的信息熵 2.3 信息熵的基本性质 2.4 离散无记忆的扩展信源"— Presentation transcript:

1 第二章 离散信源及其信息测度 2.1 信源的数学模型及分类 2.2 离散信源的信息熵 2.3 信息熵的基本性质 2.4 离散无记忆的扩展信源
2.5 离散平稳信源 2.6 马尔可夫信源 2.7 信源剩余度与自然语言的熵

2 2.1 信源的数学模型及分类 在通信系统中，收信者在未收到信息以前，对信源发出什么样的消息是不确定的，是随机的，所以可以用随机变量、随机矢量或随机过程来描述信源输出的消息，或者说用一个样本空间及其概率测度来描述信源。 不同的信源根据其输出消息的不同的随机性质进行分类。

3 2.1 信源的数学模型及分类 1、离散信源 数学模型如下： 集合X中，包含该信源包含的所有可能输出的消息，集合P中包含对应消息的概率密度，各个消息的输出概率总和应该为1。 例：天气预报

4 2.1 信源的数学模型及分类 2、连续信源 数学，模型如下： 每次只输出一个消息，但消息的可能数目是无穷多个。 例：电压、温度等。

5 2.2 离散信源的信息熵 内容提要： 根据香农对于信息的定义，信息是一个系统不确定性的度量，尤其在通信系统中，研究的是信息的处理、传输和存储，所以对于信息的定量计算是非常重要的。本章主要从通信系统模型入手，研究离散情况下各种信息的描述方法及定量计算，讨论它们的性质和相互关系。

6 2.2 离散信源的信息熵 自信息量和互信息量 一个事件的自信息量就是对其不确定性的度量。 互信息量则表明了两个随机事件的相互约束程度。

7 2.2 离散信源的信息熵 对于随机事件集X = {x1，x2，…，xi，…，xI}中的随机事件xi，其出现概率记为q(xi)，将两个事件xi ,yj同时出现的概率记为p(xi yj)，则q(xi) ，p(xi yj)应满足： 相应的条件概率为

8 收到某消息获得的信息量 = 不确定性减少的量
2.2 离散信源的信息熵 自信息量和条件自信息量 信息量直观的定义为： 收到某消息获得的信息量 = 不确定性减少的量 将某事件发生所得到的信息量记为I(x)，I(x)应该是该 事件发生的概率的函数，即 I(x)=f[q(x)]

9 直观地看，自信息量的定义应满足以下四点：
2.2 离散信源的信息熵 自信息量 直观地看，自信息量的定义应满足以下四点： a. I(x)应该是q(x)的单调递减函数：概率小的事件一旦发生赋予的信息量大，概率大的事件如果发生则赋予的信息量小； b.信息量应具有可加性：对于两个独立事件，其信息量应等于各事件自信息量之和；

10 c.当q(x)=1时，I(x)= 0：表示确定事件发生得不到任何信息；
2.2 离散信源的信息熵 c.当q(x)=1时，I(x)= 0：表示确定事件发生得不到任何信息； d.当q(x)=0时，I(x)→∞：表示不可能事件一旦发生，信息量将无穷大。

11 自信息量的单位与log函数所选用的对数底数有关， 如底数分别取 2、 e、 10， 则自信息量单位分别为：比特、奈特、哈特
2.2 离散信源的信息熵 综合上述条件，将自信息量定义为: (2-1) 自信息量的单位与log函数所选用的对数底数有关， 如底数分别取 2、 e、 10， 则自信息量单位分别为：比特、奈特、哈特

12 2.2 离散信源的信息熵 【例2.2.1】若盒中有6个电阻，阻值为1Ω、2Ω、3Ω的分别为2个、1个、3个，将从盒子中取出阻值为iΩ的电阻记为事件 （i = 1，2，3），则事件集X = {x1, x2, x3}，其概率分布 计算出各事件的自信息量列表2-1如下：

13 x1 x2 x3 1/3 1/6 1/2 log 3 log 6 log 2 消息xi 2.2 离散信源的信息熵 概率分布q (xi)
自信息量I (xi) log 3 log 6 log 2

14 2.2 离散信源的信息熵 例2.2.2：设天气预报有两种消息，晴天和雨天，出现的概率分别为1/4和3/4，我们分别用 来表示晴天，以 来表示雨天，则我们的信源模型如下：

15 1.事件xi发生以前，表示事件发生的先验不确定性
2.2 离散信源的信息熵 自信息量I(xi)代表两种含义： 1.事件xi发生以前，表示事件发生的先验不确定性 2.当事件xi发生以后，表示事件xi所能提供的最大信息量（在无噪情况下）

16 二维联合集X Y上元素xi yj的联合自信息量I(xi yj)定义为：
2.条件自信息量 在已知事件yj条件下,随机事件xi发生的概率为条件概率φ(xi︱yj),条件自信息量 I(xi︱yj)定义为：

17 【例2.2.3】某住宅区共建有若干栋商品房，每栋有5个单元，每个单元住有12户，甲要到该住宅区找他的朋友乙，若：
1.  甲只知道乙住在第5栋，他找到乙的概率有多大？他能得到多少信息？   2.   甲除知道乙住在第5栋外，还知道乙住在第3单元，他找到乙的概率又有多大？他能得到多少信息？ 用xi代表单元数，yj代表户号： （1）甲找到乙这一事件是二维联合集X Y上的等概分布 ，这一事件提供给甲的信息量为 I(xi yj ) = - log p(xi yj ) = log 60 = 5.907（比特） （2）在二维联合集X Y上的条件分布概率为 ，这一事件提供给甲的信息量为条件自信息量 I(yj︱xi) = -log p(yj︱xi) = log12 = 3.585（比特）

18 2.3 信息熵的基本性质 熵函数可以表示为：

19 2.3 信息熵的基本性质 （1）对称性 集合X = {x1，x2，…，xN }中的各元素x1，x2，…，xN任意改变其顺序时，熵只和分布（概率）有关，不关心某个具体事件对应哪个概率。 例如 和 的熵是相等的。

20 （2）非负性： H(X) 0 （3）确定性： 2.3 信息熵的基本性质
2.3 信息熵的基本性质 （2）非负性： H(X) 0 （3）确定性： 在集合X = (x1，x2，…，xN)中，若有一个事件是必然事件，则其余事件必为不可能事件，即该集合的概率分布为

21 2.3 信息熵的基本性质 （4）扩展性：离散事件集 ，增加一个 不可能事件xN+1后，得到集合，δ→0，则两个集合的熵相等

22 集合X = {x1，x2，…，xi，xi+1，…，xN}的概率分布为：
2.3 信息熵的基本性质 （5）可加性： 集合X = {x1，x2，…，xi，xi+1，…，xN}的概率分布为： 则下式成立： H(X)= H(x1，x2，…，xi，xi+1，…，xN)

23 2.3 信息熵的基本性质 （6）条件熵小于等于无条件熵 即：H (X︱Y)  H (X) X,Y 统计独立时等号成立。

24 2.3 信息熵的基本性质 （7） 联合熵大于等于独立事件的熵，小于等于两独立事件熵之和，即： H (XY)  H (X) + H (Y)

25 2.4 离散无记忆的扩展信源 实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。
我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的 如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、10和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信源称为二元无记忆信源的N此扩展信源。

26 2.4 离散无记忆的扩展信源 一般情况 设一个离散无记忆信源为： 则该信源的N次扩展信源为：

27 2.4 离散无记忆的扩展信源 其中： 根据信息熵的定义： 可以证明，对于离散无记忆的扩展信源

28 A1=a1a1 A2=a1a2 A3=a1a3 A4=a2a1 A5=a2a2 A6=a2a3 A7=a3a1 A8=a3a2
2.4 离散无记忆的扩展信源 例: 离散无记忆信源的N次扩展信源 离散无记忆信源为：X:{a1,a2,a3}; P(X):{1/4, 1/2, 1/4} 2次扩展信源为： :{A1…A9} 信源的9个符号为： A1=a1a1 A2=a1a2 A3=a1a3 A4=a2a1 A5=a2a2 A6=a2a3 A7=a3a1 A8=a3a2 A9=a3a3

29 2.4 离散无记忆的扩展信源 其概率关系为 : A1 A2 A3 A4 A5 A6 A7 A8 A9 1/16 1/8 1/4 计算可知

30 2.5 离散平稳信源 1、离散平稳信源的数学定义 一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：
信源在某一时刻发出什么样的值取决于两方面 1、这一时刻该变量的分布概率 2、这一时刻以前发出的消息 如一个人讲话 我们现在讨论平稳的随机序列，所谓平稳是指序列的统计性质与时间的推移无关（俩个任意时刻信源发出符号的概率分布完全相同）。

31 2.5 离散平稳信源 2、二维平稳信源及其信息熵 最简单的平稳信源——二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。 信源的概率空间: 连续两个信源符号出现的联合概率分布为：

32 已知符号 出现后，紧跟着 出现的条件概率为：
2.5 离散平稳信源 已知符号 出现后，紧跟着 出现的条件概率为： 由二维离散信源的发出符号序列的特点可以把其分 成每两个符号一组，每组代表新信源 中的一个 符号。并假设组与组之间是统计独立的，互不相关的。 得到一个新的离散无记忆信源 ，其联合概率空间为：

33 2.5 离散平稳信源 根据信息熵的定义，可得： （1）联合熵 可以表征信源输出长度为2的平均不确定性，或所含有的信息量。因此可以用 作为二维平稳信源的信息熵的近似值

34 2.5 离散平稳信源 (2)条件熵 则：

35 2.5 离散平稳信源 可以证明： 另外还可以得到： 只有信源统计独立时等号成立。

36 2.5 离散平稳信源 [例2-15] 设某二维离散信源的原始信源的信源空间 X={x1,x2,x3}; P(X)={1/4, 1/4, 1/2}, 一维条件概率为： p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0; p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8; p(x1/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4; 原始信源的熵为： H(X)=1.5 bit/符号 条件熵： H(X2/X1)=1.4 bit/符号 可见： H(X2/X1)<H(X) 二维信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9 bit/消息 每个信源符号提供的平均信息量为： H2(X1,X2)=H(X1,X2)/2=1.45 bit/符号。

37 2.5 离散平稳信源 分析：我们用 来近似信源的实际熵 我们现在有两种方法去近似信源的实际熵，一种是 H(X1X2)/ 为1.45bit，但这种方法不太准确，因为它把两个消息看成一组，认为两组之间是统计独立的，实际上它们之间是有关联的；另一种是我们可以用条件熵来近似，为1.4bit，到底那一种正确呢？我们可以通过对一般离散平稳信源的分析来找到这个答案。

38 2.5 离散平稳信源 3、离散平稳信源的极限熵 平均符号熵 条件熵 有以下几点性质 （1）条件熵随N的增加是非递增的 （2）N给定时，平均符号熵大于等于条件熵 （3）平均符号熵随N的增加是非递增的 （4） 称 为极限熵。

39 2.5 离散平稳信源 可以证明，对于二维离散平稳信源，条件熵等于极限熵，因此条件熵就是二维离散平稳信源的真实熵 对于一般信源，求出极限熵是很困难的，然而，一般来说，取N不大时就可以得到与极限熵非常接近的条件熵和平均符号熵，因此可以用条件熵和平均符号熵来近似极限熵

40 第六节 马尔可夫信源 在很多信源的输出序列中，符号之间的依赖关系是有限的，任何时刻信源符号发生的概率只与前边已经发出的若干个符号有关，而与更前面的符号无关。 为了描述这类信源除了信源符号集外还要引入状态集。这时，信源输出消息符号还与信源所处的状态有关。 若一个信源满足下面两个条件，则称为马尔可夫信源： （1）某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态无关； （2）信源的下一个状态由当前状态和下一刻的输出唯一确定。

41 当符号输出概率与时刻L无关，称为具有时齐性。即
2.6 马尔可夫信源 （1）某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态无关。即 当符号输出概率与时刻L无关，称为具有时齐性。即

42 （2）信源的下一个状态由当前状态和下一刻的输出唯一确定。
2.6 马尔可夫信源 （2）信源的下一个状态由当前状态和下一刻的输出唯一确定。 条件（2）表明，若信源处于某一状态 ，当它发出 一个符号后，所处的状态就变了，一定转移到另一状态。 状态的转 移依赖于发出的信源符号，因此任何时刻信源处 在什么状态完全由前一时刻的状态和发出的符号决定。

43 2.6 马尔可夫信源 例：二阶马尔可夫信源，原始符号集为{1,0}， 条件概率定为：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 由此可见，信源共有2^2=4种状态 E：{e1=00,e2=01,e3=10,e4=11}

44 2.6 马尔可夫信源 状态之间有转移概率， p(e2/e1)=p(e3/e4)=0.2 p(e2/e4)=p(e1/e3)=p(e2/e3)=p(e3/e2)=0.5 P(e1/e1)=p(e4/e4)=0.8 其状态转移图如下页。在状态转换图中，把信源的每一种状态用圆圈表示，用有向箭头表示信源发出某一符号后由一种状态到另一状态的转移。

45 2.6 马尔可夫信源 00 0:0.8 0:0.5 1:0.2 0:0.5 01 10 1:0.5 1:0.5 0:0.2 11 1:0.8 由上例可知，m阶马尔可夫信源符号集共有q个符号，则信源共有 个不同状态。信源在某一时刻时，必然处于某一种状态，等到下一个字符输出时，转移到另外一个状态。

46 举 例 [例2.2.3] 设信源符号 X∈{x1, x2, x3} ，信源所处的状态S∈{e1, e2, e3, e4, e5} 。各状态之间的转移情况由图2.2.1给出。

47 将图中信源在ei状态下发符号xk 的条件概率p(xk /ei)用矩阵表示
由矩阵看出： 由图中看出： 由图中可得状态的一步转移概率： 该信源满足马尔可夫信源定义。

48 2.6 马尔可夫信源 定义 为各状态的极限概率，则时齐、遍历的马尔可夫信源的熵为

49 2.6 马尔可夫信源 马尔可夫信源的熵： 这里这给出结论： 表明m阶马尔可夫信源的极限熵等于m阶条件熵。根据求条件熵公式还可得到

50 (3) 举 例 [例2.2.4] 二元2阶马尔可夫信源，原始信号X的符号集为{X1=0, X2=1}，其状态空间 共有nm=22=4个不同的状态e1,e2,e3,e4，即 E：{e1=00,e2=01,e3=10,e4=11} 状态转移图见右图所示。 解：p(e1/e1)= p(x1/e1)=p(0/00)=0.8 p(e2/e1)= p(x2/e1)=p(1/00)=0.2 p(e3/e2)= p(x1/e2)=p(0/01)=0.5 p(e4/e2)= p(x2/e2)=p(1/01)=0.5 p(e1/e3)= p(x1/e3)=p(0/10)=0.5 p(e2/e3)= p(x2/e3)=p(1/10)=0.5 p(e3/e4)= p(x1/e4)=p(0/11)=0.2 p(e4/e4)= p(x2/e4)=p(1/11)=0.8

51 由二元信源X∈{0,1}得到的状态空间(e1,e2,e3,e4)和相应的一步 转移概率构成的2阶马尔可夫信源模型为
求出稳定状态下的p(ej) ，称为状态极限概率。 将一步转移概率代入上式得 p(e1)=0.8 p(e1)+0.5 p(e3) p(e2)=0.2 p(e1)+0.5 p(e3) p(e3)=0.5 p(e2)+0.2 p(e4) p(e4)=0.5 p(e2)+0.8 p(e4)

52 解方程组得 p(e1)= p(e4)=5/14 p(e2)= p(e3)=2/14 计算极限熵

53 2.6 马尔可夫信源 例：一个二元二阶马尔可夫信源，信源符号集A={0,1}。信源开始时，它以概率p(0)=p(1)=0.5发出随机变量X1。然后，下一单位时间输出的随机变量X2与X1有依赖关系，由条件概率p(x2|x1)表示： 再下一单元时间输出随机变量X3，而X3依赖于前面变量。依赖关系由条件概率p(x3|x1x2)表示： x1 x2 1 0.3 0.4 0.7 0.6

54 2.6马尔可夫信源 x1x2 X3 00 01 10 11 0.4 0.2 0.3 1 0.6 0.8 0.7 由从第四单位时间开始，任意时刻信源发出的随机变量Xi 只与前面二个单位时间的随机变量有关， 根据提议可得信源的状态转移图：

55 2.6 马尔可夫信源 00 01 10 11

56 2.6 马尔可夫信源 0.4 0.3 0.5 0.2 0.4 0.6 0.7 0.5 0.8 0.6

57 2.6 马尔可夫信源 解得： 由此 ＝0.8956 当马尔可夫信源达到稳定后，符号0和1的分布概率可根据下式计算 因此得：

58 2.7 信源剩余度与自然语言的熵 1、关于离散信源熵的总结：
实际信源可能是非平稳的有记忆随机序列信源；其极限熵是不存在的；解决的方法是假设其为离散平稳随机序列信源，极限熵存在，但求解困难；进一步假设其为m阶Markov信源，用其m阶条件熵近似； 再进一步假设为一阶Markov信源，用其一阶条件熵 来近似；最简化的信源是离散无记忆信源，其熵为H(x); 最后可以假定为等概的离散无记忆信源，其熵H(x); 它们之间的关系可以表示为：

59 2.7 信源剩余度与自然语言的熵 2、熵的相对率 3、信源剩余度

60 2.7 信源剩余度与自然语言的熵 4、自然语言的熵 （1）对于英文字母 （2）对于中文 我们可以压缩剩余度来压缩信源，提高通信的可靠性。

61