二進制哈夫曼編碼

課程設(shè)計任務(wù)書2023—2023學(xué)年第一學(xué)期專業(yè)：通信工程 學(xué)號： 姓名：課程設(shè)計名稱： 信息論與編碼課程設(shè)計 設(shè)計題目： 二進制哈夫曼編碼的分析與實現(xiàn) 完成期限：自 年 月 日至 年 月 日共 一．設(shè)計目的1、深刻理解信源編碼的根本思想與目的；2、理解哈夫曼編碼方法的根本過程與特點；3、提高綜合運用所學(xué)理論學(xué)問獨立分析和解決問題的力量；二．設(shè)計內(nèi)容出二進制碼字，平均碼長和編碼效率，總結(jié)此編碼方法的特點和應(yīng)用。三．設(shè)計要求1、編寫的函數(shù)要有通用性；2、信源可以自由選擇，符號信源與圖像信源均可。四．設(shè)計條件計算機、MATLAB或其他語言環(huán)境五．參考資料[1]曹雪虹，張宗橙.信息論與編碼.北京：清華大學(xué)出版社，2023.[2]王慧琴.數(shù)字圖像處理.北京：北京郵電大學(xué)出版社，2023.指導(dǎo)教師〔簽字： 教研室主任〔簽字批準(zhǔn)日期： 年 月 日摘要(VLC)的一種。Huffman1952年提出一種編編碼。它是依據(jù)可變長最正確編碼定理，1，所以在壓縮信源信息率的有用設(shè)備中，哈夫曼編碼還是比較常用的。編碼效率等的求解。關(guān)鍵詞：Huffman；可變長編碼；信源編碼目錄\l“_TOC_250010“1.課題描述 1\l“_TOC_250009“設(shè)計原理 1\l“_TOC_250008“設(shè)計過程 2\l“_TOC_250007“課題介紹 2\l“_TOC_250006“Huffman編碼特點 2\l“_TOC_250005“哈夫曼編碼方法 3\l“_TOC_250004“設(shè)計內(nèi)容 3\l“_TOC_250003“設(shè)計步驟 4\l“_TOC_250002“哈夫曼編碼的MATLAB實現(xiàn) 5\l“_TOC_250001“總 結(jié) 8\l“_TOC_250000“參考文獻 9 課程設(shè)計說明書〔論文〕 課程設(shè)計說明書〔論文〕 19頁1. 課題描述huffman編碼是一種二進制編碼的算法，目的是縮小原來的數(shù)據(jù)，簡潔的說字，這樣起到壓縮數(shù)據(jù)的作用。哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman1952年提出一種編碼方法，該方法完全依據(jù)字符消滅概率來構(gòu)造異Huffman編碼。率的求解。設(shè)計原理設(shè)計原理如下：設(shè)數(shù)字圖像像素灰度級集合為{d1,d2,…,dm},其對應(yīng)的概率分別為p(d1),p(d2),…,p(dm)。按信息論中信源信息熵的定義，圖像的熵定義為：Hmi1

PdilbP(di)bit字符 〔2.1〕圖像的熵表示像素各個灰度級位數(shù)的統(tǒng)計平均值，給出了對此輸入灰度級集合進展編碼時所需的平均位數(shù)的下限。設(shè)βidi所對應(yīng)的碼字長度〔二進制代碼的位數(shù)P〔di〕,則該數(shù)字圖像所賜予的平均碼字長度為：Rmi1HR

iP(di) 〔2.2〕10000 〔2.3〕R≧H條件下，總可以設(shè)計出某種RH，說明這種編碼方法效率很RH。這種狀態(tài)的編碼方法，稱為最正確編碼。n表示編碼前每個符號的平均碼長，通常為用自然二進制碼時的位數(shù)，則壓縮比可表示為：r n 〔2.4〕R一般來講，壓縮比大，則說明被壓縮掉的數(shù)據(jù)量多。一個編碼系統(tǒng)要爭論0。設(shè)計過程課題介紹Huffman編碼特點〔Huffman〕編碼是最正確變長編碼方法。碼。01差。mr1nr,r為進制數(shù)，n為縮減的次數(shù)。例如，要進展三進制編碼，那么最好信源有7個符號，第1次合并后削減25223個符號時，為了盡量削減最長碼的數(shù)量，112個概率最的概率最小，從而得到最高的編碼效率。L較小的的效率仍舊需要按長序列來計算，這樣才能使平均碼字長度降低。哈夫曼編碼方法P1≧P2≧…≧Pn1兩個碼元，并將這兩個概率相加作為一個字母的概率，與未安排的二進制符號的字母重排隊。對重排后的兩個概率最小符號重復(fù)步驟〔2〕的過程。不斷連續(xù)上述過程，直到最終兩個符號配以0和1為止。相應(yīng)的碼字。設(shè)計內(nèi)容8X，各個符號消滅的概率為：符號：u1 u2 u3 u4 u5 u6 u7 u8X= 4018101007060504試進展霍夫曼編碼，并計算平均碼長、編碼效率、壓縮比、冗余度等。設(shè)計步驟最終的各符號的霍夫曼編碼如下：u1:1 u2:001 u3:011 u4:0000u5:0100u6:0101 u7:00010 u8:0001110u1:0 u2:110 u3:100 u4:1111u5:1011u6:1010 u7:11101 u8:11100全都的。再依據(jù)以上數(shù)據(jù)，可分別計算其信源的熵、平均碼長、編碼效率及冗余度，即熵:H(x)8

Pk1bPk

=－0.4lb0.4－0.18lb0.18－0.10lb0.1－0.07lb0.07－0.06lb0.06－0.05lb0.05－0.04lb0.04=2.558

kPk

=1×0.04+3×0.18+3×0.10+4×0.10+4×0.07+4×0.06+5×0.05+5×0.04=2.61H

2.55100

97.700R 2.61 0 002.61，因此壓縮比為：2.611.15冗余度為：00r100X97.72.3％的冗余。哈夫曼編碼的MATLAB實現(xiàn)matlabhumanff.mfunction[h,l]=huffman(p)iflength(find(p<0))~=0;error(”Inputisnotaprob.vector,thereisnegatibecomponent”);endifabs(sum(p)-1)>10e-10error(”Inputisnotaprob.vector,thesumofthecomponentisnotequalto1.”);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);endc(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,:)==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));endmessagemessage函數(shù)，message函數(shù)的源代碼為：functionr=message(x,n) x是概率分布，n是離散信源的分布值數(shù)目r=0;fori=1:nr=r-x(i)*log(x(i))/log(2);end此離散信源的平均信息量為”);r11的。如：13PU1 U13 16

U3

U4115

U51130huffmanmessage函數(shù)如下：clearall;p=[1/3,1/6,1/15,1/15,11/30] p=0.3333 0.1667 0.0667 0.0667 0.3667截圖為：總 結(jié)關(guān)的技術(shù)。課本上的學(xué)問是機械的，抽象的。在本次課