《信息论编码实验》由会员分享，可在线阅读，更多相关《信息论编码实验（8页珍藏版）》请在金锄头文库上搜索。
1、信息论实验报告自动化学院 09030702 2007302171 马志强0摘要:用预先规定的方法将文字、数字或其他对象编成数码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。其中Huffman编码和LZ编码由于自身的巨大优势在编码领域有更为广泛的应用,通过本次实验,具体了解编码的具体过程,通过编程实现编码,利用GUI制作可视化界面,实现编码的方便应用。1关键字：信息论，Huffman编码，LZ编码，GUI编程。2前言：2.1Huffman编码Huffman编码：基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不
2、相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了8种符号S0,S1,S2,S3,S4,S5,S6,S7，那么每种符号要编码，至少需要3比特。假设编码成000,001,010,011,100,101,110,111(称做码字)。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成 000001111000001110010010011100101000000001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减
3、少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01,11,101,0000,0001,0010,0011,100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码
4、字。我们给出的编码能够保证这一点。下面给出具体的Huffman编码算法。(1)首先统计出每个符号出现的频率，上例S0到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。(2) 从左到右把上述频率按从小到大的顺序排列。(3)每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与新一轮比较。（从下往上）(4) 重复(3)，直到最后得到和为1的根节点。(5)将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。下图展示
5、了编码过程：最终获得的编码表：LabelSignP(x)11S04/144/144/144/144/146/148/14100S13/143/143/143/144/144/146/14011S22/142/142/143/143/144/14010S31/142/142/142/143/141011S41/141/142/142/141010S51/141/141/141001S61/141/141000S71/142.2LZ编码LZ编码:编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M（u）个。若编码为二元码，段号所需码长n=log M（u）（注：代表上取整符号），每个符号需要
6、的码长为log K。单符号的码字段号为0，非单字符的码字段号为除最后一个符号外字典中相同短语的段号。例如，设U=a1，a2，a3，a4，信源序列为a1，a3，a2，a3，a2，a4，a3，a2，a1，a4，a3，a2，a1，共13位，字典如表所示：表1 编码字典 段号短语编码1a1000002a3000103a2000014a3a2010015a4000116a3a2a1100007a4a3101108a2a101100表2 符号编码表 a1a2a3a400011011表1中，8个短语使用3bit可以表示段号。每个信源符号使用2bit表示，因此，一个短语使用5bit。LZ编码的编码方法非常简捷
7、，译码也很简单，可以一边译码一边建立字典，只要传输字典的大小，无需传输字典本身。当编码的信源序列增长时，编码效率会提高，平均码长会逼近信源熵。3编程可视化界面：利用Huffman编码和LZ编码本身的特点，利用Matlab实现了高度集成的编码界面，易于操作，实用简便。具体使用说明如下：3.1程序包内容：名称格式实现功能ico文件夹内含GUI使用界面中的部分按钮及图片贴图LZ对图片的编码文件夹内含全部LZ对图片编码的源程序mrmodel文件夹内含模式识别小程序的所需部分图片互信息图片集文件夹内含互信息实验部分的比对图片和原图片bianma.mGUI界面主程序dictionary.mLZ编码所产生的
8、字典码LZ#.mLZ编码的函数文件huffman1.mHuffman一元编码函数源代码huffman2.mHuffman二元编码函数源代码m2.m模式识别小程序的源代码MI.m互信息实验所用源代码使用说明.txt本实验程序的具体使用说明3.2GUI界面效果图：图3.21主界面效果图图3.22应用huffman一元函数效果图说明：在可输入区域可输入p向量，点击红色确认按钮，待按钮变为灰色及运算完成，获得码字。图3.23通过计算获得huffman一元码字效果图图3.24 huffman2元及LZ编码使用效果图图3.25 点击成为灰色的的确认按钮，待其变为彩色，输入区即重置图3.25点击灰色按钮可以撤销相应的输入区域图3.26菜单选项可以实现相应的功能图3.27点击识别按钮可调出模式识别小程序4实验总结：经过本次实验，充分学习了编码理论及其重点内容，掌握了编码原理的同时也锻炼了编程水平，为以后的学习中出现的可能问题做好了准备，锻炼了自己的动手能力和设计能力，掌握了一种科技工具，丰富了自己的学习生活。
