July 24信息论导论信息论导论通信与信息工程学院通信与信息工程学院杨海芬杨海芬yanghf@ 信源熵o单符号离散信源联合熵单符号离散信源联合熵o多符号离散信源联合熵；条件熵多符号离散信源联合熵；条件熵o离散平稳信源、联合熵离散平稳信源、联合熵o离散平稳无记忆信源、联合熵离散平稳无记忆信源、联合熵o马尔科夫信源及其极限熵马尔科夫信源及其极限熵o冗余度与结构信息冗余度与结构信息 信源熵四、马尔科夫信源及其极限熵o安德雷安德雷··马尔可夫马尔可夫(Andrei Markov 1856(Andrei Markov 1856－－19221922），俄国数），俄国数学家n18741874年马尔可夫入年马尔可夫入圣彼得堡大学圣彼得堡大学，师从切比雪夫，，师从切比雪夫，18861886年当选为圣彼得堡科学院院士年当选为圣彼得堡科学院院士n开创了随机过程这个新的领域，以他的名字命名的开创了随机过程这个新的领域，以他的名字命名的马尔马尔可夫链可夫链在现代工程、自然科学和社会科学各个领域都有在现代工程、自然科学和社会科学各个领域都有很广泛的应用很广泛的应用o马尔可夫性：一个过程的马尔可夫性：一个过程的““将来将来””仅依赖仅依赖““现在现在””而不依而不依赖赖““过去过去”” 信源熵o马尔可夫链的应用马尔可夫链的应用n排队理论和统计学中的建模，还可作为信号模型用排队理论和统计学中的建模，还可作为信号模型用于于熵编码熵编码技术，如技术，如算术编码算术编码o著名的著名的LZMALZMA数据压缩算法就使用了马尔可夫链与数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码。
类似于算术编码的区间编码n生物学应用，生物学应用，o人口过程人口过程，可以帮助模拟生物人口过程的建模可以帮助模拟生物人口过程的建模o隐蔽马尔可夫模型还被用于隐蔽马尔可夫模型还被用于生物信息学生物信息学，用以编，用以编码区域或基因预测码区域或基因预测n马尔可夫链最近的应用是在地理统计学马尔可夫链最近的应用是在地理统计学（（geostatisticsgeostatistics）中）中, ,被称为是被称为是““马尔可夫链地理马尔可夫链地理统计学统计学””仍在发展过程中仍在发展过程中基于马尔可夫链的我国城乡居民收入演进分析基于马尔可夫链的我国城乡居民收入演进分析” 信源熵四、马尔科夫信源及其极限熵四、马尔科夫信源及其极限熵1、马尔科夫信源、马尔科夫信源定义定义N维离散平稳信源符号序列中第维离散平稳信源符号序列中第N个符号只与前个符号只与前m (≤N-1)个符号相关，该信源为个符号相关，该信源为m阶马尔科夫信源阶马尔科夫信源马尔科夫信源是离散平稳马尔科夫信源是离散平稳有限记忆有限记忆信源，其记忆信源，其记忆长度为长度为m m阶马尔科夫信源符号序列的长度阶马尔科夫信源符号序列的长度N=m+1 信源熵表示表示 信源熵状态转移图状态转移图马尔科夫链马尔科夫链表示表示马尔科夫信源可以用状态转移图表示吗？马尔科夫信源可以用状态转移图表示吗？* 信源熵 信源熵用状态表示的用状态表示的m阶马尔科夫信源等效于用状态转移阶马尔科夫信源等效于用状态转移图描述的马尔科夫链。
图描述的马尔科夫链例例1状态转移图状态转移图 信源熵s1s2s3s40.20.80.50.5设状态设状态s1=00、、s2=01、、s3=10、、s4=11 信源熵s1s2s3s40.20.80.50.50.50.50.20.8 信源熵2、马尔科夫链的遍历定理、马尔科夫链的遍历定理马尔科夫链的遍历马尔科夫链的遍历从任何一个状态出发，可以通过有限步到达任何从任何一个状态出发，可以通过有限步到达任何其他状态，该马尔科夫链是遍历的其他状态，该马尔科夫链是遍历的非遍历的马尔科夫链存在吸收态非遍历的马尔科夫链存在吸收态非遍历马尔科夫链的例子非遍历马尔科夫链的例子s1s2s3s410.50.50.50.51 信源熵马尔科夫链的遍历定理马尔科夫链的遍历定理3、马尔科夫信源的极限熵、马尔科夫信源的极限熵 信源熵极限熵定理极限熵定理N→∞时，时， N维离散平稳信源平均符号熵的极限存维离散平稳信源平均符号熵的极限存在且等于在且等于N阶条件熵的极限值，称为阶条件熵的极限值，称为N维离散平稳维离散平稳信源的极限熵，用信源的极限熵，用H∞表示即使即使N→∞，，m阶马尔科夫信源符号序列的有效长阶马尔科夫信源符号序列的有效长度只有度只有m+1。
信源熵 信源熵强调强调m阶马尔科夫信源的长度特征，一般其极限熵阶马尔科夫信源的长度特征，一般其极限熵H∞记为记为Hm+1例例2图示二元二阶马尔科夫信源的极限熵图示二元二阶马尔科夫信源的极限熵求极限熵求极限熵求求m阶条件熵阶条件熵 信源熵s1s2s3s40.20.80.50.50.50.50.20.8遍历定理遍历定理 信源熵 信源熵完备性完备性 信源熵 信源熵五、冗余度与结构信息1、冗余度冗余压缩o信息论的创始人Shannon提出把数据看作是信息和冗余度（redundancy）的组合n如在一份计算机文件中，某些符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分便可在数据编码中除去或减少n相邻的数据之间存在着相关性如图片中常常有色彩均匀的背影，电视信号的相邻两帧之间可能只有少量的变化影物是不同的，声音信号有时具有一定的规律性和周期性等等n人们由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限信源编码 信源熵o可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的o图像压缩编码 (1)无损压缩编码 (2)有损压缩编码 (3)混合编码，如 H261，JPEG，MPEG等技术标准o简单地说，如果没有数据压缩技术，我们就没法用 WinRAR 为 Email 中的附件瘦身；如果没有数据压缩技术，市场上的数码录音笔就只能记录不到 20 分钟的语音；如果没有数据压缩技术，从 Internet 上下载一部电影也许要花半年的时间o衡量一个压缩编码方法优劣的重要指标 (1)压缩比要高； (2) 算法简单，硬件实现容易； (3)解压缩的图像质量要好。
信源熵o信道前向纠错编码信道前向纠错编码（（FEC））技术通过在传输码列中加技术通过在传输码列中加入冗余纠错码，在一定条件下，通过解码可以自入冗余纠错码，在一定条件下，通过解码可以自动纠正传输误码，降低接收信号的误码率动纠正传输误码，降低接收信号的误码率（（BER））衡量衡量FEC纠错能力的指标称为纠错能力的指标称为“FEC编码增益编码增益”，，该增益越强表示纠错性能越强该增益越强表示纠错性能越强o汉明码、汉明码、奇偶校验码、奇偶校验码、RS码、码、Turbo码、码、LDPC等等o纠错性能、码率、实现复杂度纠错性能、码率、实现复杂度冗余冗余纠错纠错信道编码信道编码 信源熵中华人民共和国中华人民共和国中国中国*华人民华人民*和国和国*国国 信源熵实际信源抽象为实际信源抽象为N维离散平稳信源，维离散平稳信源，H∞是其熵率，是其熵率，即从理论上看，只要传送即从理论上看，只要传送H∞就可以了就可以了但是这必须掌握信源的全部统计特性，这显然是但是这必须掌握信源的全部统计特性，这显然是不现实的实际中，只能掌握有限记忆长度不现实的实际中，只能掌握有限记忆长度m，其，其熵率用熵率用Hm+1近似，即需要传送近似，即需要传送Hm+1与理论值相比，多传送了与理论值相比，多传送了Hm+1-H∞由于由于Hm+1>H∞，表现在信息传输上存在冗余。
表现在信息传输上存在冗余抽象描述抽象描述 信源熵定义定义信源的信源的m阶极限熵阶极限熵Hm+1与与N-1阶极限熵阶极限熵H∞的相对差的相对差为该信源的冗余度，也叫剩余度为该信源的冗余度，也叫剩余度表示表示信源的冗余度表示信源可以被压缩信源的冗余度表示信源可以被压缩的程度的程度* 信源熵o或者定义或者定义o正是由于信源存在冗余度，所以存在着进一步压缩正是由于信源存在冗余度，所以存在着进一步压缩的可能性冗余度越大，压缩潜力越大它是信源的可能性冗余度越大，压缩潜力越大它是信源编码、数据压缩的前提与基础编码、数据压缩的前提与基础H0：相同符号数的最大值：相同符号数的最大值 信源熵例例1英文信源的熵率英文信源的熵率 信源熵英文信源用英文信源用m阶马尔可夫信源近似，最大熵及各阶阶马尔可夫信源近似，最大熵及各阶极限熵极限熵（（1）近似为无记忆信源）近似为无记忆信源(零阶马尔可夫信源零阶马尔可夫信源)且字且字母等概率分布母等概率分布最大熵最大熵（（2）近似为无记忆信源，字母的概率分布）近似为无记忆信源，字母的概率分布 信源熵英文字母不等概率分布图英文字母不等概率分布图空格空格 信源熵英文字母前后存在一定的依赖关系，如英文字母前后存在一定的依赖关系，如t后出现后出现h、、r的可能性较大。
的可能性较大零阶极限熵零阶极限熵(无条件熵无条件熵)一阶极限熵一阶极限熵（（3）近似为一阶马尔可夫信源，考虑字母的一阶）近似为一阶马尔可夫信源，考虑字母的一阶条件概率分布条件概率分布 信源熵（（5）近似为全记忆信源）近似为全记忆信源(香农香农以以m=100估计估计)，，N-1阶极限熵阶极限熵（（4）近似为二阶马尔可夫信源，考虑字母的二阶）近似为二阶马尔可夫信源，考虑字母的二阶条件概率分布，二阶极限熵条件概率分布，二阶极限熵…实际信源为全记忆信源，熵率为实际信源为全记忆信源，熵率为H∞，考虑到可实，考虑到可实现性，一般取有限记忆长度现性，一般取有限记忆长度m，熵率用，熵率用Hm+1近似，近似，Hm+1>H∞，在信息传输上存在，在信息传输上存在冗余冗余 信源熵英文信源近似为无记忆信源且等概时，冗余度英文信源近似为无记忆信源且等概时，冗余度英文信源的冗余度的计算英文信源的冗余度的计算信源的冗余度表示信源可以被压缩的程度信源的冗余度表示信源可以被压缩的程度 信源熵英文信源近似为无记忆信源但概率分布已知时，英文信源近似为无记忆信源但概率分布已知时，冗余度冗余度英文信源近似为一阶马尔可夫信源，冗余度英文信源近似为一阶马尔可夫信源，冗余度 信源熵英文信源近似为二阶马尔可夫信源，冗余度英文信源近似为二阶马尔可夫信源，冗余度… 信源熵 信源熵2、结构信息、结构信息定义定义信源的信源的m阶极限熵阶极限熵Hm+1与与N-1阶极限熵阶极限熵H∞之差为该之差为该信源的结构信息。
信源的结构信息表示表示 信源熵英文信源近似为无记忆信源且等概时，结构信息英文信源近似为无记忆信源且等概时，结构信息英文信源近似为无记忆信源但概率分布已知时，英文信源近似为无记忆信源但概率分布已知时，结构信息结构信息 信源熵英文信源近似为一阶马尔可夫信源，结构信息英文信源近似为一阶马尔可夫信源，结构信息英文信源近似为二阶马尔可夫信源，结构信息英文信源近似为二阶马尔可夫信源，结构信息…习题：习题：(P68-70) 2.16、、2.17 。