信息论与编码第二章

1、 从有效而可靠地传输信息的观点出发，对组成信息传输系统的各个部分分别进行讨论。 本章首先讨论信源，重点是其统计特性和数学模型，以及离散信源的信息测度熵及其性质。引入信息理论的一些基本概念和重要结论。第二章 离散信源2.1 信源的数学模型及分类 只研究信源的输出，以及信源输出各种可能消息的不确定性。离散信源离散信源：信源可能发出的不同符号数是有限的，或是无限可列的；连续信源连续信源：消息的取值是连续的，即可能出现的消息数是不可数的无限值。 样本空间样本空间：信源输出所有消息的集合信源空间信源空间：样本空间+概率 （概率空间概率空间）完备性描述完备性描述： 用离散型随机变量或随机矢量来描述信源输出

2、的消息 qiap11)()(),(),(,: )(:,2121qqapapapaaqxpxpx离散信源 的数学模型用连续型随机变量来描述这些消息 )(),(: )(:,xpbaxpxpx)(xpRbaRdxxpdxxp1)()(连续信源 的数学模型 离散信源的简单情形是信源发出的消息是由单个符号构成的。掷骰子的结果作为信源消息，则就构成了一个这样的信源，其概率空间为： 箱中有赤、橙、黄、青、兰、紫六种颜色的32只彩球，其中赤16球，澄8球，黄4球，青2球，蓝、紫各1球。有放回抽取： 6/16/16/16/16/16/1)(654321aaaaaaxpx32/132/116/18/14/12/1

3、)(紫蓝青黄橙赤xpx2.2离散信源的自信息和信息熵2.2.1 自信息问题问题：信源发出某一符号ai后，能提供多少信息量？ 信息如何进行度量？ 收到某消息获得的信息量=不确定性减少的量=收到bj前、后对某事件ai存在的不确定性消除的量=收信前关于某事件的不确定性（先验不定度）收信后关于某事件发生的不确定性（后验不定度） 信息量与事件发生的不确定性有关，不确定性与事件发生的概率有关，应是一个函数关系 。 自信息量 ： ：事件ai发生的先验概率 )()(iiapfaI)(iap四条公理1、概率大，发生的可能性大，不确定性小， 是先验概率的单调递减函数；2、必然事件，不含信息量；3、不可能事件发生了

4、，剌激大，冲击函数4、独立事件的联合信息量，应等于它们各自信息量之和。)()(21apap12()()f pf p1)(iap0)(ipf0)(iap)(ipf)()()(log)(log)()(log)(log)(),(jijijijijijibIaIbpapbpapbapbapfbaI自信息的表达式自信息的单位取决于对数的底 ：2为底，bit；e为底，nat；10为底，Hart I(ai)有两层含义：第一事件ai发生前，收信者对ai存在的先验不确定性；第二事件ai发生后，ai所含有的（提供的）全部信息量。二进制的一位能提供的最大信息量为1bit bitnat44. 11bitHart32.

5、 31)(/1log)(iiapaI2.2.2 信息熵问题：不同的符号有不同的自信息量 自信息量I(ai)在概率空间中的统计平均值 信息单位信源符号 信源每发一个符号所提供的权平均信息量，称为“信息熵”。当对数的底为r时，可记为： 以2为底时，常简记H(x)。qiiiapapXH1)(log)()()(XHr物理含义。 (1) H(X)表示信源每发一个符号所提供的平均信息量； (2) H(X)表示信源X输出前，信源的平均不确定性；（3）H(X)表征随机性的大小。 一般情况下它并不等于平均获得的信息量，只是在信道无噪时，两者才相等。 需要注意需要注意：1.尽管小概率事件如发生会提供很大的自信息量

6、，但由于其发生的概率非常小，所以不会对熵值产生特别的影响。2.当样本空间增大时，信源的熵值将增大，既平均每条消息所含的信息量增大（可能的结果越多，随机性越大）。 2.2.3 熵的基本性质（1）对称性（2）确定性 （3）非负性 （4）扩展性 （5）可加性（6）强可加性（7）极值性 2.3 离散无记忆的扩展信源离散无记忆N次扩展信源熵为：证明：qqppaaxpx.)(11)()()()()()()()(1131121111131121112121qqqqqqqqaaapaaapaaapaaapaaaaaaaaaaaappppNNxxNqiiiNNXNHppXXXHXH121)()(log)().(

7、)(NqiiiNapapXH1)(log)()( qiqiiNiiiNiiNaaapaaap1121211).(log).(. qiqiiNiiiNiiNapapapaaap1121211)().()(log).(. qiqiqiqiiiNiiiiNiiNNapaaapapaaap111122112111)(log).(.)(log).(. qiqiiNiNiiNapaaap11211)(log).(.qiiNiNqiiiNapapNapap1111)(log)(.1) 1()(log)(1)()()(21NXHXHXH2.4 离散平稳信源一般情况下，t不同，概率分布也不同 假定随机矢量 中各

8、维联合概率分布均不随时间的推移而变化，即统计性质与时间无关，称为离散平稳信源。 平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关。换句话说，任何时刻发出什么符号只与前N个符号有关，与t无关 )()(jixpxp)|()|(2121NjjjjNiiiixxxxpxxxxp321xxxx )|()|()|(1101111NNNjjjNjNiiiNixxxxpxxxxpxxxxp 条件熵与无条件熵之间的关系 )()|(YHXYH2.5 离散平稳信源的极限熵 问题：问题：时间域上一个无限长的符号序列，又因为信源有记忆，符号间依赖的关系会延伸至无穷，这种情况下，信源每输出一个符号平均提供多大的信息

9、量？ 的几个特性：（1）证：由熵的定义：).(lim211NNNXXXHH).(21NXXXH).(21NXXXH)|()|()(121121NNXXXXHXXHXHNqiiiNapapxxHXH11)(log)()()(N个分量统计关联的随机矢量 的联合熵 ，等于起始时刻的无条件熵与各阶条件熵之和，并不随时间的推移而变化。 qiqiiNiiiNiiiiNiiNaaaapaapapaaap1112112121|()|()(log)( qiqiqiqiiiiNiiiNiiNNaapaapapaaap11111211211)/(log)()(log)( qiqiiNiiNiNiNNaaapaap1

10、1111)|(log)(qiqiqiiiiiiiaapaapapap111122111112)./(log)()(log)(1122111()log(/)NqqiiiNiNiiNiip a aap aaa )|()|()(121121NNXXXXHXXHXH21Nxxxx)(1NXXH（2）条件熵随N的增加是非递增的证明： 类似， ， 因为信源是平稳的，所以有 推广平均符号熵 ：)|()()(12112XXHXHXXH)()|(212XHXXH)|()|(23213XXHXXXH)()|()|(112213XHXXHXXXH)|()|(21111NNNNXXXHXXXH)|(312NNXXXH

11、)()|()|(112213XHXXHXXXH)()(211NNNXXXHXH根据右端每项全用最小项代替 ，有即平均熵大与N阶条件熵 )|()|()()(111211NNNXXXHXXHXHXXH)|()(11NNNXXXHXH（3）).()(11NNNXXHXH 的极限值存在，且为零与H（X）之间的某一有限值 )|()()(1211211NNNNXXXXHXXXHXXH)|()()()(111211NNNNNXXXHXXXHXXHXNH).|()() 1(111NNNXXXHXHN)()() 1()(1XHXHNXNHNNN 移项得)() 1()()(1XHNXHXNHNNN)()(1XHX

12、HNN得即HN随N非递增。反复运用上式并考虑到， 可得： 其中： ， 表明，平均符号熵HN（X）的最大值就是原始信源X p的熵，而且它随N的增加是非递增的。HN（X）由熵的非负性亦具非负性，所以HN（X）的极限 HN(X)一定存在，且是处于零和H（X）之间的某一有限值。下面求此极限熵。0)(XHN)()()()(0121XHXHXHXHNNN)()(1xHXH设一整数 ,有： 根据条件熵的递减性和平稳性有： k)(1)(1kNNkNXXXHkNXH)|()|()(1111111kNkNNNNXXXHXXXHXXHkN)/()|()|()(1)(11111111NNNNNNNkNxxxHXXXH

13、XXXHXXHkNXH)|(1)(11111NNNXXXHkNkXXHkNk，固定N ,N)(11NXXH和)|(11NNXXXH为定值，所以前一项01 kN )/()(lim11NNkNkXXXHXH)(1lim)(lim1NNNNXXHNXHHHXHXXxHXHNNN)()|()(11再令N，因极限存在 HXHNN)(lim)|(lim)(lim)(11NNNNNXXXHXHXH即：2.6 马尔柯夫信源2.6.1 马氏链的基本概念和主要特性 设序列 的取值是整数， ， ，若对任意非负整数, 有： 马尔柯夫性（无后效性）马尔柯夫性（无后效性） 一旦“现在”已知，“将来”只决定于“现在”而与“

14、过去”无关。 “Markov链” 2 , 1 , 0),(nnxllitx)(jtx)(ttttr210)(,)(,(2211rritxitxitxp)|()|(21rrijpiiijp 马氏链的最基本的统计特性 这个条件概率称为马氏链在时刻m的状态一步转移概率。 定义马氏链在时刻m的k步转移概率 : 使用全概率公式， )()(|) 1(mpimxjmxpij)()(/)()(mpimxjkmxpkij并规定： jijimpijij, 0, 1)()0()()()()()()(kmpmpmplsjIskislkij)2()() 1()()()2(1) 1() 1()(1mppmpmpmpmpn

15、jsIsmssIsIsisnsjisnijIsjsssisIsIsnnnmpmpmp1111) 1() 1()(马氏链x(n)的统计特性可由起始概率和各时刻的一步转移概率得到完整描述。如果马氏链是平稳的，即, 2 , 1 , 0),(nnx的起始概率和一步转移概率与时刻m无关，则多步转移概率和联合概率同样与时间无关。称时齐马氏链。, 2 , 1 , 0),(nnx2.6.2 马尔柯夫信源 信源当前输出的符号与前面的符号相关联 ，但可以考虑将记忆割断 ，如果在任何时刻其符号发生的概率只与前面已经发生的m个符号有关，而与更前面发生的符号无关，则称该信源为m价马尔柯夫信源，其数学模型为： 将前面m个

16、符号看作为m阶M信源在此时刻所处的状态。 )|(,21121mmkkkkqaaaapaaaqkkkkkmmmaaaap112111)|(qkkkkmm2 , 1,121)|()|()|(111ikikmkmkkmsapsapaaap将信源发出一串二进制序列转换成状态的序列，此状态序列构成时齐马尔柯夫链 遍历的马可夫信源：状态序列是遍历的马尔可夫链所对应的信源。 遍历（各态历经性），各态相通，均可经历。状态空间A= 构成的集合组成一个不可约闭集（不可再分出另一个闭集） 对于时齐、遍历的马可夫链，一定存在一个极限的概率 Q（si）满足： rSS ,.1)(lim)|(lim)(ljiljlilli

17、psssspsQEs 1EsiSSijiijijijjsQspsspEsisQsspsQ1)()()()()/()( Q(si)表示当转移步数l足够长以后，状态的l步转移概率与初始状态无关。它意味着信源在初始时刻可以处在任意状态，然后状态之间可以互相转移。经过足够长时间后，信源处于什么状态已与初始状态无关信源处于什么状态已与初始状态无关，这时稳定后处于每种状态出现的概率已达到一种稳定分布 时齐、遍历时齐、遍历的m阶马可夫信源，时间足够长后，可作为平稳平稳信源处理，信源发出的符号只与前m个符号有关，其极限熵为： 即m阶M信源的极限熵就等于m阶条件熵 )|(lim11NNNxxxHH qkqkkN

18、kkNkNkNnaaapaap111111)|(log)(limqkqkNkmkkmkNkNaaapaap111111)|(log)(limqkqkmkmkkmkmkaaapaap11111111)|(log)(1211)/(mmmHxxxxH)|()|()|(211ijikkmkkkmsspsapaaaap)|()()|()()(111ikiikkmkkmksapsQsapaapaap11( ) (/)log(/)mqqmikikiijHHQ s p asp as 例：某二进制二阶M信源x符号集0，1，起始概率（一维分布）为： ，下一单位时间的R、V，x2与x1的依赖关系由条件概率 决定： p (00)0.3 p (10)0.7 p (01)0.4 p (110.6 再下一单位时间， x3与x1 x2有依赖关系，且由二维条件概率： p (000)p (0s1)0.4, p (100)p (1s1)0.6 p (001)p (0s2)0.2, p (101)p (1s2)0.8 p (010)p (0s3)0.3, p (