第2讲——离散信源的数学模型及其信息测度1.pdf

离散信源的数学模型 及其信息测度 离散信源的数学模型 及其信息测度 离散信源的数学模型离散信源的数学模型离散信源的数学模型离散信源的数学模型 及其信息测度及其信息测度及其信息测度及其信息测度 第二讲第二讲第二讲第二讲 输 入 消 息 码 字 输 出 消 息 先 验 概 率 消息后验概率 收到 输 入 消 息 码 字 输 出 消 息 先 验 概 率 消息后验概率 收到0收到收到01收到收到011 x1 x2 x3 x4 x5 x6 x7 x8 000 001 010 011 100 101 110 111 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 4 1 4 1 4 1 4 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 1 0 0 0 0 Review 设某系统的输入空间为设某系统的输入空间为X x1 x2 分别以二元数字 组 分别以二元数字 组000和和111表示 若系统变换过程中的转移概率为表示 若系统变换过程中的转移概率为 p 0 0 p 1 1 1 p p 1 0 p 0 1 p 则不难算出当 观察到输出数字为 则不难算出当 观察到输出数字为010的过程中输入消息的过程中输入消息x1和和x2的后 验概率变化 如表所示 的后 验概率变化 如表所示 消息后验概率消息后验概率 输入 消息 输入 消息 码字码字 输出输出 消息 先验 概率 消息 先验 概率 收到收到 0后后 收到收到 01后后 收到收到 010后后 x1 x2 000 111 1 2 1 2 Review 1 p 1 2 1 p p1 2 p 信源信源信道信道 信宿信宿 噪声源噪声源 编码器编码器 译码器译码器 消息消息 干扰干扰 信号 干扰信号 干扰消息消息 数字通信系统模型数字通信系统模型 可靠性 有效性 保密性和认证性可靠性 有效性 保密性和认证性 Review 离散信源的数学模型 及信息测度 离散信源的数学模型 及信息测度 离散信源的数学模型离散信源的数学模型离散信源的数学模型离散信源的数学模型 及信息测度及信息测度及信息测度及信息测度 2 1 2 1 2 1 2 1 信源及其分类信源及其分类信源及其分类信源及其分类 信源的数学描述信源的数学描述 在通信系统中收信者在未收到消息以前对信 源发出什么消息是不确定的 在通信系统中收信者在未收到消息以前对信 源发出什么消息是不确定的 是随机的 所 以可用 是随机的 所 以可用随机变量 随机序列或随机过程随机变量 随机序列或随机过程来 描述信源输出的消息 来 描述信源输出的消息 或者说用一个样本空 间及其概率测度 或者说用一个样本空 间及其概率测度 概率空间概率空间来描述信源 来描述信源 不同的信源输出的消息的不同的信源输出的消息的随机性质随机性质不同 可以根据消 息的不同的随机性质来对信源进行分类 不同 可以根据消 息的不同的随机性质来对信源进行分类 按照某时刻信源输出消息的取值集合的离散性和连续 性 按照某时刻信源输出消息的取值集合的离散性和连续 性 信源可分为信源可分为离散信源离散信源和和连续信源连续信源 按照信源输出消息的所对应的随机序列中随机变量前 后之间有无依赖关系 按照信源输出消息的所对应的随机序列中随机变量前 后之间有无依赖关系 信源可分为信源可分为无记忆信源无记忆信源和和有记忆 信源 有记忆 信源 按照信源输出消息的所对应的随机序列的平稳性按照信源输出消息的所对应的随机序列的平稳性 信源 可分为 信源 可分为平稳信源平稳信源和和非平稳信源非平稳信源 信源的分类信源的分类 离散信源离散信源 21 21 q q aPaPaP aaa xP X 1 1 0 1 q i i i aP aP且满足 连续信源连续信源 1 b a dxxp xp ba xp X 并满足 注 注 X代表随机变 量 指的是信源整 体 代表随机变 量 指的是信源整 体 ai代表随机事 件的某一结果或信 源的某个元素 代表随机事 件的某一结果或信 源的某个元素 注 注 这里的这里的p x 代 表概率密度函数 代 表概率密度函数 简单信源简单信源 离散信源在不同时刻发出的符号之间是无依赖的 彼 此统计独立的 离散信源在不同时刻发出的符号之间是无依赖的 彼 此统计独立的 q q PPPxP X 21 21 其中 其中 qi 21 且 q i i P 1 1 离散无记忆信源离散无记忆信源 NN k k k kN N N N q i q i N i ii N i iiiii Niiii q q i N aPP aPaaaPP qiiiaaa PPPP X 111 1 21 21 21 1 21 21 21 并满足 其中 由离散无记忆信源输出由离散无记忆信源输出N长的随机序列构成的信源 长的随机序列构成的信源 4 14 14 14 1 11100100 P X01 1 2 1 2 X P 离散无记忆信源离散无记忆信源 N次扩展信源次扩展信源 掷两枚硬币掷一枚硬币掷两枚硬币掷一枚硬币 有记忆信源有记忆信源 输出的随机序列 输出的随机序列X中各随机变量之间有依赖 关系 但记忆长度有限 中各随机变量之间有依赖 关系 但记忆长度有限 其它几种常见信源其它几种常见信源 T XrYr Yr 1 马尔可夫信源实例马尔可夫信源实例 Yr是一个是一个马氏链马氏链 Yr确定后确定后 Yr 1概率分布只与概率分布只与Yr有关有关 与与Yr 1 Yr 2 等无关等无关 相对码编码器相对码编码器 有记忆信源 输出的随机序列有记忆信源 输出的随机序列X中各随机变量之间有 依赖关系 但记忆长度有限 中各随机变量之间有 依赖关系 但记忆长度有限 m阶马尔可夫信源 信源每次发出的符号只与前阶马尔可夫信源 信源每次发出的符号只与前m个 符号有关 与更前面的符号无关 个 符号有关 与更前面的符号无关 随机波形信源 信源输出的消息在时间上和取值上都 是连续的 随机波形信源 信源输出的消息在时间上和取值上都 是连续的 其它几种常见信源其它几种常见信源 2 2 2 2 2 2 2 2 离散信源熵离散信源熵离散信源熵离散信源熵 ii xpfxI 应该满足以下条件 是先验概率 应该满足以下条件 是先验概率 i xp的单调递减函数的单调递减函数 1 i xp0 i xpf 0 i xp 时 时 i xpf 两个独立事件的联合信息量等于各自信息量之和 时 两个独立事件的联合信息量等于各自信息量之和 时 1 2 3 信息量应满足的条件信息量应满足的条件 设单符号离散信源的信源空间为设单符号离散信源的信源空间为 21 21 n n xpxpxp xxx xP X 1 1 0 1 n i ii xpxp且满足 自信息量定义自信息量定义 如果知道事件如果知道事件xi已发生 则该事件所含有的信息量称 为 已发生 则该事件所含有的信息量称 为自信息 自信息 定义为定义为 log 1 log i i i xp xp xI 对数换底关系 a X X b b a log log log I xi 含义含义 当事件当事件xi发生以前发生以前 表示事件表示事件xi 发生的发生的不确定性不确定性 当事件当事件xi发生以后发生以后 表示事件表示事件xi所含有的所含有的信息量信息量 I xi 单位单位 常用对数底是常用对数底是2 信息量的单位为比特信息量的单位为比特 bit 若取自然对数若取自然对数 则信息量的单位为奈特则信息量的单位为奈特 nat 1 nat log2e l 433 bit aXX bab logloglog 自信息量定义自信息量定义 或或 1 I xi 是非负值是非负值 2 当当p xi 1时 时 I xi 0 3 当当p xi 0时 时 I xi 4 I xi 是先验概率是先验概率p xi 的单调递减函数 即 当 的单调递减函数 即 当p x1 p x2 时 时 I x1 I x2 5 两个独立事件的联合信息量等于它们分别的信息 量之和 即统计独立信源的信息量等于它们分别 两个独立事件的联合信息量等于它们分别的信息 量之和 即统计独立信源的信息量等于它们分别 的信息量之和 的信息量之和 自信息的性质自信息的性质 二进制码元二进制码元0 1 当符号概率为当符号概率为p 0 1 4 p 1 3 4 则这两个符号的自信息量为 则这两个符号的自信息量为 I 0 log2 1 4 log24 2bit I 1 log2 3 4 0 4151 bit 一个以等概率出现的二进制码元一个以等概率出现的二进制码元 0 1 所包含的 自信息量为 所包含的 自信息量为 I 0 I 1 log2 1 2 log22 1 bit 自信息量例题自信息量例题 考虑两个随机事件 其联合概率空间为考虑两个随机事件 其联合概率空间为 联合自信息量联合自信息量 1 1 0 11 12111 1212111 n i m j jiji mnm mnnmm yxpyxp yxpyxpyxpyxp yxyxyxyxyxyx XYP XY log jiji yxpyxI 联合自信息与条件自信息联合自信息与条件自信息 在事件在事件yj出现的条件下 随机事件出现的条件下 随机事件xi发生的发生的 条件自信息量条件自信息量 log 2jiji yxpyxI 含义含义 联合自信息量和条件自信息量联合自信息量和条件自信息量性质性质 联合自信息量和条件自信息量联合自信息量和条件自信息量关系关系 当当X和和Y独立时 独立时 22 22 log log log log ijijijiiji ijjijjij I x yp x yp x p yxI xI yx p x yp yp xyI yI xy 22 22 log log log log ijijij ijij I x yp x yp x p y p xp yI xI y 联合自信息与条件自信息联合自信息与条件自信息 信源各个离散消息的信源各个离散消息的自信息量的数学期望自信息量的数学期望 即概率加权的 统计平均值 为信源的平均信息量 称为信源的信息熵 也叫信源熵或香农熵 简称熵 即概率加权的 统计平均值 为信源的平均信息量 称为信源的信息熵 也叫信源熵或香农熵 简称熵 熵函数的自变量是熵函数的自变量是X表示信源整体 实质上是离散无 记忆信源平均不确定度的度量 表示信源整体 实质上是离散无 记忆信源平均不确定度的度量 与自信息不同与自信息不同 自信 息表示某一消息所含有的信息量 它是一个随机变量 自信 息表示某一消息所含有的信息量 它是一个随机变量 不能用它来作为整个信源的信息测度 不能用它来作为整个信源的信息测度 log 1 log 2 1 2i n i i i i xpxp xp ExIEXH 信源熵定义信源熵定义 信源熵信源熵H X 的两种的两种物理含义物理含义 信源输出后 每个离散消息所提供的平均信息量 信源输出前 信源的平均不确定度 反映了随机变量 信源输出后 每个离散消息所提供的平均信息量 信源输出前 信源的平均不确定度 反映了随机变量X的随机性 的随机性 信源熵理解信源熵理解 例如有两个信源 其概率空间分别为 例如有两个信源 其概率空间分别为 01 099 0 21 xx xp X 5 05 0 21 yy yp Y bitXH08 001 0log01 099 0log99 0 bitYH15 0log5 05 0log5 0 因为因为H Y H X 所以信源所以信源Y比信源比信源X的平均不确定性要大 的平均不确定性要大 信源熵理解信源熵理解 电视屏上约有电视屏上约有 500 600 3 105个格点 按每格点 有 个格点 按每格点 有10个不同的灰度等级考虑 则共能组成个 不同的画面 按等概率计算 平均每个画 面可提供的信息量为 个不同的灰度等级考虑 则共能组成个 不同的画面 按等概率计算 平均每个画 面可提供的信息量为 5 3 10 22 1 log log 1 10 n ii i H Xp xp x 9 97 105 bit 5 103 10 5 103 10 1 信源熵例题信源熵例题 有一篇千字文章 假定每字可从万字表中任选 则共 有不同的千字文 有一篇千字文章 假定每字可从万字表中任选 则共 有不同的千字文 N 100001000 104000 篇 仍按等概率 篇 仍按等概率1 100001000计算 平均每篇千字文可提供 的 信息量为 计算 平均每篇千字文可提供 的 信息量为 H X log2N 1 3 104 bit 一个电视画面一个电视画面 平均提供的信息量远远超过平均提供的信息量远远超过 一篇 千字文 一篇 千字文 提供的信息量 提供的信息量 信源熵例题信源熵例题 该信源该信源X输出符号只有两个输出符号只有两个 设为设为0和和1输出符号发生 的概率分别为 输出符号发生 的概率分别为p和和q p q l 即信源的概率空间为 即信源的概率空间为 qpP X10 信源熵例题信源熵例题 则二元信源熵为则二元信源熵为 H X plogp qlogq plogp 1 p log 1 p H p 0 0 2 0 4 0 6 0 8 1 1 0 8 0 6 0 4 0 2 p H p H p plogp 1 p log 1 p 条件熵是在联合符号集合条件熵是在联合符号集合XY上的上的条件自信息量的数学期望条件自信息量的数学期望 在已知随机变量 在已知随机变量Y的条件下 随机变量的条件下 随机变量X的条件熵定义为 的条件熵定义为 log 11 11 ji m j n i ji ji m j n i jiji yxpyxp yxIyxpyxIEYXH 要用联合 概率加权 条件熵是一个确定值 表示信宿在收到条件熵是一个确定值 表示信宿在收到Y后 信源后 信源X仍然存 在的不确定度 这是传输失真所造成的 有时称 仍然存 在的不确定度 这是传输失真所造成的 有时称H X Y 为为 信道疑义度信道疑义度 也称损失熵 称条件熵 也称损失熵 称条件熵H Y X 为为噪声熵噪声熵 log 2 11 ij n i m j jiij xypyxpxyIEXYH 条件熵条件熵 联合离散符号集合联合离散符号集合XY上的每个元素对的上的每个元素对的联合 自信息量的数学期望 联合 自信息量的数学期望 log ji n i m j jiji n i m j ji yxpyxpyxIyxpXYH 2 1111 log kji ijk kji kji ijk kji zyxpzyxp zyxIzyxpZXYH 2 ji yx 联合熵联合熵 YXHYH XYHXHXYH N n nnNN N UUUUHUUUUH UUUHUUHUHUUUH 1 121121 21312121 熵 条件熵 联合熵关系熵 条件熵 联合熵关系 一个二进信源一个二进信源X发出符号集发出符号集 0 1 经过离散无记忆信道传 输 经过离散无记忆信道传 输 信道输出用信道输出用Y表示表示 由于信道中存在噪声由于信道中存在噪声 接收端除收 到 接收端除收 到0和和1的符号外的符号外 还有不确定符号还有不确定符号 2 已知已知X的先验概率的先验概率 p x0 2 3 p x1 1 3 符号转移概率 符号转移概率 p y0 x0 3 4 p y2 x0 1 4 p y1 x1 1 2 p y2 x1 1 2 XY 0 1 0 1 2 3 4 1 2 1 2 1 4 信源熵信源熵H X bitHXH92 0 3 1 log 3 1 3 2 log 3 2 3 1 3 2 例 题例 题 得联合概率 得联合概率 p x0y0 p x0 p y0 x0 2 3 3 4 1 2 p x0y1 p x0 p y1 x0 0 p x0y2 p x0 p y2 x0 2 3 1 4 1 6 p x1y0 p x1 p y0 x1 0 p x1y1 p x1 p y1 x1 1 3 1 2 1 6 p x1y2 p x1 p y2 x1 1 3 1 2 1 6 jijijiji yxpypxypxpyxp bit xypyxpXYH ij ij ji 88 0 2 1 log 6 1 2 1 log 6 1 4 1 log 6 1 4 3 log 2 1 log 由由 例 题例 题 条件熵条件熵H Y X 联合熵联合熵H XY H XY H X H Y X 1 8bit 11 i m j jij n i ji xpyxpypyxp 得得 p y0 p xiy0 p x0y