huffman編碼用matlab的實現(xiàn)[共5頁]

1、 Huffman編碼用MTLAB的實現(xiàn)及編碼注釋 一、實驗?zāi)康?、學(xué)習(xí)Matlab軟件的使用和編程；2、進一步深入理解Huffman編碼算法的原理；3、提高獨立進行算法編程的能力。二、實驗環(huán)境硬件：計算機軟件：Windows 2003和MATLAB編程環(huán)境。三、實驗內(nèi)容1、用Matlab實現(xiàn)Huffman編碼算法程序；2、要求程序輸出顯示所有的碼字以及編碼效率； 3、設(shè)計簡單的輸入界面（可以是簡單的文字提示信息），程序運行時提示用 戶輸入代表信源符號概率的向量；要對用戶輸入的概率向量進行合法性檢查。四、實驗原理1、二進制Huffman編碼的基本原理及算法(1) 把信源符號集中的所有符號按概率從

2、大到小排隊。(2) 取概率最小的兩個符號作為兩片葉子合并（縮減）到一個 節(jié)點。(3) 視此節(jié)點為新符號，其概率等于被合并（縮減）的兩個概率之和，參與概率排隊。(4) 重復(fù)(2)(3)兩步驟，直至全部符號都被合并（縮減）到根。 (5) 從根出發(fā)，對各分枝標記0和1。從根到葉的路徑就給出了各個碼字的編碼和碼長。2、程序設(shè)計的原理 (1)程序的輸入：以一維數(shù)組的形式輸入要進行huffman編碼的信源符號的概率，在運行該程序前，顯示文字提示信息，提示所要輸入的概率矢量；然后對輸入的概率矢量進行合法性判斷，原則為：如果概率矢量中存在小于0的項，則輸入不合法，提示重新輸入；如果概率矢量的求和大于1，則輸入

3、也不合法，提示重新輸入。（2）huffman編碼具體實現(xiàn)原理： 1在輸入的概率矩陣p正確的前提條件下,對p進行排序，并用矩陣L記錄p排序之前各元素的順序，然后將排序后的概率數(shù)組p的前兩項，即概率最小的兩個數(shù)加和，得到新的一組概率序列，重復(fù)以上過程，最后得到一個記錄概率加和過程的矩陣p以及每次排序之前概率順序的矩陣a。2新生成一個n-1行n列，并且每個元素含有n個字符的空白矩陣，然后進行huffman編碼： 將c矩陣的第n-1行的第一和第二個元素分別令為0和1（表示在編碼時，根 節(jié)點之下的概率較小的元素后補0，概率較大的元素后補1，后面的編碼都遵守這個原則） 然后對n-i-1的第一、二個元素進行

4、編碼，首先在矩陣a中第n-i行找到值為1所在的位置，然后在c矩陣中第n-i行中找到對應(yīng)位置的編碼（該編碼即為第n-i-1行第一、二個元素的根節(jié)點），則矩陣c的第n-i行的第一、二個元素的n-1的字符為以上求得的編碼值，根據(jù)之前的規(guī)則，第一個元素最后補0，第二個元素最后補1，則完成該行的第一二個元素的編碼， 最后將該行的其他元素按照“矩陣c中第n-i行第j+1列的值等于對應(yīng)于a矩陣中第n-i+1行中值為j+1的前面一個元素的位置在c矩陣中的編碼值”的原則進行賦值，重復(fù)以上過程即可完成huffman編碼。3計算信源熵和平均碼長，其比值即為編碼密碼效率。五、Huffman編碼的Matlab源程序p=

5、input(please input a number:) n=length(p);for i=1:n if p(i)0 fprintf(n The sum of the probabilities in huffman can more than 1!n); p=input(please input a number:) end q=p;a=zeros(n-1,n); for i=1:n-1 q,l=sort(q) a(i,:)=l(1:n-i+1),zeros(1,i-1) q=q(1)+q(2),q(3:n),1; end for i=1:n-1 c(i,1:n*n)=blanks(n*

6、n); end c(n-1,n)=0; c(n-1,2*n)=1; for i=2:n-1 c(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 c(n-i,n+1:2*n-1)=c(n-i,1:n-1) c(n-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(a(n-i+1,:)=j+1)-1)+1:n*find(a(n-i+1,:)=j+1) end end for i=1:n h(i,1:n)=c(1,n

7、*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n) ll(i)=length(find(abs(h(i,:)=32) end l=sum(p.*ll); fprintf(n huffman code:n);hhh=sum(p.*(-log2(p); fprintf(n the huffman effciency:n); t=hh/l 6、 程序運行結(jié)果 七、實驗總結(jié)1、在該實驗的過程中，利用一個矩陣記錄每次排序前概率的所在位置，是該實驗的關(guān)鍵，在編碼的過程中利用該矩陣就能比較容易進行huffman編碼。2、通過這個實驗，對huffman編碼的具體實現(xiàn)原理了解的更加深刻，在實驗的過程中也遇到了一些問題，通過查找資料和相關(guān)書籍得到了解決，通過此次試驗，了解了Huffman編碼的特點，能夠運用Huffm