信息论大作业2

1、信息论大作业一、实验目的1、通过实验进一步理解霍夫曼编码、算术编码和LZ编码原理和方法2、熟悉matlab编程和GUI界面的设计二、实验原理1、赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman算法而产生。Huffman编码是一种基于统计的无损编码。设信源X的信源空间为：其中，现用二进制对信源X中的每一个符号(i=1,2,N)进行编码。根据变长最佳编码定理，Huffman编码步骤如下：（1）将信源符号xi按其出现的概率，由大到小顺序排列。（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支

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、编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。（3）Huffman编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了哈夫曼编码的应用。（4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小数，这也是Huffman编码无法达到最理想的压缩效果的原因。举例说明:一串信号源Ss1,s2,s3,s4,s5对应概率为p0.40，0.30，0.15，

4、0.10，0.5，按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！最后概率最大的编码为0，最小的编码为1。所以，编码结果为：s1=1s2=00s3=010s4=0110s5=01112、算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，对每个符号进行编码。而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0  n < 1.0)的小数n。所以用两个基本的参数：符号的概率和它的编码间隔

5、。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。算术编码的算法思想如下： （1）对一组信源符号按照符号的概率从大到小排序，将0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。 （2）检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。 （3）仍然按照信源符号的概率序列在当前分析区间划分比例间隔。然后重复第 二步。直到“

6、输入消息序列”检索完毕为止。（4）最后的编码输出数就是编码好的数据。3、LZ 编码原理简介：1965 年苏联数学家Kolmogolov 提出利用信源序列的结构特性来编码。而两位以色列研究者J.Ziv 和A.Lempel 独辟蹊径，完全脱离Huffman 及算术编码的设计思路，创造出了一系列比Huffman 编码更有效，比算术编码更快捷的通用压缩算法。将这些算法统称为LZ 系列算法。Ziv 和Lempel 于1977 年提出了LZ77 算法Ziv & Lempel (1977)。1984年，二人又提出了改进算法，后被命名为LZ78Ziv & Lempel (1978)。1984年

7、，T.A.Welch 提出了LZ78 算法的一个变种，即LZW 算法 Welch (1984)。1990 年后，T.C.Bell 等人又陆续提出了许多LZ 系列算法的变体或改进版本 Bell 等(1990)。LZ 系列算法用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明LZ 系列算法同样可以逼近信息熵的极限。以LZ78 算法为例：设信源符号集A=a1，a2，aK共K 个符号，设输入信源符号序列为u=(u1，u2，uL)编码是将此序列分成不同的段。分段的规范为：尽可能取最少个相连的信源符号，并保证各段都不相同。开始时，先取一个符号作为第一段，然后继续分段。若出现与前面相同

8、的符号时，就再取紧跟后面的一个符号一起组成一个段，使之与前面的段不同。这些分段构成字典。当字典达到一定大小后，再分段时就应查看有否与字典中的短语相同，若有重复就添加符号，以便与字典中短语不同，直至信源序列结束。编码的码字由段号加一个符号组成。设u 构成的字典中的短语共有M（u）个。若编码为二元码，段号所需码长n=log M（u）（注：代表上取整符号），每个符号需要的码长为log K。单符号的码字段号为0，非单字符的码字段号为除最后一个符号外字典中相同短语的段号。LZ 编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典，只要传输字典的大小，无需传输字典本身。当编码的信源序列增长时，编

9、码效率会提高，平均码长会逼近信源熵。三、实验结果（1）对该图片求霍夫曼编码由第一次实验，该图片的熵为11号的熵>> Hx(A)ans =7.0427计算得编码效率熵除以码长0.9367（2）对该图片求算术编码编码效率0.9999（3）对该图片求lz编码编码效率0.9845四、结果分析 由以上各编码的编码效率分析，不难看出，对于霍夫曼编码，算术编码，lz编码，对该图片的编码效率最高的是霍夫曼编码，霍夫曼编码效率相比较之下较低，lz编码在运行的时候耗时较长，个人认为不太实用。 哈夫曼编码所形成的码字不是唯一的，但编码效率是唯一的 在对最小的两个概率符号赋值时，可以规定为大的为“1”、小

10、的为“0”，反之也可以。如果两个符号的出现概率相等时，排列时无论哪个在前都是可以的，所以哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以编码效率是唯一的。（2）只有当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明显。 （3）哈夫曼编码必须精确地统计出原始文件中每个符号的出现频率，如果没有这些精确的统计，将达不到预期的压缩效果。霍夫曼编码通常要经过两遍操作，第一遍进行统计，第二遍产生编码，所以编码速度相对慢。另外实现的电路复杂，各种长度的编码的译码过程也是比较复杂的，因此解压缩的过程也比较慢。 （4）哈夫曼编码只能用整数来表示

11、单个符号而不能用小数，这很大程度上限制了压缩效果。 （5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面目全非算术编码与霍夫曼编码的比较：从实验的结果中可以发现，霍夫曼编码和算术编码都有着非常高的编码效率.算术编码比霍夫曼编码的编码效率略高一些。但是，在网上搜集的资料，有 如下介绍：在算术编码和哈夫曼编码之间有很大的相似性 - 实际上，哈夫曼编码只是算术编码的 一个特例 - 但是由于算术编码将整个消息翻译成一个表示为 基数 b,而不是将消息中 的每个符号翻译成一系列的以 b 为基数的数字，它通常比哈夫曼编码更能达到最优熵 编码。Lz编码： 由于程序的限制，本次实验只对一张很小

12、的图片经行了 LZ 编码，由结果可以看出，相 较于前两种的编码，LZ 编码的效率非常低。但是本实验效率低下的原因并不能说明此 编码是比较差的，因为 20×20 的图像所产生的序列非常短，随着序列长长度的不断增 加，LZ 编码的效率也会不断提高。总体来说，霍夫曼编码最适合实际应用。五、实验感悟通过本次试验，我们掌握了三种编码的原理和方法，更重要的是掌握了MATLAB 图形界面GUI的使用方法。刚开始做实验时感觉GUI很难，毕竟从前谁也没有接触过这方面的知识，但经过查阅资料以及在做实验的过程中的不断摸索，终于终做出了完整的GUI，比较完满的完成了这次实验。六、程序代码1、霍夫曼funct

13、ion 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

14、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

15、% 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 % Copyrigh

16、t 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 EDITgui_Singleton = 1;gui_State = struct('gui_Name', mfilename, . 'gui_Singleton', gui_Singleton, . 

17、9;gui_OpeningFcn', huffman_OpeningFcn, . 'gui_OutputFcn', huffman_OutputFcn, . 'gui_LayoutFcn', , . 'gui_Callback', );if nargin && ischar(varargin1) gui_State.gui_Callback = str2func(varargin1);end if nargout varargout1:nargout = gui_mainfcn(gui_State, varargin:);

18、else gui_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 b

19、e 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 huffmanhandles.output = hObject; % Update handles structureguidata(hObject, handles); % UIWAIT makes

20、 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% ev

21、entdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Get default command line output from handles structurevarargout1 = handles.output; % - Executes on button press in pushbutton1.function pushbutton1_Callback(hObject, eventdata

22、, handles)global headfilename,pathname=uigetfile('11.jpg','_');head=strcat(pathname,filename); a=imread(head); axes(handles.axes1); imshow(head);a=rgb2gray(a);%_¶ÁÈëºó׺Ϊ.jpgµÄͼƬ_²¢½

23、8;Á¢Æä»Ò¶ÈÖµµÄ¾ØÕó¡£_m,n=size(a);%_mΪ¾ØÕóµÄÐÐÊý£¬nΪ¾ØÕóµÄÁÐÊý¡£_p=ze

24、ros(1,256);%_½¨Á¢Ò»¸ö1*256µÄ¾ØÕó£¬ÓÃÓÚ·ÅÖÃÿ¸ö»Ò¶ÈÖµµÄ¸ÅÂÊ¡£_for k=0:255p(k+1)=length(find

25、(a=k)/(m*n);%_Çó¸ÅÂÊ£¬²¢½«Æä·ÅÈëp¾ØÕóÖС£_endif length(find(p<0)=0 error('Not a prob,negative,component');endif abs(sum(p)-1)>10e-10 error('Not a prob,v

26、ector,component do not add to 1');endn=length(p);q=p;m=zeros(n-1,n);for i=1:n-1 q,l=sort(q); m(i,:)=l(1:n-i+1),zeros(1,i-1); q=q(1)+q(2),q(3:n),1;endfor i=1:n-1 c(i,:)=blanks(n*n);endc(n-1,n)='1'c(n-1,2*n)='0'for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)=1)-(n-2):n*(find(m(

27、n-i+1,:)=1); c(n-i,n)='1' c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)='0' for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(m(n-i+1,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1); endendfor i=1:n h(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n); ll(i)=length(find(abs(h(i,:)=32);endl=sum(p

28、.*ll);fiden=fopen('encode.txt','w');fwrite(fiden,h);fclose(fiden); set(handles.edit2,'string',l); set(handles.edit1,'string',h); % hObject handle to pushbutton1 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handle

29、s and user data (see GUIDATA) % - Executes on button press in pushbutton2.function pushbutton2_Callback(hObject, eventdata, handles)% hObject handle to pushbutton2 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA)

30、 close function edit1_Callback(hObject, eventdata, handles)% hObject handle to edit1 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit1 as text% str2

31、double(get(hObject,'String') returns contents of edit1 as a double % - Executes during object creation, after setting all properties.function edit1_CreateFcn(hObject, eventdata, handles)% hObject handle to edit1 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% ha

32、ndles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc set(hObject,'BackgroundColor','white');else set(hObject,'BackgroundColor',get(0,'defaultUicontrolBackground

33、Color');end function edit2_Callback(hObject, eventdata, handles)% hObject handle to edit2 (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user data (see GUIDATA) % Hints: get(hObject,'String') returns contents of edit2 as t

34、ext% str2double(get(hObject,'String') returns contents of edit2 as a double % - Executes during object creation, after setting all properties.function edit2_CreateFcn(hObject, eventdata, handles)% hObject handle to edit2 (see GCBO)% eventdata reserved - to be defined in a future version of M

35、ATLAB% handles empty - handles not created until after all CreateFcns called % Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc set(hObject,'BackgroundColor','white');else set(hObject,'BackgroundColor',get(0,'defaultUicontrolB

36、ackgroundColor');end2、算术编码clearclc x1=imread('11.jpg');x2=rgb2gray(x1); M,N=size(x2);num=zeros(1,256);for m=1:M; for n=1:N; i=x2(m,n); num(i+1)=num(i+1)+1; endendp=num/(M*N); result=0;for i=1:length(p)if p(i)=0;result=result;elseresult=result-p(i)*log2(p(i);endend %ìص

37、6;Öµ F=zeros(1,256);for m=1:256 sum2=0; for n=1:m-1 sum2=sum2+p(n); end F(m)=sum2;end%ÿһ¸öÏñËØÖµµÄÀÛ»ý¸ÅÂÊF ÆäÖÐÓдíλ F(1)Î

38、;ª0µÄÀÛ»ý¸ÅÂÊ F(2)Ϊ1µÄÀÛ»ý¸ÅÂÊ S=zeros(1,M*N);P1=1;for i=1:M*N-1 S(1)=F(x2(i)+1); P1=p(x2(i)+1)*P1; S(i+1)=S(i)+P1*F(x2(i+1)+1);end%ÀÛ¼Ó LOG2P=0;for i=1:256 if p(i)

39、=0 LOG2P=LOG2P; else LOG2P=LOG2P+num(i)*log2(p(i); endend length=ceil(-LOG2P); code=dectobin(S(M*N),length);average_length=length/(M*N);efficiency=result/average_length;code1=num2str(code)function y=dectobin(innum,N)%Ê®½øÖÆСÊýת»»

40、;Ϊ¶þ½øÖÆÊý%ÊäÈë²ÎÊýΪinnumºÍN%innumΪÊäÈëµÄÊ®½øÖÆСÊý%NΪָ¶¨×&#

41、170;»»ºó¶þ½øÖƵÄλÊý if (innum>1)|(N = 0)%ÅжÏÊäÈëµÄÓÐЧÐÔ disp('error!'); return;endcount=0;tempnum=innum;record=zeros(1,N);whil

42、e(N) count=count+1;%³¤¶ÈСÓÚN if(count>N) N=0;% return; end tempnum=tempnum*2;%СÊýת»»Îª¶þ½øÖÆ,³Ë2È¡Õû if tempnum>1 record(count)=1; tempnum=te

43、mpnum-1; elseif(tempnum=1) record(count)=1; N=0;%stop loop else record(count)=0; endend y=record;3、lz编码function LZmain()%LZ encode main functionclc;%open the source file to get the contentfid=fopen('11.jpg','r');seq=fread(fid);fclose(fid);seq=reshape(seq,1,length(seq);if isempty(seq)

44、 %call the Entropy function to calculate the source entropy entropy=Entropy(seq); %call the LZcode function to encode the symbol dictionary codelength=LZcode(seq); %calculate the efficiency, and display the entropy,average length %as well as efficiency avglength=(codelength*length(dictionary)/length

45、(seq); %efficiency=(entropy/avglength); disp(strcat('Entropy = ',num2str(entropy); disp(strcat('Code length = ',num2str(codelength); disp(strcat('Average length = ',num2str(avglength); %disp(strcat('Efficiency = ',num2str(efficiency); %encode the source file,and write

46、 the enseq into the file-encode.txt display('Encoded Sequence : Look encode.txt.'); enseq=LZencode(dictionary); fiden=fopen('encode.txt','w'); en=fwrite(fiden,enseq); fclose(fiden); %decode the encode file,and write the deseq into the file-decode.txt display('Decoded Sequence : Look decode.txt.'); deseq=LZdecode(dictionary); fidde=fopen('decode.txt','w'); de=fwrite(fidde,deseq); fclose(fiden); else display('Empty Sequence.');endendfunction encode=LZencode(dictionary)%the function that encodes the source fil