課程設(shè)計-哈夫曼編碼的分析和實現(xiàn)

課程設(shè)計任務(wù)書2010—2011學(xué)年第一學(xué)期專業(yè)：通信工程學(xué)號:070110101姓名：茍孟洛課程設(shè)計名稱：信息論與編碼課程設(shè)計設(shè)計題目：哈夫曼編碼的分析與實現(xiàn)完成期限：自2010年12月2^日至2010年12月26日共±周設(shè)計目的1、深刻理解信源編碼的基本思想與目的；2、理解哈夫曼編碼方法的基本過程與特點；3、提高綜合運用所學(xué)理論知識獨立分析和解決問題的能力；4、使用MATLAB或其他語言進(jìn)行編程。設(shè)計內(nèi)容假設(shè)已知一個信源的各符號概率，編寫適當(dāng)函數(shù)，對其進(jìn)行哈夫曼編碼，得出碼字，平均碼長和編碼效率，總結(jié)此編碼方法的特點和應(yīng)用。設(shè)計要求1、編寫的函數(shù)要有通用性；2、信源可以自由選擇，符號信源與圖像信源均可。設(shè)計條件計算機、MATLAB或其他語言環(huán)境參考資料曹雪虹，張宗橙.信息論與編碼.北京：清華大學(xué)出版社，2007.王慧琴.數(shù)字圖像處理.北京：北京郵電大學(xué)出版社，2007.指導(dǎo)教師（簽字）：教研室主任（簽字）：批準(zhǔn)日期：年月日摘要哈夫曼編碼（HuffmanCoding）是一種編碼方式，以哈夫曼樹一即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計算機信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。本課題通過MATLAB編寫適當(dāng)?shù)暮瘮?shù)，對一個隨機信源進(jìn)行哈夫曼編碼，得出碼字，平均碼長和編碼效率。從而理解信源編碼的基本思想與目的以及哈夫曼編碼方法的基本過程與特點，并且提高綜合運用所學(xué)理論知識獨立分析和解決問題的能力。關(guān)鍵字：哈夫曼，信源編碼，MATLAB1課題描述錯誤！未定義書簽。2哈夫曼編碼的原理錯誤！未定義書簽。TOC\o"1-5"\h\z\o"CurrentDocument"2.1哈夫曼編碼的構(gòu)造過程1\o"CurrentDocument"2.2哈夫曼編碼的應(yīng)用舉例1\o"CurrentDocument"3哈夫曼編碼的實現(xiàn)過程4\o"CurrentDocument"3.1軟件介紹4\o"CurrentDocument"3.2設(shè)計內(nèi)容4\o"CurrentDocument"3.2設(shè)計步驟4\o"CurrentDocument"4程序運行結(jié)果分析8總結(jié)10\o"CurrentDocument"參考文獻(xiàn)111課題描述哈夫曼編碼是一種編碼方式，以哈夫曼樹一即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計算機信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)貏e的編碼表將源字符（例如某文件中的一個符號）進(jìn)行編碼。這張編碼表的特別之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。2哈夫曼編碼的原理2.1哈夫曼編碼的構(gòu)造過程實現(xiàn)哈夫曼算法的大致描述為：初始化：將2n-1個結(jié)點的三個指針域的值置為空（可用一1表示），權(quán)值為0;輸入：讀入n個葉結(jié)點的權(quán)值存入向量的前個分量中，即形成有個結(jié)點的森林（一個結(jié)點為一棵樹）；排序：按權(quán)值排序（從小到大）合并:把前兩棵樹組成一棵新樹，放回森林，直至形成一棵樹最后輸出哈夫曼編碼2.2哈夫曼編碼應(yīng)用舉例哈夫曼樹被廣泛的應(yīng)用在各種技術(shù)中，其中最典型的就是在編碼技術(shù)上的應(yīng)用。利用哈夫曼樹，我們可以得到平均長度最短的編碼。這里我們以計算機操作碼的優(yōu)化問題為例來分析說明。研究操作碼的優(yōu)化問題主要是為了縮短指令字的長度，減少程序的總長度以及增加指令所能表示的操作信息和地址信息。要對操作碼進(jìn)行優(yōu)化，就要知道每種操作指令在程序中的使用頻率。這一般是通過對大量已有的典型程序進(jìn)行統(tǒng)計得到的。設(shè)有7種不同的指令，其使用頻率如下表所示:指令使用頻（P「）J10.401J20.30J30.15A0.05i0.04A0.03J70.03由于計算機內(nèi)部只能識別0、1代碼，所以若采用定長操作碼，則需要3位（23=8）。顯然，有一條編碼沒有作用，這是一種浪費。一段程序中若有!條指令，那么程序的總位數(shù)為3xn。為了充分地利用編碼信息和減少程序的總位數(shù)，我們可以采用變長編碼。如果對每一條指令指定一條編碼，使得這些編碼互不相同且最短，是否可以滿足要求呢？即是否可以如下表所示這樣編碼呢？指令編碼L0A1J300J401Js000A001J7010這樣雖然可以使得程序的總位數(shù)達(dá)到最小，但機器卻無法解碼。例如對編碼串0010110該怎么識別呢？第一個0可以識別為L，也可以和第二個0組成的串00一起被識別為13,還可以將前三位識別為16,這樣一來，這個編碼串就有多種譯法。因此，若要設(shè)計變長的編碼，則這種編碼必須滿足這樣一個條件：任意一個編碼不能成為其它任意編碼的前綴。我們把滿足這個條件的編碼叫做前綴編碼。

利用哈夫曼算法，可以使我們設(shè)計出最優(yōu)的前綴編碼。首先，我們以每條指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹，如下圖6.27所示:對于該二叉樹，我們可以規(guī)定向左的分支標(biāo)記為1，向右的分支標(biāo)記為0。這樣，從根結(jié)點開始，沿線到達(dá)各頻度指令對應(yīng)的葉結(jié)點，所經(jīng)過的分支代碼序列就構(gòu)成了相應(yīng)頻度指令的哈夫曼編碼，如下圖所示：指令編碼J10J210J3110A11100i11101A11110J711111可以驗證，該編碼是前綴編碼。若一段程序有1000條指令，其中I1大約有400條，I2大約有300條，I3大約有150，I4大約有50條，I5大約有40，I6大約有30，I7大約有30條。對于定長編碼，該段程序的總位數(shù)大約為3x1000=3000。采用哈夫曼編碼后，該段程序的總位數(shù)大約為1x400+2x300+3x150+5x(50+40+30+30)=2200?？梢姡蚵幋a中雖然大部分編碼的長度大于定長編碼的長度3,卻使得程序的總位數(shù)變小了。可以算出該哈夫曼編碼的平均碼長為：=0.40x1+0.30x2+0.15x3+0.05x5+0.04xS+0.03x5+0.:03x5=2.20'3哈夫曼編碼的實現(xiàn)過程3.1軟件介紹MATLAB以矩陣作為基本編程單元，它提供了各種矩陣的運算與操作，并有較強的繪圖功能。MATLAB集科學(xué)計算、圖像處理、聲音處理于一身，是一個高度的集成系統(tǒng)，有良好的用戶界面，并有良好的幫助功能。MATLAB不僅流行于控制界，在機械工程、生物工程、語音處理、圖像處理、信號分析、計算機技術(shù)等各行各業(yè)中都有極廣泛的應(yīng)用。MATLAB語言的特點1.編程效率高2.用戶使用方便3.擴(kuò)充能力強4.語句簡單，內(nèi)涵豐富5.高效方便的矩陣和數(shù)組運算6.方便的繪圖功能3.2設(shè)計內(nèi)容已知一個信源的各符號概率，編寫適當(dāng)函數(shù)，對其進(jìn)行哈夫曼編碼，得出碼字，平均碼長和編碼效率，總結(jié)此編碼方法的特點和應(yīng)用。3.3設(shè)計步驟MATLAB的操作界面MATLAB操作界面主要分為：任務(wù)欄、命令窗、命令歷史窗、當(dāng)前目錄瀏覽器、工作空間瀏覽器及一個“啟動按鈕”任務(wù)欄：位于軟件的正上方。各個菜單分別為：文件、編輯、視窗、調(diào)試、桌面、窗體、幫助這幾個窗口，點擊每個窗口可以選擇需要的操作。命令窗(CommandWindow)：位于軟件操作界面的右側(cè)。在此窗口里，可以輸入各種指令、函數(shù)、變量表達(dá)式并進(jìn)行各種操作。該窗口用于輸入命令并顯示除圖形以外的所有執(zhí)行結(jié)果。窗口中的“"為命令提示符，直接在其后面輸入命令并按下回車鍵后，會出現(xiàn)計算結(jié)果在命令后面。命令歷史窗(CommandHistory):位于軟件操作界面的左下方。這個窗口記錄了命令窗口已經(jīng)運行過的所有命令(指令、函數(shù)等)，允許用戶對這些命令進(jìn)行選擇、復(fù)制。程序如下：(假定隨機信源為3,1,3,2,4,3,2,1,2,3)clearall;I=[3,1,3,2,4,3,2,1,2,3];len=length(I);t=2;biaozhi=0;b(1)=I(1);fori=2:lenforj=1:i-1ifI(j)==I(i)biaozhi=1;break;endendifbiaozhi==0b(t)=I(i);t=t+1;endbiaozhi=0;endfprintf('信源總長度:\n');disp(len);%信源總長度fprintf('字符:\n');disp(b);L=length(b);fori=1:La=0;forj=1:lenifb(i)==I①a=a+1;count(i)=a;endendendcount=count/len;%各字符概率fprintf('各字符概率:\n');disp(count);p=count;%%%%%%%%%%%%%%%%%%%%%%%%%%%s=0;l=0;H=0;N=length(p);fori=1:NH=H+(-p(i)*log2(p(i)));%計算信源信息熵endfprintf('信源信息熵:\n');disp(H);tic;fori=1:N-1%按概率分布大小對信源排序forj=i+1:Nifp(i)<p(j)m=p(j);p(j)=p(i);p(i)=m;endendendQ=p;m=zeros(N-1,N);fori=1:N-1%循環(huán)縮減對概率值排序，畫出由每個信源符號概率到1.0處的路徑[Q,l]=sort(Q);m(i,:)=[l(1:N-i+1),zeros(1,i-1)];Q=[Q(1)+Q(2),Q(3:N),1];endfori=1:N-1c(i,:)=blanks(N*N);endc(N-1,N)='0';c(N-1,2*N)='1';fori=2:N-1%對字符數(shù)組c碼字賦值過程，記下沿路徑的“1”和“0”；c(N-i,1:N-1)=c(N-i+1,N*(find(m(N-i+1,:)==1))-(N-2):N*(find(m(N-i+1,:)==1)));c(N-i,N)='0';c(N-i,N+1:2*N-1)=c(N-i,1:N-1);c(N-i,2*N)='1';forj=1:i-1c(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));endendfori=1:Nh(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.*ll);%計算平均碼長n=H/l;%計算編碼效率fprintf(編碼的碼字:\n');disp(h)%按照輸入順序排列的碼字fprintf('平均碼長:\n');disp(l)%輸出平均碼長fprintf(編碼效率:\n');disp(n)%輸出編碼效率4程序運行結(jié)果分析運行結(jié)果如下圖所示：運行結(jié)果分析：從運行結(jié)果可知該結(jié)果與理論一致，并且可以看出哈夫曼編碼的3個特點⑴哈夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼。⑵縮減信源的最后二個碼字總是最后一位碼元不同，前面各位碼元相同（二元編碼情況），從而保證了哈夫曼是即時碼。⑶每次縮減信源的最長兩個碼字有相同的碼長。這三個特點保證了所得的哈夫曼碼一定是最佳碼。因此哈夫曼是一種應(yīng)用廣泛而有效的數(shù)據(jù)壓縮技術(shù)。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，加快信息傳輸速度，降低傳輸成本。數(shù)據(jù)壓縮的過程稱為編碼，解壓的過程稱為譯碼。進(jìn)行信息傳遞時，發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)（明文）預(yù)先編碼，而接受端將傳來的數(shù)據(jù)（密文）進(jìn)行譯碼。要求數(shù)據(jù)這樣一個簡單的哈夫曼編碼譯碼器?？偨Y(jié)通過翻閱相關(guān)書籍，在網(wǎng)上查詢資料學(xué)習(xí)有關(guān)哈夫曼編碼的實現(xiàn)過程，我實在是獲益匪淺，更加深刻的感覺到哈夫曼編碼能夠大大提高通信的效率，對于我們通信工程專業(yè)來說，學(xué)好這門科學(xué)是非常重要的，在以后的圖像處理和壓縮方面這門學(xué)科能給我們很大的幫助。同時，學(xué)習(xí)這門科學(xué)也是艱辛的，因為它比較難懂，這不僅需要我們發(fā)揮我們的聰明才智