1,第3章 多符号离散信源与信道,内容提要 3.1 离散平稳信源的数学模型 3.2 离散平稳无记忆信源的信息熵 3.3 离散平稳有记忆信源的信息熵 3.4 离散平稳有记忆信源的极限熵 3.5 马尔可夫信源的极限熵 3.6 信源的剩余度和结构信息,2,3.1 离散平稳信源的数学模型,基本概念 多符号离散信源：由多个符号组成的时间（或空间）序列 才能代表一个完整的消息的信源，称为多符号离散信源。 多符号离散信道：相对于多符号离散信源来说，若信道的 输入端输入一个由多个信源符号组成的时间序列所代表的 消息，在信道的输出端相应以一定概率输出一个由同样个 数的符号组成的时间序列所代表的消息，这种信道称为多 符号离散信道。,3,3.1 离散平稳信源的数学模型,多符号离散信源的表示： 多符号离散信源可用随机变量序列Xk(k=1,2, )组成的时 间序列来表示，其中Xk表示某一单位时间k信源发出的符 号。 注：多符号离散信源 可看成时刻k(k=1,2, ) 的单符号离散信源Xk(k=1,2, )的时间序列。,4,3.1 离散平稳信源的数学模型,离散平稳信源 一般情况下，信源X的概率分布与时间k(k=1,2, )有关 设Q,T为两个任意时刻，若信源X的分布与时间无关，即有 则把信源X称为N+1维离散平稳信源。,5,3.1 离散平稳信源的数学模型,说明（符号集 ） 表明N+1维离散平稳信源的1至N+1维联合概率分布不随时间的 推移而变化，对时间的起点来说是平稳的。,6,3.1 离散平稳信源的数学模型,2. 数学模型 信源符号集 ，N维离散平稳信源，,7,3.1 离散平稳信源的数学模型,数学模型 信源空间 其中,8,3.1 离散平稳信源的数学模型,推广 不妨假定：多符号离散平稳信源发出的所有信息都由N 个符号组成；多符号离散平稳信源发出的长度为N的不同 消息间相互统计独立、互不相关，因此可将N维离散稳定 信源在时间上延长到无穷序列 中，每N个随机变量看作一组，每组代表一个完整的消息。 N维离散平稳信源 称为信源 的N次扩展。,9,一. 离散平稳无记忆信源概念 定义 3.2.1 设信源 X 输出符号集 ，r为信源发出的消息符号个数，每个符号发生的概率为 。这些消息符号彼此互不相关，且,3.2 离散平稳无记忆信源的信息熵,则 X 称为离散无记忆信源。,10,若N维离散平稳信源 中，各时刻 随机变量 之间相互统计独立，则 我们将 称为N维离散平稳无记忆信源。 对N维离散平稳无记忆信源 ，有,3.2 离散平稳无记忆信源的信息熵,11,3.2 离散平稳无记忆信源的信息熵,N维离散平稳无记忆信源 信源空间 其中,12,1. 最简单离散信源 用一维随机变量X描述，其数学模型为,且,特点:,3.2 离散平稳无记忆信源的信息熵,二 离散无记忆信源的信息熵,13,3.2 离散平稳无记忆信源的信息熵,2. 离散无记忆信源的N次扩展信源 (1)离散无记忆二进制信源的二次扩展信源 二次扩展信源输出的消息符号序列是分组发出的。每两个二进制数字构成一组，即等效信源的输出符号为00，01，10，11。,14,3.2 离散平稳无记忆信源的信息熵,二次扩展信源的数学模型为,且有，,式中，,15,3.2 离散平稳无记忆信源的信息熵,(2)离散无记忆二进制信源X的三次扩展信源 三次扩展信源共输出23=8个消息符号。概率空间为,推广： 离散无记忆二进制信源的N次扩展信源 共有2N个符号。,16,3.2 离散平稳无记忆信源的信息熵,(3)离散无记忆信源的N次扩展 定义 3.2.2 设X是一个离散无记忆信源，其概率空间为,其中，q为信源符号个数，pi=P(X=ai),i=1,2,q X的N次扩展信源XN是具有个qN消息符号的离散无记忆信源，其数学模型为,17,3.2 离散平稳无记忆信源的信息熵 (3)离散无记忆信源的N次扩展,其中,18,3.2 离散平稳无记忆信源的信息熵,3. 离散无记忆信源的N次扩展信源的熵 定理 3.2.1 离散无记忆信源X的N次扩展信源XN的熵等于信源X的熵的N倍，即,这表明离散无记忆信源X的N次扩展信源 每输出一个消息符号（即符号序列）所提供的信息熵是信源X每输出一个消息符号所提供信息熵的N倍。,P177 例 3.1,19,一 离散平稳有记忆信源的概念 若离散平稳信源在各时刻发出的符号之间并不是统计独 立的，前一刻发出的符号，依某种统计规律影响到后续发 出的符号的可能性，即任一时刻发出的符号对这一时刻之 前发出的符号是“有记忆”的，那么信源X称为是离散平稳 有记忆信源； 由X扩展而成的多符号离散平稳信源 称为N维离散平稳有记忆信源。,3.3 离散平稳有记忆信源的信息熵,20,N维平稳有记忆信源 有平稳的特性 设Q和T是任意两个时刻，即有 所以，有,3.3 离散平稳有记忆信源的信息熵,21,进而可得 表明：N维离散平稳有记忆信源 的各维条件概率也是平稳的，与起始时刻无关，不随时间的推移而发生变化。,3.3 离散平稳有记忆信源的信息熵,22,3.3 离散平稳有记忆信源的信息熵,N维离散平稳有记忆信源 信源空间 其中,N维离散平稳有记忆信源的概率空间是一个完备集。,23,3.3 离散平稳有记忆信源的信息熵,二 离散平稳有记忆信源的信息熵 1 二维离散平稳有记忆信源的信息熵,24,3.3 离散平稳有记忆信源的信息熵,(无记忆)与 (有记忆)的比较 表明：二维离散平稳有记忆信源每发一条消息提供的平均 信息量，不会超过二维离散平稳无记忆信源每发一条消息 提供的平均信息量。 之间的统计联系，即有记忆性，减少了二维离散 平稳有记忆信源每发一条消息提供的平均信息量。,25,3.3 离散平稳有记忆信源的信息熵,2 N维平稳有记忆信源的信息熵,26,3.3 离散平稳有记忆信源的信息熵,几个结论 表明：离散平稳有记忆信源每发一个符号所提供的信息量， 随记忆长度的增长而减小。记忆长度越长，在某时刻发符 号之前的关于这个符号的预备知识越多，这时刻发符号的不 确定性越小，提供的平均信息量也就小。,（1）,（2）,（3）,（4）,27,3.3 离散平稳有记忆信源的信息熵,平均符号熵 定义 对离散平稳有记忆信源X来说，因为有记忆，所以在不 同时刻所发符号提供的平均信息量是不同的。 平均符号熵成为评估N维离散平稳有记忆信源，每发一 个符号提供的平均信息量，也就是提供信息能力的一个衡 量标准。,28,3.4 离散平稳有记忆信源的极限熵,极限熵（极限信息熵） 当信源符号序列长度趋于无穷时,有,结论,1. 平均符号熵HN(X)是记忆长度的N的非递增函数；,2. 平均符号熵HN(X)的极限，即极限熵值存在。,29,3.4 离散平稳有记忆信源的极限熵,结论,说明,1 极限熵的计算转化为条件熵的极限值；,2 实际计算困难：,需要测定X的无限维条件概率和联合概率。,30,N次扩展信源熵的性质,(4) 极限熵 存在，且,(1) 条件熵 随N的增加是非递增的,(2),(3) 平均符号熵 随N的增加是非递增的。,3.4 离散平稳有记忆信源的极限熵,31,3.5 马尔可夫信源的极限熵,马尔可夫过程 3.5.1 有限状态马尔可夫链 3.5.2 马尔可夫信源,32,马尔可夫过程,1. 定义： 设X(t), tT是随机过程，任取0t1t2 tn，tiT,i=1,2, n ,若t1,t2, ,tn时刻, 取值分别为x1,x2, ,xn，并有,则称X(t)为k阶马尔可夫过程。 注： k=0时，称为零阶马尔可夫过程。 零阶马尔可夫过程=白噪声过程。,33,马尔可夫过程,2. 分类 a. 状态离散 时间参数集T 离散 马尔可夫链 b. 状态离散 时间参数集T 连续 离散马尔可夫过程 c. 状态连续 时间参数集T 离散 马尔可夫序列（泊松过程） d. 状态连续 时间参数集T 连续 连续马尔可夫过程,34,3.5.1 有限状态马尔可夫链,1.定义： (1) 设 xn , nN+ 为一随机序列，时间参数集N+=0,1,2, 其状态空间S=S1,S2,SJ有限或可数，若对所有n N+ ，有,则称, xn,nN+ 为马尔可夫链， 即有限状态一阶马尔可夫链。,35,3.5.1 有限状态马尔可夫链,(2) 转移概率,m时刻状态Si，经(n-m)步后转移到状态Sj的概率,36,3.5.1 有限状态马尔可夫链,(3) K阶马尔可夫链,37,3.5.1 有限状态马尔可夫链,(4) 时齐马尔可夫链（齐次马尔可夫链） 若pij(m)=P(xm+1=Sj|xm=Si)与时刻m无关。 即pij(m)=pij ，则称为时齐马尔可夫链（齐次马尔可夫链）, 一步转移矩阵P为,38,3.5.1 有限状态马尔可夫链,命题：设P(n)是时齐马尔可夫链的n步转移矩阵 (n1)， P=P(1)是基本转移矩阵，则,2. 切普曼科尔莫哥洛夫方程（C-K方程）,从而有,元素,注意：P(n)是经过n步的转移矩阵。,39,3.5.1 有限状态马尔可夫链,3. 初始分布,定义：设P(X0=Si)=pi , 且,则称它为马尔可夫链的初始分布,40,3.5.1 有限状态马尔可夫链,4. 平稳分布 定义： 若齐次马尔可夫链对所有i,j存在不依赖于i的极限,且满足,41,3.5.1 有限状态马尔可夫链,5. 稳态分布存在定理 (1)定义： 设有一个r状态的齐次马尔可夫链，状态空间S=S1,S2,Sr 令 Wj(n)=P(Xn=Sj)=pj (t=n时刻状态Sj) 则Wj(n)=W1(n-1)p1j+W2(n-1)p2j+Wr(n-1)prj j=1,2, ,r,42,3.5.1 有限状态马尔可夫链,设W(n)=W1(n) W2(n) Wr(n) 则 W(n)W(n1)P W(n2)P2 W(0)Pn 其中，W(0) 是初始分布矢量， P是转移矩阵 若存在W1,W2,Wr, 满足,则称此马尔可夫链稳态分布存在,43,3.5.1 有限状态马尔可夫链,(2)定理3.5.1：稳态分布唯一性 设齐次马尔可夫链转移矩阵为P=Pij, i,j=1,2,r,稳态分布为Wj , j=1,2,r，则,a.,b. W=W1 W2 Wr是稳态分布矢量，有 W=WP,c. 当初始分布W(0)=W时，对于所有的n有 W(n)=W,d. W是唯一稳态分布,44,3.5.1 有限状态马尔可夫链,(3)定理3.5.2：稳态分布存在 设P为某一马尔可夫链的状态转移矩阵，则该链稳态分布存在的充要条件是存在一个正整数N,使矩阵 中所有元素均大于零。,45,3.5.2 马尔可夫信源,1.状态 信源输出符号的概率仅与已经输出的若干个符号有关，而与更前面的符号无关，称这若干个符号为信源的状态Si，所有可能的状态集合S称为状态空间,46,对于由m个符号构成的状态 下一状态,3.5.2 马尔可夫信源,47,2.马尔可夫信源 若随机变量序列X中的任一(m+1)时刻的随机变量 只依赖于它前面的已经发生的m个随机变量 ，而与更前面的随机变量无关，则 称这种信源为m阶马尔可夫信源（简写m阶M信源）。,3.5.2 马尔可夫信源,注：m阶M信源，状态 只与前一时刻的状态 有关。,48,3.5.2 马尔可夫信源,m阶马尔可夫信源的状态空间为,其中，p(Sj|Si)由信源