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

1、<p>　　信息理論與編碼課程設(shè)計(jì)報(bào)告</p><p>　　設(shè)計(jì)題目： 哈夫曼編碼的分析與實(shí)現(xiàn) </p><p>　　專業(yè)班級： 電子信息工程 101 </p><p>　　學(xué)生姓名： </p><p>　　學(xué) 號：

2、 </p><p>　　指導(dǎo)教師： </p><p>　　設(shè)計(jì)時(shí)間： 2013.11.18－2013.11.29 </p><p>　　一、設(shè)計(jì)的作用、目的</p><p>　　《信息論與編碼》是一門理論與實(shí)踐密切結(jié)合的課程,課程設(shè)計(jì)是其實(shí)踐性教學(xué)環(huán)節(jié)之一，同時(shí)也是對課堂所學(xué)理論知識(shí)

3、的鞏固和補(bǔ)充。其主要目的是加深對理論知識(shí)的理解，掌握查閱有關(guān)資料的技能，提高實(shí)踐技能，培養(yǎng)獨(dú)立分析問題、解決問題及實(shí)際應(yīng)用的能力。</p><p>　　通過完成具體編碼算法的程序設(shè)計(jì)和調(diào)試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過程，增強(qiáng)邏輯思維能力，培養(yǎng)和提高自學(xué)能力以及綜合運(yùn)用所學(xué)理論知識(shí)去分析解決實(shí)際問題的能力，逐步熟悉開展科學(xué)實(shí)踐的程序和方法</p&

4、gt;<p><b>　　二、設(shè)計(jì)任務(wù)及要求</b></p><p>　　通過課程設(shè)計(jì)各環(huán)節(jié)的實(shí)踐，應(yīng)使學(xué)生達(dá)到如下要求：</p><p>　　1. 理解無失真信源編碼的理論基礎(chǔ)，掌握無失真信源編碼的基本方法；</p><p>　　2. 掌握哈夫曼編碼/費(fèi)諾編碼方法的基本步驟及優(yōu)缺點(diǎn)；</p><p>　　

5、3. 深刻理解信道編碼的基本思想與目的，理解線性分組碼的基本原理與編碼過程；</p><p>　　4. 能夠使用MATLAB或其他語言進(jìn)行編程，編寫的函數(shù)要有通用性。</p><p><b>　　三、設(shè)計(jì)內(nèi)容</b></p><p>　　一個(gè)有8個(gè)符號的信源X，各個(gè)符號出現(xiàn)的概率為：</p><p>　　編碼方法：先將信

6、源符號按其出現(xiàn)的概率大小依次排列，并取概率最小的字母分別配以0和1兩個(gè)碼元（先0后1或者先1后0，以后賦值固定），再將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)制符號的字母重新排隊(duì)。并不斷重復(fù)這一過程，直到最后兩個(gè)符號配以0和1為止。最后從最后一級開始，向前返回得到各個(gè)信源符號所對應(yīng)的碼元序列，即為對應(yīng)的碼字。</p><p>　　哈夫曼編碼方式得到的碼并非唯一的。在對信源縮減時(shí)，兩個(gè)概率最小的符號合并后

7、的概率與其他信源符號的概率相同時(shí)，這兩者在縮減中的排序?qū)?huì)導(dǎo)致不同碼字，但不同的排序?qū)?huì)影響碼字的長度，一般講合并的概率放在上面，這樣可獲得較小的碼方差。</p><p><b>　　四、設(shè)計(jì)原理</b></p><p>　　4.1哈夫曼編碼步驟</p><p>　?。?）將信源消息符號按照其出現(xiàn)的概率大小依次排列為</p>&l

8、t;p>　?。?）取兩個(gè)概率最小的字母分別配以0和1兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新的概率，與未分配的二進(jìn)制符號的字母重新排隊(duì)。</p><p>　?。?）對重新排列后的兩個(gè)最小符號重復(fù)步驟（2）的過程。</p><p>　?。?）不斷重復(fù)上述過程，知道最后兩個(gè)符號配以0和1為止。</p><p>　?。?）從最后一級開始，向前返回得到的各個(gè)信源符號所對

9、應(yīng)的碼元序列，即為相應(yīng)的碼字。</p><p>　　4.2哈夫曼編碼特點(diǎn)</p><p>　　哈夫曼編碼是用概率匹配的方法進(jìn)行信源匹配方法進(jìn)行信源。它的特點(diǎn)是：</p><p>　　（1）哈夫曼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分應(yīng)用了短碼。</p><p>　?。?）縮減信源的最后兩個(gè)碼字總是最后一位不同，從

10、而保證了哈夫曼編碼是即時(shí)碼。</p><p>　?。?）哈夫曼編碼所形成的碼字不是唯一的，但編碼效率是唯一的，在對最小的兩個(gè)速率符號賦值時(shí)可以規(guī)定大的為“1”，小得為“0”，如果兩個(gè)符號的出現(xiàn)概率相等時(shí)，排列時(shí)無論哪個(gè)在前都可以，所以哈夫曼所構(gòu)造的碼字不是唯一的，對于同一個(gè)信息源，無論上述的順序如何排列，他的平均碼長是不會(huì)改變的，所以編碼效率是唯一的。</p><p>　?。?）只有當(dāng)信息

11、源各符號出現(xiàn)的概率很不平均的時(shí)候，哈夫曼編碼的效果才明顯。</p><p>　?。?）哈夫曼編碼必須精確的統(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ù)雜的，因此解壓縮的過程也比較慢。</p><p>　?。?）哈夫曼編碼只能用

12、整數(shù)來表示單個(gè)符號，而不能用小數(shù)，這很大程度上限制了壓縮效果。哈夫曼所有位都是合在一起的，如果改動(dòng)其中一位就可以使其數(shù)據(jù)變得面目全非。</p><p><b>　　五、設(shè)計(jì)步驟</b></p><p>　　5.1以框圖形式畫出哈夫曼編碼過程（哈夫曼編碼要求構(gòu)建哈夫曼樹）。</p><p><b>　　表1 哈夫曼編碼</b>

13、;</p><p><b>　　哈夫曼樹：</b></p><p>　　給定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+

14、...+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)?？梢宰C明哈夫曼樹的WPL是最小的。</p><p>　?。?） 根據(jù)與n個(gè)權(quán)值{w1,w2…wn}對應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成具有n棵二叉樹的森林F={T1,T2…Tn},其中第i棵二叉樹Ti(1 i n)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹均為空。</p>

15、<p>　?。?） 在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)權(quán)值之和。</p><p>　?。?）從F中刪除構(gòu)成新樹的那兩棵，同時(shí)把新樹加入F中。</p><p>　?。?）重復(fù)第（2）和第（3）步，直到F中只含有一棵為止，此樹便為Huffman樹。</p><p><b>　　

16、圖1哈夫曼樹</b></p><p>　　5.2計(jì)算平均碼長、編碼效率、冗余度。</p><p><b>　　平均碼長為：</b></p><p>　　==0.4×1+0.18×3+0.1×3+0.1×4+0.07×4+0.06×4+</p><p>

17、;　　0.05×5+0.04×5=2.61（碼元/符號）</p><p><b>　　信源熵為：</b></p><p>　　-(0.4log0.4+0.18log0.18+0.1log0.1+</p><p>　　0.1log0.1+0.07+log0.07+0.06log0.06+0.05log0.05+0.04log0

18、.04)</p><p>　　=2.55bit/符號</p><p><b>　　信息傳輸速率為：</b></p><p>　　R===0.977bit/碼元</p><p><b>　　編碼效率為：</b></p><p><b>　　===0.977</b

19、></p><p><b>　　冗余度為：</b></p><p>　　=1-=1-0.977=0.023</p><p>　　六、哈夫曼編碼的實(shí)現(xiàn)</p><p><b>　　6.1軟件介紹 </b></p><p>　　Visual C++ 6.0，簡稱VC或者VC

20、6.0，是微軟推出的一款C++編譯器，將“高級語言”翻譯為“機(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)境（i

21、ntegrated development environment，IDE）。Visual C++6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等開發(fā)工具。 這些組件通過一個(gè)名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。Microsoft的主力軟件產(chǎn)品。Visual C++是一個(gè)功能強(qiáng)大的可視化軟件開發(fā)工具。</p><p>　　Visua

22、l 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ì)劃上尤其顯著。</p><p>　?。?）Developer Studio這是一個(gè)

23、集成開發(fā)環(huán)境，我們?nèi)粘９ぷ鞯?9%都是在它上面完成的，再加上它的標(biāo)題赫然寫著“Microsoft Visual C++”，所以很多人理所當(dāng)然的認(rèn)為，那就是Visual C++了。其實(shí)不然，雖然Developer Studio提供了一個(gè)很好的編輯器和很多Wizard，但實(shí)際上它沒有任何編譯和鏈接程序的功能，真正完成這些工作的幕后英雄后面會(huì)介紹。我們也知道，Developer Studio并不是專門用于VC的，它也同樣用于VB，VJ，VID

24、等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio當(dāng)成Visual C++， 它充其量只是Visual C++的一個(gè)殼子而已。這一點(diǎn)請切記！ </p><p><b>　?。?）MFC</b></p><p>　　從理論上來講，MFC也不是專用于Visual C++，Borland C++，C++Builder和Symantec

25、 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。 </p

26、><p>　?。?）Platform SDK</p><p>　　這才是Visual C++和整個(gè)Visual Studio的精華和靈魂，雖然我們很少能直接接觸到它。大致說來，Platform SDK是以Microsoft C/C++編譯器為核心（不是Visual C++，看清楚了），配合MASM，輔以其他一些工具和文檔資料。上面說到Developer Studio沒有編譯程序的功能，那么這項(xiàng)

27、工作是由誰來完成的呢？是CL，是NMAKE，和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio的基石。</p><p><b>　　6.2 編程</b></p><p>　　//**哈夫曼編碼**</p><p>　　#include <iostream.h></p><p>　

28、　#include <math.h></p><p>　　#include <string.h></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <vector><

29、/p><p>　　using namespace std;</p><p>　　struct Huffman_InformationSource </p><p><b>　　{</b></p><p>　　char InformationSign[10]； </p><p>　　doubl

30、e Probability； </p><p>　　char Code[10]； </p><p>　　int CodeLength;； </p><p><b>　　};</b></p><p>　　struct HuffNode </p>&

31、lt;p><b>　　{</b></p><p>　　char InformationSign[10]；</p><p>　　double Probability；</p><p>　　HuffNode *LeftSubtree,*middleSubtree,*RightSubtree,*Next；</p><p>

32、;　　char Code[10]；</p><p>　　int CodeLength；</p><p><b>　　}；</b></p><p>　　class CHuffman_2 </p><p><b>　　{</b></p><p><b>　

33、　public:</b></p><p>　　CHuffman_2() </p><p><b>　　{</b></p><p>　　ISNumber=0；</p><p>　　AvageCodeLength=0.0；</p><p>　　InformationRate=0.0

34、；</p><p>　　CodeEfficiency=0.0；</p><p>　　Redundancy=0.0；</p><p><b>　　}</b></p><p>　　CHuffman_2()</p><p><b>　　{</b></p><p&

35、gt;　　DestroyBTree(HuffTree)；</p><p><b>　　}</b></p><p>　　void Huffman_Input()； </p><p>　　void Huffman_Sort()； </p><p>　　void Huffman_Tree(

36、)； </p><p>　　void Huffman_Coding()； </p><p>　　void Huffman_CodeAnalyzing()； </p><p>　　void Huffman_Display()； </p><p>　　void DestroyBTree(

37、HuffNode *TreePointer)； </p><p><b>　　private:</b></p><p>　　vector<Huffman_InformationSource>ISarray；</p><p>　　int ISNumber；</p><p>　　double AvageCo

38、deLength；</p><p>　　double InformationRate；</p><p>　　double CodeEfficiency；</p><p>　　HuffNode * HuffTree；</p><p><b>　　private：</b></p><p>　　void

39、 Huffman_Code(HuffNode *TreePointer);</p><p><b>　　}；</b></p><p><b>　　//輸入信源信息</b></p><p>　　void CHuffman_2::Huffman_Input()</p><p><b>　　{&

40、lt;/b></p><p>　　Huffman_InformationSource temp1={"x1",0.40,"",0};</p><p>　　ISarray.push_back(temp1);</p><p>　　Huffman_InformationSource temp2={"x2",

41、0.18,"",0}；</p><p>　　ISarray.push_back(temp2);</p><p>　　Huffman_InformationSource temp3={"x3",0.10,"",0};</p><p>　　ISarray.push_back(temp3);</p>

42、<p>　　Huffman_InformationSource temp4={"x4",0.10,"",0};</p><p>　　ISarray.push_back(temp4);</p><p>　　Huffman_InformationSource temp5={"x5",0.07,"",0}

43、;</p><p>　　ISarray.push_back(temp5);</p><p>　　Huffman_InformationSource temp6={"x6",0.06,"",0};</p><p>　　ISarray.push_back(temp6);</p><p>　　Huffman_

44、InformationSource temp7={"x7",0.05,"",0};</p><p>　　ISarray.push_back(temp7);</p><p>　　Huffman_InformationSource temp8={"x8",0.04,"",0};</p><p&g

45、t;　　ISarray.push_back(temp8);</p><p>　　ISNumber=ISarray.size();</p><p><b>　　}</b></p><p>　　//按概率“從大到小”排序</p><p>　　void CHuffman_2::Huffman_Sort()</p>

46、<p><b>　　{</b></p><p>　　Huffman_InformationSource temp;</p><p><b>　　int I,j;</b></p><p>　　for(i=0;i<ISNumber-1;i++)</p><p>　　for(j=i+1;

47、j<ISNumber;j++)</p><p>　　if(ISarray[i].Probability<ISarray[j].Probability)</p><p><b>　　{</b></p><p>　　temp=ISarray[i]；</p><p>　　ISarray[i]=ISarray[j];

48、</p><p>　　ISarray[j]=temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void CHuffman_2::Huffman_Tree()</p><p><b>　　{</b&g

49、t;</p><p><b>　　int I;</b></p><p>　　HuffNode *ptr1,*ptr2,*ptr3,*ptr4,*temp1,*temp2;</p><p>　　ptr1=new HuffNode;</p><p>　　strcpy(ptr1->InformationSign,ISar

50、ray[0].InformationSign);</p><p>　　ptr1->Probability=ISarray[0].Probability;</p><p>　　strcpy(ptr1->Code,ISarray[0].Code);</p><p>　　ptr1->LeftSubtree=NULL;</p><p&g

51、t;　　ptr1->middleSubtree =NULL;</p><p>　　ptr1->RightSubtree=NULL;</p><p>　　ptr1->Next=NULL; </p><p>　　HuffTree=ptr1; </p><p>　　for(i=1;i<ISNumb

52、er;i++)</p><p><b>　　{</b></p><p>　　ptr2=new HuffNode;</p><p>　　strcpy(ptr2->InformationSign,ISarray[i].InformationSign);</p><p>　　ptr2->Probabi

53、lity=ISarray[i].Probability;</p><p>　　strcpy(ptr2->Code,ISarray[i].Code); </p><p>　　ptr2->LeftSubtree=NULL;</p><p>　　ptr2->middleSubtree =NULL;</p><p>　　ptr2-&

54、gt;RightSubtree=NULL;</p><p>　　ptr2->Next=ptr1;</p><p>　　ptr1=ptr2;</p><p><b>　　}</b></p><p>　　HuffTree=ptr1; </p><p>　　in

55、t k; </p><p>　　int s; </p><p>　　k=ceil((double)(ISNumber-3)/(3-1)); </p><p>　　s=3+k*(3-1)-ISNumber;</p><p>　　if(s==1)

56、 </p><p><b>　　{</b></p><p>　　ptr2=ptr1->Next;</p><p>　　ptr4=new HuffNode;</p><p>　　strcpy(ptr4->InformationSign,"*");</p

57、><p>　　ptr4->Probability=ptr1->Probability+ptr2->Probability; </p><p>　　strcpy(ptr4->Code,""); </p><p>　　ptr4->LeftSubtree =NULL;</p><p>　　ptr4-&

58、gt;middleSubtree=ptr1;</p><p>　　ptr4->RightSubtree=ptr2;</p><p>　　HuffTree=ptr2->Next; </p><p>　　temp1=HuffTree;</p><p>　　while(temp1&&(p

59、tr4->Probability>temp1->Probability))</p><p><b>　　{</b></p><p>　　temp2=temp1;</p><p>　　temp1=temp1->Next;</p><p><b>　　}</b></p>

60、;<p>　　ptr4->Next=temp1; </p><p>　　if(temp1==HuffTree)</p><p>　　HuffTree=ptr4;</p><p><b>　　else </b></p><p>　　temp2->Next=ptr4;

61、 </p><p>　　ptr1=HuffTree;</p><p><b>　　}</b></p><p>　　while(ptr1->Next)</p><p><b>　　{</b></p><p>　　//合并概率最小的結(jié)點(diǎn)</p&

62、gt;<p>　　ptr2=ptr1->Next;</p><p>　　ptr3=ptr2->Next;</p><p>　　ptr4=new HuffNode;</p><p>　　strcpy(ptr4->InformationSign,"*");</p><p>　　ptr4-&g

63、t;Probability=ptr1->Probability+ptr2->Probability</p><p>　　+ptr3->Probability; </p><p>　　strcpy(ptr4->Code,""); </p><p>　　ptr4->LeftSubtree=ptr

64、1;</p><p>　　ptr4->middleSubtree=ptr2;</p><p>　　ptr4->RightSubtree=ptr3;</p><p>　　HuffTree=ptr3->Next;</p><p>　　temp1=HuffTree;</p><p>　　while(tem

65、p1&&(ptr4->Probability>temp1->Probability))</p><p><b>　　{</b></p><p>　　temp2=temp1;</p><p>　　temp1=temp1->Next;</p><p><b>　　}</

66、b></p><p>　　ptr4->Next=temp1; </p><p>　　if(temp1==HuffTree)</p><p>　　HuffTree=ptr4;</p><p><b>　　else </b></p><p>　　temp2->N

67、ext=ptr4; </p><p>　　ptr1=HuffTree;</p><p><b>　　}</b></p><p><b>　　//釋放：</b></p><p>　　ptr1=NULL;</p><p>　　ptr2=NULL;</

68、p><p>　　ptr3=NULL;</p><p>　　ptr4=NULL;</p><p>　　temp1=NULL;</p><p>　　temp2=NULL;</p><p>　　strcpy(HuffTree->Code,"");</p><p>　　HuffTr

69、ee->CodeLength=0;</p><p><b>　　}</b></p><p><b>　　//生成哈夫曼碼</b></p><p>　　void CHuffman_2::Huffman_Code(HuffNode *TreePointer)</p><p><b>　　

70、{</b></p><p>　　if (TreePointer == NULL)</p><p><b>　　return;</b></p><p>　　char tempstr[10]="";</p><p>　　if(!TreePointer->LeftSubtree&&

71、amp;!TreePointer->middleSubtree</p><p>　　&&!TreePointer->RightSubtree)</p><p><b>　　{</b></p><p>　　for(int i=0;i<ISNumber;i++)</p><p>　　if(s

72、trcmp(ISarray[i].InformationSign,TreePointer->InformationSign)==0)</p><p><b>　　{</b></p><p>　　strcpy(ISarray[i].Code,TreePointer->Code);</p><p>　　ISarray[i].CodeLe

73、ngth=TreePointer->CodeLength;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　return;</b></p><p><b>　　}</b><

74、/p><p>　　if(TreePointer->LeftSubtree)</p><p><b>　　{</b></p><p>　　strcpy(tempstr,TreePointer->Code);</p><p>　　strcat(tempstr,"2");</p>&l

75、t;p>　　strcpy(TreePointer->LeftSubtree->Code,tempstr);</p><p>　　TreePointer->LeftSubtree->CodeLength=TreePointer->CodeLength+1;</p><p>　　Huffman_Code(TreePointer->LeftSubtree

76、);</p><p><b>　　}</b></p><p>　　if(TreePointer->middleSubtree)</p><p><b>　　{</b></p><p>　　strcpy(tempstr,TreePointer->Code);</p><

77、p>　　strcat(tempstr,"1");</p><p>　　strcpy(TreePointer->middleSubtree->Code,tempstr);</p><p>　　TreePointer->middleSubtree->CodeLength=TreePointer->CodeLength+1;</p&g

78、t;<p>　　Huffman_Code(TreePointer->middleSubtree);</p><p><b>　　}</b></p><p>　　if(TreePointer->RightSubtree)</p><p><b>　　{</b></p><p>

79、;　　strcpy(tempstr,TreePointer->Code);</p><p>　　strcat(tempstr,"0");</p><p>　　strcpy(TreePointer->RightSubtree->Code,tempstr);</p><p>　　TreePointer->RightSubtre

80、e->CodeLength=TreePointer->CodeLength+1;</p><p>　　Huffman_Code(TreePointer->RightSubtree);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　

81、　void CHuffman_2::Huffman_Coding()</p><p><b>　　{</b></p><p>　　Huffman_Code(HuffTree);</p><p><b>　　}</b></p><p><b>　　//編碼結(jié)果</b></p

82、><p>　　void CHuffman_2::Huffman_CodeAnalyzing()</p><p><b>　　{</b></p><p>　　for(int i=0;i<ISNumber;i++)</p><p>　　AvageCodeLength+=ISarray[i].Probability*ISar

83、ray[i].CodeLength;</p><p>　　int L=1; </p><p>　　int m=2; /</p><p>　　InformationRate=AvageCodeLength/L*(log(m)/log(2));</p><p>　　double Hx

84、=0;</p><p>　　for(int j=0;j<ISNumber;j++) </p><p>　　Hx+=-ISarray[j].Probability*log(ISarray[j].Probability)/log(2);</p><p>　　CodeEfficiency=Hx/InformationRate;</p>

85、<p>　　Redundancy=1- CodeEfficiency;</p><p><b>　　}</b></p><p>　　void CHuffman_2::Huffman_Display()</p><p><b>　　{</b></p><p>　　cout<<&q

86、uot;碼字："<<endl;</p><p>　　for(int i=0;i<ISNumber;i++)</p><p><b>　　{</b></p><p>　　cout<<"\'"<<ISarray[i].InformationSign<<&qu

87、ot;\'"<<": "<<ISarray[i].Code<<endl;</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"平均碼長："<<Ava

88、geCodeLength<<endl<<endl;</p><p>　　cout<<"編碼效率："<<CodeEfficiency<<endl<<endl;</p><p>　　cout<<"冗余度："<< Redundancy <<endl&

89、lt;<endl;</p><p><b>　　}</b></p><p>　　void CHuffman_2::DestroyBTree(HuffNode *TreePointer)</p><p><b>　　{</b></p><p>　　if (TreePointer!= NULL)&

90、lt;/p><p><b>　　{</b></p><p>　　DestroyBTree(TreePointer->LeftSubtree);</p><p>　　DestroyBTree(TreePointer->middleSubtree);</p><p>　　DestroyBTree(TreePointe

91、r->RightSubtree);</p><p>　　delete TreePointer;</p><p>　　TreePointer = NULL;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void ma

92、in()</p><p><b>　　{</b></p><p>　　CHuffman_3 YYY;</p><p>　　YYY.Huffman_Input();</p><p>　　YYY.Huffman_Sort();</p><p>　　YYY.Huffman_Tree();</p&g

93、t;<p>　　YYY.Huffman_Coding();</p><p>　　YYY.Huffman_CodeAnalyzing();</p><p>　　YYY.Huffman_Display();</p><p><b>　　}</b></p><p>　　6.3 運(yùn)行結(jié)果及分析</p>

94、<p><b>　　圖2 運(yùn)行結(jié)果</b></p><p><b>　　運(yùn)行結(jié)果分析：</b></p><p>　　從運(yùn)行結(jié)果上可以看出，該結(jié)果與理論計(jì)算一致，并且可以看出哈夫曼編碼的特點(diǎn)：</p><p>　　（1）哈夫曼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分應(yīng)用了短碼。<

95、/p><p>　?。?）縮減信源的最后兩個(gè)碼字總是最后一位不同，從而保證了哈夫曼編碼是即時(shí)碼。</p><p>　?。?）每次縮減信源的最長兩個(gè)碼字有相同的碼長。</p><p>　　這三個(gè)特點(diǎn)保證了所得的哈夫曼碼一定是最佳碼。因此哈夫曼是一種應(yīng)用廣泛而有效的數(shù)據(jù)壓縮技術(shù)。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，加快信息傳輸速度，降低傳輸成本。數(shù)據(jù)壓縮的過程稱為編

96、碼，解壓的過程稱為譯碼。進(jìn)行信息傳遞時(shí)，發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)（明文）預(yù)先編碼，而接受端將傳來的數(shù)據(jù)（密文）進(jìn)行譯碼。要求數(shù)據(jù)這樣一個(gè)簡單的哈夫曼編碼譯碼器。</p><p>　　在進(jìn)行哈夫曼編碼時(shí)，為了得到碼方差最小的碼，應(yīng)使合并的信源符號位于縮減信源序列盡可能高的。</p><p><b>　　七、體會(huì)及建議</b></p><p&g

97、t;　　在這次課程設(shè)計(jì)中，通過對程序的編寫，調(diào)試和運(yùn)行，使我更好的掌握了哈夫曼樹等數(shù)據(jù)結(jié)構(gòu)方面的基本知識(shí)和各類基本程序問題的解決方法，熟悉了各種調(diào)用的數(shù)據(jù)類型，在調(diào)試和運(yùn)行過程中，加深我對程序運(yùn)行的環(huán)境了解和熟悉的程度，同時(shí)也提高了我對程序調(diào)試分析的能力和對錯(cuò)誤糾正的能力。</p><p>　　這次信息論與編碼的程序設(shè)計(jì)，對于我來說是一個(gè)挑戰(zhàn)。我對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)在程序的設(shè)計(jì)中也有所體現(xiàn)。課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用

98、所學(xué)知識(shí)，發(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é)到很多我們在課本上沒有的知識(shí)，充分的發(fā)揮了我們的主動(dòng)性，使我們學(xué)會(huì)了自主學(xué)習(xí)，和獨(dú)立解決問題的能力。</p&g

99、t;<p>　　很多程序在結(jié)構(gòu)上是獨(dú)立的，但是本此設(shè)計(jì)的程序功能不是零散的，它有一個(gè)連接是的程序是一個(gè)整體，達(dá)到這種統(tǒng)一體十分重要，因?yàn)檫@個(gè)輸出連接是貫穿始終的。</p><p>　　通過翻閱相關(guān)書籍，在網(wǎng)上查詢資料學(xué)習(xí)有關(guān)哈夫曼編碼的實(shí)現(xiàn)過程，我實(shí)</p><p>　　在是獲益匪淺，更加深刻的感覺到哈夫曼編碼能夠大大提高通信的效率，對于我們通信工程專業(yè)來說，學(xué)好這門科學(xué)是非

100、常重要的，在以后的圖像處理和壓縮方面這門學(xué)科能給我們很大的幫助。同時(shí)，學(xué)習(xí)這門科學(xué)也是艱辛的，因?yàn)樗容^難懂，這不僅需要我們發(fā)揮我們的聰明才智，還需要我們在不斷的實(shí)踐中領(lǐng)悟。    這次的課程設(shè)計(jì)，讓我體會(huì)到了作為一個(gè)編程人員的艱辛，一個(gè)算法到具體實(shí)現(xiàn)，再到應(yīng)用層面的開發(fā)是需要有一個(gè)較長的路要走的，不是一朝一夕就可以實(shí)現(xiàn)的，而且在編好程序后，編程人員還要花很多時(shí)間去完善，過程是心酸的，外人很難能夠

101、真正明白。 今后我要更加努力的學(xué)習(xí)專業(yè)知識(shí)，提高自我的能力！</p><p>　　這次的程序軟件基本上運(yùn)行成功，可以運(yùn)用簡單的數(shù)字告訴程序的操作者下一步該如何進(jìn)行，使得程序規(guī)模相對較小，即功能還不很全面，應(yīng)用也不很普遍。原來數(shù)據(jù)結(jié)構(gòu)可以涉及很多知識(shí)，而不是枯燥無聊的簡單的代碼部分而已，利用數(shù)據(jù)結(jié)構(gòu)方面的知識(shí)，我們可以設(shè)計(jì)出更完善的軟件。</p><p>　　總而言之，這次數(shù)據(jù)結(jié)構(gòu)

102、課程設(shè)計(jì)讓我們感觸很深，使我們每個(gè)人都了解到學(xué)習(xí)不應(yīng)該只局限于課本，因?yàn)檎n本上告訴我們的只是很有限的一部分，只是理論上的死知識(shí)，所涉及的范圍也是狹窄的。我們?nèi)粝朐谟邢薜姆秶鷥?nèi)學(xué)習(xí)到無限的知識(shí)，就要我們自己懂得爭取，懂得自學(xué)，懂得充分利用身邊的任何資源。</p><p>　　在我們的程序中有一部分查找許多該方面的資料，我竭力將所獲得的信息變成自己的資源。我動(dòng)手上機(jī)操作的同時(shí)，在了解和看懂的基礎(chǔ)上對新學(xué)的知識(shí)進(jìn)行改進(jìn)

103、和創(chuàng)新，但是在我們的程序軟件中還有很多的不足，需要加以更新。通過這次課程設(shè)計(jì)，我們都意識(shí)到了自己動(dòng)手實(shí)踐的弱勢，特別是在編程方面，于是我們知道了計(jì)算機(jī)的實(shí)踐操作是很重要的，只有通過上機(jī)編程才能充分的了解自己的不足。</p><p>　　通過這次的課程設(shè)計(jì)，我們深刻意識(shí)到自己在學(xué)習(xí)中的弱點(diǎn)，同時(shí)也找到了克服這些弱點(diǎn)的方法，這是在此活動(dòng)中得到的一筆很大的財(cái)富。在以后的時(shí)間中，我們應(yīng)該利用更多的時(shí)間去上機(jī)實(shí)驗(yàn)，多編寫程

104、序，相信不久后我們的編程能力都會(huì)有很大的提高，能設(shè)計(jì)出更多的更有創(chuàng)新的軟件。同時(shí)也感謝老師給我們這次機(jī)會(huì)，發(fā)現(xiàn)自身存在的缺點(diǎn)與不足，從而在以后的大學(xué)生活中更好的提升和完善自我。</p><p><b>　　八、參考文獻(xiàn)</b></p><p>　　[1] 曹雪虹，張宗橙.信息論與編碼（第二版）.北京：清華大學(xué)出版社.2009</p><p>　

105、　[2] 呂鋒，王虹，劉皓春，蘇揚(yáng).信息論與編碼.北京：人民郵電出版社.2004</p><p>　　[3] 樊昌信，曹麗娜.通信原理（第六版）.北京：國防工業(yè)出版社.2006</p><p>　　[4] 王慧琴.數(shù)字圖像處理.北京：北京郵電大學(xué)出版社.2007</p><p>　　[5] 孫麗華. 信息論與糾錯(cuò)編碼.電子工業(yè)出版社.2005</p>