信息论与编码信源及信源熵

1、信息论与编码信源及信源熵第1页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵上一讲复习互信息量：互信息量与信源熵的关系：第2页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵连续信源熵： 它与离散信源熵的差别（差熵） 最大熵：（1）限幅度时的最大熵 （2）限平均功率时的最大熵序列信源熵： （1）离散无记忆信源序列熵：第3页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵（2）离散有记忆信源序列熵： （i）平稳有记忆序列信源：极限熵：第4页，共44页，2022年，5月20日，1点13分，星期一信息论

2、与编码-信源及信源熵二、马尔可夫信源1.马尔可夫信源设一般信源所处的状态 ，在每一状态下可能输出的符号 。定义：若信源输出的符号序列和信源所处的状态满足以下两个条件（1）某一时刻信源符号的输出只与此时刻信源所处的状态有关，而与以前的状态及以前的输出符号都无关，即第5页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵当具有齐次性时，有（2）信源某 时刻所处的状态由当前的输出符号和前一时刻 信源的状态唯一决定，即则此信源称为马尔可夫信源。第6页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵上述定义和描述的是一般的马尔可夫信源。但常见

3、的是m阶马尔可夫信源，它在任何时刻 ，符号发生的概率只与前面m个符号有关，我们可以把这前面m个符号序列看作信源在此 时刻所处的状态。因为信源符号集共有q个符号，则信源可以有 个不同的状态，他们对应于 个长度为m的不同的符号序列。第7页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵因此，m阶马尔可夫离散信源的数学模型可由一组信源符号集和一组条件概率确定：并满足第8页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵M阶马尔可夫信源在任何时刻 ，符号发生的概率只与前m个符号有关，所以可设状态 。由于 均可取可得信源的状态集 。这样一来

4、，条件概率可变换成条件概率 表示任何 时刻信源处在 状态时，发出符号 的概率。而 可任取 之一，所以可以简化成 表示。 第9页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵而在 时刻，信源发出符号 后，由符号 组成了新的信源状态 ，即信源所处的状态也由转移到 ，它们之间的转移概率叫做一步转移概率 ，简记为 ，它可由条件概率来确定，表示在 的情况下，经一步转移到状态 的概率。对于齐次马尔可夫链，其转移概率具有推移不变性，因此， 可简写为 。第10页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵推广可得 ，它表示系统在时刻m处于状

5、态 ，经(n-m)步转移后在时刻n处于状态 的概率。它具有以下性质：记k步转移概率为由于有 个状态，所以状态转移概率是一个矩阵，记为：第11页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵矩阵P中第 行元素对应与从某一个状态 转移到所有状态 的转移概率，显然矩阵中每一个元素都是非负的，并且每行元素之和均为1； 第 列元素对应与从所有状态 转移到同一个状态 的转移概率，列元素之和不一定为1。注意：状态转移矩阵与条件概率矩阵是不同的。第12页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵转移概率的切普曼-柯尔莫郭罗夫方程：当 时，

6、有用矩阵表示，就是第13页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵从上述的递推关系可知，对于齐次马尔可夫链来说，一步转移概率完全决定了k步转移概率。无条件状态概率 的计算： 就是从初始状态经k步转移后，停留在某一个状态 的概率。为了计算这个概率，需要知道初始状态概率，即 这时，第14页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵第15页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵转移概率 的平稳分布 ：两个问题：（1）此极限是否存在；（2）如果存在，其值是多少。（1）存在问题：p23

7、（2）求法：如果存在，且等于一个与起始状态 无关的被称为平稳分布的 ，则不论起始状态是什么，此马氏链可以达到最后的稳定，即所有状态的概率分布均不变。在这种情况下，就可以用（P）这一矩阵来充分描述稳定的马氏链，起始状态只使前面有限个变量的分布改变，如同电路中的暂态一样。第16页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵稳态分布概率的求法：要求只要它存在，则上式中， 与 均为稳态分布概率。再加上约束条件 ，两式联立求解，就可以求出稳态分布概率 。第17页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵例题1:有一个二阶马氏链 ，

8、其符号概率如表1，状态变量 ，求其状态转移概率表，画出其状态转移图，求出各状态的平稳分布概率。 表1 符号条件概率表 表2 状态转移概率表起始状态 符 号 0 1 00 1/2 1/2 01 1/2 2/3 10 1/4 3/4 11 1/5 4/5起始状态 终 止 状 态 (00) (01) (10) (11) 00 1/2 1/2 0 0 01 0 0 1/3 2/3 10 1/4 3/4 0 0 11 0 0 1/5 4/5第18页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵求出的状态转移表如表2所示。方法是：比如在状态01时，出现符号0，则将0加到状

9、态01后，再将第一位符号0挤出，转移到状态10，概率为1/3。依此类推。状态转移图如下图所示：第19页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵状态转移图：01001011(1)1/2(0)1/4(1)2/3(0)1/5(0)1/3(1)3/4(0)1/2(1)4/5第20页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵求状态平稳分布概率：由得：第21页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵解之得：由例子可以看出，状态转移矩阵与条件概率矩阵是不同的。例题2：三态马尔柯夫信源的状态转

10、移矩阵为第22页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵状态转移矩阵为画出其香农线图，求其稳态状态概率分布和符号概率分布。解：香农线图为第23页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵稳态状态概率分布：解得：第24页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵 3.马尔可夫信源的信息熵在马尔柯夫信源输出的符号序列中，符号之间是有依赖关系的，信源所处的起始状态不同，信源发出的符号序列也不相同。对m阶马尔柯夫信源，能够提供的平均信息量，即信源的极限熵 ，就等于 。 对于齐次、遍历的马

11、尔可夫链，其状态 由 唯一决定，因此有第25页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵而第26页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵即第27页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵即式中， 是马尔可夫链的平稳分布概率，熵函数 表示信源处于某一状态 时发出一个符号的平均不确定性，也就是说，马尔可夫信源的平均符号熵 是信源处于某一个状态 时发出一个符号的平均符号熵 ，在全部状态空间的统计平均值。第28页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源

12、及信源熵例题3：如图所示三态马尔可夫信源，写出其状态转移矩阵，画出其状态转移图，求出稳态概率分布，并求其极限熵。解：由图可以写出其 状态转移矩阵为1/0.10/0.91/0.50/0.51/0.20/0.8第29页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵稳态概率分布：解得条件熵第30页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵因此第31页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵 2.5 冗余度前几节我们讨论了各类离散信源及其信息熵。实际的离散信源可能是非平稳的，对于非平稳信源来

13、说，其 不一定存在，但可以假定它是平稳的，用平稳信源的 来近似。然而，对于一般平稳的离散信源，求 值也是极其困难的。那么，进一步可以假设它是m阶马尔可夫信源，用m阶马尔可夫信源的平均信息熵 来近似。如再进一步简化信源，即可假设信源是无记忆信源，而信源符号有一定的概率分布。这时，可用信源的平均自信息量 来近似。第32页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵最后，可以假定是等概分布的无记忆离散信源，用最大熵 来近似。由此可见，由于信源符号间的依赖关系使信源的熵减小。它们的前后依赖关系越长，信源的熵越小。当信源符号间彼此无依赖、等概率分布时，信源的熵才达到最

14、大。也就是说，信源符号之间依赖关系越强，每个符号提供的信息量就越小。每个符号提供的平均自信息量随着符号间的依赖关系长度的增加而减少。为此，我们引进信源的冗余度（也叫剩余度或多余度）来衡量信源的相关性程度。第33页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵对于一般平稳信源来说，极限熵为 ，这就是说，如果我们要传送这一信源的信息，理论上来说只需要有传送 的手段即可。但实际上我们对它的概率分布不能完全掌握，如果把它近似成m阶马尔可夫信源，则可以用能传送 的手段去传送具有 的信源，当然这里面就不太经济。我们定义信息效率为：第34页，共44页，2022年，5月20日

15、，1点13分，星期一信息论与编码-信源及信源熵定义为信源的冗余度。由冗余度的定义可见，信源的冗余度能够很好地反映信源输出的符号序列中符号之间依赖关系的强弱。冗余度 越大，表示信源的实际熵 越小，表明信源符号之间的依赖关系越强，即符号之间的记忆长度越长；反之，冗余度越小，表明信源符号之间的依赖关系越弱，即符号第35页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵之间的记忆长度越短。当冗余度等于零时，信源的熵就等于极大熵 ，表明信源符号之间不但统计独立无记忆，而且各符号还是等概分布。因此，冗余度可以用来衡量信源输出的符号序列中各符号之间的依赖程度。例：以符号是英文

16、字母的信源为例，英文字母加上空格共有27个，则最大熵为第36页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵但实际上，用英文字母组成单词，再由单词组成句子时，英文字母并不是等概率出现，比如我们知道在英语中E出现的概率大于Q出现的概率。对在英文书中各符号的概率加以统计，可以得出各个字母出现的概率，由此得出第一级近似为无记忆信源的熵：第37页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵再考察英语的结构得知，要组成有意义的单词，英文字母的前后出现是有依赖关系的，当前面某个字母出现后，后面将出现什么字母，并不是完全不确定的，而是有一

17、定的概率分布。例如字母T后面出现H、R的可能性较大，出现J、K、L、M、N的可能性极小，而根本不会出现Q、F、X。考虑到字母之间的依赖性，可以把英语信源做进一步精确的近似，看作一阶或二阶马尔可夫信源，这样可以求得：第38页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵因此可知，在信源所输出的序列中依赖关系越复杂，信息熵就越小。实际上，英文信源的信息熵比还要小得多，一般认为， 。因此，信息效率和冗余度为第39页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵这说明用英文字母写成文章时，有71%是由语言结构、实际意义等确定，而剩下只

18、有29%是写文字的人可以自由选择的。这也就意味着在传递或存储英语信息时，只需要传送或存储那些必要的信息，而有关联的则可以大幅度地压缩。例如100页的英文书，大约只要存储29页就可以了，其中的71页可以压缩掉，这压缩掉的文字完全可以根据英文的统计特性来恢复。信源的冗余度正是表示这种信源可压缩的程度的。第40页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵从提高传输信息效率的观点出发，总是希望减少或去掉冗余度。如发中文电报时，为了经济和节省时间，总希望在原意不变的情况下，尽可能地把电文写得简洁些。也就是说，实际的通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，这就是所谓的信源编码。但是，冗余度也有它的用处，因为冗余度大的消息具有强的抗干扰能力。当干扰使消息在传输过程中出现错误时，我们能从上下关联中纠正错误。例如我们收到“中X人民X和国”时，我们很容易把它纠正为“中华人民共和国”。但若我们收到的是压缩后的“中国”，而出现第41页，共44页，2022年，5月20日，1点13分，星期一信息论与编码-信源及信源熵 了错误变成了“X国”，就很难肯定发出的是“中国”、“美国”，由此将会造成很大的错误。所以，从提高抗干扰能力的角度来看，总是希望增加或者保留信源的冗余度，或者是传输之前在信源编码后去除冗余的符号序列里加入某些特殊的