信息論實驗信源的二元Huffman編碼

1、精選優(yōu)質(zhì)文檔-傾情為你奉上信源的二元Huffman編碼一. 實驗?zāi)康娜芜xC語言，C+，或MATLAB等一種方法編寫程序，對離散信源進(jìn)行二元Huffman編碼，計算平均碼長及編碼效率，并通過12個運(yùn)行的結(jié)果，驗證程序的正確性。通過實驗，掌握r元Huffman編碼的方法，學(xué)會平均碼長與編碼效率等常見計算。二. 實驗內(nèi)容編寫程序?qū)崿F(xiàn)：輸入：信源的分布，；輸出：二元變長碼，平均碼長，編碼效率。三. 實驗方案或步驟（程序設(shè)計說明）(1)把信源符號(i=1,2,m)出現(xiàn)的概率按由大到小的順序排列；(2)對兩個概率最小的符號分別標(biāo)“0”和“1”，然后把這兩個概率相加作為一個新的輔助符號的概率；(3)將這個新

2、的輔助符號與其他符號一起重新按概率大小順序排列；(4)跳到第2步，直到出現(xiàn)概率相加為1為止；(5)用線將符號連接起來，得到一個碼樹，樹的m個端點對應(yīng)m個信源符號；(6)從最后一個概率為1的節(jié)點開始，沿著碼樹分別到達(dá)每個信源符號，將一路遇到的“0”和“1”順序排列起來，就是對應(yīng)端點的信源符號的碼字。四. 實驗程序（經(jīng)調(diào)試后正確的源程序）p=input('n輸入信源X的分布,格式p1 p2 pm：n');if (length(find(p<0)=0) error('數(shù)組中概率有負(fù)的');%p概率為負(fù)拒絕編碼endif (abs(sum(p)-1)>10e

3、-10) error('概率之和不為1');%概率之和與1差的絕對值大于10的負(fù)10次方endn=length(p);%數(shù)組中元素的個數(shù)，循環(huán)操作用q=p;%信源的概率賦給q，以便后面排序、合并用m=zeros(n-1,n);%定義m為零數(shù)組，記錄排列順序（小概率求和后再重新排列，這就存在排序的問題）for i=1:n-1 q,k=sort(q);%k是排列后的順序，sort(q)是對q進(jìn)行升序 m(i,:)=k(1:n-i+1),zeros(1,i-1);%概率小的相加之后重新排序，排列順序記錄在m矩陣中 q=q(1)+q(2),q(3:n),1;%最后兩個概率小的合并成一個

4、 end for i=1:n-1 c(i,:)=blanks(n*n);%blanks(n*n)是一個1行n*n列的數(shù)組，里面是空的end c(n-1,n)='0'%把c這個空數(shù)組的(n-1,n)這個位置賦值0c(n-1,2*n)='1'%把c這個空數(shù)組的(n-1,2*n)這個位置賦值1for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)=1)-(n-2):n*(find(m(n-i+1,:)=1); c(n-i,n)='0' c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-

5、i,2*n)='1' for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(m(n-i+1,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1); endendfor i=1:n h(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n);%h是Huffman編碼 ll(i)=length(find(abs(h(i,:)=32);%ll為各碼的碼長endla=sum(p.*ll);%la是平均碼長H=sum(-p.*log2(p);%H是信息熵RW=H/la;%

6、RW是編碼效率for i=1:n%顯示概率及Huffman編碼 fprintf('概率：%g編碼：%sn',p(i),h(i,:)endfprintf('平均碼長為： %gn',la)%顯示平均碼長fprintf('編碼效率為： %gn',RW)%顯示編碼效率%例1：p=0.2,0.3,0.4,0.06,0.04;%例2：p=0.18,0.17,0.01,0.15,0.2,0.19,0.1;五程序運(yùn)行結(jié)果（列舉2-3個）輸入信源X的分布,格式p1 p2 pm：0.2,0.3,0.4,0.06,0.04概率：0.2編碼： 111概率：0.3編碼： 10概率：0.4編碼： 0概率：0.06編碼： 1101概率：0.04編碼： 1100平均碼長為： 2編碼效率為： 0.輸入信源X的分布,格式p1 p2 pm：0.18,0.17,0.01,0.15,0.2,0.19,0.1概率：0.18編碼： 111概率：0.17編碼： 110概率：0.01編碼： 1000概率：0.15編碼： 101概率：0.2編碼： 01概率：0.19編碼： 00概率：0.1編碼： 1001平均碼長為： 2.72編碼效率為： 0.六實驗總結(jié)及心得體會Huffman編碼方法是數(shù)據(jù)結(jié)構(gòu)課程中的一個重要內(nèi)容，當(dāng)時是用二叉樹來實現(xiàn)的。在信息論與編碼中，Huff