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

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

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

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

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

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

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

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

8、綜合運(yùn)用所學(xué)理論知識(shí)獨(dú)立分析和解決問(wèn)題的能力。</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)造過(guò)程……………………………..………………….………..1</p><p>　　2.2哈夫曼編碼的應(yīng)用舉例…………………………….……………..……….…….1</p><p>　　3 哈夫曼編碼的實(shí)現(xiàn)過(guò)程4</p><p>　　3.1 軟件介紹4</p><p><b>　　3.2設(shè)計(jì)內(nèi)容4</b

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

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

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

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

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

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

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

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

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

19、。對(duì)于定長(zhǎng)編碼，該段程序的總位數(shù)大約為3×1000＝3000。采用哈夫曼編碼后，該段程序的總位數(shù)大約為 1×400＋2×300＋3×150＋5×（50＋40＋30＋30）＝2200?？梢?jiàn)，哈夫曼編碼中雖然大部分編碼的長(zhǎng)度大于定長(zhǎng)編碼的長(zhǎng)度3，卻使得程序的總位數(shù)變小了。可以算出該哈夫曼編碼的平均碼長(zhǎng)為：</p><p>　　3哈夫曼編碼的實(shí)現(xiàn)過(guò)程</p>

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

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

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

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

24、窗口已經(jīng)運(yùn)行過(guò)的所有命令（指令、函數(shù)等），允許用戶對(duì)這些命令進(jìn)行選擇、復(fù)制。</p><p>　　程序如下：（假定隨機(jī)信源為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、信源總長(zhǎng)度:\n');</p><p>　　disp(len); %信源總長(zhǎng)度</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)));%計(jì)算信源信息熵</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 %按概率分布大小對(duì)信

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)縮減對(duì)概率值排序，畫出由每個(gè)信源符號(hào)概率到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 %對(duì)字符數(shù)組c碼字賦值過(guò)程，記下沿路徑的“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)); %各碼字碼長(zhǎng)</p><p><b>　　end</b></p><p>　　l=sum(p.*ll); %計(jì)算平均碼長(zhǎng)</p><p>　　n=H/l; %計(jì)算編碼效率</p><p>　　fprintf('編碼

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

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

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

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

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

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