信息论与编码 曹雪虹 PPT

1、信息论基础B1第第2章章 信源与信息熵信源与信息熵n信源描述与分类信源描述与分类n离散信源的信息熵和互信息离散信源的信息熵和互信息n离散序列信源的熵离散序列信源的熵n连续信源的熵与互信息连续信源的熵与互信息n冗余度冗余度信息论基础B22.1信源的描述与分类信源的描述与分类n信源是产生消息（符号）、消息序列和连续消信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机因此，信源是产生随机变量、随机序列和随机过程的源过程的源n信源的基本特性是信源的基本特性是具有随机不确定性具有随机不确定性信息

2、论基础B32.1信源特性与分类信源特性与分类n分类分类 时间时间 离散离散 连续连续 幅度幅度 离散离散 连续连续 记忆记忆 有有 无无 三大类：三大类： 单符号离散信源单符号离散信源 符号序列信源（有记忆和无记忆）符号序列信源（有记忆和无记忆） 连续信源连续信源信息论基础B4 2.1信源特性与分类信源特性与分类n离散无记忆序列信源离散无记忆序列信源u布袋摸球实验，若每次取出两个球，由两布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取先取出一个球，记下颜色放回布袋，再取另一个球。另一个球。)()()

3、(),(2121LLlXpXpXpXXXXp信息论基础B52.1信源特性与分类信源特性与分类n离散有记忆序列信源离散有记忆序列信源u布袋摸球实验，每次取出两个球，由两个布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色取出一个球，记下颜色不放回布袋不放回布袋，再取，再取另一个球。另一个球。)/()/()(),(1112121LLLXXXpXXpXpXXXp信息论基础B62.1信源特性与分类信源特性与分类n马尔可夫信源马尔可夫信源u当信源的记忆长度为当信源的记忆长度为m+1时，该时该发出时，该时该发出的符号与前的符号与

4、前m个符号有关联性，而与更前个符号有关联性，而与更前面的符号无关。面的符号无关。)/()/()(),(112121mLLLXXXpXXpXpXXXp信息论基础B72.1信源描述与分类信源描述与分类n描述：通过描述：通过概率空间概率空间描述描述u单符号离散信源单符号离散信源 例如：对二进制数字与数据信源例如：对二进制数字与数据信源nnpppuUuUuUupU,)(212121,211, 0,1, 010pppU信息论基础B82.1信源描述与分类信源描述与分类u连续信源连续信源为概率密度函数)(),()(),()(upUuupbaupU信息论基础B92.1信源描述与分类信源描述与分类u离散序列信源

5、离散序列信源 以以3位位PCM信源为例信源为例)(, )(, )(,)(2121LLnnLupupupuUuUuUupU3112030,111,001,000)(ppppUUUupUL信息论基础B102.1信源描述与分类信源描述与分类 当当p=1/281,81,81111,001,000)( UUUupUL信息论基础B112.1信源描述与分类信源描述与分类n离散无记忆序列信源离散无记忆序列信源u布袋摸球实验，若每次取出两个球，由两布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取先取出一个球，记下颜色

6、放回布袋，再取另一个球。另一个球。)()()(),(2121LLlXpXpXpXXXXp信息论基础B122.1信源描述与分类信源描述与分类n离散有记忆序列信源离散有记忆序列信源u布袋摸球实验，每次取出两个球，由两个布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色取出一个球，记下颜色不放回布袋不放回布袋，再取，再取另一个球。另一个球。)/()/()(),(1112121LLLXXXpXXpXpXXXp信息论基础B132.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u当信源的记忆长度为当信源的记忆长度为m+

7、1时，该时该发出时，该时该发出的符号与前的符号与前m个符号有关联性，而与更前个符号有关联性，而与更前面的符号无关。面的符号无关。)/()/()(),(112121mLLLXXXpXXpXpXXXp信息论基础B142.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u由于高阶马尔可夫信源需要引入矢量进行由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为分析，现方法将矢量转化为状态状态变量。定变量。定义状态：义状态：u信源在某一时刻出现符号概率信源在某一时刻出现符号概率xj与信源此与信源此时所处状态时所处状态si有关，用条件概率表示有关，用条件概率表示p(xj/si),状态转移概

8、率表示为状态转移概率表示为p(sj/si)nijimiiiaaAxxxxs,),(121信息论基础B152.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u更一般，经过更一般，经过n-m步后转移至步后转移至sj的概率的概率jijijijimjnijnmpnmpssPsSsSPnmp1),(0),(/),(信息论基础B16 2.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u特别关心特别关心n-m=1情况，情况，pij(m,m+1)()(1/)(:10/)(kijmkmkijjijijijimjmijpiSjSPmpkpppsSsSPmp步转移概率为信息论基础B17 2.1信

9、源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u系统在任一时刻可处于状态空间的任意一系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵状态，状态转移时，转移概率是一个矩阵， 一步转移转移矩阵为一步转移转移矩阵为QQQQQQijppppppppSjip2122111211,Pp信息论基础B18 2.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源uk步转移概率步转移概率pij(k)与与l步和步和k-l步转移概率之步转移概率之间满足切普曼间满足切普曼-柯尔莫郭洛夫方程。柯尔莫郭洛夫方程。u定义定义：如果从状态：如果从状态I转移到状态转移到状态j的概率与的概率与m

10、无关，则称这类无关，则称这类MovKov链为齐次链为齐次u对于齐次马尔可夫链，一步转移概率完全对于齐次马尔可夫链，一步转移概率完全决定了决定了k步转移概率。步转移概率。信息论基础B19 2.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u定义：若齐次马尔可夫链对一切定义：若齐次马尔可夫链对一切I,j存在不存在不依赖于依赖于I的极限，则称其具有遍历性，的极限，则称其具有遍历性，pj称称为平稳分布为平稳分布0)(10limijjijijjjkijkppppppp信息论基础B202.1信源描述与分类信源描述与分类n马尔可夫信源马尔可夫信源u定理：设有一齐次马尔可夫链，其状态转定理：设有一齐

11、次马尔可夫链，其状态转移矩阵为移矩阵为P，其稳态分布为，其稳态分布为wjWWP jjw1信息论基础B212.1信源描述与分类信源描述与分类u不可约性，对于任意一对不可约性，对于任意一对I和和j， 都存在至都存在至少一个少一个k，使，使pij(k)0.u非周期性，所有非周期性，所有pij(n)0的的n中没有比中没有比1大的大的公因子。公因子。u定理：设定理：设P是某一马尔可夫链的状态转移是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存矩阵，则该稳态分布存在的充要条件是存在一个正整数在一个正整数N，使矩阵，使矩阵PN中的所有元素中的所有元素均大于零。均大于零。信息论基础B222.1信

12、源描述与分类信源描述与分类nEg. 一个相对编码器，一个相对编码器，求平稳分布求平稳分布+TXY信息论基础B23 2.1信源描述与分类信源描述与分类nEg. 二阶马氏链，二阶马氏链，X 0,1,求平稳分布求平稳分布起始状态000110111/201/401/203/4001/301/502/304/5S1(00)S2(01)S3(10)S4(11)信息论基础B242.2离散信源熵与互信息离散信源熵与互信息n信息量信息量u自信息量自信息量u联合自信息量联合自信息量u条件自信息量条件自信息量n单符号离散信源熵单符号离散信源熵u符号熵符号熵u条件熵条件熵u联合熵联合熵信息论基础B252.2离散信源熵

13、与互信息离散信源熵与互信息n信息信息q不确定性的消除不确定性的消除n信息的度量信息的度量q随机性、概率随机性、概率q相互独立符合事件概率相乘、信息相加相互独立符合事件概率相乘、信息相加n熵熵q事件集的平均不确定性事件集的平均不确定性信息论基础B262.2离散信源熵与互信息离散信源熵与互信息G直观推导信息测度直观推导信息测度C信息信息I应该是消息概率应该是消息概率p的递降函数的递降函数C由两个不同的消息（相互统计独立）所提供的信息等由两个不同的消息（相互统计独立）所提供的信息等于它们分别提供信息之和（可加性）于它们分别提供信息之和（可加性）0)(,1,)(,)(,0,)(,iiiiiiiipIp

14、pIppIppIp时且当时且当信息论基础B272.2离散信源熵与互信息离散信源熵与互信息l定义：对于给定的离散概率空间表示的信源，定义：对于给定的离散概率空间表示的信源，x=ai事件所对应的（自）信息为事件所对应的（自）信息为 以以2为底，为底，单位单位为比特（为比特（bit) 以以e为底，单位为奈特（为底，单位为奈特（nat) 1nat=1.433bit 以以10为底，单位为笛特（为底，单位为笛特（det) 1det=3.322bit)(1log)(log)(iiiixpxpaxI 信息论基础B282.2离散信源熵与互信息离散信源熵与互信息l定义：联合概率空间中任一联合事件的联合（自）信定义

15、：联合概率空间中任一联合事件的联合（自）信息量为：息量为：l定义：联合概率空间中，事件定义：联合概率空间中，事件x在事件在事件y给定条件下的给定条件下的条件条件（自）信息量为（自）信息量为：),(1log),(log),(jijijiyxpyxpyxI )/(1log)/(log)/(jijijiyxpyxpyxI 信息论基础B292.2离散信源熵与互信息离散信源熵与互信息n联合自信息、条件自信息与自信息间的关系联合自信息、条件自信息与自信息间的关系)/()/()()()()()()/()()/(log)(log)/()(log),(log),()/()()/()(),(12112121NNN

16、xxxxIxxIxIxxxIyIxIxyIyxxyIxIxypxpxypxpyxpyxIyxpypxypxpyxp推广相互独立和当信息论基础B302.2离散信源熵与互信息离散信源熵与互信息 Eg1 设在一正方形棋盘上共有设在一正方形棋盘上共有64个方格，如果甲将个方格，如果甲将一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋子所在的位置：子所在的位置： （1）将方格按顺序编号，令乙猜测棋子所在方格的）将方格按顺序编号，令乙猜测棋子所在方格的顺序号顺序号 （2）将方格按行和列编号，甲将棋子所在的方格的）将方格按行和列编号，甲将棋子所在的方格的行（或列）

17、编号告诉乙，再令乙猜测棋子所在列（或行（或列）编号告诉乙，再令乙猜测棋子所在列（或行）所在的位置行）所在的位置。信息论基础B312.2离散信源熵与互信息离散信源熵与互信息 解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此棋子在棋盘中所处位置为二维等概率分布棋子在棋盘中所处位置为二维等概率分布 （1）联合（自）信息量为）联合（自）信息量为 （2）条件（自）信息量为）条件（自）信息量为641),(jiyxpbityxpyxIjiji6641log),(log),(22bitypyxpyxpyxIjjijiji381log)(),(log)/(

18、log)/(222信息论基础B322.2离散信源熵与互信息离散信源熵与互信息 Eg2. 一个布袋内放一个布袋内放100个球，其中个球，其中80个球为红色，个球为红色，20球为白色。若随机摸取一个球，猜测其颜色，求平球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。均摸取一次所获得的（自）信息量。 解：随机事件的概率空间为解：随机事件的概率空间为2 . 08 . 021xxPX信息论基础B332.2离散信源熵与互信息离散信源熵与互信息iiixpxpxIxpxIxpINxIxNpxIxNpINbitxpxIbitxpxI)(log)()()()()()2 . 0log2

19、. 08 . 0log8 . 0()()()()(2 . 0log)(log)(8 . 0log)(log)(221122221122222121量为平均每次所获得的信息次后所获得的信息量为信息论基础B342.2离散信源熵与互信息离散信源熵与互信息n单符号离散信源熵单符号离散信源熵l定义：对于给定离散概率空间表示的信源所定定义：对于给定离散概率空间表示的信源所定义的随机变量义的随机变量I的数学期望为的数学期望为信源的信息熵信源的信息熵，单位为单位为比特比特/符号符号iiixpxpxIEXH)(log)()()(信息论基础B352.2离散信源熵与互信息离散信源熵与互信息n离散信源条件熵离散信源条

20、件熵l定义：对于给定离散概率空间表示的信源所定义的随定义：对于给定离散概率空间表示的信源所定义的随机变量机变量I（x/y)在集合在集合X上的数学期望为给定上的数学期望为给定y条件下条件下信源的条件熵信源的条件熵，单位为单位为比特比特/序列序列iiiyxpyxpyXIEyXH)/(log)/()/()/(jijijijyxpyxpypyXHEYXH,)/(log)/()()/()/(信息论基础B362.2离散信源熵与互信息离散信源熵与互信息n离散信源联合熵离散信源联合熵l定义：对于给定离散概率空间表示的信源所定义的随定义：对于给定离散概率空间表示的信源所定义的随机变量机变量I（x，y)的数学期望

21、为集合的数学期望为集合X和集合和集合Y的的信源联信源联合熵，合熵，单位为单位为比特比特/序列序列jijijiyxpyxpxyIEXYH,),(log),()()(信息论基础B372.2离散信源熵与互信息离散信源熵与互信息n联合熵、条件熵与熵的关系联合熵、条件熵与熵的关系)/()/()()()()()()/()()()/()()()/()()/()(),(12112121NNNXXXXHXXHXHXXXHYHXHXYHYXYXHYHXYHXYHXHXYHyxpypxypxpyxp推广相互独立和当集合信息论基础B382.2离散信源熵与互信息离散信源熵与互信息n单符号离散信源互信息单符号离散信源互信

22、息l定义：对于给定离散概率空间表示的信源，在定义：对于给定离散概率空间表示的信源，在出现出现y事件后所提供有关事件事件后所提供有关事件x的信息量定义互的信息量定义互信息信息，单位为单位为比特比特YyXxxpyxpyxIa,)()/(log);(信息论基础B392.2离散信源熵与互信息离散信源熵与互信息n单符号离散信源互信息单符号离散信源互信息);()()/(log)()()/()(log)()(),(log)()()()/(log)()/(log);(xyIypxypypxpxypxpypxpyxpypxpypyxpxpyxpyxI信息论基础B402.2离散信源熵与互信息离散信源熵与互信息n条

23、件互信息量与联合互信息量条件互信息量与联合互信息量l定义：对于给定离散概率空间表示的信源，在定义：对于给定离散概率空间表示的信源，在事件事件z给定条件下，事件给定条件下，事件x与事件与事件y之间的条件之间的条件互信息量为：互信息量为：ZzYyXxzxpyzxpzyxIa,)/()/(log)/;(信息论基础B412.2离散信源熵与互信息离散信源熵与互信息n条件互信息量与联合互信息量条件互信息量与联合互信息量l定义：对于给定离散概率空间表示的信源，在定义：对于给定离散概率空间表示的信源，在事件事件x与联合事件与联合事件yz之间的联合互信息量为：之间的联合互信息量为：ZzYyXxxpyzxpyzx

24、Ia,)()/(log);(信息论基础B422.2离散信源熵与互信息离散信源熵与互信息nEg1(p23) 设信源发出设信源发出8种消息符号，各消息等概发送种消息符号，各消息等概发送，各符号分别用，各符号分别用3位二进码元表示，并输出事件。通位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设信源发过对输出事件的观察来推测信源的输出。假设信源发出的消息出的消息x4，用二进码用二进码011表示，表示， 接收到每个二进制接收到每个二进制码元后得到有关码元后得到有关x4信息。信息。ZzYyXxxpyzxpyzxIa,)()/(log);(信息论基础B432.2离散信源熵与互信息离散信

25、源熵与互信息符号符号符号/3811log)011;(/28121log)01;(/18141log)0 ;(444bitxIbitxIbitxIaaa信息论基础B442.2离散信源熵与互信息离散信源熵与互信息n平均互信息量平均互信息量 其中其中yxypxypyxypxpyxpyxxpyxpyxpyxpyxpYXI,)()/(,)()(),(,)()/(log),(log),(log),();(),()()()/()()/()();();(YXHYHXHXYHYHYXHXHXYIYXIyxyxpyxpYXH,),(1log),(),(信息论基础B452.2离散信源熵与互信息离散信源熵与互信息n熵

26、的性质熵的性质u对称性对称性u非负性非负性u确定性确定性u香农辅助定理香农辅助定理u最大熵定理最大熵定理u条件熵小于无条件熵条件熵小于无条件熵信息论基础B462.2离散信源熵与互信息离散信源熵与互信息n非负性非负性0)(0)log(lim0log0log, 100),()(021XHpppppppppHXHiipiiiini信息论基础B472.2离散信源熵与互信息离散信源熵与互信息n对称性对称性信息熵相同613121216131612131),(),()(3213213211121cccpZbbbpYaaapXpppHpppHXHnnn信息论基础B482.2离散信源熵与互信息离散信源熵与互信息

27、n确定性确定性 n香农辅助定理香农辅助定理0)0, 0 , 1 ()0 , 0 , 1 ()0 , 1 (HHHiiiiiiqppppppHloglog),(321信息论基础B492.2离散信源熵与互信息离散信源熵与互信息n最大熵定理最大熵定理 n条件熵小于无条件熵条件熵小于无条件熵MMMMHXHlog)1,1,1()()()/(YHXYH信息论基础B502.2离散信源熵与互信息离散信源熵与互信息n平均互信息的性质平均互信息的性质u非负性非负性u互易性互易性u与熵和条件熵及联合熵关系与熵和条件熵及联合熵关系u极值性极值性u凸性函数性质凸性函数性质u信息不增性原理信息不增性原理信息论基础B512

28、.2离散信源熵与互信息离散信源熵与互信息n非负性非负性0);();(0);(, 0);(0 1)/()()/(log)/()(log)/();(0);(yXIEYXIYxIyXIyxpxpyxpeyxpxpyxpyXIYXIyxx同理信息论基础B522.2离散信源熵与互信息离散信源熵与互信息n互易性互易性);()()/(log)()()/(log)();();();(,XYIypxypxypxpyxpxypYXIXYIYXIyxyx信息论基础B532.2离散信源熵与互信息离散信源熵与互信息n平均互信息与熵的关系平均互信息与熵的关系)/()()/()(log)()/(log)()(log)()(

29、)/(log)();()()()()/()()/()();(,YXHXHYXHxpxpyxpxypxpxypxpyxpxypYXIXYHYHXHXYHYHYXHXHYXIxyxyxyx信息论基础B542.2离散信源熵与互信息离散信源熵与互信息n互信息量与熵的关系互信息量与熵的关系信息论基础B552.2离散信源熵与互信息离散信源熵与互信息n极值性极值性0);(,)();()();(YXIYXYHXYIXHYXI独立当信息论基础B562.2离散信源熵与互信息离散信源熵与互信息n凸性函数凸性函数u当条件概率分布给定时，平均互信息量是输入当条件概率分布给定时，平均互信息量是输入概率分布的上凸函数概率分

30、布的上凸函数u当集合当集合X的概率分布保持不变时，平均互信息的概率分布保持不变时，平均互信息量是条件概率分布的下凸函数量是条件概率分布的下凸函数信息论基础B572.2离散信源熵与互信息离散信源熵与互信息n信息不增性信息不增性);();()/;();();(0)/;()/;()/;();();()/;();();()/;();();(YXIZXIZYXIYXIZXIYZXIZXYXYXIYZXIYXIZXIZYXIZXIYZXIYZXIYXIYZXIZXY相互独立与条件下在相互独立与条件下假设在信息论基础B58 2.3离散序列信源的熵离散序列信源的熵n离散无记忆信源的序列熵离散无记忆信源的序列熵

31、n离散有记忆信源的序列熵离散有记忆信源的序列熵信息论基础B59 2.3离散序列信源的熵离散序列信源的熵n离散无记忆信源的序列熵离散无记忆信源的序列熵 LllnininiiLiLiLinininiiiiLininiiLiiLiiniiLiiiniiiXHxpxpxpxpxpxpxpxpxpxpxpxpxpHxpxpxppppHLLLL11111112111211211)()(log)()()()(log)()()()(log)()log()()()()()()()()(log)()(111112XxxxX信息论基础B60 2.3离散序列信源的熵离散序列信源的熵n离散无记忆信源的序列熵离散无记忆信

32、源的序列熵n平均每个符号熵（消息熵）平均每个符号熵（消息熵）)(1)(XXHLHL信息论基础B61 2.3离散序列信源的熵离散序列信源的熵n离散有记忆信源的序列熵和消息熵离散有记忆信源的序列熵和消息熵LlllLLLlllLLXXHLHLHXXHXXXHXXHXHH111111121)/(1)(1)()/()/()/()()(XXX信息论基础B62 2.3离散序列信源的熵离散序列信源的熵nEg 求信源的序列熵和平均符号熵求信源的序列熵和平均符号熵 41943611321aaaPXa1a2a3a1a2a39/111/802/113/42/901/87/9信息论基础B63 2.3离散序列信源的熵离散

33、序列信源的熵n离散有记忆信源的序列熵和消息熵离散有记忆信源的序列熵和消息熵结论结论1 是是L的单调非增函数的单调非增函数结论结论2结论结论3 是是L的单调非增函数的单调非增函数结论结论4)/(1LLXXH)/()(1LLLXXHHX)(XLH),/(lim)(lim)(121LLLLLXXXXHHHLXX当信息论基础B64 2.3离散序列信源的熵离散序列信源的熵n马氏链极限熵马氏链极限熵)(),/(),/(log),(),/(log),()/(),/(11,;,111111111111111XHXXXHxxxpxxpxxxpsxxpsxpxxxp、mmiiiiiiiiiiiiiiiiiiiii

34、mmmmmmmmmmm左边遍历马氏链对于齐次信息论基础B65 2.3离散序列信源的熵离散序列信源的熵 iiiiiiiiiiiiiiiiiiiiiiiiiiisXHspHsXHspsxpsxpspsxpsxpsxpsxxpmmmmmmmmm)/()()X()/()()/(log)/()()/(log),()/(log),(11111111111,;,右边右边信息论基础B66 2.3离散序列信源的熵离散序列信源的熵nEg 求马氏链平均符号熵（三个状态）求马氏链平均符号熵（三个状态）8 . 02 . 005 . 005 . 09 . 001 . 0P信息论基础B67 2.4连续信源的熵与互信息连续信源的熵与互信息n幅度连续的单个符号信源熵幅度连续的单个符号信源熵xdxxpxdxxpxpXHXHxxpxxpxpxpXHxxpdxxpxpxiaxiaxnabxbaxnbaiXnbaiXiXnnniiXiXniiinxiaxiaiXXiiloglim)(loglim)(log)()(lim)()(log)()(log)()()()()(,) 1(,/ )(,11) 1(b ba ai iX Xi iX X) )d dx x