信息论与编码理论第3章 离散信源

信息论与编码理论

第3章离散信源3.1信源的数学模型信源是信息的发源地。信息十分抽象，要通过消息（0-1序列、汉字、字母、图像等）来研究信源。信源可以输出多个符号，每个符号以一定的概率出现。因此可以用概率来描述信源。信源的数学模型X是信源能取的符号的集合；xi是信源符号；pi(p(xi))是信源符号出现的概率。二进制信源：X={0,1}汉语：X={我,一,的,教,俄,…}英语：X={a,b,c,…,x,y,z}信源的例子数学模型则信源的输出有可能是111011111011001110110011101110011010110010110011011100010011（23个0，37个1）110101100110010001111111000010001010011000011100001101001110（31个0，29个1）3.2信源的分类信源符号彼此之间的依存关系无记忆信源有记忆信源3.2.1无记忆信源无记忆信源：信源发出的一个个消息符号是相互独立的。通俗来讲：前面已经出现的信源符号对后面将要出现哪个信源符号没有影响例如：从一个袋子里摸球，50个红的、50个白的，每次摸完之后放回则无论已经摸过的球是红的还是白的，再摸一次球，红白出现的概率都是1/2如何用概率的方法定义无记忆信源？已经出现的符号对将要出现的符号的概率没有影响：p(x|y)=p(x)更确切地，设X=x1x2…xM是信源发出的符号序列3.2.2有记忆信源有记忆信源：信源先后发出的消息符号之间彼此依存、互不独立。例如：自然语言、数字图像等。p(们)=0.01,p(碗)=0.01p(们|我)=0.05,p(碗|我)=0.001现实存在的信源多是有记忆信源有记忆信源分类有限记忆信源无限记忆信源我们、要、的、把、看、…碗、机、水、书、框、…有限记忆信源和无限记忆信源有限记忆信源：信源发出的消息符号只与前若干个符号的关系比较密切，与更前面符号的关系逐渐减弱，直至无关。p(xi|xi-1xi-2…xi-m)m叫做记忆长度无限记忆信源：信源发出的消息符号与前面出现的所有符号都有关系。p(xi|xi-1xi-2xi-3…)例3-5

判断下面这两个信源的记忆特性，无记忆还是有记忆。信源模型均为因此1无记忆，2有记忆信源序列12条件概率3.3离散无记忆信源

3.3.1定义及熵定义3-1

信源X符号集为(x1,x2,…,xn)，n为信源发出的消息符号的个数，每个符号发生的概率为p(xi),i=1,2,…,n，这些消息符号彼此互不相关，且有则称X为离散无记忆信源。3.3.1信源的熵定义3-2

信源中某个消息符号的自信息量I(xi)=-logp(xi)定义3-3

信源的平均自信息量（信源熵）信源熵的单位信源符号（消息符号）的自信息量表示该符号带有多少比特的信息量因此信源熵表示的是平均每个符号带有多少比特的信息量所以定义信源熵的单位为：比特/符号信源输出哪个符号是不确定的一旦输出一个符号，便消除了这种不确定性即带来了信息因此仍然用概率衡量信源包含的信息量的大小信源熵的例子例3-5

二元信源

它的熵为：二元信源的信息熵H(X)是概率p的函数，通常用H(p)表示。信源熵的例子例3-6

信源熵的例子例3-7请从信息论的角度说明，为什么玩扑克牌的时候需要先洗牌？假设不考虑大小王，且自己先摸对方后摸，摸到的第一张牌是A。洗牌均匀分布，则对方也摸到A的概率是3/51，摸到其他牌的概率各为4/51，熵不洗牌易出现几张同样大小的牌连续出现。假设对方也摸到A的概率上升为39/51，摸到其他牌的概率各为1/51，熵可以一个符号一个符号的来研究信源，但有时这样不能满足实际应用的需要。汉语：更多地考察的是句子，而不是汉字。英语：更多地考察的是单词，而不是字母。图像：更多地考察的是整幅图像，而不是单个像素。N次扩展信源：集合中的每一个元素是一个N维随机矢量二进制信源：X={00,01,10,11},N=2汉语：X={我们在上课，张三睡着了，…},N=5英语：X={the,car,ear,she,you,…},N=33.3.2离散无记忆信源的扩展信源3.3.2N次扩展信源

无记忆二元信源的扩展信源二次扩展信源（N=2）qN=4=22，q=2，N=2例如：p(01)=p(0)p(1)=p(1-p)三次扩展信源（N=3）qN=8=23，q=2，N=3例如：p(011)=p(0)p(1)p(1)=p(1-p)2N次扩展信源的熵定理3-1

离散无记忆信源X的N次扩展信源XN的熵等于信源X的熵的N倍，即H(XN)=NH(X)证明：扩展信源熵的例子例3-9方法一方法二3.4马尔可夫信源（有限记忆信源）

3.4.1马尔可夫信源的定义定义3-5在信源X中，如果将要出现的符号仅与刚刚出现的m个符号有关，与更早出现的符号无关，则称X为m阶马尔可夫信源，即例3-10信源X={0,1,2,3}，信源将要发出的符号是前面两个符号的和对4的余数，即显然这是一个2阶马尔可夫信源，因为将要出现的符号只与前面的两个符号有关。每一个将要发出的符号只与前面的两个符号相关，将这两个符号连在一起，看做一个整体，我们把它叫做“状态”。“状态”是马尔可夫信源中的一个重要概念，m阶马尔可夫信源的状态由m个信源符号构成。马尔可夫信源中符号对符号序列的依赖关系就变为状态对状态的依赖关系，即3.4.2有限状态马尔可夫链定义3-6一个状态序列：S1,S2,…,Sl,…，若满足以下条件：有限性：可能的状态数目J<∞，即只有有限个可能的状态；马氏性：系统将要达到的状态，只与当前的状态有关，与更早的状态无关，即则称此随机状态序列为有限状态马尔可夫链。系统将要达到的状态，仅与当前刚刚输出的状态有关，与更前面的状态（过去的状态）无关。这种特性称为马尔可夫特性。马尔可夫链并不是信源，它体现的是一种“一环扣一环”的性质。描述马尔可夫链的数学工具状态转移矩阵pkl表示由状态Sk转移为状态Sl的概率状态转移图状态转移矩阵和状态转移图之间有一一对应的关系。例3-11一个系统有2个状态{S1,S2}，状态转移矩阵为则状态转移图为3.4.3马尔可夫信源的马尔可夫链性质m阶马尔可夫信源中1个符号对m个符号的依赖关系转换为状态和状态之间的“一环扣一环”的关系，因此马尔可夫信源是具有马尔可夫链性质的信源由此可以给出马尔可夫信源的另一个定义定义3-7

若信源输出的符号和状态满足下列条件，则称此信源为m阶马尔可夫信源某一时刻，将要出现的信源符号只与当时信源所处的状态有关，与以前的状态无关，即信源的状态只由当前输出符号和前一时刻信源的状态唯一确定，即3.4.4马尔可夫信源的熵有的马尔可夫信源输出的状态序列与系统的初始状态有关例3-13信源X={0,1,2,3}，信源将要发出的符号是前面两个符号的和对4的余数初始状态状态序列状态分布符号序列信源分布信源熵（比特/符号）00000000000H(X)=002022220022022022…H(X)=0.918310100111122331101123101123…H(X)=1.792530300333322113303321303321…H(X)=1.7925无法给出信源熵的一个确定的值。因此本课程中，我们只研究状态序列不受初始状态影响的情况。这种马尔可夫信源叫做平稳马尔可夫信源。平稳马尔可夫信源的含义包括两点：经过足够长的时间之后，信源的nm个状态出现的概率逐渐稳定下来，不再发生变化状态的稳定分布与初始状态无关，即无论信源一开始处在什么状态，最终都将达到同样的稳定分布。平稳马尔可夫信源的判定定理3-2遍历的马尔可夫信源是平稳马尔可夫信源。如何判断是否遍历？状态转移图：各个状态是互相可达的状态转移矩阵：存在一个正整数N，使转移矩阵PN中的所有元素均大于0。一步转移矩阵和多步转移矩阵转移矩阵P表示一个状态经过1步转移到另外一个状态的矩阵，即转移1次的概率，因此叫做一步转移矩阵。多步转移矩阵P(r)表示一个状态经过多次转移，转移到另外一个状态的概率定理3-3设P为马尔可夫信源的一步状态转移矩阵，该信源为平稳马尔可夫信源的充要条件是存在一个正整数N，使矩阵PN中的所有元素均大于0。例3-14设有一个二进制二阶马尔可夫信源，其信源符号集为{0,1}，条件概率为p(0|00)=p(1|11)=0.8p(1|00)=p(0|11)=0.2p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5试判断这个信源是否为平稳马尔可夫信源。解：3.4.4.2平稳马尔可夫信源的熵m阶平稳马尔可夫信源的熵是在知道了已经出现的m个符号的条件下，信源符号带有的信息量的平均值，换句话说，平稳马尔可夫信源的熵实际上是一个条件熵如果则有：SP=S解方程可以求得各个p(Sj)求马尔可夫信源熵的步骤判断是否为平稳马尔可夫信源。对平稳马尔可夫信源，求出状态的平稳分布。根据公式（3-16）求得马尔可夫信源的熵。马尔可夫信源熵的例子例3-15接例3-14，求该平稳马尔可夫信源的熵。解：例3-14中已经求出该信源为平稳信源。设S=[p(00)p(01)p(10)p(11)]，有解得因此信源熵例3-16“投入-产出”模型：假设一个经济体系由煤炭、电力和钢铁三个部门组成。这是一个马尔可夫链，状态转移矩阵P2中每一个元素均大于0，这是一个平稳马尔可夫链。产出部门采购部门煤炭电力钢铁煤炭0.00.60.4电力0.40.10.5钢铁0.60.20.2PC、PE、PS分别表示煤炭、电力和钢铁部门的平衡价格，

，则SP=S，解得如果钢铁部门的平衡价格是1亿，则煤炭部门是9400万，电力部门是8500万。如果煤炭部门生产1.88万吨煤，则每吨的价格是5000元；如果电力部门生产1.7亿度电，则每度电的价格是0.5元。这就是国民生产中，确定每种商品单价的一个基本原则。极限熵对无限记忆信源，记忆长度无限，此时的熵叫做极限熵极限熵又叫做实际熵即当前符号实际上能够带给我们的信息量。3.5离散平稳信源如果信源输出各个符号的概率与时间无关，即则称此信源为一维平稳信源。如果信源输出长度为N的符号序列的概率与时间无关，即则称此信源为N维平稳信源。平稳信源的熵平稳信源输出的长度为N的符号序列的联合熵为长度为N的信源符号序列中平均每个符号所携带的信息量为平均符号熵，即设信源符号序列之间的记忆长度为N，若已知前面N−1个符号，则第N个符号所携带的平均信息量为条件熵，即性质1.性质1的含义是：我们知道的条件越多，越容易判断事件的结果2.3.4.性质2、3、4说明，当平稳信源输出的符号序列长度达到无限大时，平均符号熵HN(X)和条件熵H(XN|X1X2…XN−1)都非递增地收敛于平稳信源的极限熵。3.6信源的相关性和剩余度

相关性H(XN|X1,…,XN-1)≤H(XN-1|X1,…,XN-2)≤H(XN-2|X1,…,XN-3)≤…≤H(X2|X1)≤H(X1)

输出符号等概率分布时，