哈夫曼編碼的分析與實(shí)現(xiàn)

吉林建筑大學(xué)電氣與計(jì)算機(jī)學(xué)院信息理論與編碼課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目:哈夫曼編碼的分析與實(shí)現(xiàn)專業(yè)班級(jí):電子信息工程設(shè)計(jì)題目:哈夫曼編碼的分析與實(shí)現(xiàn)專業(yè)班級(jí):電子信息工程131學(xué)生姓名:號(hào)：指導(dǎo)教師:設(shè)計(jì)時(shí)間:2016.11.21—2016.12.2第1章概述1.1設(shè)計(jì)的作用、目的通過(guò)完成具體編碼算法的程序設(shè)計(jì)和調(diào)試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過(guò)程，增強(qiáng)邏輯思維能力，培養(yǎng)和提高自學(xué)能力以及綜合運(yùn)用所學(xué)理論知識(shí)去分析解決實(shí)際問(wèn)題的能力，逐步熟悉開(kāi)展科學(xué)實(shí)踐的程序和方法。主要目的是加深對(duì)理論知識(shí)的理解，掌握查閱有關(guān)資料的技能，提高實(shí)踐技能，培養(yǎng)獨(dú)立分析問(wèn)題、解決問(wèn)題及實(shí)際應(yīng)用的能力。通過(guò)課程設(shè)計(jì)各環(huán)節(jié)的實(shí)踐，應(yīng)達(dá)到如下要求：理解無(wú)失真信源編碼的理論基礎(chǔ)，掌握無(wú)失真信源編碼的基本方法；根據(jù)哈夫曼編碼算法，考慮一個(gè)有多種可能符號(hào)(各種符號(hào)發(fā)生的概率不同)的信源，得到哈夫曼編碼和碼樹(shù)；掌握哈夫曼編碼的優(yōu)缺點(diǎn)；通過(guò)完成具體編碼算法的程序設(shè)計(jì)和調(diào)試工作，提高編程能力，深刻理解信源編碼、信道編譯碼的基本思想和目的，掌握編碼的基本原理與編碼過(guò)程，增強(qiáng)邏輯思維能力，培養(yǎng)和提高自學(xué)能力以及綜合運(yùn)用所學(xué)理論知識(shí)去分析解決實(shí)際問(wèn)題的能力，逐步熟悉開(kāi)展科學(xué)實(shí)踐的程序和方法。1.2設(shè)計(jì)任務(wù)及要求理解無(wú)失真信源編碼的理論基礎(chǔ)，掌握無(wú)失真信源編碼的基本方法；掌握哈夫曼編碼/費(fèi)諾編碼方法的基本步驟及優(yōu)缺點(diǎn)；深刻理解信道編碼的基本思想與目的，理解線性分組碼的基本原理與編碼過(guò)程；能夠使用MATLAB或其他語(yǔ)言進(jìn)行編程，編寫(xiě)的函數(shù)要有通用性。1.3設(shè)計(jì)內(nèi)容一個(gè)有8個(gè)符號(hào)的信源X，各個(gè)符號(hào)出現(xiàn)的概率為：TOC\o"1-5"\h\zX］「xxxxxxXX=<12345678P(X)」［0.390.170.120.10.070.060.050.04進(jìn)行哈夫曼編碼，并計(jì)算平均碼長(zhǎng)、編碼效率、冗余度。第2章哈夫曼編碼的分析與實(shí)現(xiàn)2.1哈夫曼編碼介紹及原理哈夫曼編碼(HuffmanCoding)是一種熵編碼編碼壓縮方式，哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。哈夫曼壓縮是個(gè)無(wú)損的壓縮算法，一般用來(lái)壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是不同符號(hào)(例如，文本文件中的字符)用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。哈夫曼編碼的碼長(zhǎng)是變化的，對(duì)于出現(xiàn)頻率高的信息，編碼的長(zhǎng)度較短；而對(duì)于出現(xiàn)頻率低的信息，編碼長(zhǎng)度較長(zhǎng)。這樣，處理全部信息的總碼長(zhǎng)一定小于實(shí)際信息的符號(hào)長(zhǎng)度。下面給出具體的Huffman編碼算法。首先統(tǒng)計(jì)出每個(gè)符號(hào)出現(xiàn)的頻率，如本次課程設(shè)計(jì)x1到x7的出現(xiàn)頻率分別為0.39，0.17，0.12，0.1，0.07，0.06，0.05，0.04。從左到右把上述頻率按從小到大的順序排列。每一次選出最小的兩個(gè)值，作為二叉樹(shù)的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。重復(fù)(3)，直到最后得到和為1的根節(jié)點(diǎn)。將形成的二叉樹(shù)的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的0,1序列串起來(lái)，就得到了各個(gè)符號(hào)的編碼。2.2哈夫曼編碼步驟將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列為p>p>->p取兩個(gè)概率最小的字母分別分配以0和1兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)制符號(hào)的字母重新排隊(duì)。對(duì)重排后的兩個(gè)概率小符號(hào)重復(fù)步驟(2)的過(guò)程。不斷繼續(xù)上述過(guò)程，直到最后兩個(gè)符號(hào)配以0和1為止。從最后一級(jí)開(kāi)始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼子。

2.4哈夫曼編碼特點(diǎn)（1）哈弗曼的編碼方法保證了概率大的符號(hào)應(yīng)對(duì)于短碼，概率小的應(yīng)對(duì)于長(zhǎng)碼，充分利用了短碼；（2）縮減信源的最后兩個(gè)碼子總是最后一位不同，從而保證了哈弗曼碼是及時(shí)碼。（3）哈夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒(méi)有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。但如果碼串中有錯(cuò)誤，哪怕僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是后面的數(shù)據(jù)串也會(huì)接著被譯錯(cuò)，全亂了套，這種現(xiàn)象稱為錯(cuò)誤傳播（errorpropagation）o計(jì)算機(jī)對(duì)這種錯(cuò)誤也無(wú)能為力，說(shuō)不出錯(cuò)在哪里，更談不上去糾正它；（4）哈夫曼編碼只能用整數(shù)來(lái)表示單個(gè)符號(hào)而不能用小數(shù)，這很大程度上限制了壓縮效果；（5）哈夫曼所有位都是合在一起的，如果改動(dòng)其中一位就可以使其數(shù)據(jù)變得面目全非。2.5設(shè)計(jì)步驟設(shè)一個(gè)有8個(gè)符號(hào)的信源X，各個(gè)符號(hào)出現(xiàn)的概率為:XP(XXP(X)12345670.390.170.120.10.070.060.05x80.04則有兩種哈夫曼編碼方法，（0,1）編碼或者（1,0）編碼。表1哈夫曼（0,1）編碼過(guò)程框圖信源符號(hào)xi概率、P(x.)iX10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.040.390.170.120.10.090.07)0.06」10.390.170.130.120.1I0.09J0編碼過(guò)程0.390.190.170.12人0.390.250.190.13〕00.17J10.390.61、0.360.39J0.25〕1碼字Wi碼長(zhǎng)Ki110013011300004010040101400010500011511該哈夫曼碼的平均碼長(zhǎng)K為—^8K=妥p3)K=0.39*1+0.17*3+0.12*3+0/4+0.07*4+0.06*4+0.05*5+0.04*5i=1二2.63(碼元/符號(hào))信源熵H(x)為H(x)=—￡p(x)logp(x)=-(0.39log0.39+0.17log0.17+0.12log0.12+0.1log0.1iii=1+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04)二2.58(bit/符號(hào))編碼效率壁=螳.0.98K2.63冗余度丫=1—門(mén)=1-0.977=0.02表2哈夫曼(1,0)編碼過(guò)程框圖信源符號(hào)x概率p(x.)iX10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.04編碼過(guò)程0.390.390.390.390.170.170.190.2540.120.13▲017A.19]0.1,.12夕13]/0.17J0.09個(gè)/°.1〕/信源符號(hào)x概率p(x.)iX10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.04編碼過(guò)程0.390.390.390.390.170.170.190.2540.120.13▲017A.19]0.1,.12夕13]/0.17J0.09個(gè)/°.1〕/0.12J尸0/0.07]/0.09〕0/0.06J>000.36100.390.61O.25〕°碼字稱碼長(zhǎng)Ki01110310031111410114101041110151110051編碼效率H(X)2.58門(mén)=—=—="0.98K2.63冗余度y=1-n=1-0.977=0.02通過(guò)以上的兩種不同的編碼方式進(jìn)行比較，我們發(fā)現(xiàn)其實(shí)以上兩種編碼的碼雖然不同，但是其知識(shí)將原來(lái)的1換成了0，0換成了1,他的碼長(zhǎng)，編碼效率，冗余度是沒(méi)有變化的。需要注意的是，對(duì)于多進(jìn)制哈夫曼編碼，為了提高編碼效率，就要使長(zhǎng)碼的符號(hào)數(shù)量盡量少，概率盡量小，所以信源符號(hào)數(shù)最好滿足m=(r-1)n+r，其中r為進(jìn)制數(shù)，n為縮減的次數(shù)。比如說(shuō)如果要進(jìn)行三進(jìn)制編碼，那么最好信源具有7個(gè)符號(hào)，第一次合并后減少2個(gè)稱為5個(gè)，第二次合并后又減少2個(gè)稱為3個(gè)，這樣給每一個(gè)賦予三進(jìn)制符號(hào)就沒(méi)有浪費(fèi)的了。但是如果信源只有6個(gè)符號(hào)的話，為了減少最長(zhǎng)碼的數(shù)量，那么應(yīng)該在第一次合并是添置為零的虛擬符號(hào)1個(gè)，事實(shí)上只合并2個(gè)概率最小的符號(hào)，后面每次合并3個(gè)，就可以是的最長(zhǎng)的碼的符號(hào)數(shù)量最少，也就是長(zhǎng)碼的概率最小，從而得到最高的編碼效率。但是對(duì)于信源的某一個(gè)符號(hào)來(lái)說(shuō)，有時(shí)候可能還會(huì)比定長(zhǎng)碼長(zhǎng)。例如當(dāng)信源有5個(gè)是，采用定長(zhǎng)碼方式可用3個(gè)二進(jìn)制符號(hào)組成碼字。而用變長(zhǎng)碼是有時(shí)候碼字卻長(zhǎng)達(dá)4個(gè)二進(jìn)制符號(hào)。所以編碼簡(jiǎn)單化的代價(jià)就是要有大量的儲(chǔ)存設(shè)備用來(lái)緩沖碼字長(zhǎng)度的差異，也就是碼方差小的碼質(zhì)量好的原因。設(shè)一秒鐘送一個(gè)信源符號(hào)，輸出碼字卻只有5個(gè)二進(jìn)制符號(hào)，若希望平均每秒輸出_=2.61個(gè)二進(jìn)制的信息率輸出，才能從長(zhǎng)久計(jì)算，輸出和輸入保持平衡。當(dāng)儲(chǔ)存量不夠大的時(shí)候，可能有時(shí)取空，有時(shí)溢出。例如信源連續(xù)發(fā)出短碼時(shí)，就會(huì)出現(xiàn)取空，就是說(shuō)還沒(méi)有存入就要輸出。連續(xù)發(fā)出長(zhǎng)碼時(shí)，就會(huì)出現(xiàn)溢出，就是說(shuō)存入太多，以致于存滿了還未取出就要再次存入。所以應(yīng)估計(jì)所需的存儲(chǔ)器容量，才能使上述現(xiàn)象發(fā)生的概率小至可以容忍。當(dāng)我們計(jì)算兩個(gè)概率之和時(shí)，假設(shè)這兩種的概率之和與上方概率有相同，我們應(yīng)該把這個(gè)和概率放在其相同概率上方還是下方，我們就此進(jìn)行討論；設(shè)我們有一組概率為；0.4,0.2,0.2,0.1,0.1，則離散無(wú)記憶信源

X][xxxxx]P(X)「[0.40.20.20.i0.51J當(dāng)概率相同放在下方時(shí)，哈夫曼編碼為：表3哈夫曼編碼方法信源編碼概率編碼過(guò)程碼字碼長(zhǎng)X10.40.40.40.6]°/pi?Y1.0002X20.20.2/0.4、J/0.4J1102X30.2/°.2]「/。.2J1112X40.1〕J0.2J10103X50.1〕10113當(dāng)概率相同放在上方時(shí)，哈夫曼編碼為:表4哈夫曼編碼方法二信源編碼概率編碼過(guò)程碼字碼長(zhǎng)X10.40.40.40.6]。1.00.2刀0.4]00.4J0.2]。0.2J14?！?/111X20.2012X30.20002X40.100104X50.100114則上面兩表給出的哈夫曼平均碼長(zhǎng)相等，即K=28p(xi)Ki=2.2碼元符號(hào)i=1編碼效率也相同，即門(mén)=H^X1=0.965

K(￥k-K￥-K但是兩種碼的質(zhì)量不完全相同，可用碼方差來(lái)表示，即82=(￥k-K￥-K由此可見(jiàn)放在上面的哈夫曼編碼比放在下面的哈夫曼編碼得到的碼方差要小許多，故應(yīng)該放在上面。2.6哈弗曼樹(shù)原理及過(guò)程哈夫曼樹(shù)(Huffmantree)，又名最優(yōu)樹(shù)，指給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱為哈夫曼樹(shù)(Huffmantree)。哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近。若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。哈夫曼樹(shù)是一種樹(shù)形結(jié)構(gòu)，用哈夫曼樹(shù)的方法解編程題的算法就叫做哈夫曼算法。樹(shù)并不是指植物，而是一種數(shù)據(jù)結(jié)構(gòu)，因?yàn)槠浯娣欧绞筋H有點(diǎn)象一棵樹(shù)有樹(shù)叉因而稱為樹(shù)。最簡(jiǎn)哈夫曼樹(shù)是由德國(guó)數(shù)學(xué)家馮。哈夫曼發(fā)現(xiàn)的，此樹(shù)的特點(diǎn)就是引出的路程最短。哈弗曼最優(yōu)二叉樹(shù)步驟：1、初始化：根據(jù)給定的。個(gè)權(quán)值｛七七,…氣｝構(gòu)成n棵二叉樹(shù)的集合F=｛T,T，…,T｝，其中每棵二叉樹(shù)中只有一個(gè)帶權(quán)w的根結(jié)點(diǎn)，左右子樹(shù)均空。12ni2、找最小樹(shù)：在F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且至新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。3、刪除與加入：在F中刪除這兩棵樹(shù)，并將新的二叉樹(shù)加入F中。4、判斷：重復(fù)前兩步(2和3)，直到F中只含有一棵樹(shù)為止。該樹(shù)即為哈夫曼樹(shù)。圖1哈夫曼(0,1)編碼樹(shù)圖形哈夫曼(1,0)編碼樹(shù)圖形1111哈夫曼樹(shù)也可以是k叉的，只是在構(gòu)造k叉哈夫曼樹(shù)時(shí)需要先進(jìn)行一些調(diào)整。構(gòu)造哈夫曼樹(shù)的思想是每次選k個(gè)權(quán)重最小的元素來(lái)合成一個(gè)新的元素，該元素權(quán)重為k個(gè)元素權(quán)重之和。但是當(dāng)k大于2時(shí)，按照這個(gè)步驟做下去可能到最后剩下的元素少于k個(gè)。解決這個(gè)問(wèn)題的辦法是假設(shè)已經(jīng)有了一棵哈夫曼樹(shù)(且為一棵滿k叉樹(shù))，則可以計(jì)算出其葉節(jié)點(diǎn)數(shù)目為(k-1)?n?k+1式子中的nk表示子節(jié)點(diǎn)數(shù)目為k的節(jié)點(diǎn)數(shù)目。于是對(duì)給定的n個(gè)權(quán)值構(gòu)造k叉哈夫曼樹(shù)時(shí)，可以先考慮增加一些權(quán)值為0的葉子節(jié)點(diǎn)，使得葉子節(jié)點(diǎn)總數(shù)為(-1)?n?k+1這種形式,然后再按照哈夫曼樹(shù)的方法進(jìn)行構(gòu)造即可。第3章哈夫曼編碼C語(yǔ)言實(shí)現(xiàn)3.1C語(yǔ)言編程3.1.1程序介紹本程序的編碼和運(yùn)行都是在VS2008中實(shí)現(xiàn)的，整個(gè)程序雖然看似龐大，但編寫(xiě)過(guò)程清晰，采用模塊化編寫(xiě)，各個(gè)問(wèn)題逐個(gè)擊破，也方便對(duì)程序的管理和運(yùn)行。整個(gè)程序的編寫(xiě)分為五大部分：main主函數(shù)，xiaoxi子函數(shù)，add子函數(shù)，coding子函數(shù)，ordination子函數(shù)。五大部分緊密相連，環(huán)環(huán)相扣，共同實(shí)現(xiàn)程序的編碼。Main（）主函數(shù)主要負(fù)責(zé)其它函數(shù)的調(diào)用和最后結(jié)果的輸出；Xiaoxi（）子函數(shù)主要負(fù)責(zé)輸入需要的概率數(shù)據(jù)；Add（）子函數(shù)負(fù)責(zé)概率相加以便于排序；coding（）子函數(shù)負(fù)責(zé)具體編碼工作。從右往左逐列編碼，在每一列從下往上逐個(gè)編碼，與上課時(shí)學(xué)習(xí)的方法稍有不同，其原理相同。ordination（）子函數(shù)主要負(fù)責(zé)各個(gè)概率間以及概率和的排序。該程序的優(yōu)點(diǎn)有以下四個(gè)方面：1、程序在剛運(yùn)行的時(shí)候需要輸入概率數(shù)據(jù)，程序會(huì)啟動(dòng)蜂鳴器，提示需要輸入數(shù)據(jù)；在輸入需要輸入的數(shù)據(jù)個(gè)數(shù)之后，會(huì)再次啟動(dòng)蜂鳴器提醒需要輸入概率數(shù)程序具有的提醒功能是本程序的一大特色。2、程序在輸入完需要的數(shù)據(jù)后，會(huì)自動(dòng)排序，而不需要再去麻煩的排序。3、程序在運(yùn)行過(guò)程中會(huì)自動(dòng)檢錯(cuò)（錯(cuò)誤報(bào)警）：a、當(dāng)輸入的概率大于1或小于0的時(shí)候，系統(tǒng)會(huì)自動(dòng)提示錯(cuò)誤；b、當(dāng)輸入的概率之和大于1時(shí)，系統(tǒng)會(huì)自動(dòng)檢錯(cuò)。4、程序的編碼過(guò)程清晰，編碼過(guò)程中所有的概率都會(huì)在顯示窗口顯示出來(lái)，更清楚易懂。5、若兩概率之和與另一概率相等，概率之和會(huì)自動(dòng)排在后面。a、理論上講求和排序的時(shí)候是按照列的形式，但程序按照行的形式。當(dāng)然了，再完美的計(jì)劃也會(huì)有破綻，這個(gè)程序也不可避免地存在些小缺點(diǎn)：b、出錯(cuò)報(bào)警時(shí)增加蜂鳴器長(zhǎng)時(shí)間工作；c、add函數(shù)語(yǔ)句重復(fù)，流程圖中已經(jīng)進(jìn)行了修改。程序使用說(shuō)明：該程序是在VS2008環(huán)境下編寫(xiě)的，運(yùn)行也需要在VS2008中運(yùn)行，請(qǐng)確

保你在裝載有VS2008環(huán)境下運(yùn)行。3.2程序流程圖以及說(shuō)明說(shuō)明主程序說(shuō)明三重循環(huán)初始化，使其所有值為2顯示“三重循環(huán)初始化，使其所有值為2顯示“請(qǐng)輸入消息個(gè)數(shù)”，響蜂鳴器調(diào)用獲取概率函數(shù)，將返回值給y數(shù)組a一維，存放輸入概率數(shù)組b，二維存放編碼過(guò)程概率數(shù)組c，三維，存放編碼每個(gè)位置即時(shí)編碼；數(shù)組d，一維存放碼長(zhǎng)i為整型變量計(jì)數(shù)編碼次數(shù)m為整型n，x為控制循環(huán)整型變量，y為檢錯(cuò)控制整型變量，K為存放平均碼長(zhǎng)浮點(diǎn)型變量，H為存放信源熵浮點(diǎn)型變量，調(diào)用獲取概率函數(shù)，將返回值給yY=0存在錯(cuò)誤，結(jié)束程序圖3主程序流程圖3.3C語(yǔ)言源程序#include<stdio.h>#include<math.h>#definew10floata[w],b[w][w]={0},f[w]={0};inti,c[w][w][w],d[w]={0},m;xiaoxi(){intn;floatP=0;printf("\n請(qǐng)分別輸入消息概率(區(qū)間在[0,1],概率之和應(yīng)為):\n\a");for(n=0;n<m;n++){scanf("%f",&a[n]);if(a[n]>=1||a[n]<=0){printf("出錯(cuò)，概率應(yīng)在[0,1]范圍內(nèi)\n");return(0);break;}P+=a[n];}if(P!=1){printf("出錯(cuò)，概率和應(yīng)為1\n");return(0);}elsereturn(1);}ordination(intf,float*e){intg,j;floatk;for(g=0;g<f-1;g++)for(j=g+1;j<f;j++)if(e[g]<e[j]){k=e[g];e[g]=e[j];e[j]=k;}}coding(){intj,k,t,r;i=m-3;r=0;c[i+1][0][0]=0;c[i+1][1][0]=1;for(;i>=0;i--){t=0;for(k=m-2-i;k>=0;k--){if((f[i]==b[i+1][k])&&(t==0)){t=1;for(r=0;c[i+1][k][r]!=2;r++){c[i][m-i-2][r]=c[i+1][k][r];c[i][m-i-1][r]=c[i+1][k][r];}c[i][m-i-2][r]=0;c[i][m-i-1][r]=1;}}for(j=m-i-3;j>=0;j--)for(k=m-2-i;k>=0;k--)if(b[i][j]=b[i+1][k])for(r=0;c[i+1][k][r]!=2;r++)c[i][j][r]=c[i+1][k][r];}}add(){intj;for(i=0;i<m;i++)b[0][i]=a[i];for(i=1;i<m;i++){b[i][m-i-1]=b[i-1][m-i-1]+b[i-1][m-i];f[i-1]=b[i][m-i-1];for(j=0;j<m-i-1;j++)b[i][j]=b[i-1][j];ordination(m-i,b[i]);}}main(){intn,x,y;floatK=0,H=0;for(n=0;n<w;n++)for(x=0;x<w;x++)for(y=0;y<w;y++)c[n][x][y]=2;printf("\n請(qǐng)輸入消息個(gè)數(shù):\n\a");scanf("%d",&m);printf("\n");y=xiaoxi();if(y=1);{ordination(m,a);add();coding();printf("\n編碼過(guò)程如下:\n");for(n=0;n<m;n++){printf("\n第％d列:",n+1);for(x=0;x<m;x++){if(b[n][x]==0)break;printf("\t%5.4f",b[n][x]);}printf("\n");}printf("\n");for(n=0;n<m;n++){printf("概率為％5審的符號(hào)編碼后碼字為:\t",a[n]);for(x=0;x<m;x++){if(c[0][n][x]==2)break;printf("%d",c[0][n][x]);d[n]++;}K+=a[n]*d[n];H+=(-a[n]*log10l(a[n]))/log10l(2);printf("\t其碼長(zhǎng)為:％d\n",d[n]);}printf("\n平均碼長(zhǎng)K=");printf("%3.2f",K);printf("\n信源?=%3.2f",H);printf("\n編碼效率n=(H/K)=%3.2f%%”,H*100/K);printf("\n冗余度y=(-n)=%3.2f\n",1-H/K);}}

3.4程序步驟及運(yùn)行本程序會(huì)對(duì)輸入的概率自動(dòng)檢錯(cuò)，任何輸入大于1或小于0的概率，或概率之和不等于1，系統(tǒng)都會(huì)提示錯(cuò)誤。Q3C:\Windosyste-m32\cmcle-jce-請(qǐng)輸入消息個(gè)數(shù)：8請(qǐng)分別輸入消息概率｛區(qū)間在[oq],概宰之和應(yīng)為M：0.020.03001Q.760OSQ.430.050.03出諸，概率,和應(yīng)為1圖4仿真糾錯(cuò)情況及結(jié)果進(jìn)行哈弗曼編碼:第一步，輸入你所需要的概率個(gè)數(shù)：如你需要輸入概率x1~x8，請(qǐng)輸入8,點(diǎn)回車(chē)鍵。第二步，輸入你所需要的概率，程序會(huì)自動(dòng)排序：如輸入概*x1~x8，分別點(diǎn)回車(chē)鍵確認(rèn)，否則請(qǐng)按退格鍵。第三步，輸入完成后，按下回車(chē)鍵，程序會(huì)出現(xiàn)結(jié)果。圖5哈夫曼（1,0）編碼運(yùn)行結(jié)果顯示各列重新排列的概率值

刃'D^ProgramFilesrxB&)\Micnc?softVisualStudio\Cofhftion\MSDev9&\Bin\Debug\a.exe'|i=i|即圖5哈夫曼（1,0）編碼運(yùn)行結(jié)果顯示各列重新排列的概率值Q.060.950.64請(qǐng)分別輸入消息概率0.390.17G.12Q.060.950.64編嗎過(guò)程0.39900.17000.120Q0.109Q0.0GS06.05000.04000.39300.17000.12G00.10300.39900.17000.120Q0.109Q0.0GS06.05000.04000.39300.17000.12G00.10300.0900&.07G06.OGO0第3.列0.12000.13300.17600.39300.2560Q.36Q00.3990第6列;0.39001.909012344455為為為為為為為為rzTrrdTnTTnT?0.12000.13300.17600.39300.2560Q.36Q00.3990第6列;0.39001.909012344455為為為為為為為為rzTrrdTnTTnT?馬馬rdTrzrr

-.fl?而???而彳

其其苴箕苴八其其苴一1nniun0000oiso0101HMH1kl00011^ZT..'.-1.■習(xí),--,^rx^rx^-,\7圭主了壬車(chē)馬馬rfTrfT馬Fd^rdrrdrLLF馬馬馬馬馬馬馬局同扁扁扁肩扁扁號(hào)號(hào)號(hào)號(hào)號(hào)號(hào)號(hào)號(hào)符3第差弟u^iV—MJVL^MIrn—:-CT"-,r^r~Tlj*n2.__h.口.--Ij^TTAl—I「3.390SH.17RR9.1G0@3.070G3.3G0@W-MhWM9.&—-c~.—-c~.志芯上查基X忐慕十rnn:-3J.1■mam"T-m-lmXHaJ4mi平力碼長(zhǎng)W-2.fc3輕源fr2-5S編袒效=<HZK>=VB.W1XL冗余度T=(1-n)=0-02Pressanytocont±nue圖6哈夫曼（0,1）編碼樹(shù)運(yùn)行結(jié)果顯示各列重新排列的概率值從運(yùn)行結(jié)果可知該結(jié)果與理論一致，并且可以看出哈夫曼編碼的3個(gè)特點(diǎn)：（1）哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼。（2）縮減信源的最后二個(gè)碼字總是最后一位碼元不同，前面各位碼元相同（二元編碼情況），從而保證了哈夫曼是即時(shí)碼。（3）每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)。這三個(gè)特點(diǎn)保證了所得的哈夫曼碼一定是最佳碼。因此哈夫曼是一種應(yīng)用廣泛而有效的數(shù)據(jù)壓縮技術(shù)。利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，加快信息傳輸速度，降低傳輸成本。數(shù)據(jù)壓縮的過(guò)程稱為編碼，解壓的過(guò)程稱為譯碼。進(jìn)行信息傳遞時(shí)，發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)（明文）預(yù)先編碼，而接受端將傳來(lái)的數(shù)據(jù)（密文）進(jìn)行譯碼。第4章總結(jié)本次課程設(shè)計(jì)，讓我對(duì)哈夫曼編碼以及c語(yǔ)言有了更深的理解和操作能力。開(kāi)始針對(duì)題目進(jìn)行分析，將所涉及的知識(shí)點(diǎn)，及相關(guān)函數(shù)做了分析，大體能夠把握整體的設(shè)計(jì)流程及思路。再通過(guò)查閱相關(guān)資料，使自己的知識(shí)也更加豐富了，明白了哈夫曼編碼的原理以及仿真的實(shí)現(xiàn)。首先對(duì)給題目進(jìn)行了計(jì)算，進(jìn)行哈夫曼編碼，求出平均碼長(zhǎng)，編碼效率，開(kāi)始時(shí)不是很順利，以前學(xué)的很多書(shū)本上的東西記得不太清楚了，經(jīng)過(guò)復(fù)習(xí)課本的內(nèi)容，掌握原理后順利求出結(jié)果。然后是利用c語(yǔ)