信息论编码实验.docxVIP

信息论实验报告 自动化学院2007302171 马志强 0摘要: 用预先规定的方法将文字、数字或其他对象编成数码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。其中Huffman编码和LZ编码由于自身的巨大优势在编码领域有更为广泛的应用,通过本次实验,具体了解编码的具体过程,通过编程实现编码,利用GUI制作可视化界面,实现编码的方便应用。 1关键字：信息论，Huffman编码，LZ编码，GUI编程。 2前言： 2.1Huffman编码 Huffman编码：基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了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的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：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的码字。我们给出的编码能够保证这一点。 下面给出具体的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序列串起来，就得到了各个符号的编码。 下图展示了编码过程： 最终获得的编码表： Label Sign P(x) 11 S0 4/14 4/14 4/14 4/14 4/14 6/14 8/14 1 00 S1 3/14 3/14 3/14 3/14 4/14 4/14 6/14 011 S2 2/14 2/14 2/14 3/14 3/14 4/14 010 S3 1/14 2/14 2/14 2/14 3/14 1011 S4 1/14 1/14 2/14 2/14 1010 S5 1/14 1/14 1/14 1001 S6 1/14 1/14 1000 S7 1/14 2.2LZ编码 LZ编码:编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M（u）个。若编码为二元码，段号所需码长n=「log M（u）「（注：代表上取整符号），每个符号需要的码长为「log K「。单符号的码字段号为0，非单字符的码字段号为除最后一个符号外字典中相同短语的段号。 　　例如，设U={a1，a2，a3，a4}，信源序列为a1，a3，a2，a3，a2，a4，a3，a2，a1，a4，a3，a2，a1，共13位，字典如表所示： 　　表1 编码字典 　　 段号 　　 短语 　　 编码 　　 1 　　 a1 　　 00000 　　 2 　　 a3 　　 00010 　　 3 　　 a2 　　 00001 　　 4 　　 a3a2 　　 01001 　　 5 　　 a4 　　 00011 　　 6 　　 a3a2a1 　　 10000 　　 7 　　 a4a3 　　 10110 　　 8 　　 a2a1 　　 01100 　　 　　表2 符号编码表 　　 a1 　　 a2 　　 a3 　　 a4 　　 00 　　 01 　　 10 　　 11 　　 　　表1中，8个短语使用3bit可以表示段号