信源熵統(tǒng)計與哈夫曼編碼

1、信息論與編碼課程設(shè)計報告設(shè)計題目：統(tǒng)計信源嫡與哈夫曼編碼專業(yè)班級學(xué)號學(xué)生姓名指導(dǎo)教師教師評分2014年1月26日 目錄TOC o 1-5 h z HYPERLINK l bookmark6一、設(shè)計任務(wù)與要求2 HYPERLINK l bookmark8二、設(shè)計思路3 HYPERLINK l bookmark10三、設(shè)計流程圖4 HYPERLINK l bookmark12四、程序運行及結(jié)果5 HYPERLINK l bookmark14五、心得體會6 HYPERLINK l bookmark16參考文獻(xiàn)7 HYPERLINK l bookmark18附錄：源程序8 一、設(shè)計任務(wù)與要求要求完成兩

2、個題目，1和2選做一題，3、4和5選做一題。1、統(tǒng)計信源爛要求：統(tǒng)計任意文本文件中各字符（不區(qū)分大小寫）數(shù)量，計算字符概率，并計算信源爛。2、判斷唯一可譯碼要求：利用尾隨后綴法判斷任意輸入的碼是否為唯一可譯碼。3、香農(nóng)編碼要求：任意輸入消息概率，利用香農(nóng)編碼方法進(jìn)行編碼，并計算信源爛和編碼效率。4、費諾編碼要求：任意輸入消息概率，利用費諾編碼方法進(jìn)行編碼，并計算信源爛和編碼效率。5、哈夫曼編碼要求：任意輸入消息概率，利用哈夫曼編碼方法進(jìn)行編碼，并計算信源爛和編碼效率。 二、設(shè)計思路此設(shè)計是將統(tǒng)計信源爛與哈夫曼編碼結(jié)合在一起。程序中采用模塊化思想將實現(xiàn)某個功能的程序獨立成一個模塊，然后在主程序中

3、加以調(diào)用。H（X丿表示信源輸出后，每個消息（或符號）所提供的平均信息量。統(tǒng)計信源爛模塊是程序從鍵盤中讀取用戶輸入的字母（不區(qū)分大小寫）或空格，并分別統(tǒng)計出總數(shù)N和每個字母、空格出現(xiàn)的次數(shù)“以及概率Pg）,然后由公式nt=i可計算出信源爛。哈夫曼是將信源消息符號按其出現(xiàn)的概率大小依次排列，然后取兩個概率最小的符號分別配以o和1,并將這兩個概率相加作為一個新符號的概率，與未分配碼元的符號重新排隊。對重排后的兩個概率最小符號重復(fù)以上的過程。繼續(xù)上述過程，直到最后兩個符號配以o和1為止。從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。哈夫曼編碼模塊是將各個字符的概率進(jìn)行排序并寫

4、出每一個的碼字存放于一個相應(yīng)的結(jié)構(gòu)體中。哈夫曼編碼是可變字長編碼的一種，這種編碼方法完全依據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的碼字，有時稱之為最佳編碼。它可以充分利用短碼，使出現(xiàn)概率高的符號使用短的位序列，而那些很少出現(xiàn)的符號則用較長的位序列。在此次課程設(shè)計中先通過所輸入的字母和空格進(jìn)行相應(yīng)的統(tǒng)計，計算各自的概率，然后選用哈夫曼編碼，通過編程運行來進(jìn)一步感受哈夫曼編碼的便利之處。三、設(shè)計流程圖圖1設(shè)計流程圖 四、程序運行及結(jié)果在程序中可以輸入字母及空格，對于輸入的其他字符程序會給出錯誤提示。設(shè)在程序中輸入了字符“ABCDabcd”，則程序輸出的結(jié)果如下圖所示：圖2實驗結(jié)果圖 五、心得體會這次的

5、課程設(shè)計讓我鞏固了一個學(xué)期的所學(xué)，前半部分是求信源爛，后半年部分是考察編碼。我們所選取的的實驗樣本很簡單，只有四個字符而且都是等概率出現(xiàn)的，計算信源爛時很簡單，使用哈弗曼編碼時編碼效率達(dá)到了100%。真正到我們工作時不會遇到如此簡單的項目。這次的課程設(shè)計，我們的主要目的是為了鞏固所學(xué)，復(fù)習(xí)信源爛的求法和三種編碼方法。這次課程設(shè)計，我們對香農(nóng)編碼，費諾編碼以及哈弗曼編碼有了一個更全面的認(rèn)識。信息論與編碼是一門實用性很強(qiáng)的學(xué)科，同時也很有針對性。這次我們選用的樣本這么簡單，我在編程上還不能順利寫出，到后來程序還是同組同學(xué)寫的，我深深地認(rèn)識到自己在編程上的不足。學(xué)習(xí)本就是一個從不會到會的過程，同學(xué)之

6、間的合作，我們才順利完成課程設(shè)計。理論是為實踐服務(wù)的，學(xué)好理論才能去接觸實踐，因為學(xué)時所限制，我們在課堂上學(xué)習(xí)的東西僅僅是皮毛。信息論與編碼，需要大量地概率論與數(shù)理統(tǒng)計的只是作為依托，所以數(shù)學(xué)是基礎(chǔ)。任何一門課程都不會獨立與其他課程之外。作為一個工科的學(xué)生一定要把所學(xué)用于實踐，相信我下次能做的更好。 參考文獻(xiàn)1曹雪虹，張宗橙.信息論與編碼北京.清華大學(xué)出版社.2009.2StanleyB.LippmanJoseeLajoie,BarbaraE.Moo著，李師賢，蔣愛軍，梅曉勇,林瑛譯.C+Primer中文版.北京.人民郵電出版社.2006.3傅祖蕓.信息論基礎(chǔ)北京.電子工業(yè)出版社，1989譚浩

7、強(qiáng).C語言程序設(shè)計（第三版）北京.清華大學(xué)出版社，2009.10 附錄：源程序#includeviosteamA包含頭文件#include#include#include#include#includeusingnamespacestd;stmctList_num定義一個stmct類型用于存放概率和對應(yīng)的字符標(biāo)識floatprobability=0;bitsetkey;structBinary.alphabet用于存放碼字vectorbitset=A&wordi=h&woidi=N)numwordi-8+;elsecout11ERROE!ii您輸入的其他字符，請重新輸入字符(字母或空格)!”e

8、ndlendl;gotorepet;不是人寫字符和空格的情況if(word.size()=0)沒有輸入字符的情況coutnERROR!ii您沒有輸入字符，請重新輸入字符！”endlendl;gotorepet;for(inti=0;i=l;j+)for(inti=0;i27;i+)if(Alphabet_probabilitynj.keyi=1)CharToBinaryi.key.push_back(1);/概率最小的碼值為1if(Alphabet_probabilityn-j-l.keyi=1)CharToBinaryi.key.push_back(O);/概率次最小的碼值為0Alphabe

9、t_probabilitynJ-1.piobability=Alphabet_bability+Alphabet_bability;for(mtk=0;k27;k+)將最小的二個概率相加，將相應(yīng)的字符標(biāo)識也置1if(Alphabet_probabilityn-j.keyk=1)Alphabet_probabilityn-j-l.keyk=1;Insert_Sort(n-j);進(jìn)行一遍后，再進(jìn)行排序cout”統(tǒng)計結(jié)果及由哈夫曼編碼可得的各個字符的碼字如卞所示：”endl;cout”你輸入的總數(shù)為:word.sizeQen

10、dl;cout“字符次數(shù)概率碼字2字符次數(shù)概率碼字-endl;CharToBuiaiy_output();調(diào)用輸出碼字的函數(shù)cout”信源爛為：nInforniation_S_EQntM/信源爛”平均碼長為：HAveiage_Code_Lengtli()ntH平均碼長編碼效率為：MIiifdrniation_S_EQ/Average_Code_Length()*100亡iidl;/編碼效率cout轉(zhuǎn)換后的編碼為：endl;Binary_Output();調(diào)用輸出編碼后的序列coutendl;repet:后面的goto語句要用的標(biāo)號for(inti=0;i27;i+)將相應(yīng)的變量初始化，以便下一

11、次再使用numi=0;Alphabet_probabilityi.key.reset();Alphabet_bability=0;CharToBmaiyfi.key.clearQ;couthji請按Enter清除屏幕iiH;while(1)if(getcharQ=W)break; Isystem(cls);cout”請按”Ctrl+Z”然后再按Enter結(jié)束該程序!n”請輸入一串字符：n”；return0;unsignedmtPiobability_NotzeroQ將概率中不是0概率的個數(shù)返回unsignedmtn=0,i=0;for(;i27;i+)if(Al

12、phabet_probabilityi.piobabilitv!=0)n+;returnn;voidInseit_Soil(unsignedmtn)采用插入排序法unsignedmti;mtj;List_numtemp;for(i=l;iAlphabet_piobabilityj.piobability&j=0)Alphabet_probabilityj+1=AlphabeCprobabilitylj；j-;AlphabeCprobabilityj+1=temp;voidCharToBinary_outputQ各個碼字的輸出函數(shù)mtk=0;for(mti=0;i0)if(i=26)cout”空

13、格，；coutnumi;if(k%2=0)gotoxv(lO);if(k%2=1)gotoxv(50);float(numi)/woid.sizeO)/出其他字符概率for(intj=ChaiToBmaiyi.key.size()1;j=0;j)coutCliarToBinaryi.keyj;coutendl;elsek+；coutchar(65+i),7Hchar(97+i)coutnumi;if(k%2=1)gotoxv(lO);if(k%2=0)gotoxv(50);float(numi)/woid.sizeO)/出其他字符概率for(intj=ChaiToBmaiyi.key.size

14、()1;j=0;j)coutCliarToBinaryi.keyj;if(k%20)輸出2組數(shù)后，進(jìn)行換行coutendl;elsegotoxv(40);if(ChaiToBmary26.key.size()=0&k%2=1)coutendl;voidBiiiaiy_Output()整體編碼的輸出 for(unsignediiiti=0;i=A&woidi=0;j)coutChaiToBiiiaiywordi-WJ.keylj；elsefor(intj=ChaiToBiiiaiywordi-hkeysize()-1;j=0;j-)coutChaiToBinarywordi-.keyjj;els

15、efor(intj=ChaiToBiiiaiy26.key.sizeQ-1;j=0;j)coutChaiToBiiiary26.keyj；floatAvreiage_Code_Length()/計算平均碼長floatsum=0;for(unsignediiiti=0;i27;i+)if(CharToBiiiaiyi.key.sizeO!=0)sum+=(float(numi)/float(word.sizeQ)*ChaiToBiiiaiy1.key.size();returnsum;floatIiifbnnation_S_E()計算平均信源爛floatsum=0;for(mti=0;i27;i+)log2(float(numi)if(CharToBiiiaryi.key.sizeQ!=0)sum+=(float(numi)/float(word.size()*float(word.size();return(-sum);voidgotoxy(iiitx)在屏幕的具體位置