资源描述：
《信息论编码实验new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、信息论实验报告自动化学院090307022007302171马志强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这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们
3、采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01,11,101,0000,0001,0010,0011,100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果S
4、0的码字为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)，直到最后得到和
5、为1的根节点。(5)将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。下图展示了编码过程：最终获得的编码表：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/14
6、1000S71/142.2LZ编码LZ编码:编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M（u）个。若编码为二元码，段号所需码长n=「logM（u）「（注：代表上取整符号），每个符号需要的码长为「logK「。单符号的码字段号为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
7、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可以表示段号。每个信源符号使用2bit表示，因此，一个短语使用5bit。 LZ编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典，只要传输字典的大小，无需传输字典本身。当编码的信源序列增长时，编码效率会提高，平均码长会逼近信源熵。3编程可
8、视化界面：利用Huffman编码和LZ编码本身的特点，利用Matlab实现了高度集成的编码界面
