《[理学]信息论-第3章多符号离散信源与信道》由会员分享,可在线阅读,更多相关《[理学]信息论-第3章多符号离散信源与信道(61页珍藏版)》请在金锄头文库上搜索。
1、1,第3章 多符号离散信源与信道,内容提要 3.1 离散平稳信源的数学模型 3.2 离散平稳无记忆信源的信息熵 3.3 离散平稳有记忆信源的信息熵 3.4 离散平稳有记忆信源的极限熵 3.5 马尔可夫信源的极限熵 3.6 信源的剩余度和结构信息,2,3.1 离散平稳信源的数学模型,基本概念 多符号离散信源:由多个符号组成的时间(或空间)序列 才能代表一个完整的消息的信源,称为多符号离散信源。 多符号离散信道:相对于多符号离散信源来说,若信道的 输入端输入一个由多个信源符号组成的时间序列所代表的 消息,在信道的输出端相应以一定概率输出一个由同样个 数的符号组成的时间序列所代表的消息,这种信道称为
2、多 符号离散信道。,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
3、维联合概率分布不随时间的 推移而变化,对时间的起点来说是平稳的。,6,3.1 离散平稳信源的数学模型,2. 数学模型 信源符号集 ,N维离散平稳信源,,7,3.1 离散平稳信源的数学模型,数学模型 信源空间 其中,8,3.1 离散平稳信源的数学模型,推广 不妨假定:多符号离散平稳信源发出的所有信息都由N 个符号组成;多符号离散平稳信源发出的长度为N的不同 消息间相互统计独立、互不相关,因此可将N维离散稳定 信源在时间上延长到无穷序列 中,每N个随机变量看作一组,每组代表一个完整的消息。 N维离散平稳信源 称为信源 的N次扩展。,9,一. 离散平稳无记忆信源概念 定义 3.2.1 设信源 X 输
4、出符号集 ,r为信源发出的消息符号个数,每个符号发生的概率为 。这些消息符号彼此互不相关,且,3.2 离散平稳无记忆信源的信息熵,则 X 称为离散无记忆信源。,10,若N维离散平稳信源 中,各时刻 随机变量 之间相互统计独立,则 我们将 称为N维离散平稳无记忆信源。 对N维离散平稳无记忆信源 ,有,3.2 离散平稳无记忆信源的信息熵,11,3.2 离散平稳无记忆信源的信息熵,N维离散平稳无记忆信源 信源空间 其中,12,1. 最简单离散信源 用一维随机变量X描述,其数学模型为,且,特点:,3.2 离散平稳无记忆信源的信息熵,二 离散无记忆信源的信息熵,13,3.2 离散平稳无记忆信源的信息熵,
5、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是一个离散无记忆信源,其概
6、率空间为,其中,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,一 离散平稳有记忆信源的概念 若离散平稳信源在各时刻
7、发出的符号之间并不是统计独 立的,前一刻发出的符号,依某种统计规律影响到后续发 出的符号的可能性,即任一时刻发出的符号对这一时刻之 前发出的符号是“有记忆”的,那么信源X称为是离散平稳 有记忆信源; 由X扩展而成的多符号离散平稳信源 称为N维离散平稳有记忆信源。,3.3 离散平稳有记忆信源的信息熵,20,N维平稳有记忆信源 有平稳的特性 设Q和T是任意两个时刻,即有 所以,有,3.3 离散平稳有记忆信源的信息熵,21,进而可得 表明:N维离散平稳有记忆信源 的各维条件概率也是平稳的,与起始时刻无关,不随时间的推移而发生变化。,3.3 离散平稳有记忆信源的信息熵,22,3.3 离散平稳有记忆信源
8、的信息熵,N维离散平稳有记忆信源 信源空间 其中,N维离散平稳有记忆信源的概率空间是一个完备集。,23,3.3 离散平稳有记忆信源的信息熵,二 离散平稳有记忆信源的信息熵 1 二维离散平稳有记忆信源的信息熵,24,3.3 离散平稳有记忆信源的信息熵,(无记忆)与 (有记忆)的比较 表明:二维离散平稳有记忆信源每发一条消息提供的平均 信息量,不会超过二维离散平稳无记忆信源每发一条消息 提供的平均信息量。 之间的统计联系,即有记忆性,减少了二维离散 平稳有记忆信源每发一条消息提供的平均信息量。,25,3.3 离散平稳有记忆信源的信息熵,2 N维平稳有记忆信源的信息熵,26,3.3 离散平稳有记忆信
9、源的信息熵,几个结论 表明:离散平稳有记忆信源每发一个符号所提供的信息量, 随记忆长度的增长而减小。记忆长度越长,在某时刻发符 号之前的关于这个符号的预备知识越多,这时刻发符号的不 确定性越小,提供的平均信息量也就小。,(1),(2),(3),(4),27,3.3 离散平稳有记忆信源的信息熵,平均符号熵 定义 对离散平稳有记忆信源X来说,因为有记忆,所以在不 同时刻所发符号提供的平均信息量是不同的。 平均符号熵成为评估N维离散平稳有记忆信源,每发一 个符号提供的平均信息量,也就是提供信息能力的一个衡 量标准。,28,3.4 离散平稳有记忆信源的极限熵,极限熵(极限信息熵) 当信源符号序列长度趋
10、于无穷时,有,结论,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. 定义
11、: 设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+ 为一随机序列
12、,时间参数集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 有限状态马尔可夫
13、链,命题:设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=
14、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是
15、稳态分布矢量,有 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)由信源