信息論大作業(yè)2

1、信息論大作業(yè)一、實(shí)驗(yàn)?zāi)康?、通過實(shí)驗(yàn)進(jìn)一步理解霍夫曼編碼、算術(shù)編碼和LZ編碼原理和方法2、熟悉matlab編程和GUI界面的設(shè)計(jì)二、實(shí)驗(yàn)原理1、赫夫曼（Huffman）編碼是1952年提出的，是一種比較經(jīng)典的信息無損熵編碼，該編碼依據(jù)變長最佳編碼定理，應(yīng)用Huffman算法而產(chǎn)生。Huffman編碼是一種基于統(tǒng)計(jì)的無損編碼。設(shè)信源X的信源空間為：其中，現(xiàn)用二進(jìn)制對(duì)信源X中的每一個(gè)符號(hào)(i=1,2,N)進(jìn)行編碼。根據(jù)變長最佳編碼定理，Huffman編碼步驟如下：（1）將信源符號(hào)xi按其出現(xiàn)的概率，由大到小順序排列。（2）將兩個(gè)最小的概率的信源符號(hào)進(jìn)行組合相加，并重復(fù)這一步驟，始終將較大的概率分支

2、放在上部，直到只剩下一個(gè)信源符號(hào)且概率達(dá)到1.0為止；（3）對(duì)每對(duì)組合的上邊一個(gè)指定為1，下邊一個(gè)指定為0（或相反：對(duì)上邊一個(gè)指定為0，下邊一個(gè)指定為1）；（4）畫出由每個(gè)信源符號(hào)到概率1.0處的路徑，記下沿路徑的1和0；（5）對(duì)于每個(gè)信源符號(hào)都寫出1、0序列，則從右到左就得到非等長的Huffman碼。Huffman編碼的特點(diǎn)是：（1）Huffman編碼構(gòu)造程序是明確的，但編出的碼不是唯一的，其原因之一是兩個(gè)概率分配碼字“0”和“1”是任意選擇的（大概率為“0”，小概率為“1”，或者反之）。第二原因是在排序過程中兩個(gè)概率相等，誰前誰后也是隨機(jī)的。這樣編出的碼字就不是唯一的。（2）Huffman

3、編碼結(jié)果，碼字不等長，平均碼字最短，效率最高，但碼字長短不一，實(shí)時(shí)硬件實(shí)現(xiàn)很復(fù)雜（特別是譯碼），而且在抗誤碼能力方面也比較差。（3）Huffman編碼的信源概率是2的負(fù)冪時(shí)，效率達(dá)100%，但是對(duì)等概率分布的信源，產(chǎn)生定長碼，效率最低，因此編碼效率與信源符號(hào)概率分布相關(guān)，故Huffman編碼依賴于信源統(tǒng)計(jì)特性，編碼前必須有信源這方面的先驗(yàn)知識(shí)，這往往限制了哈夫曼編碼的應(yīng)用。（4）Huffman編碼只能用近似的整數(shù)位來表示單個(gè)符號(hào)，而不是理想的小數(shù)，這也是Huffman編碼無法達(dá)到最理想的壓縮效果的原因。舉例說明:一串信號(hào)源Ss1,s2,s3,s4,s5對(duì)應(yīng)概率為p0.40，0.30，0.15，

4、0.10，0.5，按照遞減的格式排列概率后，根據(jù)第二步，會(huì)得到一個(gè)新的概率列表，依然按照遞減排列，注意：如果遇到相同概率，合并后的概率放在下面！最后概率最大的編碼為0，最小的編碼為1。所以，編碼結(jié)果為：s1=1s2=00s3=010s4=0110s5=01112、算術(shù)編碼是一種無損數(shù)據(jù)壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在于，其他的熵編碼方法通常是把輸入的消息分割為符號(hào)，對(duì)每個(gè)符號(hào)進(jìn)行編碼。而算術(shù)編碼是直接把整個(gè)輸入的消息編碼為一個(gè)數(shù)，一個(gè)滿足(0.0  n < 1.0)的小數(shù)n。所以用兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔

5、。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。算術(shù)編碼的算法思想如下： （1）對(duì)一組信源符號(hào)按照符號(hào)的概率從大到小排序，將0,1)設(shè)為當(dāng)前分析區(qū)間。按信源符號(hào)的概率序列在當(dāng)前分析區(qū)間劃分比例間隔。 （2）檢索“輸入消息序列”，鎖定當(dāng)前消息符號(hào)（初次檢索的話就是第一個(gè)消息符號(hào)）。找到當(dāng)前符號(hào)在當(dāng)前分析區(qū)間的比例間隔，將此間隔作為新的當(dāng)前分析區(qū)間。并把當(dāng)前分析區(qū)間的起點(diǎn)（即左端點(diǎn)）指示的數(shù)“補(bǔ)加”到編碼輸出數(shù)里。當(dāng)前消息符號(hào)指針后移。 （3）仍然按照信源符號(hào)的概率序列在當(dāng)前分析區(qū)間劃分比例間隔。然后重復(fù)第 二步。直到“

6、輸入消息序列”檢索完畢為止。（4）最后的編碼輸出數(shù)就是編碼好的數(shù)據(jù)。3、LZ 編碼原理簡介：1965 年蘇聯(lián)數(shù)學(xué)家Kolmogolov 提出利用信源序列的結(jié)構(gòu)特性來編碼。而兩位以色列研究者J.Ziv 和A.Lempel 獨(dú)辟蹊徑，完全脫離Huffman 及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比Huffman 編碼更有效，比算術(shù)編碼更快捷的通用壓縮算法。將這些算法統(tǒng)稱為LZ 系列算法。Ziv 和Lempel 于1977 年提出了LZ77 算法Ziv & Lempel (1977)。1984年，二人又提出了改進(jìn)算法，后被命名為LZ78Ziv & Lempel (1978)。1984年

7、，T.A.Welch 提出了LZ78 算法的一個(gè)變種，即LZW 算法 Welch (1984)。1990 年后，T.C.Bell 等人又陸續(xù)提出了許多LZ 系列算法的變體或改進(jìn)版本 Bell 等(1990)。LZ 系列算法用一種巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域，而且，可以從理論上證明LZ 系列算法同樣可以逼近信息熵的極限。以LZ78 算法為例：設(shè)信源符號(hào)集A=a1，a2，aK共K 個(gè)符號(hào)，設(shè)輸入信源符號(hào)序列為u=(u1，u2，uL)編碼是將此序列分成不同的段。分段的規(guī)范為：盡可能取最少個(gè)相連的信源符號(hào)，并保證各段都不相同。開始時(shí)，先取一個(gè)符號(hào)作為第一段，然后繼續(xù)分段。若出現(xiàn)與前面相同

8、的符號(hào)時(shí)，就再取緊跟后面的一個(gè)符號(hào)一起組成一個(gè)段，使之與前面的段不同。這些分段構(gòu)成字典。當(dāng)字典達(dá)到一定大小后，再分段時(shí)就應(yīng)查看有否與字典中的短語相同，若有重復(fù)就添加符號(hào)，以便與字典中短語不同，直至信源序列結(jié)束。編碼的碼字由段號(hào)加一個(gè)符號(hào)組成。設(shè)u 構(gòu)成的字典中的短語共有M（u）個(gè)。若編碼為二元碼，段號(hào)所需碼長n=log M（u）（注：代表上取整符號(hào)），每個(gè)符號(hào)需要的碼長為log K。單符號(hào)的碼字段號(hào)為0，非單字符的碼字段號(hào)為除最后一個(gè)符號(hào)外字典中相同短語的段號(hào)。LZ 編碼的編碼方法非常簡捷，譯碼也很簡單，可以一邊譯碼一邊建立字典，只要傳輸字典的大小，無需傳輸字典本身。當(dāng)編碼的信源序列增長時(shí)，編

9、碼效率會(huì)提高，平均碼長會(huì)逼近信源熵。三、實(shí)驗(yàn)結(jié)果（1）對(duì)該圖片求霍夫曼編碼由第一次實(shí)驗(yàn)，該圖片的熵為11號(hào)的熵>> Hx(A)ans =7.0427計(jì)算得編碼效率熵除以碼長0.9367（2）對(duì)該圖片求算術(shù)編碼編碼效率0.9999（3）對(duì)該圖片求lz編碼編碼效率0.9845四、結(jié)果分析 由以上各編碼的編碼效率分析，不難看出，對(duì)于霍夫曼編碼，算術(shù)編碼，lz編碼，對(duì)該圖片的編碼效率最高的是霍夫曼編碼，霍夫曼編碼效率相比較之下較低，lz編碼在運(yùn)行的時(shí)候耗時(shí)較長，個(gè)人認(rèn)為不太實(shí)用。 哈夫曼編碼所形成的碼字不是唯一的，但編碼效率是唯一的 在對(duì)最小的兩個(gè)概率符號(hào)賦值時(shí)，可以規(guī)定為大的為“1”、小

10、的為“0”，反之也可以。如果兩個(gè)符號(hào)的出現(xiàn)概率相等時(shí)，排列時(shí)無論哪個(gè)在前都是可以的，所以哈夫曼所構(gòu)造的碼字不是唯一的，對(duì)于同一個(gè)信息源，無論上述的前后順序如何排列，它的平均碼長是不會(huì)改變的，所以編碼效率是唯一的。（2）只有當(dāng)信息源各符號(hào)出現(xiàn)的概率很不平均的時(shí)候，哈夫曼編碼的效果才明顯。 （3）哈夫曼編碼必須精確地統(tǒng)計(jì)出原始文件中每個(gè)符號(hào)的出現(xiàn)頻率，如果沒有這些精確的統(tǒng)計(jì)，將達(dá)不到預(yù)期的壓縮效果。霍夫曼編碼通常要經(jīng)過兩遍操作，第一遍進(jìn)行統(tǒng)計(jì)，第二遍產(chǎn)生編碼，所以編碼速度相對(duì)慢。另外實(shí)現(xiàn)的電路復(fù)雜，各種長度的編碼的譯碼過程也是比較復(fù)雜的，因此解壓縮的過程也比較慢。 （4）哈夫曼編碼只能用整數(shù)來表示

11、單個(gè)符號(hào)而不能用小數(shù)，這很大程度上限制了壓縮效果。 （5）哈夫曼所有位都是合在一起的，如果改動(dòng)其中一位就可以使其數(shù)據(jù)變得面目全非算術(shù)編碼與霍夫曼編碼的比較：從實(shí)驗(yàn)的結(jié)果中可以發(fā)現(xiàn)，霍夫曼編碼和算術(shù)編碼都有著非常高的編碼效率.算術(shù)編碼比霍夫曼編碼的編碼效率略高一些。但是，在網(wǎng)上搜集的資料，有 如下介紹：在算術(shù)編碼和哈夫曼編碼之間有很大的相似性 - 實(shí)際上，哈夫曼編碼只是算術(shù)編碼的 一個(gè)特例 - 但是由于算術(shù)編碼將整個(gè)消息翻譯成一個(gè)表示為 基數(shù) b,而不是將消息中 的每個(gè)符號(hào)翻譯成一系列的以 b 為基數(shù)的數(shù)字，它通常比哈夫曼編碼更能達(dá)到最優(yōu)熵 編碼。Lz編碼： 由于程序的限制，本次實(shí)驗(yàn)只對(duì)一張很小

12、的圖片經(jīng)行了 LZ 編碼，由結(jié)果可以看出，相 較于前兩種的編碼，LZ 編碼的效率非常低。但是本實(shí)驗(yàn)效率低下的原因并不能說明此 編碼是比較差的，因?yàn)?20×20 的圖像所產(chǎn)生的序列非常短，隨著序列長長度的不斷增 加，LZ 編碼的效率也會(huì)不斷提高。總體來說，霍夫曼編碼最適合實(shí)際應(yīng)用。五、實(shí)驗(yàn)感悟通過本次試驗(yàn)，我們掌握了三種編碼的原理和方法，更重要的是掌握了MATLAB 圖形界面GUI的使用方法。剛開始做實(shí)驗(yàn)時(shí)感覺GUI很難，畢竟從前誰也沒有接觸過這方面的知識(shí)，但經(jīng)過查閱資料以及在做實(shí)驗(yàn)的過程中的不斷摸索，終于終做出了完整的GUI，比較完滿的完成了這次實(shí)驗(yàn)。六、程序代碼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、算術(shù)編碼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