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

1、吉林建筑大學(xué)電氣與電子信息工程學(xué)院信息理論與編碼課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目： 哈夫曼編碼的分析與實(shí)現(xiàn) 專業(yè)班級： 電子信息工程 101 學(xué)生姓名： 學(xué) 號： 指導(dǎo)教師： 呂卅 王超 設(shè)計(jì)時(shí)間： 2013.11.182013.11.29 教師評語：成績 評閱教師 日期 一、設(shè)計(jì)的作用、目的信息論與編碼是一門理論與實(shí)踐密切結(jié)合的課程,課程設(shè)計(jì)是其實(shí)踐性教學(xué)環(huán)節(jié)之一，同時(shí)也是對課堂所學(xué)理論知識的鞏固和補(bǔ)充。其主要目的是加深對理論知識的理解，掌握查閱有關(guān)資料的技能，提高實(shí)踐技能，培養(yǎng)獨(dú)立分析問題、解決問題及實(shí)際應(yīng)用的能力。通過完成具體編碼算法的程序設(shè)計(jì)和調(diào)試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的

2、基本思想和目的，掌握編碼的基本原理與編碼過程，增強(qiáng)邏輯思維能力，培養(yǎng)和提高自學(xué)能力以及綜合運(yùn)用所學(xué)理論知識去分析解決實(shí)際問題的能力，逐步熟悉開展科學(xué)實(shí)踐的程序和方法二、設(shè)計(jì)任務(wù)及要求通過課程設(shè)計(jì)各環(huán)節(jié)的實(shí)踐，應(yīng)使學(xué)生達(dá)到如下要求：1. 理解無失真信源編碼的理論基礎(chǔ)，掌握無失真信源編碼的基本方法；2. 掌握哈夫曼編碼/費(fèi)諾編碼方法的基本步驟及優(yōu)缺點(diǎn)；3. 深刻理解信道編碼的基本思想與目的，理解線性分組碼的基本原理與編碼過程；4. 能夠使用MATLAB或其他語言進(jìn)行編程，編寫的函數(shù)要有通用性。三、設(shè)計(jì)內(nèi)容一個(gè)有8個(gè)符號的信源X，各個(gè)符號出現(xiàn)的概率為：編碼方法：先將信源符號按其出現(xiàn)的概率大小依次排列

3、，并取概率最小的字母分別配以0和1兩個(gè)碼元（先0后1或者先1后0，以后賦值固定），再將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)制符號的字母重新排隊(duì)。并不斷重復(fù)這一過程，直到最后兩個(gè)符號配以0和1為止。最后從最后一級開始，向前返回得到各個(gè)信源符號所對應(yīng)的碼元序列，即為對應(yīng)的碼字。 哈夫曼編碼方式得到的碼并非唯一的。在對信源縮減時(shí)，兩個(gè)概率最小的符號合并后的概率與其他信源符號的概率相同時(shí)，這兩者在縮減中的排序?qū)?dǎo)致不同碼字，但不同的排序?qū)绊懘a字的長度，一般講合并的概率放在上面，這樣可獲得較小的碼方差。四、設(shè)計(jì)原理4.1哈夫曼編碼步驟（1）將信源消息符號按照其出現(xiàn)的概率大小依次排列為

4、（2）取兩個(gè)概率最小的字母分別配以0和1兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新的概率，與未分配的二進(jìn)制符號的字母重新排隊(duì)。（3）對重新排列后的兩個(gè)最小符號重復(fù)步驟（2）的過程。（4）不斷重復(fù)上述過程，知道最后兩個(gè)符號配以0和1為止。（5）從最后一級開始，向前返回得到的各個(gè)信源符號所對應(yīng)的碼元序列，即為相應(yīng)的碼字。4.2哈夫曼編碼特點(diǎn)哈夫曼編碼是用概率匹配的方法進(jìn)行信源匹配方法進(jìn)行信源。它的特點(diǎn)是：（1）哈夫曼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分應(yīng)用了短碼。（2）縮減信源的最后兩個(gè)碼字總是最后一位不同，從而保證了哈夫曼編碼是即時(shí)碼。（3）哈夫曼編碼所形成的碼字不是

5、唯一的，但編碼效率是唯一的，在對最小的兩個(gè)速率符號賦值時(shí)可以規(guī)定大的為“1”，小得為“0”，如果兩個(gè)符號的出現(xiàn)概率相等時(shí)，排列時(shí)無論哪個(gè)在前都可以，所以哈夫曼所構(gòu)造的碼字不是唯一的，對于同一個(gè)信息源，無論上述的順序如何排列，他的平均碼長是不會改變的，所以編碼效率是唯一的。（4）只有當(dāng)信息源各符號出現(xiàn)的概率很不平均的時(shí)候，哈夫曼編碼的效果才明顯。（5）哈夫曼編碼必須精確的統(tǒng)計(jì)出原始文件中每個(gè)符號出現(xiàn)頻率，如果沒有這些精確的統(tǒng)計(jì)將達(dá)不到預(yù)期效果。哈夫曼編碼通常要經(jīng)過兩遍操作 ，第一遍進(jìn)行統(tǒng)計(jì)，第二遍產(chǎn)生編碼，所以編碼速度相對慢。另外實(shí)現(xiàn)電路復(fù)雜，各種長度的編碼的編譯過程也是比較復(fù)雜的，因此解壓縮的

6、過程也比較慢。（6）哈夫曼編碼只能用整數(shù)來表示單個(gè)符號，而不能用小數(shù)，這很大程度上限制了壓縮效果。哈夫曼所有位都是合在一起的，如果改動(dòng)其中一位就可以使其數(shù)據(jù)變得面目全非。五、設(shè)計(jì)步驟5.1以框圖形式畫出哈夫曼編碼過程（哈夫曼編碼要求構(gòu)建哈夫曼樹）。表1 哈夫曼編碼信源編碼概率編碼過程碼字碼長X10.4 0.4 0.4 0.4 0.4 0.4 0.6 0 1.0 0.18 0.18 0.19 0.23 0.37 0 0.4 1 0.1 0.13 0.18 0.19 0 0.23 1 0.1 0.1 0.13 0 0.18 1 0.09 0.1 0 0.1 1 0.07 0 0.09 1 0.06

7、 10111X20.180013X30.10113X40.100004X50.0701004X60.0601014X70.05000105X80.04000115哈夫曼樹：給定n個(gè)實(shí)數(shù)w1，w2，wn（n2），求一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉數(shù)，使其帶權(quán)路徑長度最小。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度為葉結(jié)點(diǎn)的層數(shù)）。樹的帶權(quán)路徑長度為WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,.n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長度為Li(i=1,2,.n)。可以證明哈夫曼

8、樹的WPL是最小的。（1） 根據(jù)與n個(gè)權(quán)值w1,w2wn對應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成具有n棵二叉樹的森林F=T1,T2Tn,其中第i棵二叉樹Ti(1 i n)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹均為空。（2） 在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)權(quán)值之和。（3）從F中刪除構(gòu)成新樹的那兩棵，同時(shí)把新樹加入F中。（4）重復(fù)第（2）和第（3）步，直到F中只含有一棵為止，此樹便為Huffman樹。圖1哈夫曼樹5.2計(jì)算平均碼長、編碼效率、冗余度。平均碼長為： =0.4×1+0.18×3+0.1×3+0.1

9、×4+0.07×4+0.06×4+0.05×5+0.04×5=2.61（碼元/符號）信源熵為： -(0.4log0.4+0.18log0.18+0.1log0.1+0.1log0.1+0.07+log0.07+0.06log0.06+0.05log0.05+0.04log0.04)=2.55bit/符號信息傳輸速率為： R=0.977bit/碼元編碼效率為： =0.977冗余度為：=1-=1-0.977=0.023六、哈夫曼編碼的實(shí)現(xiàn)6.1軟件介紹 Visual C+ 6.0，簡稱VC或者VC6.0，是微軟推出的一款C+編譯器，將“高級語言”翻

10、譯為“機(jī)器語言（低級語言）”的程序。Visual C+是一個(gè)功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C+1.0后，隨著其新版本的不斷問世，Visual C+已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。Visual C+6.0由Microsoft開發(fā), 它不僅是一個(gè)C+ 編譯器，而且是一個(gè)基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrated development environment，IDE）。Visual C+6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等開發(fā)工具。 這些組件通過

11、一個(gè)名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。Microsoft的主力軟件產(chǎn)品。Visual C+是一個(gè)功能強(qiáng)大的可視化軟件開發(fā)工具。Visual C+6.0以擁有“語法高亮”，自動(dòng)編譯功能以及高級除錯(cuò)功能而著稱。比如，它允許用戶進(jìn)行遠(yuǎn)程調(diào)試，單步執(zhí)行等。還有允許用戶在調(diào)試期間重新編譯被修改的代碼，而不必重新啟動(dòng)正在調(diào)試的程序。其編譯及創(chuàng)建預(yù)編譯頭文件(stdafx.h)、最小重建功能及累加連結(jié)(link)著稱。這些特征明顯縮短程序編輯、編譯及連結(jié)的時(shí)間花費(fèi)，在大型軟件計(jì)劃上尤其顯著。（1）Developer Studio這是一個(gè)集成開發(fā)環(huán)境，我們?nèi)粘９ぷ鞯?9%都是在它

12、上面完成的，再加上它的標(biāo)題赫然寫著“Microsoft Visual C+”，所以很多人理所當(dāng)然的認(rèn)為，那就是Visual C+了。其實(shí)不然，雖然Developer Studio提供了一個(gè)很好的編輯器和很多Wizard，但實(shí)際上它沒有任何編譯和鏈接程序的功能，真正完成這些工作的幕后英雄后面會介紹。我們也知道，Developer Studio并不是專門用于VC的，它也同樣用于VB，VJ，VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio當(dāng)成Visual C+， 它充其量只是Visual C+的一個(gè)殼子而已。這一點(diǎn)請切記！ （2）MFC從理論上來講，M

13、FC也不是專用于Visual C+，Borland C+，C+Builder和Symantec C+同樣可以處理MFC。同時(shí)，用Visual C+編寫代碼也并不意味著一定要用MFC，只要愿意，用Visual C+來編寫SDK程序，或者使用STL，ATL，一樣沒有限制。不過，Visual C+本來就是為MFC打造的，Visual C+中的許多特征和語言擴(kuò)展也是為MFC而設(shè)計(jì)的，所以用Visual C+而不用MFC就等于拋棄了Visual C+中很大的一部分功能。但是，Visual C+也不等于MFC。 （3）Platform SDK這才是Visual C+和整個(gè)Visual Studio的精華和

14、靈魂，雖然我們很少能直接接觸到它。大致說來，Platform SDK是以Microsoft C/C+編譯器為核心（不是Visual C+，看清楚了），配合MASM，輔以其他一些工具和文檔資料。上面說到Developer Studio沒有編譯程序的功能，那么這項(xiàng)工作是由誰來完成的呢？是CL，是NMAKE，和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio的基石。6.2 編程/*哈夫曼編碼*#include <iostream.h>#include <math.h>#include <string.h>#include <st

15、dio.h>#include <stdlib.h>#include <vector>using namespace std;struct Huffman_InformationSource char InformationSign10； double Probability； char Code10； int CodeLength;； ;struct HuffNode char InformationSign10；double Probability；HuffNode *LeftSubtree,*middleSubtree,*RightSubtree,*Next；

16、char Code10；int CodeLength；class CHuffman_2 public:CHuffman_2() ISNumber=0；AvageCodeLength=0.0；InformationRate=0.0；CodeEfficiency=0.0； Redundancy=0.0； CHuffman_2()DestroyBTree(HuffTree)；void Huffman_Input()； void Huffman_Sort()； void Huffman_Tree()； void Huffman_Coding()； void Huffman_CodeAnalyzing(

17、)； void Huffman_Display()； void DestroyBTree(HuffNode *TreePointer)； private:vector<Huffman_InformationSource>ISarray；int ISNumber；double AvageCodeLength；double InformationRate；double CodeEfficiency；HuffNode * HuffTree；private：void Huffman_Code(HuffNode *TreePointer);；/輸入信源信息void CHuffman_2:Hu

18、ffman_Input()Huffman_InformationSource temp1="x1",0.40,"",0;ISarray.push_back(temp1);Huffman_InformationSource temp2="x2",0.18,"",0；ISarray.push_back(temp2);Huffman_InformationSource temp3="x3",0.10,"",0;ISarray.push_back(temp3);Huffman_Inf

19、ormationSource temp4="x4",0.10,"",0;ISarray.push_back(temp4);Huffman_InformationSource temp5="x5",0.07,"",0;ISarray.push_back(temp5);Huffman_InformationSource temp6="x6",0.06,"",0;ISarray.push_back(temp6);Huffman_InformationSource temp7=&qu

20、ot;x7",0.05,"",0;ISarray.push_back(temp7);Huffman_InformationSource temp8="x8",0.04,"",0;ISarray.push_back(temp8);ISNumber=ISarray.size();/按概率“從大到小”排序void CHuffman_2:Huffman_Sort()Huffman_InformationSource temp;int I,j;for(i=0;i<ISNumber-1;i+)for(j=i+1;j<ISNu

21、mber;j+)if(ISarrayi.Probability<ISarrayj.Probability)temp=ISarrayi；ISarrayi=ISarrayj;ISarrayj=temp;void CHuffman_2:Huffman_Tree()int I;HuffNode *ptr1,*ptr2,*ptr3,*ptr4,*temp1,*temp2;ptr1=new HuffNode;strcpy(ptr1->InformationSign,ISarray0.InformationSign);ptr1->Probability=ISarray0.Probabili

22、ty;strcpy(ptr1->Code,ISarray0.Code);ptr1->LeftSubtree=NULL;ptr1->middleSubtree =NULL;ptr1->RightSubtree=NULL;ptr1->Next=NULL; HuffTree=ptr1; for(i=1;i<ISNumber;i+)ptr2=new HuffNode;strcpy(ptr2->InformationSign,ISarrayi.InformationSign);ptr2->Probability=ISarrayi.Probability;s

23、trcpy(ptr2->Code,ISarrayi.Code); ptr2->LeftSubtree=NULL;ptr2->middleSubtree =NULL;ptr2->RightSubtree=NULL;ptr2->Next=ptr1;ptr1=ptr2;HuffTree=ptr1; int k; int s; k=ceil(double)(ISNumber-3)/(3-1); s=3+k*(3-1)-ISNumber;if(s=1) ptr2=ptr1->Next;ptr4=new HuffNode;strcpy(ptr4->Informat

24、ionSign,"*");ptr4->Probability=ptr1->Probability+ptr2->Probability; strcpy(ptr4->Code,""); ptr4->LeftSubtree =NULL;ptr4->middleSubtree=ptr1;ptr4->RightSubtree=ptr2;HuffTree=ptr2->Next; temp1=HuffTree;while(temp1&&(ptr4->Probability>temp1->

25、Probability)temp2=temp1;temp1=temp1->Next;ptr4->Next=temp1; if(temp1=HuffTree)HuffTree=ptr4;else temp2->Next=ptr4; ptr1=HuffTree;while(ptr1->Next)/合并概率最小的結(jié)點(diǎn)ptr2=ptr1->Next;ptr3=ptr2->Next;ptr4=new HuffNode;strcpy(ptr4->InformationSign,"*");ptr4->Probability=ptr1->

26、;Probability+ptr2->Probability+ptr3->Probability; strcpy(ptr4->Code,""); ptr4->LeftSubtree=ptr1;ptr4->middleSubtree=ptr2;ptr4->RightSubtree=ptr3;HuffTree=ptr3->Next;temp1=HuffTree;while(temp1&&(ptr4->Probability>temp1->Probability)temp2=temp1;temp1=tem

27、p1->Next;ptr4->Next=temp1; if(temp1=HuffTree)HuffTree=ptr4;else temp2->Next=ptr4; ptr1=HuffTree;/釋放：ptr1=NULL;ptr2=NULL;ptr3=NULL;ptr4=NULL;temp1=NULL;temp2=NULL;strcpy(HuffTree->Code,"");HuffTree->CodeLength=0;/生成哈夫曼碼void CHuffman_2:Huffman_Code(HuffNode *TreePointer)if (Tr

28、eePointer = NULL)return;char tempstr10=""if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtree&&!TreePointer->RightSubtree)for(int i=0;i<ISNumber;i+)if(strcmp(ISarrayi.InformationSign,TreePointer->InformationSign)=0)strcpy(ISarrayi.Code,TreePointer->Co

29、de);ISarrayi.CodeLength=TreePointer->CodeLength;return;return;if(TreePointer->LeftSubtree)strcpy(tempstr,TreePointer->Code);strcat(tempstr,"2");strcpy(TreePointer->LeftSubtree->Code,tempstr);TreePointer->LeftSubtree->CodeLength=TreePointer->CodeLength+1;Huffman_Code

30、(TreePointer->LeftSubtree);if(TreePointer->middleSubtree)strcpy(tempstr,TreePointer->Code);strcat(tempstr,"1");strcpy(TreePointer->middleSubtree->Code,tempstr);TreePointer->middleSubtree->CodeLength=TreePointer->CodeLength+1;Huffman_Code(TreePointer->middleSubtre

31、e);if(TreePointer->RightSubtree)strcpy(tempstr,TreePointer->Code);strcat(tempstr,"0");strcpy(TreePointer->RightSubtree->Code,tempstr);TreePointer->RightSubtree->CodeLength=TreePointer->CodeLength+1;Huffman_Code(TreePointer->RightSubtree);void CHuffman_2:Huffman_Codi

32、ng()Huffman_Code(HuffTree);/編碼結(jié)果void CHuffman_2:Huffman_CodeAnalyzing()for(int i=0;i<ISNumber;i+)AvageCodeLength+=ISarrayi.Probability*ISarrayi.CodeLength;int L=1; int m=2; /InformationRate=AvageCodeLength/L*(log(m)/log(2);double Hx=0;for(int j=0;j<ISNumber;j+) Hx+=-ISarrayj.Probability*log(IS

33、arrayj.Probability)/log(2);CodeEfficiency=Hx/InformationRate;Redundancy=1- CodeEfficiency;void CHuffman_2:Huffman_Display()cout<<"碼字："<<endl;for(int i=0;i<ISNumber;i+)cout<<"'"<<ISarrayi.InformationSign<<"'"<<": "

34、<<ISarrayi.Code<<endl;cout<<endl;cout<<"平均碼長："<<AvageCodeLength<<endl<<endl;cout<<"編碼效率："<<CodeEfficiency<<endl<<endl;cout<<"冗余度："<< Redundancy <<endl<<endl;void CHuffman_2:Destroy

35、BTree(HuffNode *TreePointer)if (TreePointer!= NULL)DestroyBTree(TreePointer->LeftSubtree);DestroyBTree(TreePointer->middleSubtree);DestroyBTree(TreePointer->RightSubtree);delete TreePointer;TreePointer = NULL;void main()CHuffman_3 YYY;YYY.Huffman_Input();YYY.Huffman_Sort();YYY.Huffman_Tree(

36、);YYY.Huffman_Coding();YYY.Huffman_CodeAnalyzing();YYY.Huffman_Display();6.3 運(yùn)行結(jié)果及分析圖2 運(yùn)行結(jié)果運(yùn)行結(jié)果分析：從運(yùn)行結(jié)果上可以看出，該結(jié)果與理論計(jì)算一致，并且可以看出哈夫曼編碼的特點(diǎn)：（1）哈夫曼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分應(yīng)用了短碼。（2）縮減信源的最后兩個(gè)碼字總是最后一位不同，從而保證了哈夫曼編碼是即時(shí)碼。（3）每次縮減信源的最長兩個(gè)碼字有相同的碼長。這三個(gè)特點(diǎn)保證了所得的哈夫曼碼一定是最佳碼。因此哈夫曼是一種應(yīng)用廣泛而有效的數(shù)據(jù)壓縮技術(shù)。利用哈夫曼編碼進(jìn)行通信可以

37、大大提高信道利用率，加快信息傳輸速度，降低傳輸成本。數(shù)據(jù)壓縮的過程稱為編碼，解壓的過程稱為譯碼。進(jìn)行信息傳遞時(shí)，發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)（明文）預(yù)先編碼，而接受端將傳來的數(shù)據(jù)（密文）進(jìn)行譯碼。要求數(shù)據(jù)這樣一個(gè)簡單的哈夫曼編碼譯碼器。在進(jìn)行哈夫曼編碼時(shí)，為了得到碼方差最小的碼，應(yīng)使合并的信源符號位于縮減信源序列盡可能高的。七、體會及建議在這次課程設(shè)計(jì)中，通過對程序的編寫，調(diào)試和運(yùn)行，使我更好的掌握了哈夫曼樹等數(shù)據(jù)結(jié)構(gòu)方面的基本知識和各類基本程序問題的解決方法，熟悉了各種調(diào)用的數(shù)據(jù)類型，在調(diào)試和運(yùn)行過程中，加深我對程序運(yùn)行的環(huán)境了解和熟悉的程度，同時(shí)也提高了我對程序調(diào)試分析的能力和對錯(cuò)誤糾

38、正的能力。這次信息論與編碼的程序設(shè)計(jì)，對于我來說是一個(gè)挑戰(zhàn)。我對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)在程序的設(shè)計(jì)中也有所體現(xiàn)。課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識，發(fā)現(xiàn)問題、提出問題、分析問題和解決問題的過程，鍛煉學(xué)生的邏輯思維能力和實(shí)踐能力，是對學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程。在整個(gè)課程程序中，我們充分應(yīng)用和調(diào)用各個(gè)程序模塊，從而部分實(shí)現(xiàn)了此次程序設(shè)計(jì)的所應(yīng)該有的功能。就是我在課程設(shè)計(jì)是比較成功的方面，而在這個(gè)過程中，讓我感覺收獲最大的就是我們都能利用這次課程設(shè)計(jì)學(xué)到很多我們在課本上沒有的知識，充分的發(fā)揮了我們的主動(dòng)性，使我們學(xué)會了自主學(xué)習(xí)，和獨(dú)立解決問題的能力。很多程序在結(jié)構(gòu)上是獨(dú)立的，但是本此設(shè)計(jì)的程序功能不是零散的，它有一個(gè)連接是的程序是一個(gè)