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

1、<p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　2010—2011學(xué)年第一學(xué)期</p><p>　　課程設(shè)計名稱： 信息論與編碼課程設(shè)計 </p><p>　　設(shè)計題目： 哈夫曼編碼的分析與實現(xiàn) </p><p>　　完成期限：自 2010 年 12月 20 日至 2

2、010 年 12 月 26 日共 1 周</p><p><b>　　一．設(shè)計目的</b></p><p>　　1、深刻理解信源編碼的基本思想與目的；</p><p>　　2、理解哈夫曼編碼方法的基本過程與特點；</p><p>　　3、提高綜合運用所學(xué)理論知識獨立分析和解決問題的能力；</p><

3、p>　　4、使用MATLAB或其他語言進行編程。</p><p><b>　　二．設(shè)計內(nèi)容</b></p><p>　　假設(shè)已知一個信源的各符號概率，編寫適當函數(shù)，對其進行哈夫曼編碼，得出碼字，平均碼長和編碼效率，總結(jié)此編碼方法的特點和應(yīng)用。</p><p><b>　　三．設(shè)計要求</b></p>&

4、lt;p>　　1、編寫的函數(shù)要有通用性；</p><p>　　2、信源可以自由選擇，符號信源與圖像信源均可。</p><p><b>　　四．設(shè)計條件</b></p><p>　　計算機、MATLAB或其他語言環(huán)境</p><p><b>　　五、參考資料</b></p><

5、;p>　　[1]曹雪虹，張宗橙.信息論與編碼.北京：清華大學(xué)出版社，2007.</p><p>　　[2]王慧琴.數(shù)字圖像處理.北京：北京郵電大學(xué)出版社，2007.</p><p>　　指導(dǎo)教師（簽字）： 教研室主任（簽字）： </p><p>　　批準日期： 年 月 日<

6、/p><p><b>　　摘要</b></p><p>　　哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計算機信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進

7、行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。</p><p>　　本課題通過MATLAB編寫適當?shù)暮瘮?shù)，對一個隨機信源進行哈夫曼編碼，得出碼字，平均碼長和編碼效率。從而理解信源編碼的基本思想與目的以及哈夫曼編碼方法的基本過程與特點，并且提高

8、綜合運用所學(xué)理論知識獨立分析和解決問題的能力。</p><p>　　關(guān)鍵字：哈夫曼，信源編碼，MATLAB</p><p><b>　　目 錄</b></p><p><b>　　1 課題描述1</b></p><p>　　2 哈夫曼編碼的原理.1</p><p>　　

9、2.1哈夫曼編碼的構(gòu)造過程……………………………..………………….………..1</p><p>　　2.2哈夫曼編碼的應(yīng)用舉例…………………………….……………..……….…….1</p><p>　　3 哈夫曼編碼的實現(xiàn)過程4</p><p>　　3.1 軟件介紹4</p><p><b>　　3.2設(shè)計內(nèi)容4</b

10、></p><p>　　3.2設(shè)計步驟……………………………………………………………………………….....4</p><p>　　4 程序運行結(jié)果分析…………………………………………….…………………………….8</p><p><b>　　總 結(jié)10</b></p><p><b>　　參考文獻

11、11</b></p><p><b>　　1課題描述</b></p><p>　　哈夫曼編碼是一種編碼方式，以哈夫曼樹─即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計算機信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損耗壓縮。這一術(shù)語是指使用一張?zhí)貏e的編碼表將源字符（例如某文件中的一個

12、符號）進行編碼。這張編碼表的特別之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。</p><p><b>　　2哈夫曼編碼的原理</b></p><p>　　2.1 哈夫曼編碼的構(gòu)造過程</p><p&

13、gt;　　實現(xiàn)哈夫曼算法的大致描述為： </p><p>　　初始化：將2n-1個結(jié)點的三個指針域的值置為空（可用－1表 示），權(quán)值為0； </p><p>　　輸入：讀入n個葉結(jié)點的權(quán)值存入向量的前個分量中，即形成有個結(jié)點的森林（一個結(jié)點為一棵樹）； </p><p>　　排序：按權(quán)值排序（從小到大） </p><p>　　合并:把前兩棵樹

14、組成一棵新樹,放回森林,直至形成一棵樹</p><p><b>　　最后輸出哈夫曼編碼</b></p><p>　　2.2哈夫曼編碼應(yīng)用舉例</p><p>　　哈夫曼樹被廣泛的應(yīng)用在各種技術(shù)中，其中最典型的就是在編碼技術(shù)上的應(yīng)用。利用哈夫曼樹，我們可以得到平均長度最短的編碼。這里我們以計算機操作碼的優(yōu)化問題為例來分析說明。</p>

15、<p>　　研究操作碼的優(yōu)化問題主要是為了縮短指令字的長度，減少程序的總長度以及增加指令所能表示的操作信息和地址信息。要對操作碼進行優(yōu)化，就要知道每種操作指令在程序中的使用頻率。這一般是通過對大量已有的典型程序進行統(tǒng)計得到的。</p><p>　　設(shè)有7種不同的指令，其使用頻率如下表所示：</p><p>　　由于計算機內(nèi)部只能識別0、1代碼，所以若采用定長操作碼，則需要3位

16、（23＝8）。顯然，有一條編碼沒有作用，這是一種浪費。一段程序中若有n條指令，那么程序的總位數(shù)為3×n。為了充分地利用編碼信息和減少程序的總位數(shù)，我們可以采用變長編碼。如果對每一條指令指定一條編碼，使得這些編碼互不相同且最短，是否可以滿足要求呢？即是否可以如下表所示這樣編碼呢？</p><p>　　這樣雖然可以使得程序的總位數(shù)達到最小，但機器卻無法解碼。例如對編碼串0010110該怎么識別呢？第一個0可

17、以識別為I1，也可以和第二個0組成的串00一起被識別為I3，還可以將前三位識別為I6，這樣一來，這個編碼串就有多種譯法。因此，若要設(shè)計變長的編碼，則這種編碼必須滿足這樣一個條件：任意一個編碼不能成為其它任意編碼的前綴。我們把滿足這個條件的編碼叫做前綴編碼。</p><p>　　利用哈夫曼算法，可以使我們設(shè)計出最優(yōu)的前綴編碼。首先，我們以每條指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹，如下圖6.27所示：</p>

18、<p>　　對于該二叉樹，我們可以規(guī)定向左的分支標記為1，向右的分支標記為0。這樣，從根結(jié)點開始，沿線到達各頻度指令對應(yīng)的葉結(jié)點，所經(jīng)過的分支代碼序列就構(gòu)成了相應(yīng)頻度指令的哈夫曼編碼，如下圖所示：</p><p>　　可以驗證，該編碼是前綴編碼。若一段程序有1000條指令，其中I1大約有400條，I2大約有300條，I3大約有150，I4大約有50條，I5大約有40，I6大約有30，I7大約有30條

19、。對于定長編碼，該段程序的總位數(shù)大約為3×1000＝3000。采用哈夫曼編碼后，該段程序的總位數(shù)大約為 1×400＋2×300＋3×150＋5×（50＋40＋30＋30）＝2200?？梢?，哈夫曼編碼中雖然大部分編碼的長度大于定長編碼的長度3，卻使得程序的總位數(shù)變小了?？梢运愠鲈摴蚵幋a的平均碼長為：</p><p>　　3哈夫曼編碼的實現(xiàn)過程</p>

20、<p><b>　　3.1軟件介紹</b></p><p>　　MATLAB以矩陣作為基本編程單元，它提供了各種矩陣的運算與操作，并有較強的繪圖功能。MATLAB集科學(xué)計算、圖像處理、聲音處理于一身，是一個高度的集成系統(tǒng)，有良好的用戶界面，并有良好的幫助功能。MATLAB不僅流行于控制界，在機械工程、生物工程、語音處理、圖像處理、信號分析、計算機技術(shù)等各行各業(yè)中都有極廣泛的應(yīng)用

21、。MATLAB語言的特點1．編程效率高 2．用戶使用方便 3．擴充能力強 4．語句簡單，內(nèi)涵豐富 5．高效方便的矩陣和數(shù)組運算 6．方便的繪圖功能 </p><p><b>　　3.2設(shè)計內(nèi)容</b></p><p>　　已知一個信源的各符號概率，編寫適當函數(shù)，對其進行哈夫曼編碼，得出碼字，平均碼長和編碼效率，總結(jié)此編碼方法的特點和應(yīng)用。</p>&

22、lt;p><b>　　3.3設(shè)計步驟</b></p><p>　　MATLAB的操作界面MATLAB操作界面主要分為：任務(wù)欄、命令窗、命令歷史窗、當前目錄瀏覽器、工作空間瀏覽器及一個“啟動按鈕”</p><p>　　任務(wù)欄：位于軟件的正上方。各個菜單分別為：文件、編輯、視窗、調(diào)試、桌面、窗體、幫助這幾個窗口，點擊每個窗口可以選擇需要的操作。</p>

23、<p>　　命令窗(Command Window)：位于軟件操作界面的右側(cè)。在此窗口里，可以輸入各種指令、函數(shù)、變量表達式并進行各種操作。該窗口用于輸入命令并顯示除圖形以外的所有執(zhí)行結(jié)果。窗口中的“>>”為命令提示符，直接在其后面輸入命令并按下回車鍵后，會出現(xiàn)計算結(jié)果在命令后面。</p><p>　　命令歷史窗(Command History)：位于軟件操作界面的左下方。這個窗口記錄了命令

24、窗口已經(jīng)運行過的所有命令（指令、函數(shù)等），允許用戶對這些命令進行選擇、復(fù)制。</p><p>　　程序如下：（假定隨機信源為3,1,3,2,4,3,2,1,2,3）</p><p>　　clear all;</p><p>　　I=[3,1,3,2,4,3,2,1,2,3];</p><p>　　len=length(I);</p>

25、;<p><b>　　t=2;</b></p><p>　　biaozhi=0;</p><p>　　b(1)=I(1);</p><p>　　for i=2:len</p><p>　　for j=1:i-1</p><p>　　if I(j)==I(i)</p>&

26、lt;p>　　biaozhi=1;</p><p><b>　　break;</b></p><p><b>　　end </b></p><p><b>　　end </b></p><p>　　if biaozhi==0</p><p>　

27、　b(t)=I(i);</p><p><b>　　t=t+1;</b></p><p><b>　　end </b></p><p>　　biaozhi=0;</p><p><b>　　end</b></p><p>　　fprintf('

28、信源總長度:\n');</p><p>　　disp(len); %信源總長度</p><p>　　fprintf('字符:\n');</p><p><b>　　disp(b );</b></p><p>　　L=length(b);</p><p><b>　

29、　for i=1:L</b></p><p><b>　　a=0;</b></p><p>　　for j=1:len</p><p>　　if b(i)==I(j)</p><p><b>　　a=a+1;</b></p><p>　　count(i)=a;&l

30、t;/p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　count=count/len;%各字符概率</p><p>　　fprintf('各字符概率:

31、\n');</p><p>　　disp(count);</p><p><b>　　p=count;</b></p><p>　　%%%%%%%%%%%%%%%%%%%%%%%%%%%</p><p><b>　　s=0;</b></p><p><b>

32、　　l=0;</b></p><p><b>　　H=0;</b></p><p>　　N=length(p);</p><p><b>　　for i=1:N</b></p><p>　　H=H+(- p(i)*log2(p(i)));%計算信源信息熵</p><p

33、><b>　　end</b></p><p>　　fprintf('信源信息熵:\n');</p><p><b>　　disp(H);</b></p><p><b>　　tic;</b></p><p>　　for i=1:N-1 %按概率分布大小對信

34、源排序</p><p>　　for j=i+1:N</p><p>　　if p(i)<p(j)</p><p><b>　　m=p(j);</b></p><p>　　p(j)=p(i);</p><p><b>　　p(i)=m;</b></p>&l

35、t;p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　Q=p;</b></p><p>　　m=zeros(N-1,N);</p><

36、;p>　　for i=1:N-1 %循環(huán)縮減對概率值排序，畫出由每個信源符號概率到1.0 處的路徑</p><p>　　[Q,l]=sort(Q);</p><p>　　m(i,:)=[l(1:N-i+1),zeros(1,i-1)]; </p><p>　　Q=[Q(1)+Q(2),Q(3:N),1];</p><p><b&g

37、t;　　end</b></p><p>　　for i=1:N-1</p><p>　　c(i,:)=blanks(N*N); </p><p><b>　　end</b></p><p>　　c(N-1,N)='0';</p><p>　　c(N-1,2*N)=

38、9;1';</p><p>　　for i=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)));</p><p>　　c(N-i,N)='0';</p><p>

39、　　c(N-i,N+1:2*N-1)=c(N-i,1:N-1);</p><p>　　c(N-i,2*N)='1';</p><p>　　for j=1:i-1</p><p>　　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

40、));</p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　for i=1:N </p><p>　　h(i,1:N)=c(1,N*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*N);%碼字賦值</p>

41、<p>　　ll(i)=length(find(abs(h(i,:))~=32)); %各碼字碼長</p><p><b>　　end</b></p><p>　　l=sum(p.*ll); %計算平均碼長</p><p>　　n=H/l; %計算編碼效率</p><p>　　fprintf('編碼

42、的碼字:\n');</p><p>　　disp(h) %按照輸入順序排列的碼字</p><p>　　fprintf('平均碼長:\n');</p><p>　　disp(l) %輸出平均碼長</p><p>　　fprintf('編碼效率:\n');</p><p>　　dis

43、p(n) %輸出編碼效率</p><p><b>　　4程序運行結(jié)果分析</b></p><p>　　運行結(jié)果如下圖所示：</p><p><b>　　運行結(jié)果分析：</b></p><p>　　從運行結(jié)果可知該結(jié)果與理論一致，并且可以看出哈夫曼編碼的3個特點⑴哈夫曼碼的編碼方法保證了概率大的符號對

44、應(yīng)于短碼，概率小的符號對應(yīng)于長碼。⑵縮減信源的最后二個碼字總是最后一位碼元不同，前面各位碼元相同（二元編碼情況），從而保證了哈夫曼是即時碼。⑶每次縮減信源的最長兩個碼字有相同的碼長。這三個特點保證了所得的哈夫曼碼一定是最佳碼。因此哈夫曼是一種應(yīng)用廣泛而有效的數(shù)據(jù)壓縮技術(shù)。利用哈夫曼編碼進行通信可以大大提高信道利用率，加快信息傳輸速度，降低傳輸成本。數(shù)據(jù)壓縮的過程稱為編碼，解壓的過程稱為譯碼。進行信息傳遞時，發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)

45、據(jù)（明文）預(yù)先編碼，而接受端將傳來的數(shù)據(jù)（密文）進行譯碼。要求數(shù)據(jù)這樣一個簡單的哈夫曼編碼譯碼器。</p><p><b>　　總結(jié)</b></p><p>　　通過翻閱相關(guān)書籍，在網(wǎng)上查詢資料學(xué)習(xí)有關(guān)哈夫曼編碼的實現(xiàn)過程，我實在是獲益匪淺，更加深刻的感覺到哈夫曼編碼能夠大大提高通信的效率，對于我們通信工程專業(yè)來說，學(xué)好這門科學(xué)是非常重要的，在以后的圖像處理和壓縮方面

46、這門學(xué)科能給我們很大的幫助。同時，學(xué)習(xí)這門科學(xué)也是艱辛的，因為它比較難懂，這不僅需要我們發(fā)揮我們的聰明才智，還需要我們在不斷的實踐中領(lǐng)悟。</p><p>　　這次的課程設(shè)計，讓我體會到了作為一個編程人員的艱辛，一個算法到具體實現(xiàn)，再到應(yīng)用層面的開發(fā)是需要有一個較長的路要走的，不是一朝一夕就可以實現(xiàn)的，而且在編好程序后，編程人員還要花很多時間去完善，過程是心酸的，外人很難能夠真正明白。</p>&l

47、t;p>　　最后非常感謝一直給我知道的老師和同學(xué)們，他們的支持和鼓勵讓我在遇到挫折時能夠戰(zhàn)勝它，也讓我成功了完成了這次課程設(shè)計。今后我要更加努力的學(xué)習(xí)專業(yè)知識，提高自我的能力！</p><p><b>　　參考文獻</b></p><p>　　[1]曹雪虹，張宗橙.信息論與編碼.北京：清華大學(xué)出版社，2007.</p><p>　　[2]