信息编码实验报告

信息论与编码技术实验报告信息论与编码技术实验报告 实 验 题 目 香浓编码 学生专业班级 信息与计算科学 1001 学生姓名 学号 曹雪萍 指 导 教 师 吴慧 完 成 时 间 2013 年 5 月 18 日 2013 年 5 月 18 日 信息论与编码技术实验报告信息论与编码技术实验报告 实 验 题 目 Huffman 编码软件实现 学生专业班级 信息与计算科学 1001 学生姓名 学号 曹雪萍 指 导 教 师 吴慧 完 成 时 间 2013 年 5 月 19 日 2013 年 5 月 19 日 实验一实验一 香农编码的香农编码的实验报告实验报告 一一 实验目的 实验目的 1 了解香农编码的基本原理及其特点 2 熟悉掌握香农编码的方法和步骤 3 掌握 C 语言或者 Matlab 编写香农编码的程序 二 实验要求二 实验要求 对于给定的信源的概率分布 按照香农编码的方法进行计算机实现 三 实验原理三 实验原理 给定某个信源符号的概率分布 通过以下的步骤进行香农编码 1 信源符号按概率从大到小排列 2 对信源符号求累加概率 表达式 Gi Gi 1 p xi 3 求自信息量 确定码字长度 自信息量I xi log p xi 码字长度取大于 等于自信息量的最小整数 4 将累加概率用二进制表示 并取小数点后码字的长度的码 四 实验内容四 实验内容 离散无记忆信源符号 S 的概率分布 S 1 S 2 S 3 S 4 s 5 s 6 S 7 s P S 0 20 0 19 0 18 0 17 0 15 0 10 0 01 对离散无记忆信源分布 S 进行香农编码 1 画出程序设计的流程图 开始 输入信源符号的个数 输入对应符号的概率 P i 判断概率 和 S 是否 等于 1 按概率分布大小对信源排序 计算平均码长 计算编码效率 计算累加概率 将累加概率转化为二进制码字 输出累加概率 码长 码字 自信息量 平均码长 编码效率 计算自信息量 2 写出程序代码 N input N 输入信源符号的个数 s 0 l 0 H 0 for i 1 N p i input p 输入信源符号概率分布矢量 p i 0 error 不符合概率分布 end for i 1 N 1 for j i 1 N if p i p j m p j p j p i p i m 结束 end end end 按概率分布大小对信源排序 for i 1 N a log2 p i if mod a 1 0 w a else w fix a 1 end 计算各信源符号的码长 l l p i w 计算平均码长 end l l n H l 计算编码效率 P 1 0 for i 2 N P i 0 for j 1 i 1 P i P i p j end end 计算累加概率 for i 1 N for j 1 w W i j fix P i 2 P i P i 2 fix P i 2 end end 将累加概率转化为 L i 位二进制码字 disp W 显示码字 disp l 显示平均码长 disp n 显示编码效率 disp I 显示自信息量 3 写出在调试过程中出现的问题 问题 1 自信量程序不会编写 问题 2 累加概率时注意 P 1 0 问题 3 程序运行时要依次输入各个符号概率 4 对实验的结果进行分析 由程序运行结果 得 2 34 2 41 2 48 2 56 2 74 3 34 6 66 所以我们得到每个信源符号的自信息量为 I s1 2 34 I s2 2 41 I s3 2 48 I s4 2 56 I s5 2 74 I s6 3 34 I s7 6 66 根据公式 我们得到每个信源符号的码长为log log 1 iii p slp s l1 3 l2 3 l3 3 l4 3 l5 3 l6 4 l7 7 由程序运行结果 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 我们得到每个信源符号的为对应的二进制数为 i G G1 0 G2 0 G3 0 G4 0 G5 0 G6 0 G7 0 所以我们得到每个信源符号的码字为 S1 000 s2 001 s3 011 s4 100 s5 101 s6 1110 s7 平均码长为 3 14 编码效率为 0 831 五 实验结论与心得五 实验结论与心得 此次实验让我认识和熟悉了及步骤 对 MATLAB 软件也有更加深刻的掌握 会用它求某个符号信源的香农编码程序算法 对我的实验能力有所提高 HuffmanHuffman 编码软件实现实验报告编码软件实现实验报告 一 实验目的一 实验目的 1 进一步熟悉 Huffman 编码过程 2 掌握 Matlab 程序的设计和调试技术 二 实验要求二 实验要求 1 输入 信源符号个数 r 信源的概率分布 P 2 输出 每个信源符号对应的 Huffman 编码的码字 编码效率 三 实验原理 三 实验原理 1 二进制 Huffman 编码的基本原理 设信源s 其中对应的概率分布为 P 则 654321 ssssss i S 654321 pppppp 其编码步骤如下 1 将 q 个信源符号按概率递减的方式排列 2 用 0 1 码符号分别表示概率最小的两个信源符号 并将这两个概率最小的 信源符号合并成一个新的符号 从而的得到的只含 q 1 个符号的新信源 称为信源的缩减信源S 1 S 3 将缩减信源中的符号仍按概率大小以递减次序排列 重复步骤 2 1 S 4 重复 1 2 3 三步骤 直至缩减信源只剩下两个符号为止 将这最后两 个符号分别用 0 1 码字表示 5 从最后一级缩减信源开始 向前返回 得出各信源符号所对应的码符号序列 即为对应信源符号的码字 2 二进制 Huffman 编码程序设计的原理 编码步骤 1 1 程序的输入 程序的输入 以一维数组的形式输入要进行 Huffman 编码的信源符号的概率 在运行该程序 前 显示文字提示信息 提示所要输入的概率矢量 然后对输入的概率矢量进 行合法性判断 原则为 如果概率矢量中存在小于 0 的项 则输入不合法 提 示重新输入 如果概率矢量的求和大于 1 则输入也不合法 提示重新输入 2 2 HuffmanHuffman 编码具体实现原理 编码具体实现原理 在输入的概率矩阵 p 正确的前提条件下 对 p 进行排序 并用矩阵 L 记 录 p 排序之前各元素的顺序 然后将排序后的概率数组 p 的前两项 即概率最 小的两个数加和 得到新的一组概率序列 重复以上过程 最后得到一个记录 概率加和过程的矩阵 p 以及每次排序之前概率顺序的矩阵 a 新生成一个 n 1 行 n 列 并且每个元素含有 n 个字符的空白矩阵 然后进 行 Huffman 编码 将 c 矩阵的第 n 1 行的第一和第二个元素分别令为 0 和 1 表示在编码时 根节点之下的概率较小的元素后补 0 概率较大的元素后补 1 后面的编码都遵守这个原则 然后对 n i 1 的第一 二个元素进行编码 首 先在矩阵 a 中第 n i 行找到值为 1 所在的位置 然后在 c 矩阵中第 n i 行中找 到对应位置的编码 该编码即为第 n i 1 行第一 二个元素的根节点 则矩阵 c 的第 n i 行的第一 二个元素的 n 1 的字符为以上求得的编码值 根据之前 的规则 第一个元素最后补 0 第二个元素最后补 1 则完成该行的第一二个元 素的编码 最后将该行的其他元素按照 矩阵 c 中第 n i 行第 j 1 列的值等于 对应于 a 矩阵中第 n i 1 行中值为 j 1 的前面一个元素的位置在 c 矩阵中的编 码值 的原则进行赋值 重复以上过程即可完成 Huffman 编码 计算信源熵和平均码长 其比值即为编码密码效率 3 部分伪代码 1 节点信息结构体 struct HuffNode int weight 信源符号的概率 int parent int lchild int rchild 2 算法 void Huffman int weight int n HuffNode hn HuffCode hc for i 0 i 2 n 1 i create Huffman Node step 1 for i 0 i n 1 i create Huffman Node step 2 for j 0 j n i j if hn j weight min1 for i 1 n if p i 0 fprintf n The sum of the probabilities in huffman can more than 1 n p input please input a number end q p a zeros n 1 n 生成一个 n 1 行 n 列的数组 for i 1 n 1 q l sort q a i l 1 n i 1 zeros 1 i 1 q q 1 q 2 q 3 n 1 end for i 1 n 1 c i 1 n n blanks n n end c n 1 n 0 c n 1 2 n 1 for i 2 n 1 c n i 1 n 1 c n i 1 n find a n i 1 1 n 2 n find a n i 1 1 c n i n 0 c n i n 1 2 n 1 c n i 1 n 1 c n i 2 n 1 for j 1 i 1 c n i j 1 n 1 j 2 n c n i 1 n find a n i 1 j 1 1 1 n find a n i 1 j 1 end end for i 1 n h i 1 n c 1 n find a 1 i 1 1 find a 1 i n ll i length find abs h i 32 end l sum p ll fprintf n huffman code n h hh sum p log2 p fprintf n the huffman effciency n t hh l 3 3 运行源程序后 实验过程中的测试结果运行源程序后 实验过程中的测试结果 p 0 32 0 22 0 18 0 16 0 08 0 04 q 0 04 0 08 0 16 0 18 0 22 0 32 q 0 12 0 16 0 18 0 22 0 32 1 00 q 0 18 0 22 0 28 0 32 1 00 1 00 q 0 28 0 32 0 40 1 00 1 00 1 00 q 0 40 0 60 1 00 1 00 1 00 1 00 ll 2 4 2 2 3 4 huffman code h 00 1001 01 11 101 1000 the huffman effciency t 0 9801 实验结果分析实验结果分析 信源 的码字长度分别为 2 4 2 2 3 4 654321 ssssss 所对应的码字为 11 0110 10 00 010 0111 编码效率为 0 9801 5 5 总结实验过程遇到的问题及解决方法 总结实验过程遇到的问题及解决方法 1 在实验过程中 遇到以下几个问题 在实验过程中 遇到以下几个问题 信源缩减不知怎么表示 不知如何运用矩阵存储对应概率所对应的位置 起初忘记对输入的各个概率以及概率之和进行判断 导致的程序的不合 理性与不可行性 2 2 解决方法 解决方法 通过查找资料和相关书籍 学习类似的哈夫曼编码的程序的编写 使得 问题得到解决 六 实验心得六 实验心得 通过此次试验 使得我对 Huffman 编码的编写原理 基本步骤有了更加深刻 的理解 此外 我还学到了有关 MATLAB 知识的运用 比如 一些特殊语句的应 用 矩阵存储知识的应用等等 总之 我认为此次实验还是比较成功的 同 收回房屋 1 承租人擅自将房屋转让或转借的 登鹳雀楼 唐代 王之涣 白日依山尽 黄河入海流 欲穷千里目 更上一层楼 译文及注释 译文 夕阳依傍着西山慢慢地沉没 滔滔黄河朝着东海汹涌奔流 若想把千里的风光景物看够 那就要登上更高的一层城楼 注释 鹳雀楼 旧址在山西永济县 楼高三层 前对中条山 下临黄河 传说常有鹳雀在此停留 故有此名 白日 太阳 依 依傍 尽 消失 这句话是说太阳依傍山峦沉落 欲 想要得到某种东西或达到某种目的的愿望 但也有希望 想要的意思 穷 尽 使达到极点 千里目 眼界宽阔 更 替 换 不是通常理解的 再 的意思 这首诗写诗人在登高望远中表现出来的不凡的胸襟抱负 反映了盛唐时期人们积极向 上的进取精神 其中 前两句写所见 白日依山尽 写远景 写山 写的是登楼望见的景 色 黄河入海流 写近景 写水写得景象壮观 气势磅礴 这里 诗人运用极其朴素 极 其浅显的语言 既高度形象又高度概括地把进入广大视野的万里河山 收入短短十个字中 而后人在千载之下读到这十个字时 也如临其地 如见其景 感到胸襟为之一开 首句写 遥望一轮落日向着楼前一望无际 连绵起伏的群山西沉 在视野的尽头冉冉而没 这是天 空景 远方景 西望景 次句写目送流经楼前下方的黄河奔腾咆哮 滚滚南来 又在远处折而东向 流归大海 这是由地面望到天边 由近望到远 由西望到东 这两句诗合起来 就把上下 远近 东 西的景物 全都容纳进诗笔之下 使画面显得特别宽广 特别辽远 就次句诗而言 诗人 身在鹳雀楼上 不可能望见黄河入海 句中写的是诗人目送黄河远去天边而产生的意中景 是把当前景与意中景溶合为一的写法 这样写 更增加了画面的广度和深度 而称太阳为 白日 这是写实的笔调 落日衔山 云遮雾障 那本已减弱的太阳的光辉 此时显得更 加暗淡 所以诗人直接观察到 白日 的奇景 至于 黄河 当然也是写实 它宛若一条 金色的飘带 飞舞于层峦叠嶂之间 诗人眼前所呈现的 是一幅溢光流彩 金碧交辉的壮丽图画 这幅图画还处于瞬息多 变的动态之中 白日依山而尽 这仅仅是一个极短暂的过程 黄河向海而流 却是一种永 恒的运动 如果说 这种景色很美 那么 它便是一种动态的美 充满了无限生机的活泼 的美 这不是所谓 定格 不是被珍藏的化石或标本 读者深深地为诗人的大手笔所折服 后两句写所想 欲穷千里目 写诗人一种无止境探求的愿望 还想看得更远 看到目力 所能达到的地方 唯一的办法就是要站得更高些 更上一层楼 千里 一层 都