1二進制哈夫曼編碼的原理及步驟（1）信源編碼的計算設有N個碼元組成的離散、無記憶符號集，其中每個符號由一個二進制碼字表示，信源符號個數(shù)n、信源的概率分布P={p(si)},i=1,…..,n。且各符號xi的以li個碼元編碼，在變長字編碼時每個符號的平均碼長為；信源熵為：；唯一可譯碼的充要條件：；其中m為碼符號個數(shù)，n為信源符號個數(shù)，Ki為各碼字長度。構(gòu)造哈夫曼數(shù)示例如下圖所示。1.000000001.000000000.400.600.400.600.300.300.300.3050.150.090.600.090.600.030.030.040.050.030.030.040.05（2）二元霍夫曼編碼規(guī)則（1）將信源符號依出現(xiàn)概率遞減順序排序。（2）給兩個概率最小的信源符號各分配一個碼位“0”和“1”，將兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含（n-1）個信源符號的新信源。稱為信源的第一次縮減信源，用s1表示。（3）將縮減信源s1的符號仍按概率從大到小順序排列，重復步驟(2)，得到只含（n-2）個符號的縮減信源s2。（4）重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1，然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。2功能介紹輸入一段字符序列，通過本程序可得出該字符序列中各個字符出現(xiàn)的次數(shù)，以及每個字符出現(xiàn)的概率，并能計算出信源符號熵，每個字符的哈弗曼編碼，和相應的平均碼長，編碼效率，碼方差。3算法基本步驟描述得到信源序列得到信源序列輸出得出信源序列輸出得出信源序列個數(shù)得出信源序列的概率輸出計算信源符號熵輸出計算信源符號熵輸出信源符號的哈弗曼編碼輸出信源符號的哈弗曼編碼平均碼長輸出平均碼長輸出輸出編碼效率輸出編碼效率輸出碼方差輸出碼方差4C語言源代碼#include<stdio.h>#include<string.h>#include<math.h>#defineMAX100//定義全局變量h存放信息熵doubleh=0;for(i=0;i<a-1;i++){//min,lmin中存放兩個無父結(jié)點且結(jié)點權(quán)值最小的兩個結(jié)點min=lmin=MAX;//找出所有結(jié)點中權(quán)值最小、無父結(jié)點的兩個結(jié)點，并合并之為一顆二叉樹for(j=0;j<a+i;j++){if((INFORMATION[j].PROBABILITY<min)&&(INFORMATION[j].parent==-1)){lmin=min;lm=m;min=INFORMATION[j].PROBABILITY;m=j;}elseif((INFORMATION[j].PROBABILITY<lmin)&&(INFORMATION[j].parent==-1)){lmin=INFORMATION[j].PROBABILITY;lm=j;}}//設置找到的兩個子結(jié)點m、lm的父結(jié)點信息INFORMATION[m].parent=a+i;INFORMATION[lm].parent=a+i;INFORMATION[a+i].PROBABILITY=INFORMATION[m].PROBABILITY+INFORMATION[lm].PROBABILITY; INFORMATION[a+i].parent=-1;INFORMATION[a+i].lchild=m;INFORMATION[a+i].rchild=lm;} for(i=0;i<a;i++){cd.start=a-1;c=i;p=INFORMATION[c].parent;while(p!=-1)/*父結(jié)點存在*/{if(INFORMATION[p].lchild==c)cd.Code[cd.start]=1;elsecd.Code[cd.start]=0;cd.start--;/*求編碼的低一位*/c=p;p=INFORMATION[c].parent;/*設置下一循環(huán)條件*/}//保存求出的每個葉結(jié)點的哈夫曼編碼和編碼的起始位for(j=cd.start+1;j<m;j++){INFORMATION[i].Code[j]=cd.Code[j];}INFORMATION[i].start=cd.start; }}voidmain(){//定義存放信源符號的數(shù)組 charinformationsource[MAX]; inti,j,m; doubleaverageofhuffmancode=0.0,Eita,cV=0.0; printf("pleaseinputthesourceofinformation:"); for(i=0;;i++){ scanf("%c",&informationsource[i]); if(informationsource[i]=='\n') break; } informationsource[i]='\0'; printf("信源序列為:");//顯示已輸入的一串信源符號 puts(informationsource);//返回不同信源符號的數(shù)目 m=Pofeachsource(informationsource,i);//求信源的符號熵 H(m); printf("信源的符號熵:H(X)=%.3f(比特/符號)\n",h); Huffman(m);//輸出已保存好的所有存在編碼的哈夫曼編碼for(i=0;i<m;i++){printf("%c'sHuffmancodeis:",INFORMATION[i].SOURCECODE);for(j=INFORMATION[i].start+1;j<m;j++)printf("%d",INFORMATION[i].Code[j]); INFORMATION[i].lengthofhuffmancode=m-INFORMATION[i].start-1;printf("\n");}//求哈夫曼編碼的平均碼長和編碼效率 for(i=0;i<m;i++) averageofhuffmancode+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode; printf("哈夫曼編碼的平均碼長為:%lf(碼元/信源符號)\n",averageofhuffmancode); Eita=h/averageofhuffmancode; printf("哈夫曼編碼的編碼效率為:%lf\n",Eita);//求哈弗曼編碼的碼方差 for(i=0;i<m;i++) cV+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode*INFORMATION[i].lengthofhuffmancode; cV-=averageofhuffmancode*averageofhuffmancode; printf("哈弗曼編碼的碼方差為：%lf\n",cV);}5運行結(jié)果截圖:6實驗分析（1）在哈弗曼編碼的過程中，對縮減信源符號按概率有大到小的順序重新排列，應使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復編碼次數(shù)減少，使短碼得到充分利用。（2）哈弗曼編碼效率相當高，對編碼器的要求也簡單得多。（3）哈弗曼它保證了信源概率大的符號對應于短碼，概率小的符號對應于長碼，每次縮減信源的最后兩個碼字總是最后一位碼元不同，前面的各位碼元都相同，每次縮減信源的最長兩個碼字有相同的碼長。（4）哈弗曼的編法并不一定是唯一的。7實驗總結(jié)此次設計用C語言實現(xiàn)哈夫曼對信源無失真編碼。由于課本知識點的不太理解，一點都不知道編碼的過程，后來通過閱讀<<信息論與編碼>>課本、網(wǎng)上查閱資料，最后才對本次設計有了一定的理解，詳細理解了哈夫曼的具體編碼過程。經(jīng)過理解，發(fā)現(xiàn)這種編碼其實挺簡單的，最重要的是怎樣用程序把他實現(xiàn)，這對我們的編程能力也是一次考驗。設計要求中要求計算信源熵，這又考察了現(xiàn)代通信原理的知識。所以這次設計所設計的知識面廣，有利于我們對相關知識進一步加深、鞏固。更加深刻的感覺到哈夫曼編碼能夠大大提高通信的效率通過這次設計，讓我明白，在平時的學習中，對于每一個知識點都不能一知半解，否則在具體的實際運用中就會現(xiàn)“原形”。比如這次哈夫曼編碼，如果我們只讀一下它的編碼過程的步驟，不實際舉一個例子來驗證，我們就很有可能在很多地方犯錯。所以需要我們在閱讀課本的時候還要仔細思考課本有關編碼的示例，這對于我們掌握課本知識