信息论大作业一、实验目的1、通过实验进一步理解霍夫曼编码、算术编码和LZ编码原理和方法2、熟悉 matlab编程和 GUI界面的设计二、实验原理1、赫夫曼（ Huffman）编码是 1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman算法而产生 Huffman编码是一 种基于统计的无损编码 设信源 X的信源空间为：)()()()(:)(:: ][32121NN xPxPxPxPXPxxxXPX其中，1)(1NiixP， 现用二进制对信源 X中的每一个符号ix (i=1,2,,N)进行编码 根据变长最佳编码定理，Huffman编码步骤如下： （1）将信源符号 xi 按其出现的概率，由大到小顺序排列 （2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终 将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0 为 止； （3）对每对组合的上边一个指定为1，下边一个指定为 0（或相反：对上边 一个指定为 0，下边一个指定为 1）； （4）画出由每个信源符号到概率1.0 处的路径，记下沿路径的1和0； （5）对于每个信源符号都写出1、0序列，则从右到左就得到非等长的 Huffman码。
Huffman编码的特点是： （1）Huffman编码构造程序是明确的， 但编出的码不是唯一的， 其原因之一是两 个概率分配码字“ 0”和“ 1”是任意选择的（大概率为“0”，小概率为“ 1”， 或者反之）第二原因是在排序过程中两个概率相等，谁前谁后也是随机的这 样编出的码字就不是唯一的 （2）Huffman编码结果，码字不等长，平均码字最短，效率最高，但码字长短不 一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差 （3）Huffman编码的信源概率是 2的负幂时，效率达 100% ，但是对等概率分布的 信源， 产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman 编码依赖于信源统计特性， 编码前必须有信源这方面的先验知识，这往往限制了 哈夫曼编码的应用 （4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小数， 这 也是Huffman编码无法达到最理想的压缩效果的原因举例说明 : 一串信号源 S＝{s1,s2,s3,s4,s5}对应概率为 p＝{0.40 ，0.30，0.15，0.10 ，0.5} ，按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！最后概率最大的编码为 0，最小的编码为 1。
所以，编码结果为：s1=1 s2=00 s3=010 s4=0110 s5=0111 2、算术编码是一种无损数据压缩方法，也是一种熵编码的方法和其它熵编码方法不同的地方在于， 其他的熵编码方法通常是把输入的消息分割为符号，对每 个符号进行编码 而算术编码是直接把整个输入的消息编码为一个数，一个满足 (0.0 ≤ n > Hx(A) ans = 7.0427 计算得编码效率熵除以码长0.9367 （2）对该图片求算术编码编码效率 0.9999 （3）对该图片求lz 编码编码效率0.9845 四、结果分析由以上各编码的编码效率分析，不难看出，对于霍夫曼编码，算术编码，lz 编码，对该图片的编码效率最高的是霍夫曼编码，霍夫曼编码效率相比较之下较 低，lz 编码在运行的时候耗时较长，个人认为不太实用 哈夫曼编码所形成的码字不是唯一的，但编码效率是唯一的在对最小的两个 概率符号赋值时，可以规定为大的为“1”、小的为“ 0”，反之也可以如果两 个符号的出现概率相等时， 排列时无论哪个在前都是可以的，所以哈夫曼所构造 的码字不是唯一的， 对于同一个信息源， 无论上述的前后顺序如何排列，它的平 均码长是不会改变的，所以编码效率是唯一的。
（2）只有当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明 显 （3）哈夫曼编码必须精确地统计出原始文件中每个符号的出现频率，如果没有 这些精确的统计，将达不到预期的压缩效果霍夫曼编码通常要经过两遍操作， 第一遍进行统计， 第二遍产生编码， 所以编码速度相对慢 另外实现的电路复杂， 各种长度的编码的译码过程也是比较复杂的，因此解压缩的过程也比较慢 （4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限制 了压缩效果 （5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面 目全非 算术编码与霍夫曼编码的比较：从实验的结果中可以发现， 霍夫曼编码和算术编码都有着非常高的编码效率. 算术编码比霍夫曼编码的编码效率略高一些但是，在网上搜集的资料，有 如下介绍：在算术编码和哈夫曼编码之间有很大的相似性-- 实际上，哈夫曼编码只是算术编码的一个特例 -- 但是由于算术编码将整个消息翻译成一个表示为基数b, 而不是将消息中的每个符号翻译成一系列的以 b 为基数的数字，它通常比哈夫曼编码更能达到最优熵编码Lz编码：由于程序的限制，本次实验只对一张很小的图片经行了 LZ 编码，由结果可以看出，相 较于前两种的编码， LZ 编码的效率非常低。
但是本实验效率低下的原因并不能说明此编码是比较差的，因为 20 ×20 的图像所产生的序列非常短，随着序列长长度的不断增加，LZ 编码的效率也会不断提高总体来说，霍夫曼编码最适合实际应用五、实验感悟通过本次试验，我们掌握了三种编码的原理和方法， 更重要的是掌握了 MATLAB 图 形界面 GUI的使用方法 刚开始做实验时感觉 GUI很难，毕竟从前谁也没有接触过 这方面的知识， 但经过查阅资料以及在做实验的过程中的不断摸索，终于终做出 了完整的 GUI，比较完满的完成了这次实验六、程序代码1、霍夫曼function varargout = huffman(varargin) % HUFFMAN M-file for huffman.fig % HUFFMAN, by itself, creates a new HUFFMAN or raises the existing % singleton*. % % H = HUFFMAN returns the handle to a new HUFFMAN or the handle to % the existing singleton*. % % HUFFMAN('CALLBACK',hObject,eventData,handles,...) calls the local % function named CALLBACK in HUFFMAN.M with the given input arguments. % % HUFFMAN('Property','Value',...) creates a new HUFFMAN or raises the % existing singleton*. Starting from the left, property value pairs are % applied to the GUI before huffman_OpeningFunction gets called. An % unrecognized property name or invalid value makes property application % stop. All inputs are passed to huffman_OpeningFcn via varargin. % % *See GUI Options on GUIDE's Tools menu. Choose “GUI allows only one % instance to run (singleton)“. % % See also: GUIDE, GUIDATA, GUIHANDLES% Copyright 2002-2003 The MathWorks, Inc.% Edit the above text to modify the response to help huffman% Last Modified by GUIDE v2.5 07-Oct-2011 20:57:31% Begin initialization code - DO NOT EDIT gui_Singleton = 1; gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @huffman_OpeningFcn, ... 'gui_OutputFcn', @huffman_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []); if nargin endif nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); elsegui_mainfcn(gui_State, varargin{:}); end % End initialization code - DO NOT EDIT% --- Executes just before huffman is made visible. function huffman_OpeningFcn(hObject, eventdata, handles, varargin) % This function has no output args, see OutputFcn. % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % varargin command line arguments to huffman (see VARARGIN)% Choose default command line output for huffman handles.output = hObject; % Update handles structure guidata(hObject, handles); % UIWAIT makes huffman wait for user response (see UIRESUME) % uiwait(handles.figure1);% --- Outputs from this function are returned to the command line. function varargout = huffman_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT); % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDA。