信息論編碼哈夫曼編碼的實(shí)現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上信息論編碼哈夫曼編碼的實(shí)現(xiàn) 院系：信息工程院系 專業(yè)：通信工程專業(yè)學(xué)號(hào)： 信息論發(fā)展簡(jiǎn)史與信息科學(xué)信息論從誕生到今天，已有五十多年歷史，現(xiàn)已成為一門獨(dú)立的理論科學(xué)，回顧它的發(fā)展歷史，我們可以知道理論是如何從實(shí)踐中經(jīng)過(guò)抽象、概括、提高而逐步形成的。1.信息論形成的背景與基礎(chǔ)    信息論是在人們長(zhǎng)期的通信工程實(shí)踐中，由通信技術(shù)和概率論、隨機(jī)過(guò)程和數(shù)理統(tǒng)計(jì)相結(jié)合而逐步發(fā)展起來(lái)的一門學(xué)科。人們公認(rèn)的信息論的奠基人是當(dāng)代偉大的數(shù)學(xué)家、美國(guó)貝爾實(shí)驗(yàn)室杰出的科學(xué)家香農(nóng)，他在1948年發(fā)表了著名的論文通信的數(shù)學(xué)理論，為信息論奠定了理論基礎(chǔ)。近

2、半個(gè)世紀(jì)以來(lái)，以通信理論為核心的經(jīng)典信息論，正以信息技術(shù)為物化手段，向高精尖方向迅猛發(fā)展，并以神奇般的力量把人類社會(huì)推入了信息時(shí)代。隨著信息理論的迅猛發(fā)展和信息概念的不斷深化，信息論所涉及的內(nèi)容早已超越了狹義的通信工程范疇，進(jìn)入了信息科學(xué)領(lǐng)域。通信系統(tǒng)是人類社會(huì)的神經(jīng)系統(tǒng)，即使在原始社會(huì)也存在著最簡(jiǎn)單的通信工具和通信系統(tǒng)，這方面的社會(huì)實(shí)踐是悠久漫長(zhǎng)的。  電的通信系統(tǒng)(電信系統(tǒng))已有100多年的歷史了。在一百余年的發(fā)展過(guò)程中，一個(gè)很有意義的歷史事實(shí)是：當(dāng)物理學(xué)中的電磁理論以及后來(lái)的電子學(xué)理論一旦有某些進(jìn)展，很快就會(huì)促進(jìn)電信系統(tǒng)的創(chuàng)造發(fā)明或改進(jìn)。這是因?yàn)橥ㄐ畔到y(tǒng)對(duì)人類社會(huì)的發(fā)

3、展，其關(guān)系實(shí)在是太密切了。日常生活、工農(nóng)業(yè)生產(chǎn)、科學(xué)研究以及戰(zhàn)爭(zhēng)等等，一切都離不開(kāi)消息傳遞和信息流動(dòng)。  例如，當(dāng)法拉第(MFaraday)于1820年-1830年期間發(fā)現(xiàn)電磁感應(yīng)的基本規(guī)律后，不久莫爾斯(FBMorse)就建立起電報(bào)系統(tǒng)(18321835)。1876年，貝爾(AGBELL)又發(fā)明了電話系統(tǒng)。1864年麥克斯韋(Maxell)預(yù)言了電磁波的存在，1888年赫茲(HHertz)用實(shí)驗(yàn)證明了這一預(yù)言。接著1895年英國(guó)的馬可尼(G.Marconi)和俄國(guó)的波波夫(ACooB)就發(fā)明了無(wú)線電通信。  本世紀(jì)初(1907年)，根據(jù)電子運(yùn)動(dòng)的規(guī)律，

4、福雷斯特(1，F(xiàn)orest)發(fā)明了能把電磁波進(jìn)行放大的電子管。之后很快出現(xiàn)了遠(yuǎn)距離無(wú)線電通信系統(tǒng)。大功率超高頻電子管發(fā)明以后，電視系統(tǒng)就建立起來(lái)了(19251927)。電子在電磁場(chǎng)運(yùn)動(dòng)過(guò)程中能量相互交換的規(guī)律被人們認(rèn)識(shí)后，就出現(xiàn)了微波電子管(最初是磁控管，后來(lái)是速調(diào)管、行波管)，接著，在三十年代末和四十年代初的二次世界大戰(zhàn)初期，微波通信系統(tǒng)、微波雷達(dá)系統(tǒng)等就迅速發(fā)展起來(lái)。五十年代后期發(fā)明了量子放大器，六十年代初發(fā)明的激光技術(shù)，使人類進(jìn)入了光纖通信的時(shí)代。  隨著工程技術(shù)的發(fā)展，有關(guān)理論問(wèn)題的研究也逐步深入。1832年莫爾斯電報(bào)系統(tǒng)中高效率編碼方法對(duì)后來(lái)香農(nóng)的編碼理論是有啟發(fā)

5、的。1885年凱爾文(L.Kelvin)曾經(jīng)研究過(guò)一條電纜的極限傳信率問(wèn)題。1922年卡遜(JRCarson)對(duì)調(diào)幅信號(hào)的頻譜結(jié)構(gòu)進(jìn)行了研究，并建立了信號(hào)頻譜概念。1924年奈奎斯特(HNyquist)指出，如果以一個(gè)確定的速度來(lái)傳輸電報(bào)信號(hào)，就需要一定的帶寬。他把信息率與帶寬聯(lián)系起來(lái)了。1928年哈特萊(RVHartley)發(fā)展了奈奎斯特的工作，并提出把消息考慮為代碼或單語(yǔ)的序列。他的工作對(duì)后來(lái)香農(nóng)的思想是有影響的。  1936年阿姆斯特朗(EHArmstrong)認(rèn)識(shí)到在傳輸過(guò)程中增加帶寬的辦法對(duì)抑制噪聲干擾肯定有好處。根據(jù)這一思想他提出了寬偏移的頻率調(diào)制方法，該方法是

6、有劃時(shí)代意義的。信息論作為一門嚴(yán)密的科學(xué)分支，主要?dú)w功于貝爾實(shí)驗(yàn)室的香農(nóng)。他在1948年發(fā)表的論文通信的數(shù)學(xué)理論奠定了信息論的基礎(chǔ)?？刂普摰膭?chuàng)始人維納也對(duì)信息論有不可忽視的貢獻(xiàn)。香農(nóng)和維納的基本思想都是把通信作為統(tǒng)計(jì)過(guò)程來(lái)處理。他們采用的術(shù)語(yǔ)、方法也主要依靠統(tǒng)計(jì)理論。1.哈夫曼編碼簡(jiǎn)介 哈夫曼編碼(Huffman Coding)是一種編碼方式，哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。uffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng) 度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作Huffman編碼。  2.

7、哈夫曼編碼原理 哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹(shù)即最優(yōu)二叉樹(shù)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。 在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無(wú)損耗壓縮。這一術(shù)語(yǔ)是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來(lái)的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的）。這種方法是由Davi

8、d.A.Huffman發(fā)展起來(lái)的。 例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)位(bit)來(lái)表示，而z則可能花去25個(gè)位（不是26）。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)（byte），即8個(gè)位。二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無(wú)損壓縮的比例。  3哈夫曼編碼步驟 首先，哈夫曼編碼是哈夫曼樹(shù)的一個(gè)應(yīng)用，哈夫曼書(shū)又稱優(yōu)二樹(shù)，是一種帶路徑長(zhǎng)度最短的二叉樹(shù)，所謂樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中

9、所有的葉節(jié)點(diǎn)的權(quán)值乘上其到根節(jié)點(diǎn)的路徑長(zhǎng)度（若根節(jié)點(diǎn)為0，葉節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度為葉節(jié)點(diǎn)的層數(shù)）。樹(shù)的帶全路徑長(zhǎng)度記為WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,.n)構(gòu)成一棵有N哥葉節(jié)點(diǎn)的二叉樹(shù)，相應(yīng)的葉節(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i(i=1,2,.n)?？梢宰C明哈夫曼樹(shù)的WPL是最小的。 哈夫曼編碼步驟： 1.對(duì)給點(diǎn)的n個(gè)權(quán)值W1,W2,W3,.,Wi,.,Wn構(gòu)成n棵二叉樹(shù)的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉樹(shù)Ti中只有一個(gè)權(quán)值為Wi的根節(jié)點(diǎn)，它的左右子樹(shù)均為空。（為方便在計(jì)算機(jī)上實(shí)現(xiàn)算法，一般還要求以

10、Ti的權(quán)值的升序排列）。 2.在F中選取兩棵根節(jié)點(diǎn)權(quán)值最小的樹(shù)作為新的構(gòu)造的二叉樹(shù)的左右子樹(shù)，新二叉樹(shù)的根節(jié)點(diǎn)的權(quán)值為其左右子樹(shù)的根節(jié)點(diǎn)的權(quán)值之和。 3.從F中刪除這兩棵樹(shù)，并把這棵樹(shù)新的二叉樹(shù)同樣一升序排列加入到集合F中。 4.重復(fù)二和三兩步，知道集合F中只有一棵二叉樹(shù)為止。 簡(jiǎn)易的理解就是，假如我有A,B,C,D,E五個(gè)字符，出現(xiàn)的頻率（即權(quán)值）分別為5,4,3,2,1，那么我們第一步先取兩個(gè)最小權(quán)值作為左右子樹(shù)構(gòu)造一個(gè)新樹(shù)，即取1,2構(gòu)成新樹(shù)，其節(jié)點(diǎn)為1+2=3，如圖所示：虛線為新生成的節(jié)點(diǎn)，第二步再把新生成的權(quán)值3的節(jié)點(diǎn)放到剩下的集合中，所以集合

11、變成5,4,3,3，再根據(jù)第二步，取最小的兩個(gè)權(quán)值構(gòu)成新樹(shù)，如圖：再一次建立哈夫曼樹(shù)，如下圖：其中各個(gè)權(quán)值替換對(duì)應(yīng)的字符即為下圖：所以各字符對(duì)應(yīng)的編碼為：A->11,B->10,C->00,D->011,E->010 哈夫曼編碼是一種無(wú)前綴編碼，解碼時(shí)不會(huì)混淆。其主要應(yīng)用在數(shù)據(jù)壓縮，加密解密等場(chǎng)合。  4.C語(yǔ)言編寫(xiě)代碼及運(yùn)行結(jié)果 /*對(duì)文本文件進(jìn)行huffman編碼、解碼  讀取文本文件，并統(tǒng)計(jì)文件中字母?jìng)€(gè)數(shù)  建立huffman樹(shù)  對(duì)文件進(jìn)行huffman編碼

12、  對(duì)文件進(jìn)行huffman解碼*/ #include <stdio.h>  #define MAXBIT 10 /*定義哈夫曼編碼的最大長(zhǎng)度*/  #define MAXVALUE 10000 /*定義最大權(quán)值*/  #define MAXLEAF 30 /*定義哈夫曼樹(shù)中最多葉子節(jié)點(diǎn)個(gè)數(shù)*/  #define MAXNODE MAXLEAF*2-1&#

13、160;/*哈夫曼樹(shù)最多結(jié)點(diǎn)數(shù)*/  typedef struct  /*哈夫曼編碼信息的結(jié)構(gòu)*/  int bitMAXBIT;  int start;Hcodetype;  typedef struct  /*哈夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)*/  int weight;  int parent;  int lchild; int rch

14、ild;  Hnodetype;  void huffmantree(Hnodetype huffnodeMAXNODE,int n) /*構(gòu)造哈夫曼樹(shù)的函數(shù)*/    int i,j,m1,m2,x1,x2;  for(i=0;i<2*n-1;i+) /*存放哈夫曼樹(shù)結(jié)點(diǎn)的數(shù)組huffnode初始化*/    huffnodei.weight=0;  huffnodei

15、.parent=-1;  huffnodei.lchild=-1;  huffnodei.rchild=-1;    for(i=0;i<n;i+) /*輸入入N個(gè)葉子節(jié)點(diǎn)的權(quán)值*/   printf("please input %d character's weightn",i);  scanf("%d",&huffnodei.weight); 

16、;   for(i=0;i<n-1;i+) /*開(kāi)始循環(huán)構(gòu)造哈夫曼樹(shù)*/    m1=m2=MAXVALUE;  x1=x2=0;  for(j=0;j<n+i;j+)    if(huffnodej.weight<m1&&huffnodej.parent=-1)    m2=m1;x2=x1;m1=huffnodej.weight;x1=j; 

17、0;  else if(huffnodej.weight<m2&&huffnodej.parent=-1)    m2=huffnodej.weight;x2=j;     huffnodex1.parent=n+i;  huffnodex2.parent=n+i;  huffnoden+i.weight=huffnodex1.weight+huffnodex2.weight;  huffnod

18、en+i.lchild=x1;  huffnoden+i.rchild=x2;      void main()    Hnodetype huffnodeMAXNODE;  Hcodetype huffcodeMAXLEAF,cd;  int i,j,c,p,n;printf("please input nn");  scanf("%d",&n); /*輸入葉子節(jié)點(diǎn)個(gè)數(shù)*/  huffmantree(huffnode,n); /*建立哈夫曼樹(shù)*/  for(i=0;i<n;i+) /*該循環(huán)求每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)字符的哈夫曼編碼*/    cd.start=n-1;c=i;  p=huffnodec.parent;  while(p!