信息论与编码-第4讲-信源及其信息量3-多符号信源

第1页2024/4/14第二章信源及其信息量本章重点：信源的统计特性和数学模型、各类信源的信息测度—熵及其性质。2.1单符号离散信源2.2多符号离散平稳信源2.3连续信源2.4离散无失真信源编码定理2.5小结ElectronicsEngineeringDepartment,XXXXXxxXxxx第2页2024/4/142.2多符号离散平稳信源2.2.1多符号离散平稳信源2.2.2离散平稳无记忆信源2.2.3离散平稳有记忆信源2.2.4马尔可夫信源2.2.5信源冗余度及信息变差第3页2024/4/142.2.1多符号离散平稳信源(1)扩展信源(2)随机矢量／随机变量序列(3)多符号离散平稳信源2.2多符号离散平稳信源第4页2024/4/142.2.1多符号离散平稳信源(1)扩展信源实际的信源输出的消息是时间或空间上离散的一系列随机变量。这类信源每次输出的不是一个单个的符号，而是一个符号序列。在信源输出的序列中，每一位出现哪个符号都是随机的，而且一般前后符号的出现是有统计依赖关系的。这种信源称为多符号离散信源／扩展信源。

举例：电报系统，发出的是一串有、无脉冲的信号系列。2.2多符号离散平稳信源第5页2024/4/142.2.1多符号离散平稳信源(2)随机矢量／随机变量序列多符号离散信源可用随机矢量／随机变量序列描述，即：X=X1,X2,X3,…信源在不同时刻的随机变量

Xi和Xi+r

的概率分布P(Xi)

和P(Xi+r)

一般来说是不相同的，即随机变量的统计特性随着时间的推移而有所变化。2.2多符号离散平稳信源第6页2024/4/142.2.1多符号离散平稳信源(3)多符号离散平稳信源为了便于研究，假定随机矢量X

中随机变量的各维联合概率分布均不随时间的推移变化。或者说，信源所发符号序列的概率分布与时间的起点无关，这种信源称为多符号离散平稳信源。2.2多符号离散平稳信源第7页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源(2)离散平稳无记忆信源的熵(3)举例2.2多符号离散平稳信源第8页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源①基本概念②序列的成组传送③离散无记忆信源的数学模型2.2多符号离散平稳信源第9页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源①基本概念离散平稳无记忆信源：为了方便，假定随机变量序列的长度是有限的，如果信源输出的消息序列中符号之间是无相互依赖关系／统计独立，则称这类信源为离散平稳无记忆信源／离散平稳无记忆信源的扩展信源。2.2多符号离散平稳信源第10页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源②序列的成组传送把信源输出的序列看成是一组一组发出的。例1：电报系统中，认为每二个二进制数字组成一组。信源输出由2个二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源，由4个符号00，01，10，11组成，该信源称为二进制无记忆信源的二次扩展。2.2多符号离散平稳信源第11页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源②序列的成组传送把信源输出的序列看成是一组一组发出的。例2：把每3个二进制数字组成一组，这样长度为3的二进制序列就有8种不同的序列，等效成一个具有8个符号的信源，称为二进制无记忆信源的三次扩展信源。二进制无记忆信源的N次扩展：把每N个二进制数字组成一组，则信源等效成一个具有2N个符号的新信源，称为二进制无记忆信源的N次扩展信源。2.2多符号离散平稳信源第12页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源③离散无记忆信源的数学模型离散无记忆信源X，取值于集合{x1,x2,…,xn}，对它的输出消息序列，可以用一组组长度为N的序列来表示它。这时它就等效成了一个新信源；新信源输出的符号是N长的消息序列，用N维离散随机矢量来描述:每个分量

都是随机变量，都取值于同一信源X，

并且分量之间统计独立。2.2多符号离散平稳信源第13页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源③离散无记忆信源的数学模型由随机矢量X

组成的新信源称为离散无记忆信源X的N次扩展信源。用N重概率空间来描述它。2.2多符号离散平稳信源第14页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源③离散无记忆信源的数学模型

N次扩展信源的数学模型单符号离散信源的数学模型为：2.2多符号离散平稳信源第15页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源③离散无记忆信源的数学模型

N次扩展信源的数学模型信源X的N次扩展信源用

XN

表示，它是具有nN个符号的离散信源，其数学模型为：每个符号ai是对应于某一个由N

个

xi组成的序列。

ai的概率p(ai)是对应的N

个xi组成的序列的概率。2.2多符号离散平稳信源第16页2024/4/142.2.2离散平稳无记忆信源(1)离散平稳无记忆信源③离散无记忆信源的数学模型

N次扩展信源的数学模型因为信源是无记忆的，所以消息序列：2.2多符号离散平稳信源第17页2024/4/142.2.2离散平稳无记忆信源(2)离散平稳无记忆信源的熵根据信息熵的定义，N次扩展信源的熵：离散无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍，即：H(X)=H(XN)=NH(X)2.2多符号离散平稳信源第18页2024/4/142.2.2离散平稳无记忆信源(2)离散平稳无记忆信源的熵[证明]：H(X)=H(XN)=NH(X)

设ai是XN概率空间中的一个符号，对应于由N个xi组成的序列

N次扩展信源的熵：求和号是对信源XN中所有nN个符号求和，所以求和号共有nN个。这种求和号可以等效于N

个求和号，其中的每一个又是对X中的n

个符号求和。2.2多符号离散平稳信源第19页2024/4/142.2.2离散平稳无记忆信源(2)离散平稳无记忆信源的熵[证明]：H(X)=H(XN)=NH(X)所以：因此：2.2多符号离散平稳信源第20页2024/4/142.2.2离散平稳无记忆信源(2)离散平稳无记忆信源的熵[证明]：H(X)=H(XN)=NH(X)上式共有N项，考察其中第一项：

H(X)=H(XN)=H(X)+H(X)+…+H(X)=NH(X)2.2多符号离散平稳信源第21页2024/4/142.2.2离散平稳无记忆信源(3)举例有一离散无记忆信源：求这个离散无记忆信源的二次扩展信源，扩展信源的每个符号是信源X的输出长度为2的符号序列。因为信源X共有3个不同符号，所以由信源X中每两个符号组成的不同排列共有32=9

种，得二次扩展信源共有9个不同的符号。因为信源X是无记忆的，则有：2.2多符号离散平稳信源第22页2024/4/142.2.2离散平稳无记忆信源(3)举例H(X)=1.5

比特/符号（此处的符号是指X信源的输出符号xi）H(X)=H(X2)=3

比特/符号（此处的符号是指扩展信源的输出符号

ai

，它是由二个xi符号组成）,

所以：H(X)=2H(X)上述结论的解释：因为扩展信源XN的每一个输出符号ai是由N个xi所组成的序列，并且序列中前后符号是统计独立的。现已知每个信源符号xi含有的平均信息量为H(X)，那么，N个xi组成的无记忆序列平均含有的信息量就为NH(X)（根据熵的可加性）。因此信源XN每个输出符号含有的平均信息量为NH(X)。2.2多符号离散平稳信源第23页2024/4/142.2.3离散平稳有记忆信源(1)离散平稳有记忆信源的数学模型(2)离散平稳有记忆信源的信息熵(3)离散平稳有记忆信源的极限熵2.2多符号离散平稳信源第24页2024/4/142.2.3离散平稳有记忆信源(1)离散平稳有记忆信源的数学模型①一维平稳信源②二维平稳信源③离散平稳信源2.2多符号离散平稳信源第25页2024/4/142.2.3离散平稳有记忆信源(1)离散平稳有记忆信源的数学模型①一维平稳信源对于随机矢量X

=X1X2…XN若任意两个不同时刻i和j（大于1的任意整数）信源发出消息的概率分布完全相同，即：P(Xi=x1)=P(Xj=x1)=p(x1)P(Xi=x2)=P(Xj=x2)=p(x2)

…P(Xi=xn)=P(Xj=xn)=p(xn)一维平稳信源无论在什么时刻均以{p(x1),p(x2),…,p(xn)}分布发出符号。2.2多符号离散平稳信源第26页2024/4/142.2.3离散平稳有记忆信源(1)离散平稳有记忆信源的数学模型②二维平稳信源除上述条件外，如果联合概率分布P(XiXi+1)也与时间起点无关，即：P(XiXi+1)=P(XjXj+1)（i，j为任意整数，且i≠j）这种信源在任何时刻发出两个符号的概率完全相同。2.2多符号离散平稳信源第27页2024/4/142.2.3离散平稳有记忆信源(1)离散平稳有记忆信源的数学模型③离散平稳信源如果各维联合概率分布均与时间起点无关，即对两个不同的时刻i和j，有：

P(Xi)=P(Xj)P(XiXi+1)=P(XjXj+1)P(XiXi+1Xi+2)=P(XjXj+1Xj+2)

…P(XiXi+1…Xi+N)=P(XjXj+1…Xj+N)这种各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。2.2多符号离散平稳信源第28页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵②离散平稳信源的信息熵2.2多符号离散平稳信源第29页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵二维平稳信源的数学模型最简单的离散平稳信源：二维平稳信源X

=X1X2；每两个符号看做一组，每组代表信源

X

=X1X2的一个消息；每组中的后一个符号和前一个符号有统计关联，这种概率性的关系与时间起点无关；2.2多符号离散平稳信源第30页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵二维平稳信源的数学模型

假定符号序列的组与组之间是统计独立的（这与实际情况不符，由此得到的信源熵仅仅是近似值。但是当每组中符号的个数很多时，组与组之间关联性比较强的只是前一组末尾的一些符号和后一组开头的一些符号，随着每组序列长度的增加，这种差距越来越小）。2.2多符号离散平稳信源第31页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵二维平稳信源的数学模型

X的数学模型2.2多符号离散平稳信源第32页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵二维平稳信源的信息熵2.2多符号离散平稳信源第33页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵二维平稳信源的信息熵结论：两个有相互依赖关系的随机变量X1和X2所组成的随机矢量X=X1X2的联合熵H(X)，等于第一个随机变量的熵H(X1)与第一个随机变量X1已知的前提下，第二个随机变量X2的条件熵H(X2/X1)之和。2.2多符号离散平稳信源第34页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵

离散无记忆信源是离散平稳信源的特例

当随机变量X1和X2相互统计独立时，则：因此：2.2多符号离散平稳信源第35页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵离散无记忆信源是离散平稳信源的特例结论：

随机变量X1和X2统计独立时，二维离散平稳无记忆信源X

=X1X2的熵H(X)等于X1的熵H(X1)和X2的熵H(X2)之和。当X1和X2取值于同一集合时，H(X1)=H(X2)=H(X)，H(X)=H(X2)=2H(X)，与离散无记忆信源二次扩展信源的情况相同。2.2多符号离散平稳信源第36页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵离散无记忆信源是离散平稳信源的特例结论：可以把离散无记忆信源的二次扩展信源看成是二维离散平稳信源的特例；反过来又可以把二维离散平稳信源看成是离散无记忆信源的二次扩展信源的推广。2.2多符号离散平稳信源第37页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵离散无记忆信源是离散平稳信源的特例结论：

前面已证明H(X2/X1)≤H(X2)（极值性），所以：H(X2X1)≤H(X1)+H(X2)。即二维离散平稳有记忆信源的熵小于等于二维平稳无记忆信源的熵。原因：前后两个符号互不相关，第一个符号发生与否对第二个符号不产生任何影响，即H(X2/X1)=H(X2)；X1和X2之间存在统计依赖关系，第一个符号的发生已经提供了第二个符号的部分相关信息。2.2多符号离散平稳信源第38页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵[例2.2.2]：设二维离散信源X=X1X2的原始信源X的信源模型为：X=X1X2中前后两个符号的条件概率列于上表。原始信号X的熵：2.2多符号离散平稳信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵[例2.2.2]：由上表的条件概率确定条件熵：条件熵H(X2/X1)比信源熵/无条件熵H(X)减少了0.672比特/符号，这是由于符号之间的依赖性造成的；第39页2024/4/142.2.3离散平稳有记忆信源2.2多符号离散平稳信源第40页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵①二维平稳信源的信息熵[例2.2.2]：信源平均每发一个消息提供的信息量，即联合熵：H(X1X2)=H(X1)+H(X2/X1)=1.542+0.870=2.412（比特/符号）每一个信源符号提供的平均信息量：H2(X)小于信源提供的平均信息量H(X)，这同样是由于符号之间的统计相关性所引起。2.2多符号离散平稳信源第41页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵②离散平稳信源的信息熵将二维离散平稳有记忆信源推广到N维的情况：

H(X)=H(X1)+H(X2/X1)+H(X3/X1X2)+…+H(XN/X1X2…XN-1)[证明]：2.2多符号离散平稳信源第42页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵②离散平稳信源的信息熵[证明]：H(X)=H(X1X2…XN－1XN)令：Y1=X1X2…

XN－1Y2=X1X2…

XN－2

……

YN－2=X1X2

则：2.2多符号离散平稳信源第43页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵②离散平稳信源的信息熵[证明]：H(X)=H(X1X2…XN－1XN)H(X)=H(Y1XN

)=H(Y1)+H(XN

/Y1)=H(X1X2…

XN－1)+H(XN/X1X2…

XN－1)=H(Y2)+H(XN－1/Y2)+H(XN/X1X2…

XN－1)=H(X1X2…

XN－2)+H(XN－1/X1X2…

XN－2)+H(XN/X1X2…

XN－1)…………=H(YN－2)+H(X3/YN－2)+…+H(XN/X1X2…

XN－1)=H(X1X2)+H(X3/X1X2)+…+H(XN/X1X2…

XN－1)=H(X1)+H(X2/X1)+H(X3/X1X2)+…+H(XN/X1X2…

XN－1)2.2多符号离散平稳信源第44页2024/4/142.2.3离散平稳有记忆信源(2)离散平稳有记忆信源的信息熵②离散平稳信源的信息熵将二维离散平稳有记忆信源推广到N维的情况：

H(X)=H(X1)+H(X2/X1)+H(X3/X1X2)+…+H(XN/X1X2…XN-1)[证明]：结论：多符号离散平稳有记忆信源X

的熵H(X)是X

中起始时刻随机变量X1的熵与各阶条件熵之和。由于信源是平稳的，这个和值与起始时刻无关。2.2多符号离散平稳信源第45页2024/4/142.2.3离散平稳有记忆信源(3)离散平稳有记忆信源的极限熵①条件熵的非递增性②平均符号熵与条件熵的关系③极限熵

结论2.2扩展信源2.2多符号离散平稳信源第46页2024/4/142.2.3离散平稳有记忆信源(3)离散平稳有记忆信源的极限熵①条件熵的非递增性条件熵H(XN/X1X2…XN－1)

随

N的增加是非递增的，即：H(XN/X1X2…XN－1)≤

H(XN－1/X1X2…XN－2)2.2多符号离散平稳信源第47页2024/4/142.2.3离散平稳有记忆信源(3)离散平稳有记忆信源的极限熵①条件熵的非递增性[证明]：根据前面已证明的

H(X2/X1)≤H(X2)

同理可证H(X3/X1X2)≤H(X3/X2)

由于信源是平稳的，所以H(X3/X1X2)≤H(X3/X2)=H(X2/X1)H(X2/X1)≤H(X2)=H(X1)

对于平稳信源递推H(XN/X1X2…XN－1)≤H(XN－1/X1X2…XN－2)

≤H(XN－2

/X1X2…XN－3)

≤

…┇

≤H(X3/X1X2)

≤H(X2/X1)

≤H(X1)2.2多符号离散平稳信源第48页2024/4/142.2.3离散平稳有记忆信源(3)离散平稳有记忆信源的极限熵②平均符号熵与条件熵的关系H(X)（矢量熵）=H(X1X2…XN-1XN)（联合熵）：表示平均发一个消息（由N个符号组成）提供的信息量。平均符号熵：信源平均每发一个符号提供的信息量为：2.2多符号离散平稳信源第49页2024/4/142.2.3离散平稳有记忆信源(3)离散平稳有记忆信源的极限熵②平均符号熵与条件熵的关系

N

给定时，平均符号熵≥条件熵，即：HN

(X)≥H(XN/X1X2…XN－1)2.2多符号离散平稳信源第50页2024/4/142.2.3离散平稳有记忆信源(3)离散平稳有记忆信源的极限熵②平均符号熵与条件熵的关系[证明]：根据离散平稳信源的信源熵H(X)=H(X1)+H(X2/X1)+H(X3/X1X2)+…+H(XN/X1X2…XN－1)直接运用①的结果：H(X)=NHN

(X)≥H(XN/X1X2…XN－1)＋…＋H(XN/X1X2…XN－1)