离散无记忆简单DMS 离散 信源(DMS)「X4且边n p(r) 信源 离散有记 忆信源 信 源 时间离散简单连续信源 连续 的连续源 X||(a,b) R P(x)」Lp(x)Lp(x) 信源 随机波形且∫p(x)d=:或p(x)=1 源 定义2-1:设离散信源X,其概率空间为: X 1, p(x)[Lp(a1),p(a2),…,p(an)分 则其中事件a的自信息为: 1(ai)=log m(a)=-gp(a,(=,q)
定义 2-1:设离散信源 X,其概率空间为: , ( ) 1 ( ), ( ), , ( ) , , , ( ) 1 2 1 1 2 = = = q i i q q p a p a p a p a a a a p x X 则其中事件 ai的自信息为: log ( ), ( 1, ) ( ) 1 ( ) log p a i q p a I a i i i = = − = 信 源 离散 信源 连续 信源 离散无记忆 信源(DMS) 离散有记 忆信源 时间离散 的连续源 随机波形 源 简单 DMS: , 1 ( ) 1 1 1 = = = q i i q q p p p a a p x X 且: 复杂信源: ( ) ( ) ( ) ( ) DMS ( ) , 1 ( ) 1 ( ) ( ) ( ), , ( ) ( ) 1 1 1 1 1 1 1 1 1 + + + + + − = = = = = = = = = i i i N i i i i N i i N N k i k q i i q q q q N p x x x p x p x x p x x x p x p i q p p p a a a a p x X N N N 对有记忆信源有: 其中,对 有 : 且 : 简单连续信源: = = = R b a p x dx p x dx p x R p x a b p x X ( ) 1, ( ) 1 ( ) ( ) ( , ) ( ) 且: 或 或
定义2-2:信源输出各消息的自信息量I(a) 的数学期望为信源的平均自信息量, Ep: H(X)=E((a, =-Ep(a: )log p(a 又称为信源ⅹ的信息熵或熵。 定义2-3:联合集XY上每对元素x的自 信息量的概率加权平均值定义为联合熵 H(XY)=∑∑p(xy)/(xy) 或H(XY=∑p(xy)ogp(xy) 定义2-3:联合集ⅹY上条件自信息量的概 率加权平均值定义为条件熵 H(X)=∑p(x)(yx) 或H(xX)=∑p(xy)logp(yx)
定义 2-2:信源输出各消息的自信息量 I(ai) 的数学期望为信源的平均自信息量, 即: ( ) [ ( )] ( )log ( ) 1 i q i H X E I ai p ai p a = = = − 又称为信源 X 的信息熵或熵。 定义 2-3:联合集 XY 上每对元素 xiyj的自 信息量的概率加权平均值定义为联合熵。 = − = XY i j i j i j i j i j H XY p x y p x y H XY p x y I x y ( ) ( )log ( ) ( ) ( ) ( ) 或 定义 2-3:联合集 XY 上条件自信息量的概 率加权平均值定义为条件熵。 = − = XY i j j i XY H Y X p x y p y x H Y X p xy I y x ( ) ( )log ( ) ( ) ( ) ( ) 或
N次扩展信源的数学模型: N次扩展信源 X=(X1X2…XN X1∈X=|a1a2 c1=(a1a1…a1 ), P(x)P(a)=P(a12…a)=∏Pan) 且∑P( 例:已知DMS: X P(x)」1/21/41/4 二次扩展信源: 二次扩展信源 X=(X1X2), X;∈X=|a1,a2,a3l 2 X ana a1a2 ana3 a2a a2a2 a2a3 a3 a1 a3a2 a3a P(x)1/41/81/81/81/161/161/81/161/16
N 次扩展信源的数学模型: = = = = = = = = N N k N q i i N k i i i i i q q q N q P P P a a a P a a a a a a a P x X 1 1 1 1 1 1 ( ) 1 ( ) ( ) ( ) ( ), ( ) ( ) 1 2 且 例:已知 DMS: = ( ) 1/ 2 1/ 4 1/ 4 a1 a2 a3 P x X 二次扩展信源: = ( ) 1/ 4 1/8 1/8 1/8 1/16 1/16 1/8 1/16 1/16 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 2 a a a a a a a a a a a a a a a a a a P x X N 次扩展信源 [ , , ] ( ), 1 2 1 2 i q N X X a a a X X X X = = 二次扩展信源 [ , , ] ( ), 1 2 3 1 2 X X a a a X X X i = =
例:有一连续信源,其输出信号的概率分布密度曲 线如图例2所示,现将信号等间隔采样,并量化为 3个电平,则该连续信源转换成三元离散信源,其 符号间的条件概率分布如表例2-1所示。求该离 散信源熵。 P(1 2/3 5/9 1/3 0.5 1.5 P(al ai a=0a=1a=2 aF0 9/111/80 2/113/42/9 0187/9 离散二维平稳信源:「X 1,, 41 Lp(x)L3‘’4 二维联合概率为: P(ai an) aF0 Fl F2 141/18 11/18 1/3 1/187/36
例:有一连续信源,其输出信号的概率分布密度曲 线如图例 2 所示,现将信号等间隔采样,并量化为 3 个电平,则该连续信源转换成三元离散信源,其 符号间的条件概率分布如表例 2-1 所示。求该离 散信源熵。 P(aj| ai) ai=0 ai=1 ai=2 aj=0 9/11 1/8 0 aj=1 2/11 3/4 2/9 aj=2 0 1/8 7/9 离散二维平稳信源: = 4 1 , 9 4 36 11 , , ( ) 1 2 3 , a a a p x X 二维联合概率为: P(ai aj) ai=0 ai=1 ai=2 aj=0 1/4 1/18 0 aj=1 1/18 1/3 1/18 aj=2 0 1/18 7/36 p(V) 2/3 5/9 1/3 0 0.5 1.5 3 V
法一:分组法 二次扩展信源: 000102101112202122 Px)」1/41/1801/181/31/1801/187/36 思考题(猜数游戏): 设A从[0,1,…,63]中选中一数 字,B通过“是一否”问答方式进行猜测, 问B至少须几次问答才能猜中此数?
法一:分组法 二次扩展信源: = 1/ 4 1/ 18 0 1/ 18 1/ 3 1/ 18 0 1/ 18 7 / 36 00 01 02 10 11 12 20 21 22 ( ) 2 P x X 思考题(猜数游戏): 设 A 从[0,1,…,63]中选中一数 字, B 通过“是-否”问答方式进行猜测, 问 B 至少须几次问答才能猜中此数?
定理2-1:对于离散平稳信源,当H1(X)< 时,有 1)条件熵H(XNⅩ12,XN1)随N的增加是 非递增的,即: H(XNX1,XN1)≤H(XN1|X1,XN2)≤…≤H(X2X1)≤H(X1) 2)N给定时,平均符号熵大于条件熵, 即:H(X)≥H(XNX1, 3)平均符号熵随N的增加是非递增的, 即 0≤HN(X)≤HN1(X))≤…≤H2(X)≤H1(X)≤∞ 4)H=lmH(X,且 lim HN(X)=lim H(XNX ..XN-I) N→∞ 称H为平稳信源的极限熵或极限信息 量 最大离散熵定理: 个有q个符号的DMS,必满足: H(P1,P2,…,Pq)≤H(1/q,1{q,…1q)=ogq
定理 2-1:对于离散平稳信源,当 H1(X)< ∞时,有: 1) 条件熵 H(XN|X1,…,XN-1)随 N 的增加是 非递增的,即: H(XN|X1,…XN-1)≤H(XN-1|X1,…XN-2)≤…≤H(X2|X1)≤H(X1) 2) N 给定时,平均符号熵大于条件熵, 即:HN(X)≥H(XN|X1,…XN-1) 3) 平均符号熵随 N 的增加是非递增的, 即:0≤HN(X) ≤HN-1(X) )≤…≤H2(X) ≤H1(X) ≤∞ 4) H lim HN (X),且 N → = lim ( ) lim ( ) 1 −1 → → = N N N N N H X H X X X 称 H∞为平稳信源的极限熵或极限信息 量。 最大离散熵定理: 一个有 q 个符号的 DMS,必满足: H(P1,P2,…,Pq)≤H(1/q, 1/q, …1/q)=logq
英语字母概率表 字母 概率 字母 概率 空格 0.1859 N 0.0574 0.0642 0.0632 0.0127 0.0152 ABCDEFGH 0.0218 PQRsT 0.0008 0.0317 0.0484 0.1031 0.0514 0.0208 0.0796 0.0152 0.0228 0.0467 0.0083 0.0575 0.0175 0.0008 K 0.0049 WxYz 0.0013 0.0164 L 0.0321 0.0005 M 0.0198
英语字母概率表 字母 概率 字母 概率 空格 0.1859 N 0.0574 A 0.0642 O 0.0632 B 0.0127 P 0.0152 C 0.0218 Q 0.0008 D 0.0317 R 0.0484 E 0.1031 S 0.0514 F 0.0208 T 0.0796 G 0.0152 U 0.0228 H 0.0467 V 0.0083 I 0.0575 W 0.0175 J 0.0008 X 0.0013 K 0.0049 Y 0.0164 L 0.0321 Z 0.0005 M 0.0198
英文语言模型 1.英文字母序列的第零次近似 XPOWL RXKHRJFF JUJ ZLPWCFWKCYJ F FJEYVKCQ SGHYD QPAAMKBZAACIBZL HJOD 2.英文字母序列的第一次近似 OCRO HLI RGWR NMIELWIS EU LL NbnesebYa TheeI AlhenHttpa Oo BTTVA NAH BRL 3.英文字母序列的第二次近似 ON E ANTSOUTINYS ARE INCTORE ST BE S DEAMY ACHIN D ILONASIV E TUCOOWE AT TEASON ARE FUSO TIZIN ANDY TOBE SEACE CTISBE 4.英文字母序列的第三次近似 IN NO IST LAT WHE CRATICT FROURE BIRS GROCID PONDENOME OF DEMO NSTURES OF THE REPTAGIN IS REGOA CTION OF CRE
英文语言模型 1. 英文字母序列的第零次近似 XPOWL RXKHRJFF JUJ ZLPWCFWKCYJ F FJEYVKCQ SGHYD QPAAMKBZAACIBZL HJQD 2. 英文字母序列的第一次近似 OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA THEEI ALHENHTTPA OO BTTVA NAH BRL 3. 英文字母序列的第二次近似 ON IE ANTSOUTINYS ARE INCTORE ST BE S DEAMY ACHIN D ILONASIV E TUCOOWE AT TEASON ARE FUSO TIZIN ANDY TOBE SEACE CTISBE 4. 英文字母序列的第三次近似 IN NO IST LAT WHE CRATICT FROURE BIRS GROCID PONDENOME OF DEMO NSTURES OF THE REPTAGIN IS REGOA CTION OF CRE