信息論與編碼課程大作業(yè)二進制哈夫曼編碼

1、信息論與編碼課程大作業(yè)題目：二進制哈夫曼編碼學(xué)生姓名：學(xué)號：2010020200專業(yè)班級：2010級電子信息班2013年5月18日二進制哈夫曼編碼1、二進制哈夫曼編碼的原理及步驟1、1信源編碼的計算設(shè)有N個碼元組成的離散、無記憶符號集，其中每個符號由一個二進制碼字表示，信源符號個數(shù)n、信源的概率分布P=p(si),i=1,.,n。且各符號xin的以li個碼兀編碼，在變長字編碼時每個符號的平均碼長為Lp(xi)li;i1n信源嫡為：H(X)p(xi)10gp(xi);i1n唯一可譯碼的充要條件：mKi1；i1其中m為碼符號個數(shù)，n為信源符號個數(shù)，Ki為各碼字長度。構(gòu)造哈夫曼數(shù)示例如下圖所示。0.

2、030.03|0.040.051、2二元霍夫曼編碼規(guī)則(1)將信源符號依出現(xiàn)概率遞減順序排序。(2)給兩個概率最小的信源符號各分配一個碼位“0”和“1”，將兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含（n-1）個信源符號的新信源。稱為信源的第一次縮減信源,用si表示。（3）將縮減信源si的符號仍按概率從大到小順序排列，重復(fù)步驟（2）,得到只含（n-2）個符號的縮減信源s20（4）重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1,然后從最后一級縮減信源開始，依編碼路徑向前返回,就得到各信源符號所對應(yīng)的碼字。1、3二元哈夫曼

3、編碼流程圖如下圖所示。2、二元哈夫曼編碼程序p=input('pleaseinputanumber:')%提示輸入界面n=length(p);fori=1:nifp(i)<0fprintf('nTheprobabilitiesinhuffmancannotlessthan0!n');p=input('pleaseinputanumber:')%如果輸入的概率數(shù)組中有小于0的值，endendifabs(sum(p)-1)>0fprintf('nThesumoftheprobabilitiesinhuffmancanmoretha

4、n1!n');p=input('pleaseinputanumber:')%如果輸入的概率數(shù)組總和大于1，則重endq=p;a=zeros(n-1,n);%生成一個n-1行n列的數(shù)組fori=1:n-1q,l=sort(q);%寸概率數(shù)組q進行從小至大的排序，并且用l數(shù)組返回一個q排序前的順序編號a(i,:)=l(1:n-i+1),zeros(1,i-1);%由數(shù)組l構(gòu)建一個矩陣，該矩陣表明概率合并q=q(1)+q(2),q(3:n),1;%將排序后的概率數(shù)組q的前兩項，即概率最小的兩endfori=1:n-1c(i,1:n*n)=blanks(n*n);endc(n-

5、1,n尸'0'燦于a矩陣的第n-1行的前兩個元素為進行huffman編碼加和運算時所得的最c(n-1,2*n)='1'fori=2:n-1c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)=1)-(n-2):n*(find(a(n-i+1,:)=1);c(n-i,n)='0'%根據(jù)之前的規(guī)則，在分支的第一個元素最后補0c(n-i,n+1:2*n-1)=c(n-i,1:n-1);c(n-i,2*n)='1'%根據(jù)之前的規(guī)則，在分支的第一個元素最后補1forj=1:i-1c(n-i,(j+1)*n+1:(j

6、+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)=j+1)-1)+1:n*find(a(n-i+1,:)=j+1);endend%完成huffman碼字的分配fori=1:nh(i,1:n)=c(1,n*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n);ll(i)=length(find(abs(h(i,:)=32);%計算每一個huffman編碼的長度enddisp('二元霍夫曼編碼平均碼長)l=sum(p.*ll)%計算平均碼長%fprintf('nhuffmancode:n');hdisp('信源嫡')

7、hh=sum(p.*(-log2(p)%計算信源熵%fprintf('nthehuffmaneffciency:n');disp('編碼效率)t=hh/l%計算編碼效率3、運行結(jié)果及分析當(dāng)輸入數(shù)據(jù)0.01,0.02,0.03,0.04,0.10,0.15,0.20,0.25,0.20時3、 1運行結(jié)果：pleaseinputanumber:0.01,0.02,0.03,0.04,0.10,0.15,0.20,0.25,0.20p=Columns1through50.01000.02000.03000.04000.1000Columns6through90.15000.2

8、0000.25000.2000二元霍夫曼編碼平均碼長l=2.7400h=11101001110101111011111001111110001001信源熵hh=2.6883編碼效率t=0.98113、2分析：1 、在哈弗曼編碼的過程中，對縮減信源符號按概率有大到小的順序重新排列，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。2 、哈弗曼編碼效率相當(dāng)高，對編碼器的要求也簡單得多。3 、哈弗曼它保證了信源概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，每次縮減信源的最后兩個碼字總是最后一位碼元不同，前面的各位碼元都相同，每次縮減信源的最長兩個碼

9、字有相同的碼長。4 、哈弗曼的編法并不一定是唯一的。4、體會此次設(shè)計用matlab編程實現(xiàn)哈夫曼對信源無失真編碼。由于課本知識點的不太理解，一點都不知道編碼的過程，后來通過閱讀<<信息論與編碼>>課本、網(wǎng)上查閱資料，最后才對本次設(shè)計有了一定的理解，詳細理解了哈夫曼的具體編碼過程。經(jīng)過理解，發(fā)現(xiàn)這種編碼其實挺簡單的，最重要的是怎樣用程序把他實現(xiàn)，這對我們的編程能力也是一次考驗。設(shè)計要求中要求計算信源嫡，這又考察了現(xiàn)代通信原理的知識。所以這次設(shè)計所設(shè)計的知識面廣，有利于我們對相關(guān)知識進一步加深、鞏固。更加深刻的感覺到哈夫曼編碼能夠大大提高通信的效率通過這次設(shè)計，讓我明白，在平時的學(xué)習(xí)中，對于每一個知識點都不能一知半解，否則在具體的實際運用中就會現(xiàn)“原形”。比如這次哈夫曼編碼，如果我們只讀一下它的編碼過程的步驟，不實際舉一個例子來驗證，我們就很有可能在很多地方犯錯。所以需要我們在閱讀課本的時候還要仔細思考課本有關(guān)編碼的示例，這對于我們掌握課本知識尤其重要的。這次設(shè)計編程的思路，編輯，調(diào)試等讓我明白編程時一定要保持清醒的頭腦，有嚴謹?shù)乃季S才能將實驗要求實現(xiàn)得完整；調(diào)試過程會發(fā)現(xiàn)很多問題，這時不能