资源描述
信源与信息熵第二章第二章12.1 2.1 信源的描述和分类信源的描述和分类2.2 2.2 离散信源熵和互信息离散信源熵和互信息2.3 2.3 离散序列信源的熵离散序列信源的熵2.4 2.4 连续信源的熵和互信息连续信源的熵和互信息2.5 2.5 冗余度冗余度内容22.3 离散序列信源的熵3离散离散信源信源离散离散无记忆无记忆信源信源离散离散有记忆有记忆信源信源发出单个符号的无记忆信源发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源发出符号序列的马尔可夫信源2.3.1 离散无记忆信源的序列熵发出发出单个符号单个符号的信源的信源指信源每次只发出一个符号代表一个消息指信源每次只发出一个符号代表一个消息；发出发出符号序列符号序列的信源的信源指信源每次发出一组含二个以上符号的符号序指信源每次发出一组含二个以上符号的符号序列代表一个消息。列代表一个消息。4离散无记忆序列信源离散无记忆序列信源u布袋摸球实验，若每次取出两个球，由布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色若先取出一个球，记下颜色放回布袋放回布袋，再取另一个球。再取另一个球。5离散有记忆序列信源离散有记忆序列信源u布袋摸球实验，每次取出两个球，由两个布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色取出一个球，记下颜色不放回布袋不放回布袋，再取，再取另一个球。另一个球。6离散无记忆信源的序列熵 随机序列的概率为随机序列的概率为 设信源输出的随机序列为设信源输出的随机序列为 X=(X1X2XlXL)序列中的变量序列中的变量Xl x1,x2,xn X称为离散无记忆信源称为离散无记忆信源X的的L次扩展信源次扩展信源 7 离散无记忆信源的序列熵8离散无记忆信源的序列熵 当信源当信源无记忆无记忆时时 信源的序列熵信源的序列熵 9离散无记忆信源的序列熵若又满足若又满足平稳特性平稳特性,即与序号即与序号l无关时：无关时：信源的序列熵信源的序列熵 平均每个符号平均每个符号(消息消息)熵为熵为 10例例:有一个无记忆信源随机变量有一个无记忆信源随机变量X(0,1),等概率分等概率分布布,若以单个符号出现为一事件若以单个符号出现为一事件,则此时的信源熵则此时的信源熵:即用即用 1比特就可表示该事件。比特就可表示该事件。如果以两个符号出现如果以两个符号出现(L=2的序列的序列)为一事件，为一事件，则随机序列则随机序列X(00,01,10,11)，信源的序列，信源的序列熵熵即用即用2比特才能表示该事件。比特才能表示该事件。信源的符号熵信源的符号熵11例例:有一离散平稳无记忆信源有一离散平稳无记忆信源 求：二次扩展信源的求：二次扩展信源的熵熵X2信源信源的元素的元素 a1 a2a3a4a5a6a7a8a9对应的的消息序列消息序列 x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3 x2x3 x3概率概率p(ai)1/4 1/81/81/81/161/161/81/16 1/1612平均每个符号平均每个符号(信息信息)熵为熵为 信源的序列熵信源的序列熵13离散有记忆信源的序列熵对于对于有记忆有记忆信源信源,就不像无记忆信源那样简单就不像无记忆信源那样简单,它它必须引入条件熵的概念必须引入条件熵的概念,而且只能在某些特殊情而且只能在某些特殊情况下才能得到一些有价值的结论。况下才能得到一些有价值的结论。对于由对于由两个符号两个符号组成的联合信源组成的联合信源,有下列有下列结论结论:当前后符号当前后符号无依存关系无依存关系时时,有下列推论：有下列推论：14若信源输出一个若信源输出一个L长序列长序列,则信源的则信源的序列熵序列熵为为平均每个符号的熵为：平均每个符号的熵为：若当信源退化为若当信源退化为无记忆无记忆时时:若进一步又满足平稳性时若进一步又满足平稳性时 15ai aja0a1a2a09/112/110a11/83/41/8a202/97/9例例已知离散有记忆信源中已知离散有记忆信源中各符号的概率空间为各符号的概率空间为:设发出的符号只与前一个符号有关设发出的符号只与前一个符号有关,这两个符这两个符号的概率关联性用条件概率号的概率关联性用条件概率p(aj|ai)表示表示,如表如表p(aj|ai)求离散信源的序列熵和平均每个符号的熵求离散信源的序列熵和平均每个符号的熵?16由由 p(ai,aj)=p(ai)p(aj|ai)计算得联合概率计算得联合概率p(ai aj)如如表表a0a1a2a01/41/180a11/181/31/18a201/187/36当信源符号之间当信源符号之间无依赖性无依赖性时时,信源信源X的信息熵为的信息熵为当考虑符号之间当考虑符号之间有依赖性有依赖性时时,计算得条件熵计算得条件熵 H(X2|X1)H(X)信信源源的的条条件件熵熵比比无无依依赖赖时时的的熵熵H(X)减减少少了了0.671比比特特,这这正正是是因因为为符符号号之之间间有有依依赖赖性性所造成的结果。所造成的结果。17联合熵联合熵H(X1,X2)表示平均每二个信源符号所携表示平均每二个信源符号所携带的信息量。带的信息量。我们用我们用1/2H(X1,X2)作为二维平稳信源作为二维平稳信源X的信息的信息熵的近似值。那么平均每一个信源符号携带的熵的近似值。那么平均每一个信源符号携带的信息量近似为信息量近似为:符号之间存在关联性符号之间存在关联性发发二重符号二重符号序列的熵序列的熵 比较比较18 离散平稳序列信源离散平稳序列信源(1)时时间间不不变变性性:联联合合概概率率具具有有时时间间推推移移不不变性：变性：pXi1=x1,Xi2=x2,.,XiL=xL =pXi1+h=x1,Xx2+h=x2,XiL+h=xL 19(2)H(XL/XL-1)是是L的单调递减函数的单调递减函数证明证明:H(XL/X1X2XL-1)H(XL/X2X3XL-1)(条件较多的熵小于或等于减少一些条件的熵条件较多的熵小于或等于减少一些条件的熵)=H(XL-1/X1X2XL-2)（平稳性）（平稳性）H(XL-1/X2X3XL-2)(条件较多的熵小于或等于减少一些条件的熵条件较多的熵小于或等于减少一些条件的熵)=H(XL-2/X1X2XL-3)（平稳性）（平稳性）H(X2/X1)20(3)HL(X)H(XL/XL-1)证明证明:HL(X)=H(X1X2XL)/L =H(X1)+H(X2/X1)+H(XL/X1X2XL-1)/L LH(XL/X1X2XL-1)/L =H(XL/XL-1)21(4)HL(X)是是L的单调递减函数的单调递减函数证明证明:LHL(X)=H(X1X2XL)=H(X1X2XL-1)+H(XL/X1X2XL-1)=(L-1)HL-1(X)+H(XL/XL-1)(L-1)HL-1(X)+HL(X)所以所以 HL(X)HL-1(X)同理同理,有有 H(X)HL+1(X)HL(X)HL-1(X)H0(X)22(5)H(X)=HL(X)=H(XL/X1X2XL-1)H(X)叫极限熵或极限信息量。叫极限熵或极限信息量。证明：证明：HL+k(X)=H(X1X2XL-1)+H(XL/X1X2XL-1)+H(XL+k/X1X2XL+k-1)H(X1X2XL-1)+H(XL/X1X2XL-1)+H(XL/X1X2XL-1)=H(X1X2XL-1)+H(XL/X1X2XL-1)23当固定当固定L时，有时，有 HL+k(X)H(XL/X1X2XL-1)=H(XL/XL-1)又因为又因为 H(XL/XL-1)HL(X)所以，所以，当当 时，时，HL(X)=HL+k(X)得：得：HL(X)=H(XL/X1X2XL-1)推广可得结论：推广可得结论：H(X)H2(X)H1(X)H0(X)式中，式中，H0(X)为等概率无记忆信源单个符号的熵，为等概率无记忆信源单个符号的熵，H1(X)为一般无记忆（不等概率）信源单个符号的熵为一般无记忆（不等概率）信源单个符号的熵H2(X)为两个符号组成的序列平均符号熵，依次类推。为两个符号组成的序列平均符号熵，依次类推。24说明说明:(i)如何计算极限熵是一个十分困难的问题如何计算极限熵是一个十分困难的问题.(ii)在实际应用中常取有限在实际应用中常取有限L下的条件熵下的条件熵 H(XL/XL-1)作为作为H(X)的近似值。的近似值。(iii)当平稳离散信源输出序列的相关性随着当平稳离散信源输出序列的相关性随着L的增加的增加 迅速减小时，其序列熵的增加量迅速减小时，其序列熵的增加量H(XL/XL-1)与相关与相关性有关，相关性很弱，则性有关，相关性很弱，则 H（XL/X1X2XL-1）H（XLX2 XL-1）=H（XL-1/X1 XL-2），增加），增加量不再变小，所以平均符号熵也几乎不再减小。量不再变小，所以平均符号熵也几乎不再减小。25(6)设信源发出的符号只与前面的设信源发出的符号只与前面的m个符号有关，个符号有关，而与更前面出现的符号无关时而与更前面出现的符号无关时,有有 H(X)=H(Xm+1/X1X2Xm)=Hm+1(X)证明证明:信源发出的符号只与前面的信源发出的符号只与前面的m个符号有关，而个符号有关，而与更前面出现的符号无关。用概率意义表达为与更前面出现的符号无关。用概率意义表达为 p(xt/xt-1,xt-2,xt-3,xt-m,)=p(xt/xt-1,xt-2,xt-m)则根据则根据（5）可得可得 =H(Xm+1/X1X2Xm)=Hm+1(X)26补充：补充：马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源一类相对简单的离散平稳信源一类相对简单的离散平稳信源该信源在某一时刻发出字母的该信源在某一时刻发出字母的概率概率除与该除与该字母有关外字母有关外,只与此前发出的只与此前发出的有限有限个字母有个字母有关关m m阶马尔可夫信源阶马尔可夫信源：信源输出某一符号的概率仅与以前的信源输出某一符号的概率仅与以前的m m个符个符号有关，而与更前面的符号无关。号有关，而与更前面的符号无关。用概率意义表达为用概率意义表达为27马氏链的基本概念马氏链的基本概念 一阶马尔可夫信源一阶马尔可夫信源：若把若把有限个字母有限个字母记作一个记作一个状态状态S S，则信源发出则信源发出某一字母的概率除与该字母有关外，只与该时某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。刻信源所处的状态有关。信源信源将来的状态将来的状态及其送出的字母将只与信源及其送出的字母将只与信源现现在的状态在的状态有关，而与信源过去的状态无关。有关，而与信源过去的状态无关。28马氏链的基本概念马氏链的基本概念 令令si=(xi1,xi2,xim)xi1,xi2,xim(a1,a2,an)状态集状态集S=s1,s2,sQ Q=nm信源输出的随机信源输出的随机符号符号序列为：序列为：x1,x2,x i-1,x i信源所处的随机信源所处的随机状态状态序列为：序列为：s1,s2,si-1,si,例：二元序列为例：二元序列为0101110001011100考虑考虑m=2，Q=nm=22=4s1=00 s2=01 s3=10 s4=11变换成对应的变换成对应的状态序列状态序列为为 s2 s3 s2 s4 s4 s3 s1m m个字母组成个字母组成的各种可能的的各种可能的序列就对应于序列就对应于信源全部可能信源全部可能的状态的状态S.S.29马尔可夫信源马尔可夫信源设信源在时刻设信源在时刻m m处于处于si状态状态,它在下一时刻它在下一时刻(m+1)状状态转移到态转移到sj的的转移概率转移概率为：为：pij(m)=pSm+1=sj|Sm=si=psj|si pij(m)：基本转移概率（一步转移概率）基本转移概率（一步转移概率）若若pij(m)与与m 的取值无关的取值无关,则称为则称为齐次马尔可夫齐次马尔可夫链链 pij=pSm+1=sj|Sm=si=pS2=sj|S1=sipij具有下列性质：具有下列性质：pij030若信源处于某一状态若信源处于某一状态si,当它发出一个符号后当它发出一个符号后,所处状态所处状态就变了就变了,任何时候信源处于什么状态完全由前一时刻的状任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。态和发出符号决定。系统在任一时刻可处于状态空间系统在任一时刻可处于状态空间S=S=s1,s2,sQ 中的任中的任意一个状态意一个状态,状态转移时状态转移时,转移概率矩阵转移概率矩阵符号符号条件概率矩阵条件概率矩阵31例例2-12-1，如图所示是一个相对码编码器，如图所示是一个相对码编码器,输入的码输入的码X Xr r(r r=1,2,)=1,2,)是相互独立的，取值是相互独立的，取值0 0或或1 1，且已知，且已知P(X=0)=P(X=0)=p p,P(X=1)=1,P(X=1)=1p p=q q，输出的码是，输出的码是Y Yr r，显然，显然TXrYrYr-1+Y Yr r是一个是一个马氏链马氏链,Y Yr r确定后确定后,Y Yr+1r+1概率分布只与概率分布只与Y Yr r有有关关,与与Y Yr-1r-1 、Y Yr-2r-2 等无关等无关,且知且知Y Yr r序列的条件概序列的条件概率率32sos1pqqpp00=P(Y2=0/Y1=0)=P(X=0)=p p01=P(Y2=1/Y1=0)=P(X=1)=q p10=P(Y2=0/Y1=1)=P(X=1)=q p11=P(Y2=1/Y1=1)=P(X=0)=p 33马尔可夫信源状态转移图状态转移图齐次马尔可夫链可以用其状齐次马尔可夫链可以用其状态转移图态转移图(香农线图香农线图)表示表示每个圆圈代表一种每个圆圈代表一种状态状态 状态之间的有向线代表某一状态之间的有向线代表某一状态向另一状态的状态向另一状态的转移转移有向线一侧的符号和数字分有向线一侧的符号和数字分别代表发出的别代表发出的符号符号和和条件概条件概率率sos11/0.60/0.30/0.4s21/0.20/0.81/0.734齐次马尔可夫链中的状态分类齐次马尔可夫链中的状态分类:如状态如状态S Si i经若干步后总能到达状态经若干步后总能到达状态S Sj j，即存在，即存在k k,使使p pijij(k k)0 0，则称，则称S Si i可到达可到达S Sj j;若两个状态相互可到达若两个状态相互可到达,则称此则称此二状态相通；二状态相通；过渡态过渡态：一个状态经过若干步以后总能到达某一其他状：一个状态经过若干步以后总能到达某一其他状态，但不能从其他状态返回态，但不能从其他状态返回,如图中的状态如图中的状态s1s1；吸收态吸收态：一个只能从自身返回到自身而不能到达其他任：一个只能从自身返回到自身而不能到达其他任何状态的状态，如图中的状态何状态的状态，如图中的状态s6s6；常返态常返态：经有限步后迟早要返回的状态，如：经有限步后迟早要返回的状态，如s2s2、s3s3、s4s4和和s5s5；35s3s2s4s5s1s6周期性的：在常返态中,有些状态仅当k能被某整数d1整除时才有pii(k)0,图中的周期为2；x5:1非周期性的：对于pii(k)0的所有k值，其最大公约数为1。常返态：经有限步后迟早要返回的状态，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/436周期性的周期性的：在常返态中，有些状态仅当：在常返态中，有些状态仅当k k能能被某整数被某整数d d1 1整除时才有整除时才有p pijij(k k)0 0，如图，如图中的状态中的状态s4s4和和s5s5，其周期为，其周期为2 2；非周期性的非周期性的：对于：对于p pijij(k k)0 0的所有的所有k k值，其值，其最大公约数为最大公约数为1 1。37遍历状态遍历状态：非周期的、常返的状态非周期的、常返的状态,如图中的状态如图中的状态s s2 2和和s s3 3不可约的不可约的：从任意某个状态从任意某个状态S Si i开始，总有可能到达其他开始，总有可能到达其他任意某个状态任意某个状态S Sj j对任意一对对任意一对i i、j j，都存在，都存在至少一个至少一个k k，使，使p pijij(k k)0 0。38马氏链可约性马氏链可约性:若对所有若对所有 k，都有，都有p(k)ij=0，就意味着一旦出，就意味着一旦出现现 Si以后不可能到达以后不可能到达Sj,也就是不能各态遍历，也就是不能各态遍历，或者状态中应把或者状态中应把Sj取消，这样就成为可约的了。取消，这样就成为可约的了。S1S3S21/21/21/21/21S4S51/21/2可约马氏链可约马氏链1/21/239马氏链周期性马氏链周期性 下图周期为下图周期为2.因为从因为从S1出发再回到出发再回到S1所需的所需的步数必为步数必为2，4，6，.S1S4S21/21/21/2周期性马氏链周期性马氏链S31/21/21/21/21/21/240马尔可夫信源一个不可约的、非周期的、状态有限的马尔可夫一个不可约的、非周期的、状态有限的马尔可夫链其链其k k步转移概率步转移概率p pijij(k k)在在kk时趋于一个和初始时趋于一个和初始状态无关的状态无关的极限概率极限概率W Wj j，它是满足方程组，它是满足方程组 的唯一解；的唯一解；W Wj j ：马尔可夫链的一个：马尔可夫链的一个平稳分布平稳分布，W Wj j p(s p(sj j)就是系统此时处于状态就是系统此时处于状态s sj j的概率。的概率。41sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例42例例2-2：有一个二元二阶马尔可夫信源有一个二元二阶马尔可夫信源,其信其信源符号集为源符号集为0，1，已知符号条件概率：，已知符号条件概率：p(0|00)=1/2 p(1|00)=1/2 p(0|01)=1/3 p(1|01)=2/3 p(0|10)=1/4 p(1|10)=3/4 p(0|11)=1/5 p(1|11)=4/5求：求：信源全部状态及状态转移概率信源全部状态及状态转移概率画出完整的二阶马尔可夫信源状态转移图。画出完整的二阶马尔可夫信源状态转移图。求平稳分布概率求平稳分布概率 43状态转移概率矩阵符号条件概率矩阵(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/544稳态分布概率稳态分布概率稳态后的符号概率分布稳态后的符号概率分布45马尔可夫信源的信息熵 M阶马尔可夫信源阶马尔可夫信源齐次、遍历的马尔可夫信源的熵齐次、遍历的马尔可夫信源的熵46马尔可夫信源的信息熵马氏链极限熵47马尔可夫信源的信息熵48s2s31/0.61/0.20/0.5s11/0.51/0.10/0.9例例三状态马尔可夫信源三状态马尔可夫信源0/0.84950 2.4连续信源的熵与互信息幅度连续的单个符号信源熵幅度连续的单个符号信源熵51 2.4连续信源的熵与互信息幅度连续的单个符号信源熵幅度连续的单个符号信源熵52 0 1 2 3 x1/2Px(x)（a）信源输出信号概率密度）信源输出信号概率密度例例 已知信源概率密度，求连续熵？已知信源概率密度，求连续熵？由图（由图（a）得）得 53 2.4连续信源的熵与互信息波形信源熵波形信源熵54 2.4连续信源的熵与互信息最大熵定理最大熵定理-峰值功率受限的最大相对熵定理峰值功率受限的最大相对熵定理:对于定义域为有限的随机矢量对于定义域为有限的随机矢量X,当它当它是是均匀分布均匀分布时，其熵最大。时，其熵最大。55 2.4连续信源的熵与互信息最大熵定理最大熵定理限平均功率最大熵定理：对于相关矩阵一定的随机变量X，当它是正态分布时具有最大熵.562.5 冗余度57冗余度冗余度冗余度(多余度、剩余度多余度、剩余度)表示信源在实际发出消息时所包含的多余信息。表示信源在实际发出消息时所包含的多余信息。冗余度：冗余度：信源符号间的相关性。信源符号间的相关性。相关程度越大相关程度越大,信源的实际熵越小信源的实际熵越小信源符号分布的不均匀性。信源符号分布的不均匀性。等概率分布时信源熵最大。等概率分布时信源熵最大。58对于有记忆信源对于有记忆信源,极限熵极限熵为为H(X)。这就是说我们需要传送这一信源的信息这就是说我们需要传送这一信源的信息,理论理论上只需要传送上只需要传送H(X)即可。但必须掌握信源全即可。但必须掌握信源全部概率统计特性部概率统计特性,这显然是不现实的。这显然是不现实的。实际上实际上,只能算出只能算出Hm(X)。那么与理论极限值相。那么与理论极限值相比比,就要多传送就要多传送Hm(X)H(X)。为了定量地描述信源的有效性为了定量地描述信源的有效性,定义定义:信息效率信息效率冗余度冗余度表示不肯定的程度表示不肯定的程度 表示肯定性的程度，因为肯定性不含有信息量，因此是冗余的。表示肯定性的程度，因为肯定性不含有信息量，因此是冗余的。59冗余度由于信源存在由于信源存在冗余度冗余度,即存在一些不必要传送即存在一些不必要传送的信息的信息,因此信源也就存在进一步因此信源也就存在进一步压缩压缩其信息其信息率的可能性。率的可能性。信源冗余度越大信源冗余度越大,其进一步压缩的潜力越大其进一步压缩的潜力越大。这是信源编码与数据压缩的前提与这是信源编码与数据压缩的前提与理论基础。理论基础。例：例：英文字母：英文字母：等概率等概率 H0=log27=4.76比特比特/符号符号 不等概率不等概率 H1=4.03比特比特/符号符号 考虑相关性考虑相关性 H2=3.32比特比特/符号符号 极限熵极限熵 H=1.4比特比特/符号符号冗余度冗余度英语文章有英语文章有71%71%是由语言结构是由语言结构定好的定好的,只有只有29%29%是自由选择是自由选择60 结论：结论：在实际通信系统中，为了提高传输效率，在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即往往需要把信源的大量冗余进行压缩，即所谓所谓信源编码信源编码。但是考虑通信中的抗干扰。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因问题，则需要信源具有一定的冗余度。因此在传输之前通常加入某些特殊的冗余度，此在传输之前通常加入某些特殊的冗余度，即所谓即所谓信道编码信道编码，以达到通信系统理想的，以达到通信系统理想的传输有效性和可靠性。传输有效性和可靠性。61写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits62 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日
展开阅读全文