信息论哈夫曼编码算术编码lz编码.pdf

信息论实验报告 实验人：邓放 学号：2012302257 2014年11月21 日 一、实验目的 1、掌握哈夫曼编码算法的基本原理；要求对图片进行哈夫曼编码。 2、掌握算术编码算法的基本原理；要求对图片进行算术编码。 3 LZ LZ 、掌握 算法的基本原理；要求对图片进行 编码。 二、实验原理 1、哈夫曼编码 l）将信号源的符号按照出现概率递减的顺序排列。（注意，一定要递减） 2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出 现的概率。 3）重复进行步骤1和2直到概率相加的结果等于1为止。 4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。 5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符 号的编码。 下面我举个简单例子: 一串信号源S＝{s1,s2,s3,s4,s5}对应概率为p＝{40，30，15，10，5}，（百 分率） 按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然 按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！ 最后概率最大的编码为0，最小的编码为1。如图所示： 所以，编码结果为 s1=1 s2=00 s3=010 s4=0110 s5=0111 霍夫曼编码具有如下特点： 1) 编出来的码都是异字头码，保证了码的唯一可译性。 2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当 费时。 3) 编码长度不统一，硬件实现有难度。 4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达 到100％的编码效率；若信号源符号的概率相等，则编码效率最低。 5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其 平均码长是一样的，故不影响编码效率与数据压缩性能。 2、算术编码 根据信源可能发现的不同符号序列的概率，把[0，1]区间划分为互不重叠的子 区间，子区间的宽度恰好是各符号序列的概率。这样信源发出的不同符号序列将 与各子区间一一对应，因此每个子区间内的任意一个实数都可以用来表示对应的 符号序列，这个数就是该符号序列所对应的码字。显然，一串符号序列发生的概 率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因而相应的码字 就越短。 P(S,a )P(S)p(S)Pr r  1  L log   p(S)  3、LZ编码 设信源符号集A={a1，a2，…，aK}共K个符号，设输入信源符号序列为u=(u1，u2，…， uL)编码是将此序列分成不同的段。分段的规范为：尽可能取最少个相连的信源符号，并保 证各段都不相同。 开始时，先取一个符号作为第一段，然后继续分段。若出现与前面相同的符号时，就再 取紧跟后面的一个符号一起组成一个段，使之与前面的段不同。这些分段构成字典。当字典 达到一定大小后，再分段时就应查看有否与字典中的短语相同，若有重复就添加符号，以便 与字典中短语不同，直至信源序列结束。 编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M （u）个。若编码 为二元码，段号所需码长n= 「logM （u） 「（注：代表上取整符号），每个符号需要的码长 为log[M （u)] 。单符号的码字段号为0，非单字符的码字段号为除最后一个符号外字典中相 同短语的段号。 例如，设U={a1，a2，a3，a4}，信源序列为a1，a3，a2，a3，a2，a4，a3，a2，a1，a4， a3，a2，a1，共13位，字典如表所示： 三、实验结果 1.哈夫曼 2.算术编码 Gui界面 3.Lz编码 四．代码 哈夫曼： clc clear closeall; %定义HufData/Len为全局变量