第二章-信息论基本概念

1、回顾：回顾：单符号无记忆信源熵：单符号无记忆信源熵：H(X) bit/符号符号符号序列无记忆信源熵：符号序列无记忆信源熵：KH(X) bit/序列序列 符号序列有记忆信源熵：联合熵符号序列有记忆信源熵：联合熵 H(X1X2XN) bit/序列序列 平均符号熵平均符号熵 极限熵极限熵121lim()lim()bit/NNNNHHH X XXNX符号121() bit/NH X XXN符号121lim()lim(/)bit/NNNNNHHH XX XXX符号平稳信源平稳信源马尔可夫信源马尔可夫信源有记忆的特点：1、有限记忆长度2、信源输出不仅与符号集有关，而且与状态有关3、发出一个个符号，每发一个

2、符号状态要发生转移状态：状态：有限的相关符号组构成的序列马尔可夫信源：马尔可夫信源：以信源输出符号序列内各 符号间条件概率来反映记忆特性的一类信源。m阶马尔可夫信源：阶马尔可夫信源：信源输出的当前符号仅与前面m个符号有关的马尔可夫信源。1111211()()(,)mmmnimmiiiiix xxXxXPpXXxxsxx此时，状态模型阶马尔可夫信源的数学m121, ,1,2,mi iin马尔可夫信源的定义马尔可夫信源的定义：（1）某一时刻信源符号的输出只与当前的信源状态）某一时刻信源符号的输出只与当前的信源状态有关，而与以前的状态无关。有关，而与以前的状态无关。 (2) 信源状态只由当前输出符号

3、和前一时刻的信源状信源状态只由当前输出符号和前一时刻的信源状态唯一确定。态唯一确定。llXXXX121输出符号序列：llSSSS121输出状态序列：符号条件概率:状态转移概率:)(iksxp)(ijssp通过引入符号条件概率和状态转移概率,马尔可夫信源可转化为马尔可夫链。一步转移概率：一步转移概率：1( )(|)ijmjmip mp SsSs1( )(|)ijmjmiijp mp SsSsp对于齐次马尔可夫链，有(|)kip xs状态转移概率可用条件概率计算。转移概率矩阵和状态转移图转移概率矩阵和状态转移图（香农线图）（香农线图）1111.=.qqqqppPpp状态转移图（香农线图）状态转移图

4、（香农线图）圆圈表示状态。圆圈表示状态。状态之间的有向线段表示状态转移。状态之间的有向线段表示状态转移。有向线段边的符号和数字代表发出的符号和条件概率。有向线段边的符号和数字代表发出的符号和条件概率。 马尔可夫链可以用香农线图表示。马尔可夫链可以用香农线图表示。(a),(b),(c)(a),(b),(c)分别表示信源含两种字母分别表示信源含两种字母(D(D2)2)的一的一阶、二阶和三阶马尔可夫链的线图。阶、二阶和三阶马尔可夫链的线图。(d),(e)(d),(e)分别表示分别表示D D3 3和和D D4 4的一阶马尔可夫链的的一阶马尔可夫链的线图。线图。AA(A)(B)BB(a)(AAA)(BB

5、B)(ABB)(BAA)(BBA)(AAB)(ABA)(BAB)ABBBAAAABBBAABBA(c)(A)(B)(C)(D)ACBCBDBAAACDDBCD(e)2k.K,4. X ,kkXX XXX12mkiiii112n1 输出的消息是符号序列： x xx2 发出的符号序列是顺序发出3 在第 次发出的符号x 取自单符号信源从而信源模型可以表示为：x xx马尔可夫信源的特点：马尔可夫信源的特点：15.)(|)kk mkiiikp xxxkk-mk-m+1k-1iiii在第 次发出的符号x 与前面m个符号有关。（xxx称为状态这种关联性用条件概率表示：111106.)(|)(|)7.(|)(

6、|)(|)kk mkmjmiiiimjmijijikp SsSsp xxxp SsSsp SsSsp sskk-mk-m+1k-1k-m+1k-m+1kiiiiijiii在第 次发出的符号x ,状态改变s =（xxxs =（xxx用状态转移概率表示：齐次马尔可夫信源例：例：(0|00)(1|11)0.8(1|00)(0|11)0.2(0|01)(0|10)0.5(1|01)(1|10)0.5pppppppp设有一个二进制二阶马尔可夫信源，其信源符号集为0,1, 条件概率为求状态转移矩阵，并给出香农线图。1234112132421323344400010(|)(0|00)0.8(|)(1|00)

7、0.2(|)(0|01)0.5(|)(1|01)0.5(|)(0|10)0.5(|)(1|10)0.5(|)(0|11)0.2(|)(1|11)0.8ssssp sspp sspp sspp sspp sspp sspp sspp ssp令 ， ， 1 ， 11，转移概率矩阵P为0.80.P=00000.50.50.50.500000.20.82001001110.80.20.50.50.50.20.50.8m阶马尔可夫信源的极限熵阶马尔可夫信源的极限熵121lim()NNNXHHX XX111)(mmmHXXXH)s/X(H)s (p)/sx(logp)s/x(p)s (p)/sx(logp

8、)s ,x(p)XXX/X(HHHin1iin1in1jijijin1in1jijijm211m1mmmmP(si)为状态概率的平稳分布，由转移概率矩阵决定，H(X/si)表示信源处于某一状态si时发出某一个消息符号的平均不确定性。遍历性遍历性 对于齐次马尔可夫链，若对于所有状态si , sj , 均存在不依赖于初始状态si 的极限1,0lim)(jjijiijjnijnpppppp且满足则称其为具有遍历性的马尔可夫链。遍历性的意义遍历性的意义 无论从哪个状态出发，当转移步数足够大时，转移到状态sj的概率近似等于一个常数pj。也就是说：马尔可夫链在初始时刻可以处于任意状态，经过足够长时间的状态

9、转移后，它所处的状态与初始状态无关。此时每种状态出现的概率已达到一种平稳分布。()lim()jjkjkpp sp Ss称为状态的平稳分布。jijiiWpWWPW即有对齐次马尔可夫链，例例: 一个二阶马尔可夫信源，其香农线图如下，求其信源熵。001001110.80.20.50.50.50.20.50.81234112132421323344400010(|)(0|00)0.8(|)(1|00)0.2(|)(0|01)0.5(|)(1|01)0.5(|)(0|10)0.5(|)(1|10)0.5(|)(0|11)0.2(|)(1|11)0.8ssssp sspp sspp sspp sspp s

10、spp sspp sspp ssp令 ， ， 1 ， 11，转移概率矩阵P为0.80.P=00000.50.50.50.500000.20.82令平稳分布： 4321,spspspspW 则： 41iijijjsspspspW写成矩阵形式：WPW 145( )()14p sp s232()()14p sp s)5.0log5.05.0log5.0()/()/()2.0log2.08.0log8.0()/()/()/(log)/()/()(8.0)/()(324121413sXHsXHsXHsXHsxpsxpsXHbitsXHspHHijijjiiii这里：符号注意：注意：1、平稳信源，即其概率

11、分布具有时间推移不变性。Hnm一、并非在任何情况下都存在，对 元阶马尔可夫信源2()1,2,mjp sjn、存在，二、m阶马尔可夫与发生长度为m的符号序列的有记忆信源的区别：1、马尔可夫信源发出一个个符号，有限长度有记忆信源发出一组组符号；2、马尔可夫信源记忆长度虽然有限，但依赖关系延伸到无穷远。长为m的有限记忆信源符号间的依赖关系仅限于每组内，组与组之间没有依赖关系；有记忆信源的极限熵是平均符号熵的极限。是条件熵，熵、马尔可夫信源的极限13mH)(1limXHNN例：设某信源符号例：设某信源符号XA=a1,a2,a3,信源所处的状态信源所处的状态SE=E1,E2,E3,E4,E5.各状态之间

12、的转移情况如下各状态之间的转移情况如下图所示，请判断这是否是一个马尔可夫信源？图所示，请判断这是否是一个马尔可夫信源？马尔可夫信源定义：若一信源满足下列两点，即为马尔可夫信源。输出符号只与当前状态有关；(1) 当前状态和输出唯一决定了下一状态。解解：（：（1）信源在）信源在Ei状态下输出符号状态下输出符号ak的条件概率的条件概率p(ak/Ei)用矩阵用矩阵表示为表示为2141410014104321210414121)|(ikEap31(|)1,1,2,3,4,5kikp aEi并且满足并且满足（2）该信源在）该信源在l时刻所处的状态由当前的输出符号与前一时刻时刻所处的状态由当前的输出符号与前

13、一时刻(l-1)信源的状态唯一决定信源的状态唯一决定状态的一步转移概率：状态的一步转移概率：1 11002 441 100 02 23 1 (|)00 04 40 0 00 13 10 0 04 4jip EE此信源满足马尔可夫信源的两个条件，此信源满足马尔可夫信源的两个条件，是马尔可夫信源，并且是齐次马尔可夫信源。是马尔可夫信源，并且是齐次马尔可夫信源。 例：例： 设两位二进制码所代表的四个状态分别为设两位二进制码所代表的四个状态分别为 0000，0101，1010，1111，其，其符号转移概率和状态转移概率由下列两表给出：符号转移概率和状态转移概率由下列两表给出： 试求稳定条件下各状态的概

14、率试求稳定条件下各状态的概率起始状态发出符号S0(00)S1(01)S2(10)S3(11) 011/21/31/41/51/22/33/44/5起始状态终止状态S0(00)S1(01)S1(01)S2(10)S3(11)S0(00)S2(10) S3(11)1/201/4 01/203/40 01/301/5 02/3 04/5 解：据题意，可画出相应的香农线图解：据题意，可画出相应的香农线图 设稳定状态下，各个状态的概率为设稳定状态下，各个状态的概率为 P(SP(S0 0) )P P0 0， P(SP(S1 1) )P P1 1， P(SP(S2 2) )P P2 2， P(SP(S3 3

15、) )P P3 3 根据图示，可得根据图示，可得 P P0 0 1/2P1/2P0 0 1/4P1/4P2 2 P P1 1 1/2P1/2P0 0 3/4P3/4P2 2 P P2 2 1/3P1/3P1 1 1/5P1/5P3 3 P P3 3 4/5P4/5P3 3 2/3P2/3P1 1 P P0 0 P P1 1 P P2 2 P P3 3 1 1 由上面五个方程，可得：由上面五个方程，可得： P P0 03/35 3/35 ， P P1 16/35, P6/35, P2 26/356/35， P P3 34/74/7(01)(10)(11)011110001/21/21/32/31

16、/43/4(00)1/54/5 例：有一个一阶马尔可夫信源，已知例：有一个一阶马尔可夫信源，已知 试画出该信源的香农线图，并求出信源熵。试画出该信源的香农线图，并求出信源熵。 解：该信源的香农线图为：解：该信源的香农线图为： 在计算信源熵之前，先用转移概率求稳定状态下二个状态在计算信源熵之前，先用转移概率求稳定状态下二个状态x1和和 x2 的概率的概率 和和 3211)(xxp3112)(xxp1)(21xxp0)(22xxp1/3(x2)(x1)2/31)(2xp)(1xp)()()(21321xpxpxp)(0)()(21312xpxpxp1)()(21xpxp4/ 3)(1xp4/ 1)

17、(2xp2211()()log()322111loglog1 log14333340.689ijijiijHp xp x xp x x bit/符号 小结小结 两种有记记忆信源比较两种有记记忆信源比较类型类型 m阶马氏过程阶马氏过程 m长有记忆信源长有记忆信源 依赖关系依赖关系(相当于相当于)记忆长度为记忆长度为m符号间关系可延伸到无穷符号间关系可延伸到无穷（卷积码）（卷积码） m个符号为一组个符号为一组组内相关，组间无关组内相关，组间无关（分组码）（分组码） 描述描述 状态转移状态转移(条件条件)概率概率 联合概率联合概率 每符号每符号平均熵平均熵 极限熵极限熵Hm+1 Hm(X)=(1/m

18、)H(X1X2Xm) 总结总结: :各种离散信源的熵各种离散信源的熵 (1) (1) 发出单个符号消息的离散无记忆信源熵发出单个符号消息的离散无记忆信源熵 若信源发出若信源发出N N个不同符号个不同符号X1，X2，Xi，XN , 代表代表N N种不种不同的消息，各个符号的概率分别为同的消息，各个符号的概率分别为 P P1 1， P P2 2， P Pi，P PN N 因为这些符号相互独立，所以该信源熵为：因为这些符号相互独立，所以该信源熵为： H H（X X） P PiloglogP Pi bit/ bit/符号符号 (2)(2)发出符号序列消息的离散无记忆信源熵发出符号序列消息的离散无记忆信

19、源熵 发出发出K K重符号序列消息的离散无记忆信源熵为共熵重符号序列消息的离散无记忆信源熵为共熵H(XH(XK K) )，它与，它与单个符号消息信源熵单个符号消息信源熵H(X)H(X)有如下关系：有如下关系： H(XH(XK K) )KH(X)KH(X)KK P PiloglogP Pi bit/ bit/符号序列符号序列 Ni 1Ni 1 (3)(3)发出符号序列消息的离散有记忆信源熵发出符号序列消息的离散有记忆信源熵 发出发出K K重符号序列消息的离散有记忆信源熵也为共熵重符号序列消息的离散有记忆信源熵也为共熵H(XH(XK K) ) 当当K K2 2时时 H(XH(X2 2) )H(X)

20、H(X)H(X|X)H(X|X) H(X|X) H(X) H(X|X) H(X) H(XH(X2 2) 2H(X) 2H(X) 推广到推广到K K重重 H(XH(XK K) )H(X)H(X)H(X|X)H(X|X)H(X|XXX) H(X|XXX) bit/bit/符号序列符号序列 (K1)个个 (4) (4) 发出符号序列消息的马尔可夫信源熵发出符号序列消息的马尔可夫信源熵 马尔可夫信源熵是条件熵马尔可夫信源熵是条件熵 若从前一状态若从前一状态E Ei转移到后一状态转移到后一状态E Ej有多种可能性，则信源由状态有多种可能性，则信源由状态E Ei发出发出一个符号的熵一个符号的熵H H（X/

21、X/i）为为 H H（X/X/i） P(xP(xj j|E|Ei i)logP(x)logP(xj j|E|Ei i) ) 再进一步对前一状态再进一步对前一状态E Ei的全部可能性作统计平均，就得到马尔可夫信源的全部可能性作统计平均，就得到马尔可夫信源熵熵 H H 为为 H H P(EP(Ei i) H) H（X/X/i） P(EP(Ei i) P(x) P(xj j|E|Ei i)logP(x)logP(xj j|E|Ei i) bit/) bit/符号符号 jjii 1.5 1.5 各种离散信源的时间熵各种离散信源的时间熵 信源的时间熵信源的时间熵在单位时间内信源发出的平均信息量，单位在单

22、位时间内信源发出的平均信息量，单位 为为bit/s.bit/s. 发出单个符号消息的离散无记忆信源的时间熵发出单个符号消息的离散无记忆信源的时间熵 已知离散无记忆信源各符号的概率空间已知离散无记忆信源各符号的概率空间 由于发出各符号所占有时间是不同的由于发出各符号所占有时间是不同的 可设符号可设符号X1的长度为的长度为b b1 1，X2为为b b2 2，Xi为为b bi，XN为为b bN 单位均为单位均为s(s(秒秒) ) 则信源各符号的平均长度是各个符号长度的概率加权平均值，则信源各符号的平均长度是各个符号长度的概率加权平均值，即即 X XP(X)P(X)X1，X2， ，Xi，XNP P1

23、1， P P2 2， P Pi， P PNNiiibPb1s/符号 则信源的时间熵则信源的时间熵 H Ht t为：为： 若各符号时间长度相同，均为若各符号时间长度相同，均为b(s)b(s)，则可直接得，则可直接得 又若信源每秒平均发出又若信源每秒平均发出 n n个符号，有个符号，有 此时，此时，时间时间熵熵 H Ht t为：为：NiiiNiiitbPPPbXHH11log)(bit/sbit/sbb bn1符号符号/sNiiitPPnXnHH1log)(bit/sbit/s 发出符号序列消息的离散无记忆信源的时间熵发出符号序列消息的离散无记忆信源的时间熵 对对K K重符号序列的离散无记忆信源的

24、信源熵为：重符号序列的离散无记忆信源的信源熵为： H(XH(XK K) ) KH(X) bit/KH(X) bit/符号序列符号序列 K K重符号序列消息的平均长度为信源各符号平均长度的重符号序列消息的平均长度为信源各符号平均长度的K K倍，即倍，即 这种信源的时间熵这种信源的时间熵 H Ht t为：为： 可见，它在数值上与上面一种信源的时间熵相同可见，它在数值上与上面一种信源的时间熵相同NiiibPKbKB1s/s/符号序列符号序列 NiiiNiiiKtbPPPbXHbKXKHBXHH11log)()()(bit/sbit/s 若该信源每秒内平均发出若该信源每秒内平均发出n n个个K K重符

25、号序列消息，则有：重符号序列消息，则有： 发出符号序列消息的离散有记忆信源的时间熵发出符号序列消息的离散有记忆信源的时间熵 计算方法与发出符号序列无记忆信源的时间熵一致，但计算方法与发出符号序列无记忆信源的时间熵一致，但 H(XH(XK K) ) KH(X) KH(X) 同样若信源在每秒内平均发出同样若信源在每秒内平均发出n n个个K K重符号序列消息，有重符号序列消息，有 )()(XnKHXnHHKtbit/sbit/sbKXHBXHHKKt)()(bit/sbit/s)(KtXnHHbit/sbit/s连续随机变量可以看作是离散随机变量的极限，故可采用离连续随机变量可以看作是离散随机变量的

26、极限，故可采用离散随机变量来逼近。散随机变量来逼近。 首先类比概率首先类比概率p pi i与概率密度函数与概率密度函数p(x)p(x)： （一）单个连续随机变量信源熵（一）单个连续随机变量信源熵 连续信源的熵连续信源的熵令令xa,b，且，且ab,现将它均匀的划分为现将它均匀的划分为n份，每份宽度为份，每份宽度为 ，则，则x处于第处于第i个区间的概率为个区间的概率为pi，则则pi= (中值定理中值定理)即当即当p(x)为为x的连续函数时，由中值定理，必存在一个的连续函数时，由中值定理，必存在一个xi值，值，使上式成立。使上式成立。再按照离散信源的信息熵的定义有：再按照离散信源的信息熵的定义有：

27、nab ( )()(1)iaip x dxp xai( )log()log()()log()logiiniiiiiiiHxppp xp xp xp x 于是我们定义前一项取有限值的项为连续信源的信息熵，并记为于是我们定义前一项取有限值的项为连续信源的信息熵，并记为H Hc c( (X X).).也叫相对熵也叫相对熵0lim()lim( )log( )lim( )log( )log( )lim( ) log( )log( )niiinnniibiiabaHXp xp xp xp xp x dxp xp xp x dx 即：即：Hc(X)= 也可记为：也可记为：Hc(X)= 其中其中R1 表示实轴。表示实轴。 ( )log( )bap xp x dx1( )log( )Rp xp x dx),(二二)两个连续随机变量信源熵两个连续随机变量信源熵 联合熵联合熵条件熵条件熵22()()log()cRHXYp xyp xy dxdy 22(/ )()log( / )cRHX Yp xyp x y dxdy 22( /)()log( / )cRH Y Xp xyp y x dxdy 几种特殊连续信源的熵和最大熵定理几种特殊连续信源的熵和最大熵定理一、均匀分布信源：一、均匀分布信源： Hc(X)= log2(b-a) 结论结论 熵值只与均匀分布