1、課程設計任務書2013學年第一學期專業：通信工程學號:_姓名：邊陽課程設計名稱：信息論與編碼課程設計設計題目：二進制哈夫曼編碼的分析與實現完成期限：自2013年11月4日至2013年11月10日共1周1、深刻理解信源編碼的基本思想與目的；2、理解哈夫曼編碼方法的基本過程與特點；3、提高綜合運用所學理論知識獨立分析和解決問題的能力；4、使用MATLAB或其他語言進行編程。二.設計內容假設已知一個信源的各符號概率，編寫適當函數，對其進行哈夫曼編碼，得出M進制碼字，平均碼長和編碼效率，總結此編碼方法的特點和應用。三.設計要求1、編寫的函數要有通用性；2、信源可以自由選擇，符號信源與圖像信源均可。四.

2、設計條件計算機、MATLAB或其他語言環境五.參考資料1曹雪虹，張宗橙.信息論與編碼.北京：清華大學出版社，2007.2王慧琴.數字圖像處理.北京：北京郵電大學出版社，2007.指導教師（簽字）：教研室主任（簽字）：批準日期：年月日摘要霍夫曼編碼是可變字長編碼（VLC）的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。它是根據可變長最佳編碼定理，應用哈夫曼算法而產生的一種編碼方法。在非均勻符號概率分布的情況下，變長編碼總的編碼效率要高于等字長編碼。因為具體規定了編碼的方法，能使無失真

3、編碼的效率非常接近與1,所以在壓縮信源信息率的實用設備中，哈夫曼編碼還是比較常用的。本課題利用哈夫曼編碼的方法實現了對信源符號的嫡、平均碼長、傳輸速率、編碼效率等的求解。關鍵詞：哈弗曼編碼；信源；哈夫曼樹1課題描述4.2設計原理4.3設計過程5.3.1 課題介紹5.3.1.1 Huffman編碼特點6.3.1.2 哈夫曼編碼方法6.3.3設計步驟7.4哈夫曼編碼的MATLAB實現8.總結1.1.參考文獻1.21課題描述huffman編碼是一種二進制編碼的算法，目的是縮小原來的數據，簡單的說就是將出現概率較高的符號分配較少的碼字，而出現概率大的符號分配較長的碼字，這樣起到壓縮數據的作用。哈夫曼編

4、碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。本課題是利用哈夫曼編碼方式來實現對信源符號碼字、平均碼長及編碼效率的求解。開發工具：MATLAB。2設計原理設計原理如下：(2.1)設數字圖像像素灰度級集合為d1,d2,，dm,其對應的概率分別為p(d1),p(d2),p(dm)。按信息論中信源信息嫡的定義，圖像的嫡定義為：H=P(di)lbP(di)bit/字符圖像的嫡表示像素各個灰度級位數的統計平均值，給出了對此輸入灰度級集合進行編碼時所需的平均位數的下

5、限。設Bi為數字圖像中灰度級di所對應的碼字長度(二進制代碼的位數)，其相應出現的概率為P(di),則該數字圖像所賦予的平均碼字長度為：(2.(2)(2.(3)R八，-iP(di)H=10000R根據信息論中信源編碼理論，可以證明在R呈H條件下，總可以設計出某種無失真編碼方法。當然如果編碼結果使R遠大于H,表明這種編碼方法效率很低，占用比特數太多。最好編碼結果是使R等于或接近于Ho這種狀態的編碼方法，稱為最佳編碼。壓縮比是指編碼前后平均碼長之比，如果用n表示編碼前每個符號的平均碼長，通常為用自然二進制碼時的位數，則壓縮比可表示為：(2.4)般來講，壓縮比大，則說明被壓縮掉的數據量多。一個編碼系

6、統要研究的問題是設法減小編碼平均長度R,使編碼效率“盡量趨于1,而冗余度趨于03設計過程3.1 課題介紹3.1.1 Huffman編碼特點凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼。為此必須將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。哈夫曼（Huffman）編碼是最佳變長編碼方法的一種，它是根據可變長最佳編碼定理，應用哈夫曼算法而產生的一種編碼方法。進行哈夫曼編碼時，為得到碼方差最小的碼，應使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合作的次數，充分利用短碼。哈夫曼碼是用概率匹配方法進行信源編碼。它有

7、兩個明顯的特點：一是哈夫曼碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；二是縮減信源的最后兩個碼字總是最后一位不同，從而保證了哈夫曼編碼是即時碼。哈夫曼編碼方法得到的碼并非是唯一的，造成并非唯一的原因是：首先，每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1可以任意的，所以可以得到不同的哈夫曼碼，但不會影響碼字的長度。其次：對信源進行縮減時，兩個概率最小的符號合并后的概率與其他信源符號的概率相同時，這兩者在縮減信源中進行概率排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將合并的概率放在上面，這樣可以獲得較小的碼

8、方差。對于多進制哈夫曼編碼，為了提高編碼效率，就要使長碼的符號數量盡量少、概率盡量小，所以信源符號數最好滿足m=(r-1F+r,其中r為進制數，n為縮減的次數。例如，要進行三進制編碼，那么最好信源有7個符號，第1次合并后減少2個成為5個，第2次合并后又減少2個成為3個，這樣給每一步賦予三進制符號就沒有浪費了。但如果信源只有6個符號時，為了盡量減少最長碼的數量，則應該在第1次合并時添置概率為零的虛擬符號1個，事實上只合并2個概率最小的符號，后面每次合并三個，就可以使得最長碼的符號數量最少，也就是長碼的概率最小，從而得到最高的編碼效率。哈夫曼變長碼的效率是相當高的，它可以單個信源符號編碼或用L較小

9、的信源序列編碼，對編碼器的設計來說也將簡單的多。但是應當注意，要達到很高的效率仍然需要按長序列來計算,這樣才能使平均碼字長度降低。3.1.2 哈夫曼編碼方法(1)將信源消息符號按其出現的概率大小依次排列為P住P2呈呈Pn(2)將兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進制符號的字母重新排隊。(3)對重排后的兩個概率最小符號重復步驟(2)的過程。(4)不斷繼續上述過程，直到最后兩個符號配以0和1為止。(5)從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字。3.2 設計內容一個有8個符號的信源X,各個符號出現的概率為：符號

10、：u1u2u3u4u5u6u7u8X=概率：0.400.180.100.100.070.060.050.04試進行霍夫曼編碼，并計算平均碼長、編碼效率、壓縮比、冗余度等。3.3 設計步驟最終的各符號的霍夫曼編碼如下：u1:1u2:001u3:011u4:0000u5:0100u6:0101u7:00010u8:00011霍夫曼編碼時，對同一源圖像序列，霍夫曼編碼并不是唯一的。如果節標1和標0的對調，則相應的霍夫曼編碼變成：u1:0u2:110u3:100u4:1111u5:1011u6:1010u7:11101u8:11100對照兩組霍夫曼編碼不難看出，盡管兩者的組成不同，但兩者的平均碼長是一

11、致的。再根據以上數據，可分別計算其信源的嫡、平均碼長、編碼效率及冗余度，即嫡：8H(x)-Pk1bPkk二=-0.4lb0.40.18lb0.180.10lb0.1-0.07lb0.070.06lb0.06-0.05lb0.05-0.04lb0.04=2.55平均碼長：8R(x)八-kPkkg=1X0.04+3X0.18+3X0.10+4>0.10+4>0.07+4>0.06+5X0.05+5X0.04=2.61編碼效率：H2.55=10000=97.70。R2.61壓縮之前8個符號需要3個比特量化，經壓縮之后的平均碼字長度為2.61,因此壓縮比為：C=32.61=1.15冗

12、余度為：r=1_-2.300對上述信源X的霍夫曼編碼，其編碼效率已達97.7%,僅有2.3%的冗余。4哈夫曼編碼的MATLAB實現在matlab中調用了用戶自定義文件humanff.m的文件，其源代碼為：functionh,l=huffman(p)iflength(find(p<0)=0;error('Inputisnotaprob.vector,thereisnegatibecomponent');endifabs(sum(p)-1)>10e-10error('Inputisnotaprob.vector,thesumofthecomponentisnot

13、equalto1.');endn=length(p);%得到輸入的元素個數q=p;m=zeros(n-1,n);fori=1:n-1,q,e=sort(q);m(i,:)=e(1:n-i+1),zeros(1,i-1);q=q(1)+q(2)+q(3:n),e;endfori=1:n-1,c(i,:)=blanks(n*n);end%以下計算各個元素碼字c(n-1,n)='0'c(n-2,2*n)='1'fori=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(n-i+1,

14、:)=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);end在計算信源平均信息量的時候調用了message函數，在計算信源平均信息量的時候調用了message函數，message®數的源代碼為：functionr=message(x,n)%參數x是概率分布，n是離散信源的分布值數目r=0;for

15、i=1:nr=r-x(i)*10g(x(i)/10g(2);enddisp('此離散信源的平均信息量為');r通常哈夫曼編碼學的效率是小于1的，但當信源為某些特殊情況時，可以是效率達到1,當然是不可能超過1的。如：'U1U2U3U4U5、P=Q/31/61/151/1511/30,分別調用huffman和message®數如下：clearall;p=1/3,1/6,1/15,1/15,11/30%定義概率序列P=0.33330.16670.06670.06670.3667截圖為:匚tdlgfadflQhMwJWndm?匕*口吁汽電電7薜NEJ學EX»

16、-tratxHn方寸Aid呵Fkht'bI*iEutrcntKHfM.tW¥-Fs'-MATLAD'-wwIcCurran*:IT4ctir-EF：'ilATlAE'i.vca-k317SiEd*tfi©通,Ji-1X:UeIFbl+S-r*IU.1:I:IBQ0QQ3ma0G1,niSodiumSoiOUD.mSChsrv*9lmfirirhm語畫mhufTman.-asvH4訕EdtorAutnsaM-fiiiMReM-FrieEdtOsAu«&ea.M-HflM恤M-fiaEdtcaAl£ds32Q1

17、1d2-31in2011.1M1i,2010-12-2512010-12-Z2ZI11-12-S1：2011-12-81,3010-12-352010-12-252011-1201To£4Lsiaji«i.spJflciNbHahlporSqfroatJigJklprodu»hIhu*allp-lJ/3.1/6.V15.j/jS.JJ/301*S.ftT.PFNP*0.羽第0.16670.。幅F。的打&便；1ettolLDiriclwir.cckiAiE總結通過該課程設計，我掌握了編譯程序的原理以及步驟，還有編譯程序工作的基本過程及其各階段的基本任務，熟悉

18、了編譯程序總流程框圖，構造工具及其相關的技術。課本上的知識是機械的，抽象的。在本次課程設計，我有很大的收獲。這首先體現在理論知識的完善上：采用等長編碼的優點是編碼過程和解碼過程簡單，可是這種方法沒有考慮各個符號出現的概率，實際上就是將它們當做等概率事件處理的，所以它的編碼效率比較低，而哈夫曼編碼是根據可變長最佳編碼定理，應用哈夫曼算法而產生的一種編碼方法，它的平均碼長最小，消息傳輸速率最大，編碼效率最高；同時實踐能力和動手能力有了質的飛躍！設計中，我自感知識的缺陷，不斷的上網查閱資料，翻閱各類相關書籍，自己動手，自己設計，讓我的思維邏輯更加清晰。在上機操作中，靠這次設計我熟練掌握了計算機編程，將理論變為實際開了一個好頭。在我設計好之后，老師對我進行指導，使得我的課程設計進一步完善，更加完美。在這次課程設計過程中，我發現了自己綜合應用能力的欠缺。以后，我會更加重視用軟件編程，應用計算機來對處理信號。總之，基本達到了預期的課程設計目的。參考文獻1李朝輝，張弘.數字圖像處理及應用.北京：機械工業