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

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

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

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

4、符號熵H( U)<log K,因此，上述條件還可以表示為【H(C)+ &】/log L< MM< log K/log L 特別，若有 K=L,那么，只要 H( C)<log K,就可能有 N<M從而提高信息載荷的效率。由上面這個條件可以看出，H(U)離log K越遠,通過編 碼所能獲得的效率改善就越顯著。實質(zhì)上，定長編碼方法提高信息載荷能力的關(guān) 鍵是利用了漸近等分性，通過選擇足夠大的M把本來各個符號概率不等因而H( C)<log K的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。離散無記憶信源的變長編碼定理變長編

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

6、 H(U)離log K越遠，則嚻越小于具體實現(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ī)定一個譯碼差錯率的容許值，只要實際的譯碼差錯率不超過這個容許值即認為滿意(見 信息率-失真理論和多用戶信源編碼)。二、Huffman

7、 編碼霍夫曼編碼方法的具體過程是：首先把信源的各個輸出符號序列按概率遞降 的順序排列起來，求其中概率最小的兩個序列的概率之和，并把這個概率之和看 作是一個符號序列的概率，再與其他序列依概率遞降順序排列(參與求概率之和 的這兩個序列不再出現(xiàn)在新的排列之中)，然后，對參與概率求和的兩個符號序 列分別賦予二進制數(shù)字o和1。繼續(xù)這樣的操作，直到剩下一個以1為概率的符號序 列。最后，按照與編碼過程相反的順序讀出各個符號序列所對應(yīng)的二進制數(shù)字組， 就可分別得到各該符號序列的碼字。三、Huffman編碼的Matlab源程序1、Huffman源程序p=in put('please in put a n

8、u mber:') % 提示輸入界面 n=len gth(p);for i=1: nif p(i)<0fprin tf('n The probabilities in huffma n can no t less tha n 0!n');p=i nput('please in put a number:')%如果輸入的概率數(shù)組中有小于0的值，則重新輸入概率數(shù)組endendif abs(sum(p)-1)>0fprin tf('n The sum of the probabilities in huffma n can more tha

9、 n 1!n');p=i nput('please in put a number:')%如果輸入的概率數(shù)組總和大于1,則重新輸入概率數(shù)組endq=p;a=zeros (n-1, n);for i=1: n-1q,l=sort(q)%生成一個n-1行n列的數(shù)組%對概率數(shù)組q進行從小至大的排序，并且用1數(shù)組返回一個數(shù)組，該數(shù)組表示概率數(shù)組q排序前的順序編號a(i,:)=l(1:n-i+1),zeros(1,i-1)%由數(shù)組I構(gòu)建一個矩陣，該矩陣表明概率合并時的順序，用于后面的編碼q=q(1)+q(2),q(3: n),1;%將排序后的概率數(shù)組q的前兩項，即概率最小的兩個數(shù)

10、加和， 得到新的一組概率序列endfor i=1: n-1c(i,1: n*n )=bla nks( n*n);%生成一個n-1行n列，并且每個元素的的長度為n的空白數(shù)組，c矩陣用于進行huffman編碼，并且在編碼中與 a矩陣有一定的對應(yīng)關(guān)系endc(n-1,n)='0：%由于a矩陣的第n-1行的前兩個元素為進行 huffman編碼加和運算時所得的最c(n-1,2* n)='1：后兩個概率，因此其值為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

11、)-(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)='0'%根據(jù)之前的規(guī)則，在分支的第一個元素最后補0c(n-i,n+1:2*n-1)=c(n-i,1:n-1)%矩陣c的第n-i的第二個元素的n-1的字符與第n-i行的第一個元素的前n-1個符號相同，因為其根節(jié)點相同c(n-i,2* n)='1' for j=1:i-1%根據(jù)之前的規(guī)則，在分支的第一個元素最后補1c(n-i,(j+1)* n+1:(j+2)* n)=c(

12、 n-i+1, n*(fi nd(a( n-i+1,:)=j+1)-1)+1: n*fin d(a( n-i+1,:)=j+1) %矩陣c中第n-i行第j+1列的值等于對應(yīng)于a矩陣中第n-i+1行中值為j+1的前面一 個元素的位置在c矩陣中的編碼值endendfor i=1: n%完成huffman碼字的分配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);%計算平均碼長fprin tf('n huffma n code:n');hhh=sum(p.*(-log2(p);