huffman編碼的matlab實現(xiàn).doc

1、文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.Huffman 編碼的 matlab 實現(xiàn)一、信源編碼介紹為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對所施行的變換。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法， 把信源輸出符號序列變換為最短的碼字序列， 使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復(fù)原來的符號序列。既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對信源輸出符號序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預(yù)測、域變換和數(shù)據(jù)壓縮等。當(dāng)然，這些都是廣義的信源編

2、碼。一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個： 使序列中的各個符號盡可能地互相獨立； 使序列中各個符號的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。信源編碼的一般問題可以表述如下：信源編碼若某信源的輸出為長度等于 M的符號序列集合 式中符號 A 為信源符號表，它包含著 K 個不同的符號， A= k|k=1, ,K ，這個信源至多可以輸出 KM個不同的符號序列。記 U =KM。所謂對這個信源的輸出信源編碼進行編碼，就是用一個新的符號表 B 的符號序列集合 V 來表示信源輸出的符號序列集合 U。若 V 的各個序列的長度等于 N，即 式中新的符號

3、表 B 共含 L 個符號，B= bl|l=1, ,L 。它總共可以編出 LN個不同的碼字。類似地 , 記 V=LN。為了使信源的每個輸出符號序列都能分配到一個獨特的碼字與之對應(yīng)， 至少應(yīng)滿足關(guān)系V=LN U =KM或者 N/ M log K/log L下面的幾個編碼定理，提供了解決這個矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。離散無記憶信源的定長編碼定理對于任意給定的 0，只要滿足條件N/ M( H( U)+ )/log L那么，當(dāng) M足夠大時，上述編碼幾乎沒有失真 ; 反之 , 若這個條件不滿足，就不可能實現(xiàn)無失真的編碼。式中 H( U) 是信源輸出序列的符號熵。信源編碼通

4、常，信源的符號熵 H( U)log K，因此，上述條件還可以表示為 【H( U)+ 】 /log LN/ Mlog K/log L 特別，若有 K=L, 那么 , 只要 H( U)log K, 就可能有 NM，1文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.從而提高信息載荷的效率。 由上面這個條件可以看出， H( U) 離 log K 越遠 , 通過編碼所能獲得的效率改善就越顯著。 實質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性，通過選擇足夠大的 M，把本來各個符號概率不等 因而 H( U)log K 的信源輸出符號序列變換為概率均勻的典型序列， 而碼字的唯

5、一可譯性則由碼字的定長性來解決。離散無記憶信源的變長編碼定理變長編碼是指V 的各個碼字的長度不相等。只要V 中各個碼字的長度Ni ( i =1， ， V) 滿足克拉夫特不等式這 V個碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長編碼定理指出： 若離散無記憶信源的輸出符號序列為， 式中 A= k|k=1, ,K, 符號熵為 H( U) ，對 U 進行唯一可譯的變長編碼，編碼字母表 B 的符號數(shù)為 L, 即 B= bl|l=1, ,L, 那么必定存在一種編碼方法，使編出 的碼 字 Vi =( vi1, , viNi) ， ( i =1, , V ) ，具有平 均長度 嚻： MH( U)/log

6、 L嚻 MH( U)/log L+1若 L=K，則當(dāng) H( U)log K=log L 時, 必有嚻 M；H( U) 離 log K 越遠，則嚻越小于M。具體實現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費諾編碼法和霍夫曼編碼法。 其他方法都是這些經(jīng)典方法的變形和發(fā)展。 所有這些經(jīng)典編碼方法， 都是通過以短碼來表示常出現(xiàn)的符號這個原則來實現(xiàn)概率的均勻化，從而得到高的信息載荷效率； 同時，通過遵守克拉夫特不等式關(guān)系來實現(xiàn)碼字的唯一可譯。以上幾個編碼定理，在有記憶信源或連續(xù)信源的情形也有相應(yīng)的類似結(jié)果。在實際工程應(yīng)用中， 往往并不追求無差錯的信源編碼和譯碼， 而是事先規(guī)定一個譯碼

7、差錯率的容許值， 只要實際的譯碼差錯率不超過這個容許值即認為滿意 （見信息率 - 失真理論和多用戶信源編碼） 。二、 Huffman 編碼霍夫曼編碼方法的具體過程是： 首先把信源的各個輸出符號序列按概率遞降的順序排列起來， 求其中概率最小的兩個序列的概率之和， 并把這個概率之和看作是一個符號序列的概率， 再與其他序列依概率遞降順序排列 （參與求概率之和的這兩個序列不再出現(xiàn)在新的排列之中） ，然后，對參與概率求和的兩個符號序列分別賦予二進制數(shù)字 0和1。繼續(xù)這樣的操作 , 直到剩下一個以 1為概率的符號序列。最后，按照與編碼過程相反的順序讀出各個符號序列所對應(yīng)的二進制數(shù)字組，就可分別得到各該符號

8、序列的碼字。三、 Huffman 編碼的 Matlab 源程序1、Huffman 源程序p=input(please input a number:)% 提示輸入界面n=length(p);for i=1:nifp(i)0fprintf(n The sum of the probabilities in huffman can more than 1!n);p=input(please input a number:)% 如果輸入的概率數(shù)組總和大于1，則重新輸入概率數(shù)組endq=p;a=zeros(n-1,n);% 生成一個 n-1 行 n 列的數(shù)組for i=1:n-1q,l=sort(q)

9、%對概率數(shù)組q 進行從小至大的排序，并且用l 數(shù)組返回一個數(shù)組，該數(shù)組表示概率數(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 的前兩項，即概率最小的兩個數(shù)加和，得到新的一組概率序列endfor i=1:n-1c(i,1:n*n)=blanks(n*n);%生成一個 n-1 行 n 列，并且每個元素的的長度為n 的空白數(shù)組， c 矩陣用于進行huffman 編碼，并且在編碼中與a 矩陣有一定的對應(yīng)關(guān)系endc(n-1,n)=0

10、;c(n-1,2*n)=1;%由于 a 矩陣的第 n-1 行的前兩個元素為進行 huffman 編碼加和運算時所得的最后兩個概率， 因此其值為0 或 1，在編碼時設(shè)第 n-1 行的第一個空白字符為0，第二個空白字符 1。for i=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-1 的字符賦值為對應(yīng)于a 矩陣中第 n-i+1 行中值為 1 的位置在 c 矩陣中的編碼值c(n-i,n)=0c(n-i,n+1:2*n-1)=c(n-i,1:n-1)c(n

11、-i,2*n)=1for j=1:i-1%根據(jù)之前的規(guī)則，在分支的第一個元素最后補0%矩陣 c 的第 n-i 的第二個元素的 n-1 的字符與第 n-i 行的第一個元素的前 n-1 個符號相同，因為其根節(jié)點相同%根據(jù)之前的規(guī)則，在分支的第一個元素最后補1c(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) %矩陣 c 中第 n-i 行第 j+1 列的值等于對應(yīng)于 a 矩陣中第 n-i+1 行中值為 j+1 的前面一個元素的位置在 c 矩陣中的編碼值endend% 完成 huffman 碼字的分配for i=1:n3%計算編碼效率%計算信源熵文檔來源為 :從網(wǎng)絡(luò)收集整理.word 版本可編輯 .歡迎下載支持.h(i,1:n)=c(1,n*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n)%用 h 表示最后的huffman 編碼，矩陣 h的第 i 行的元素對應(yīng)于矩陣c 的第一行的第 i 個元素ll(i)=length(find(abs(h(i,:)=32)%計算每一個 huffman 編碼的長度endl=sum(p.*ll);% 計算平均碼長fprintf(n huffman code:n);hhh=su