信息论-第3章多符号离散信源与信道.ppt

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 qX的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离散平稳有记忆信源的信息熵 2N维平稳有记忆信源的信息熵 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 t T 是随机过程 任取0 t1 t2 tn ti T 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 n N 为一随机序列 时间参数集N 0 1 2 其状态空间S S1 S2 SJ 有限或可数 若对所有n N 有 则称 xn n N 为马尔可夫链 即有限状态一阶马尔可夫链 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步转移矩阵 n 1 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 prjj 1 2 r 42 3 5 1有限状态马尔可夫链 设W n W1 n W2 n Wr n 则W n W n 1 P W n 2 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 W1W2 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 由信源符号条件概率 确定 49 状态一步转移矩阵 P 每行元素处于 0 1 且每行元素之和等于1 3 5 2马尔可夫信源 50 m阶M信源状态n步转移矩阵 P n 3 5 2马尔可夫信源 说明 状态一步转移概率是描述m阶M信源有依赖地发出消息 状态 的统计特性的最本质的参数 51 3 5 2马尔可夫信源 3信源的极限熵当时间足够长时 遍历的m阶马尔可夫信源可视为平稳信源 52 3 5 2马尔可夫信源 说明 m阶M信源的Markov性 使求解离散平稳有记忆信源的极限熵的无限问题 转化成有限问题 53 极限熵中的状态概率应是m阶M信源到达稳定时出现状态的概率 把这种概率称为状态极限概率 若对于有限平稳的m阶M信源 由m个符号组成的消息 状态 和存在一个正整数 且经过步 从状态转移到状态的步转移概率则这种m阶M信源具有各态历经性 3 5 2马尔可夫信源 54 各态历经定理对各态历经的m阶M信源来说 对每个都存在不依赖于起始状态的状态极限概率而且状态极限概率是在约束件的约束下 方程组的唯一解 3 5 2马尔可夫信源 55 3 6信源的剩余度与结构信息 1 相关性 1 平稳信源条件熵H XN X1X2 XN 1 随N的增加是非递增的 56 4 信源输出符号间的依赖关系使信源熵减小 这就是信源的相关性 相关长度越长 信源熵越小 趋于极限熵H 相关长度越短 信源熵越大 趋于极限熵H0 2 等概分布时 平稳信源熵最大 Hmax H0 logq 3 3 6信源的剩余度与结构信息 57 当信源等概率分布时 H0 Hmax logq 2 剩余度 1 信源剩余度定义为 其中 H 为信源实际熵H0 Hmax为信源最大熵 3 6信源的剩余度与结构信息 58 2 信源实际熵与具有同样符号集的最大熵的比值称为熵的相对率 所以