信息論編碼課程設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

11、致的。再根據(jù)以上數(shù)據(jù)，可分別計(jì)算其信源的嫡、平均碼長(zhǎng)、編碼效率及冗余度，即嫡：8H(x)-Pk1bPkk二=-0.4lb0.40.18lb0.180.10lb0.1-0.07lb0.070.06lb0.06-0.05lb0.05-0.04lb0.04=2.55平均碼長(zhǎng)：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個(gè)符號(hào)需要3個(gè)比特量化，經(jīng)壓縮之后的平均碼字長(zhǎng)度為2.61,因此壓縮比為：C=32.61=1.15冗

12、余度為：r=1_-2.300對(duì)上述信源X的霍夫曼編碼，其編碼效率已達(dá)97.7%,僅有2.3%的冗余。4哈夫曼編碼的MATLAB實(shí)現(xiàn)在matlab中調(diào)用了用戶自定義文件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);%得到輸入的元素個(gè)數(shù)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%以下計(jì)算各個(gè)元素碼字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在計(jì)算信源平均信息量的時(shí)候調(diào)用了message函數(shù)，在計(jì)算信源平均信息量的時(shí)候調(diào)用了message函數(shù)，message®數(shù)的源代碼為：functionr=message(x,n)%參數(shù)x是概率分布，n是離散信源的分布值數(shù)目r=0;for

15、i=1:nr=r-x(i)*10g(x(i)/10g(2);enddisp('此離散信源的平均信息量為');r通常哈夫曼編碼學(xué)的效率是小于1的，但當(dāng)信源為某些特殊情況時(shí)，可以是效率達(dá)到1,當(dāng)然是不可能超過1的。如：'U1U2U3U4U5、P=Q/31/61/151/1511/30,分別調(diào)用huffman和message®數(shù)如下：clearall;p=1/3,1/6,1/15,1/15,11/30%定義概率序列P=0.33330.16670.06670.06670.3667截圖為:匚tdlgfadflQhMwJWndm?匕*口吁汽電電7薜NEJ學(xué)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語(yǔ)畫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總結(jié)通過該課程設(shè)計(jì)，我掌握了編譯程序的原理以及步驟，還有編譯程序工作的基本過程及其各階段的基本任務(wù)，熟悉

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