信息论基础复习题目PPT课件

例2 1 有12个球 只有一个是非标重球 问是否存在用天平称3次必然找到该球的方法 从信息的角度解决 解 天平的状态有三种 平衡 左轻 左重每称一次消除一种状态 则带来的信息量为log3则称3次后 带来的信息量为3log3 log27 结论 而一个非标球的携带的信息量为 可见 信息的度量是为了找到解决问题的方法 而不是纯粹度量信息的大小 设离散无记忆信源 其发生的消息为 202120130213001203210110321010021032011223210 求 1 此消息的自信息量 2 在此消息中平均每个符号携带的信息量 例2 2 解 1 消息的自信息量就是等于消息中各个符号的自信息量之和 根据题意可得 此消息中共有14个 0 符号 13个 1 符号 12个 2 符号 6个 3 符号 则得到的自信息量是 2 此消息中平均每个符号携带的信息量为 原因 2 问的值是该特定消息中平均每个符号携带的信息量 而信息熵是离散无记忆信源平均每个符号携带的信息量 是统计平均值 信源的信息熵 结论 2 问的值与信源的信息熵不完全相等 设在一正方形棋盘上共有64个方格 如果甲将一粒棋子随意放在棋盘中的某方格且让乙猜测棋子所在的位置所携带的信息量 1 将方格按顺序编号 令乙猜测棋子所在方格的顺序号 2 将方格分别按行和列编号 甲将棋子所在方格的行或列编号告诉乙之后 再令乙猜测棋子所在列或行的位置 例2 3 解 1 令把棋子任意放在棋盘的某一格为事件xi 则该事件发生的概率为 则该事件携带的信息量为 2 设行为随机变量X 列为随机变量Y 则在事件yj发生后事件xi发生的概率为 则该事件携带的信息量为 由结果可知 事件yj的出现降低了事件xi发生所携带的信息量 原因 事件yj的出现带来了事件xi的部分的信息 导致对事件xi的不确定性减小 设一系统的输入符号集X x1 x2 x3 x4 x5 输出符号集Y y1 y2 y3 y4 输入符号与输出符号间的联合分布为 试求 H XY H X H Y H Y X 和H X Y 例2 4 解 由全概率公式可知 则从已知可求 H Y X H XY H X 2 665 2 066 0 599bit symbol H X Y H XY H Y 2 665 1 856 0 809bit symbol 定义 联合集 中 在给定zk的条件下 xi与yj之间的互信息量定义为条件互信息量 即 表明 在随机变量Z出现符号zk的前提条件下 随机变量Y出现符号yj前 后 对信源发送符号xi的条件不确定性的减少 2 2 2条件互信息 上式表明 在随机变量Z出现符号zk的前提条件下 信道1通信前 后 输入与输出端同时出现yj和xi的条件不确定性的减少 利用互信息和条件互信息可解决符号序列的信息测量问题 发送的信息 H X 损失的信息 H X Y 通过信道传递到接收端的关于X的信息 I X Y 例2 6 问 通信中发送的信息是多少 信道中损失的信息是多少 X通过信道传递了多少信息给信宿 如果X Y 说明信道无干扰 则I X Y H X 如果X与Y相互独立 说明干扰很大 I X Y 0 例2 7 把已知信源 信道上 求在该信道上传输的平均互信息量I X Y 疑义度H X Y 噪声熵H Y X 和联合熵H XY 接到下图所示的 解 由题意可知 平均互信息 噪声熵 疑义度 例2 10 设有一批电阻 按阻值分70 是2千欧姆 30 是5千欧姆 按功耗分64 是1 8W 其余是1 4W 现已知2千欧姆阻值的电阻中80 是1 8W 问通过测量阻值可以平均得到的关于瓦数的信息量是多少 解 根据题意 设电阻的阻值为事件X 电阻的功率为事件Y 它们的概率空间分别为 并且已知 首先计算 根据全概率公式 可得 通过测量电阻阻值可以得到关于瓦数的平均信息量就是平均互信息I X Y 则通过测量阻值可以平均得到的关于瓦数的信息量是0 816比特 例2 11 有一离散无记忆信源 其输出为 相应的概率为 设计两个独立试验去观察它 其结果分别为 已知条件概率为 解 1 因为 所以必须求出 则有 由此可知第二个试验好 2 因为 所以必须求出 又由于试验Y1 Y2是相互独立的试验 所以 则有 则有 由此可知 做 两个试验比做 可多得关于X的信息为 中的一个试验各 3 表示做完实验Y2后 从实验Y1可获得关于X的信息量为0 5bit signal 表示做完实验Y1后 从实验Y2可获得关于X的信息量为1bit signal 例3 1 例3 2 1 为了使电视图像获得良好的清晰度和规定的适当的对比度 需要用 个像素和10个不同亮度的电平 设每秒要传递30帧图像 所有象素是独立变化的 且所有亮度电平等概率出现 求传递此图像所需的信息率 比特 秒 2 设某彩电系统 除了满足对黑白电视系统的上述要求外 还须有30个不同的色彩度 试证明传输这彩色系统的信息率约是黑白系统信息率的2 5倍 解 1 每个象素亮度信源的概率空间为 每个象素亮度含有的信息量为 H X log10 1哈特来 象素 3 32比特 象素 每帧图像含有的信息量为 设每秒传送30帧图像 则传递此图像所需的信息率为 每个象素色彩度含有的信息量为 H Y log30 4 91比特 象素 亮度和色彩度同时出现 每个象素含有的信息量为 H XY H X H Y log10 log30 8 23比特 象素 传输这彩色系统的信息率与传输黑白系统的信息率之比就等于彩色系统每象素含有的信息量与黑白系统每象素含有信息量之比 即 H XY H X 2 5 则证明传输这彩色系统的信息率是传输黑白系统的信息率的2 5倍 例3 3 每帧电视图像可以认为是由 个象素组成的 所以象素都是独立变化的 且每一个象素又取128个不同的亮度电平 并设亮度电平等概率出现 若现有一个广播员在约10000个汉字的字集中选1000个字来口述此电视图像 设每个字是等概率分布的 并且彼此独立的 试问广播员描述此图像所广播的信息量是多少 若要恰当描述此图像 广播员在口述中至少需用多少汉字 解 1 分析可知汉字字集是等概率分布的 则汉字字集信源为 得该汉字字集中每个汉字含有的信息量为 H Y log10000 13 29比特 字 广播员描述此帧图像所广播的信息量为 2 分析可知每个象素的亮度信源为 每个象素亮度含有的信息量为 H X log128 7比特 象素 每帧图像含有的信息量为 广播员口述此图像至少需用的汉字数为 例3 4 对一最高频率分量为4kHz的模拟信号以奈奎斯特采样定理采样 已知抽样结果是一个独立的平稳随机序列 现将每个抽样值量化为5个离散电平之一 已知这5个电平构成的符号集 X 的概率特性为 求这个离散信源每秒传送的平均信息量 例3 5 设某二阶离散平稳信源X X1X2的原始信源的信源模型为 X X1X2中前后两个符号的条件概率为 比较原始信源与二阶信源的熵 信源X提供的熵 平均每个符号携带的信息量 结论 极限熵 条件熵都小于原始信源的熵原因 符号之间存在相关性 解 原始信源的熵 条件概率确定的条件熵 二 马尔可夫信源的状态转移图 例3 6 设有一个二进制一阶马尔可夫信源 其信源符号集为A 0 1 条件概率为求状态转移矩阵 解 信源符号个数q 2 k 1 故状态数 则令状态S1 0 状态S2 1 状态图 根据状态图求状态转移概率 p S1 S1 0 25p S2 S1 0 75p S1 S2 0 50p S2 S2 0 50 则状态转移矩阵为 有一个二进制二阶马尔可夫信源 其信源符号集为A 0 1 条件概率为 求状态转移矩阵 例3 7 由状态图可知转移矩阵 则令 状态S1 00 状态S2 01 状态S3 10 状态S4 11 则状态图 解 信源符号个数q 2 k 2 故状态数 解 由此判断 稳态分布存在 由WP W以及各状态概率之和为1 得 和 3 举例说明马尔可夫信源熵的计算方法 例3 9 有一个二进制二阶马尔可夫信源 其信源符号集为A 0 1 条件概率为 求状态转移矩阵 解 由例7可知状态转移矩阵为 可知 此信源是遍历性的马尔可夫信源 稳态分布存在 设稳态分布为 则利用WP W和可知 对于遍历性马尔可夫信源有 由 则有 3 5信源的相关性和剩余度 一 信源的相关性 信源输出符号之间的依赖关系 对于离散平稳信源有 当信源输出符号之间的相关程度越长 实际熵越小 二 信源冗余度 例3 10 英文26个字母加空格共27个符号 根据统计出现的概率如表所示 则英文字母携带的最大信息量是多少 冗余度为多少 解 英文字母携带的最大信息量即为等概时携带的信息量 英文字母携带的实际熵 英文字母的冗余度 例3 11 中文冗余度的统计比英文要复杂得多 难得多 假如以 辞海 上海 1989 收集的大约15000汉字为信源消息符号 则中文的最大信息熵为 目前还没有找到给出中文实际熵好的统计方法的文献 但根据目前广泛使用的文本压缩软件的压缩率来看 中文实际熵应该不会大于5比特 汉字 估计中文的冗余度大约在80 左右 讨论 从提高抗干扰能力角度出发 希望减少或去掉剩余度 希望增加或保留信源的剩余度 因为 剩余度大的消息具有很强的抗干扰能力 当干扰使消息在传输过程中出现错误时 能从它的上下关联中纠正错误 从提高信息传输的有效性观点出发 原因是什么 例3 12 黑白气象传真图的消息只有黑白两种颜色 即信源X 黑 白 且p 黑 0 3 p 白 0 7 1 假设图上黑白消息出现前后没有关系 求熵H X 2 假设消息前后由关系 其依赖关系为p 白 白 0 9 p 黑 白 0 1 p 白 黑 0 2 p 黑 黑 0 8 求此一阶马尔可夫信源的熵H2 3 分别求上述两种信源得剩余度 并比较H X 和H2的大小 并说明其物理意义 信源的信息熵 2 分析得此信源为一阶马尔可夫信源 它的的状态集为 A S1 黑 S2 白 则状态转移图 解 1 假设黑白气象传真图上黑白消息出现的前后没有关系 则等效于一个离散无记忆信源 信源概率空间为 则其状态转移矩阵为 由此可见 此马尔可夫信源是遍历的 稳态分布存在 则设W p S1 p S2 根据WP W可得 可以求出 则此信源的熵为 3 黑白消息信源的剩余度 即 二元对称信道 BSC 二进制对称信道 其中 p q表示正确传输的概率 二元删除信道 二进制删除信道 例4 2 考虑二元对称信道 其信源概率空间为 求其平均互信息 解 应用全概率公式 则有 则平均互信息 当信道固定 即p为一个固定常数时 可得到I X Y 是信源输出分布 的上凸函数 当信源固定 即 是一个常数时 可得到I X Y 是信道传递概率p的下凸函数 当p 0 5时 I X Y 0 在接收端未获得信息量 当 1 2时 即取极大值 例4 3 掷色子 如果结果是1 2 3 4 则抛一次硬币 如果结果是5 6 则抛两次硬币 试计算从抛硬币的结果可以得到多少掷色子的信息量 例4 4 求二元无记忆对称信道的二次扩展信道 定理1 若信道的输入 输出分别为N长序列X和Y 且信道是无记忆的 即 用两个定理回答这个问题 定理2 若信道的输入 输出分别为N长序列X和Y 且信源是无记忆的 即 当每个序列中的分量Xi取值于同一信源符号集 且具有同一种概率分布 则输出Y的分量Yi也取值同一符号集 则各I Xi Yi 是相等的 即 对于N次扩展 则有 例4 5 下图中的X Y Z满足马氏链 求该串联信道的总信道矩阵 例4 6 考虑二元对称信道 其信源概率空间为 求该信道的信道容量 例4 7 求具有以下信道矩阵的信道的信道容量 解 分析可知这是一个对称信道 则信道容量为 结论 在该对称信道中 只有当信道输入符号等概分布时 每个符号平均能传送的信息为0 126bit 一般情况下每个符号平均传输的信息都是小于0 126bit 对于二元对称信道 r 2 则信道容量C 解 均匀信道是对称信道的一种特例 则其信道容量用对称信道的信道容量的求解公式 则 例4 9 求二元对称删除信道的信道容量 例4 10 设有扰离散信道的传输情况如图所示 求C以及达到C时的输入概率分布 利用对称信道的信道容量公式求得 解 I X Y H Y H Y X 则有 达到C时的输入分布 六 N次扩展离散无记忆信道的信道容量 表示某时刻通过离散无记忆信道传输的最大信息量 则 对于离散无记忆信道有 对于N次扩展信道 任何时刻是相同的 例4 12 已知信道的带宽B为3kHz 信号在信道传输中受到单边功率谱密度为的加性白高斯噪声的干扰 信号的平均功率S为9W 1 求信道的容量 2 若信道带宽增加到原来的10倍 并保持信道容量不变 那么信号平均功率要改变多少dB 无损信道的剩余度 第五节信源与信道匹配 一 信道剩余度 C I X Y C R 二 相对剩余度 1 R C 对于无损信道 C logr 无损信道的相对剩余度 信源的剩余度 对于无损信道 可通过信源编码 减小信源的剩余度 提高信道的信息传输率使之达到C 例4 13 有一个二元对称信道 其信道矩阵如图所示 设该信道以1500个二元符号 秒的速度传输输入符号 现有一消息序列共有14000个二元符号 并设在这消息中p 1 p 0 1 2 问从信息传输的角度来考虑 10秒内能否将这消息序列无失真传送完 解 分析得消息信源的熵为H X 1比特则这个消息序列含有信息量14000 1 14000比特 由图可知 信道矩阵为 由信道矩阵可知 此信道为二元对称信道 所以其信道容量 最大信息传输率 为 信道的最大信息传输速率 信道在10秒钟内能无失真传输的最大信息量 12879比特14000 12879则从信息传输的角度考虑 不可能在10秒内将这消息无失真传输完 2 二元码 3 定长码 8 非同价码 信道的基本符号集中码元个数为2 每个码元所占的传输时间不完全相同 7 同价码 每个码元所占的传输时间相同 6 奇异码 码中码字至少有两个相同 5 非奇异码 码中所有的码字都不相同 4 变长码 码中的码字长短不一 码中所有码字的长度都相同 二 码的类型 1 分组码 将信源符号集中的每个信源组符号映射成一个固定的码字 例5 1 设有二元信道的信源编码器 其概率空间 编码后的结果 信源符号Si码1码2码3码4S100000S201011110S3100010000S4111111110 定长码非奇异码 非奇异码变长码 变长码奇异码 9 N次扩展码 类似N次扩展信源 举例 10 唯一可译码 一个分组码若对任意有限的整数N 其N次扩展码均为非奇异码 则称为唯一可译码 或每个信源符号序列映射成一个固定的码字 并且代码组中每个码字只能唯一地被译成所对应的信源符号序列 11 即时码 无需考虑后续的码符号即可从码符号序列中译出码字 这样的唯一可译码称为即时码 又称非延时码 唯一可译码要成为即时码的条件 其中任一码字都不是其他码字的前缀 即时码可用树图构造 1 树图的最顶部的节点称为树根 树枝的尽头称为节点 2 每个节点的分支数等于码元数 且各分支分别对应一个固定的码元 各分支伸出方向所对应的码元是统一的 如图向左伸出为0 向右伸出为1 3 各码字分布在码树的终端节点 即不再分支的节点 4 节点一旦被分配码字 后边的枝便要去掉 否则成为非即时码 例5 2 英文电报有32个符号 26个字母加上6个字符 请问对信源符号进行二进制编码 要想有唯一可译码 码长至少为多少 解 r 2 q 32 N 1 要想有唯一可译码 则 二 定长编码定理 进行长度为的定长编码 对 用码元集 设离散无记忆信源 的熵为H S 其N次扩展 对于 只要满足 正定理 则当N足够大时 几乎可实现无失真信源编码 此时译码差错小于 反之 若 则当N足够大时 译码错误概率趋于1 编码误差任意大 逆定理 信源为 解 等概时所需的码长是5 而考虑相关性时需要的码长是2 三 编码效率 当允许错误概率小于 时 信源符号序列的长度N 为自信息的方差 如果为最佳编码 则 二 克拉夫特 Kraft 不等式和麦克米伦 McMillan 不等式 1 Kraft不等式 2 McMillan不等式 在满足kraft不等式的条件下 唯一可译码存在的充要条件是 设S0为原始码字的集合 再构造一系列集合S1 S2 Sn 构造S1 S2 Sn的方法 1 首先考察S0中所有的码字 若码字Wj是码字Wi的前缀 即Wi WjA 则将后缀A列为S1中的元素 S1就是由所有具有这种性质的A构成的集合 2 当n 1 则将S0于Sn 1比较 看是否S0中的码字是Sn 1的前缀 如果是 则取后缀为Sn中元素 且看Sn 1中码字是否为S0中码字的前缀 如果是 则取后缀为Sn中元素 如此构成集合Sn 三 唯一可译码判断准则 准则 一种码为唯一可译码的充要条件是S1 S2 中没有一个含有S0中的码字 用0 1码符号分别代表概率最小的两个信源符号 并将这两个概率最小的信源符号合并成一个 从而得到只包含q 1个符号的新信源S1 称为缩减信号源 三 二元Huffman编码 1 编码步骤 将信源发出的q个信源按其概率依次从大到小排列 把缩减信源S1的符号按概率从大到小排列 再将其最后两个概率最小的符号合并成一个符号 并分别用0和1码元表示 这样形成q 2个符号的新信源S2 依此类推 直至信源只剩两个符号为止 并分别用 0 和 1 表示 从最后一级缩减信源开始 向前返回 得出各信源符号所对应的码符号序列 即相应码字 例5 8 信源符号Si概率p Si 编码过程码字Wi码长liS1S2S3S10 4S20 2S30 2S40 1S50 1 0 40 2 0 40 6 编码过程 101200030010400114 用树图检验是否为即时码 1 每次对信号缩减时 赋予最后两个概率最小的符号用 0 和 1 是可任意的 2 对信源进行缩减时两个概率最小的符号合并后的概率与其他符号概率相同时 可任意排序 经哈夫曼编码方法得到的码并非是唯一的 造成非唯一的原因 例题5 8 由此可见 结论 当进行哈夫曼编码时 为了得到质量好的码 应使合并的信源符号位于缩减信源序列尽可能高的位置 这样可充分利用短码 r元哈夫曼码可由二元哈夫曼码的编码方法推广得到 只是编码过程中构成缩减信源时 每次将r个概率最小的符号合并 并分别用0 1 r 1码元表示 为了充分利用短码 使哈夫曼码的平均码长最短 必须是最后一个缩减信源有r个信源符号 因此 对于r元哈夫曼码 信源S的符号个数q必须满足 如果信源S的符号个数q不满足上式 则增补一些概率为0的信源符号 四 r元哈夫曼码 例5 9 有一离散无记忆信源 码元集X 0 1 2 对S进行3元哈夫曼编码 解 信源符号概率编码过程码字Wi码长liSip Si S1S2WiliS10 40 40 401S20 30 30 321S30 20 20 3102S40 050 05122S50 0250 051103S60 0251113S701123 2 1 0 2 1 0 2 1 0 霍夫曼编码的特点 1 由于霍夫曼编码总是以最小概率相加的方法来缩减参与皮埃对的概率个数 因此概率越小 对缩减的贡献越大 其对应消息的码字也越长 2 最小概率相加的方法使得编码不具有唯一性 尤其是碰到存在几个消息符号有着相同概率的情况 将会有多种路径选择 即既具有多种可能的代码组集合 3 尽管对同一信源存在着多种结果的霍夫曼编码 但它们的平均码长几乎都是相等的 因为每一种路径选择都是使用最小概率相加的方法 其实质都是遵循最佳编码的原则 因此霍夫曼编码是最佳编码 霍夫曼编码存在的问题 1 霍夫曼编码要求信源消息概率已知或可估计 由于初始信源不可能总是统计好了概率 为此编码之前必须先估算信源的统计特性 在信源具有记忆性能并用霍夫曼编码来表示信源的扩展输出时 概率的估计很耗费时间 2 霍夫曼编码是建立在编码器和译码器都知道码树结构的基础上的 如果信源消息数目变大 则树型结构的大小和算法的复杂性会呈指数规律增加 例6 1 参见下图 假设P a1 0 4 分别求出4种译码规则所对应的平均差错率 解 信道输入概率矩阵和转移矩阵分别为 转移矩阵各行元素乘以对应的输入概率 得联合概率矩阵 译码规则F1对应的平均差错率为 其它译码规则对应的平均差错率分别为 Pe F2 0 4Pe F3 0 14Pe F4 0 86 四种规则相比 F3最好 F4最差 例6 2参见下图 假设P a1 0 4 求最佳译码规则 解 例6 1已经求出联合概率矩阵 重写为 则最大联合概率译码规则为 对应的平均差错概率 按最大转移概率条件确定的译码规则 例6 3 已知信道转移矩阵 试确定译码规则 解 按转移概率最大原则确定极大似然译码规则如下 二 极大似然译码规则 提问 传输系统的Pe要求控制在10 6以下 而利用译码规则的Pe太高 如何降低平均差错率呢 信道编码 一 简单重复编码 对信源符号进行 重复2次 编码 重复2次 编码规则为 求出3次扩展信道的转移矩阵 按极大似然译码规则得译码函数 即 译码差错率为 结论 信道编码降低平均错误率 提问 信道编码对信息传输速率有什么影响呢 信道编码 或称为纠错编码 就是靠增加 冗余 码元来克服或减轻噪声影响的 结论 信道编码降低了信道的信息传输率 信道编码之后的信息率或信道待传的信息率为 无信道编码的信息率或信道待传的信息率为 二 对符号串编码 矢量编码 例6 4 二元信源U 若取二元符号串 00 01 10 11 作为消息 则消息个数增加为M 4 提问 此时平均差错率又发生怎样的变化呢 结论 增加信源消息个数 可提高信道的信息传输率 取码长N 3 则编码后的信息率为R log4 3 2 3比特 码元 码长N 3 可供选择的码字为 选择以下编码函数 根据信道转移矩阵 确定极大似然译码规则为 则平均差错率为 结论 增加消息个数M与重复编码相比 在提高信息率的同时会使平均差错率增大 第四节汉明距离 两个等长符号序列x和y之间的汉明距离 记为D x y 是x与y之间对应位置上不同符号的个数 解 求汉明距离 D x z 2 D y z 3因此 z与x的相似程度高于与y的相似程度 一 定义 例6 5 x 100111 y 111000 z 111111 比较z与x和y的相似程度 X和Y是二元序列 记为 是等长码 则C中任意两个不同码字之间的汉明距离或码间距离为 码C的最小码间距离定义为 二元对称信道 可以根据汉明距离来决定译码规则 经N次扩展信道传送之后 按极大似然译码规则进行译码 记N长二元符号串为 由信道无记忆可知转移概率为 码元错误概率为p 正确概率为 则有 极大似然译码规则等价为最小汉明距离译码规则 最小距离译码规则可在一般信道中采用 但不一定与极大似然译码规则等价 只有对于二元对称信道 它才与极大似然译码规则等价 并且当输入等概时是最佳的 对于二元对称信道 若输入等概 无论用什么规则确定译码函数 与之对应的平均差错率都可用汉明距离表示 结论 第五节有噪信道编码定理 一 正定理 香农第二定理 若信道是离散 无记忆 平稳的 且信道容量为C 只要待传送的信息率RC 就一定找不到一种信道编码方法 使得码长足够大时 平均差错率任意接近于零 信道编码定理告诉我们 RC时 无论如何编码 都不可能使平均差错绿逼近零 因此 信道容量C是确保可靠性传输的信息传输率的上限 例7 1假定离散矢量信源N 3 输出矢量序列为X X1X2X3 其中Xi i 1 2 3的取值为 0 1 经信道传输后的输出为Y Y1Y2Y3 其中Yj j 1 2 3的取值为 0 1 定义失真函数为d 0 0 d 1 1 0 d 0 1 d 1 0 1 求矢量失真矩阵 dN 解 由矢量失真函数的定义得 类似可以得到其