信息论与编码实验指导书

信息论与编码 实验指导书 邹东尧 等编 计算机与通信工程学院 信息与通信工程系 2010 年 10 月 绪 论 随着信息产业的飞速发展 对从事信息 通信 电子工程类等专业的人 员的要求也越来越高 而 信息论与编码 是这类专业的专业必修课 这门 课主要介绍了有关信息论的基本原理以及信源编码 信道编码的内容 通过理论与实践的结合 才能更好的领会知识的真谛 信息论与编码 结合实验的实践 让学生更能深刻的理解和掌握这门课的基本概念 基本理 论 并培养学生的动手实践能力 本实验指导书正是配合教学计划的实验教学而编写 主要是基于 matlab 仿真软件对信源编解码和信道容量进行仿真 本书共有三个实验 绘制信源 熵函数曲线 哈夫曼编解码和离散信道容量 为实验大纲要求的必做实验 本书主要由邹东尧编写 主要参考了李祖贺等编写的 信息论与编码 实验指导书 并得到了李祖贺等老师的大力支持 特此对他们表示衷心的感 谢 由于时间仓促 错误难免 恳请读者谅解和指正 郑州轻工业学院 计算机与通信工程学院 信息与通信工程系 2010 年 10 月 目 录 实验一 绘制信源熵函数曲线 4 实验二 哈夫曼编解码 7 实验三 离散信道容量 13 1 实验一实验一 绘制信源熵函数曲线绘制信源熵函数曲线 一 实验目的一 实验目的 1 掌握离散信源熵的原理和计算方法 2 熟悉 matlab 软件的基本操作 练习应用 matlab 软件进行信源熵函数曲 线的绘制 3 理解信源熵的物理意义 并能从信源熵函数曲线图上进行解释其物理 意义 二 实验原理二 实验原理 1 离散信源相关的基本概念 原理和计算公式 产生离散信息的信源称为离散信源 离散信源只能产生有限种符号 假定 X 是一个离散随机变量 即它的取值范围 R x1 x2 x3 是有限 或可数的 设第 i 个变量 xi发生的概率为 pi P X xi 则 定义一个随机事件的自信息量 I xi 为其对应的随机变量 xi出现概率 对数的负值 即 I xi log2 p xi 定义随机事件 X 的平均不确定度 H X 为离散随机变量 xi出现概率的 数学期望 即 ii iiii xpxpxIxpXH log 单位为 比特 符号 或 比特 符号序列 平均不确定度 H X 的定义公式与热力学中熵的表示形式相同 所以 又把平均不确定度 H X 称为信源 X 的信源熵 必须注意一下几点 a 某一信源 不管它是否输出符号 只有这些符号具有某些概率特性 必有信源的熵值 这熵值是在总体平均上才有意义 因而是个确定 值 一般写成 H X X 是指随机变量的整体 包括概率分布 b 信息量则只有当信源输出符号而被接收者收到后 才有意义 这就 是给与信息者的信息度量 这值本身也可以是随机量 也可以与接 收者的情况有关 c 熵是在平均意义上来表征信源的总体特征的 信源熵是表征信源的 平均不确定度 平均自信息量是消除信源不确定度时所需要的信息 的量度 即收到一个信源符号 全部解除了这个符号的不确定度 或者说获得这么大的信息量后 信源不确定度就被消除了 信源熵 和平均自信息量两者在数值上相等 但含义不同 d 当某一符号 xi的概率 p xi 为零时 p xi log p xi 在熵公式中无意义 为此规定这时的 p xi log p xi 也为零 当信源 X 中只含有一个符 号 x 时 必有 p x 1 此时信源熵 H X 为零 例 1 1 设信源符号集 X 0 1 每个符号发生的概率分别为 p 0 p p 1 q p q 1 即信源的概率空间为 1 0 qpP X 则该二元信源的信源熵为 H X p log p q log q p log p 1 p log 1 p 即 H p p log p 1 p log 1 p 其中 0 p 1 P 0 时 H 0 0 P 1 时 H 1 0 2 MATLAB 二维绘图 例对函数 y f x 进行绘图 则用 matlab 中的命令 plot x y 就可以自动绘 制出二维图来 如果打开过图形窗口 则在最近打开的图形窗口上绘制此图 如果未打开图形窗口 则开一个新的图形窗口绘图 例 1 2 在 matlab 上绘制余弦曲线图 y cos x 其中 0 x 2 x 0 0 1 2 pi 生成横坐标向量 使其为 0 0 1 0 2 6 2 y cos x 计算余弦向量 plot x y 绘制图形 三 实验内容三 实验内容 用 matlab 软件绘制二源信源熵函数曲线 根据曲线说明信源熵的物理意义 四 实验要求四 实验要求 1 提前预习实验 认真阅读实验原理以及相应的参考书 2 认真高效的完成实验 实验中服从实验室管理人员以及实验指导老师 的管理 3 认真填写实验报告 2 实验二实验二 哈夫曼编码哈夫曼编码 一 实验目的一 实验目的 1 掌握哈夫曼编码的原理及编码步骤 2 练习 matlab 中哈夫曼编码函数的调用及通信工具箱的使用 二 实验原理二 实验原理 通信的根本问题是如何将信源输出的信息在接收端的信宿精确或近似的复 制出来 为了有效地复制信号 就通过对信源进行编码 使通信系统与信源的 统计特性相匹配 若接收端要求无失真地精确地复制信源输出的信息 这样的信源编码即为 无失真编码 即使对于一个小的时间段内 连续信源输出的信息量也可以是无 限大的 所以对其是无法实现无失真编码的 而离散信源输出的信息量却可以 看成是有限的 所以只有离散信源才可能实现无失真编码 凡是能载荷一定的信息量 且码字的平均长度最短 可分离的变长码的码 字集合都可以称为最佳码 为此必须将概率大的信息符号编以短的码字 概率 小的符号编以长的码字 使得平均码字长度最短 变字长编码的最佳编码定理 在变字长码中 对于概率大的信息符号编以 短字长的码 对于概率小的信息符号编以长字长的码 如果码字长度严格按照 符号概率的大小顺序排列 则平均码字长度一定小于俺任何顺序排列方式得到 的码字长度 哈夫曼编码就是利用了这个定理 讲等长分组的信源符号 根据其概率分 布采用不等长编码 概率大的分组 使用短的码字编码 概率小的分组 使用 长的码字编码 哈夫曼编码把信源按概率大小顺序排列 并设法按逆次序分配 码字的长度 在分配码字的长度时 首先将出现概率最小的两个符号相加 合 成一个概率 第二步把这个合成的概率看成是一个新组合符号的概率 重复上 述做法 直到最后只剩下两个符号的概率为止 完成以上概率相加顺序排列后 再反过来逐步向前进行编码 每一步有两个分支 各赋予一个二进制码 可以 对概率大的编为 0 码 概率小的编为 1 码 反之亦然 哈夫曼编码的具体步骤归纳如下 1 统计 n 个信源消息符号 得到 n 个不同概率的信息符号 2 将这 n 个信源信息符号按其概率大小依次排序 p x1 p x2 p xn 3 取两个概率最小的信息符号分别配以 0 和 1 两个码元 并将这两个概 率相加作为一个新的信息符号的概率 和未分配的信息符号构成新的 信息符号序列 4 将剩余的信息符号 按概率大小重新进行排序 5 重复步骤 3 将排序后的最后两个小概论相加 相加和与其他概率再排 序 6 如此反复重复 n 2 次 最后只剩下两个概率 7 从最后一级开始 向前返回得到各个信源符号所对应的码元序列 即 相应的码字 构成霍夫曼编码字 编码结束 哈夫曼编码产生最佳整数前缀码 即没有一个码字是另一个码字的前缀 因此哈夫曼编码是唯一码 编码之后 哈夫曼编码的平均码长为 1 n ii i Kp x K 哈夫曼编码的效率为 H x K 信源熵 平均码长 例 2 1 设信源共 7 个符号消息 其概率如下表所示 信源消息符号 xix1x2x3x4x5x6x7 符号概率 P xi 0 200 190 180 170 150 100 01 其编码过程如下所示 该哈夫曼码的平均码长为 编码效率为 三 实验内容三 实验内容 为某一信源进行哈夫曼编码 该信源的字符集为 X x1 x2 x6 相应的 概率矢量为 P 0 30 0 25 0 21 0 10 0 09 0 05 即 X P 的概率空间为 123456 0 30 0 25 0 21 0 10 0 09 0 05 Xxxxxxx P 根据哈夫曼编码算法对该信源进行哈夫曼编码 并计算其平均码长和编码 效率 调用 matlab 哈夫曼编码函数进行哈夫曼编码 与人工编码结果做比较 1 huffmandict 函数 为已知概率分布的信源模型生成哈夫曼编解码索引 表 调用方法如下 dict avglen huffmandict symbols p dict avglen huffmandict symbols p N dict avglen huffmandict symbols p N variance 7 1 2 72ii i Kp x K 码元 符号 2 61 0 9596 2 72 H X K 比特码元 四 实验要求四 实验要求 1 提前预习实验 认真阅读实验原理以及相应的参考书 2 认真高效的完成实验 实验中服从实验室管理人员以及实验指导老师 的管理 3 认真填写实验报告 3实验三实验三 离散信道容量离散信道容量 一 实验目的一 实验目的 1 掌握离散信道容量的计算 2 理解离散信道容量的物理意义 3 练习应用 matlab 软件进行二元对称离散信道容量的函数曲线的绘制 并从曲线上理解其物理意义 二 实验原理二 实验原理 信道是传送信息的载体 信号所通过的通道 信息是抽象的 而信道则是具体的 比如二人对话 二人间的空气就是信 道 打电话 电话线就是信道 看电视 听收音机 收 发间的空间就是信道 研究信道的目的 在通信系统中研究信道 主要是为了描述 度量 分析 不同类型信道 计算其容量 即极限传输能力 并分析其特性 二元对称信道 BSC Binary Symmetric Channel 二进制离散信道模型有一个允许输入值的集合 X 0 1 和可能输出值的集 合 Y 0 1 以及一组表示输入和输出关系的条件概率 转移概率 组成 如 果信道噪声和其他干扰导致传输的二进序列发生统计独立的差错 且条件概率 对称 即 0 1 1 0 1 1 0 0 1 p YXp YXp p YXp YXp 这种对称的二进制输入 二进制输出信道称做二元对称信道 或二进制对 称信道 简称 BSC 信道 如下图所示 信道容量公式