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

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

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

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

4、logK,就可能有NM從而提高信息載荷的效率。由上面這個(gè)條件可以看出，H(U)離logK越遠(yuǎn),通過編碼所能獲得的效率改善就越顯著。實(shí)質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性，通過選擇足夠大的M把本來各個(gè)符號概率不等因而H(C)logK的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。離散無記憶信源的變長編碼定理變長編碼是指V的各個(gè)碼字的長度不相等。只要V中各個(gè)碼字的長度Ni(i=1,，|V|)滿足克拉夫特不等式這|V|個(gè)碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列為，式中A=ck|k=1,K

5、,符號熵為H(U)，對U進(jìn)行唯一可譯的變長編碼，編碼字母表B的符號數(shù)為L,即B=bl|l=1,丄,那么必定存在一種編碼方法，使編出的碼字Vi=(vi1,viNi)，(i=1,，|V|)，具有平均長度嚻：MH(U)/logLw嚻M-(U)/logL+1若L=K,則當(dāng)H(C)logK=logL時(shí)，必有嚻MH(U)離logK越遠(yuǎn)，則嚻越小于具體實(shí)現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費(fèi)諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號這個(gè)原則來實(shí)現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時(shí)，通過遵守克拉夫特不

6、等式關(guān)系來實(shí)現(xiàn)碼字的唯一可譯。以上幾個(gè)編碼定理，在有記憶信源或連續(xù)信源的情形也有相應(yīng)的類似結(jié)果。在實(shí)際工程應(yīng)用中，往往并不追求無差錯(cuò)的信源編碼和譯碼，而是事先規(guī)定一個(gè)譯碼差錯(cuò)率的容許值，只要實(shí)際的譯碼差錯(cuò)率不超過這個(gè)容許值即認(rèn)為滿意(見信息率-失真理論和多用戶信源編碼)。二、Huffman編碼霍夫曼編碼方法的具體過程是：首先把信源的各個(gè)輸出符號序列按概率遞降的順序排列起來，求其中概率最小的兩個(gè)序列的概率之和，并把這個(gè)概率之和看作是一個(gè)符號序列的概率，再與其他序列依概率遞降順序排列(參與求概率之和的這兩個(gè)序列不再出現(xiàn)在新的排列之中)，然后，對參與概率求和的兩個(gè)符號序列分別賦予二進(jìn)制數(shù)字o和1。繼

7、續(xù)這樣的操作，直到剩下一個(gè)以1為概率的符號序列。最后，按照與編碼過程相反的順序讀出各個(gè)符號序列所對應(yīng)的二進(jìn)制數(shù)字組，就可分別得到各該符號序列的碼字。三、Huffman編碼的Matlab源程序1、Huffman源程序p=input(pleaseinputanumber:)%提示輸入界面n=length(p);fori=1:nifp(i)0fprintf(nThesumoftheprobabilitiesinhuffmancanmorethan1!n);p=input(pleaseinputanumber:)%如果輸入的概率數(shù)組總和大于1，則重新輸入概率數(shù)組end%生成一個(gè)n-1行n列的數(shù)組%生成

8、一個(gè)n-1行n列的數(shù)組q=p;a=zeros(n-1,n);fori=1:n-1q,l=sort(q)q,l=sort(q)a(i,:)=l(1:n-i+1),zeros(1,i-1)q=q(1)+q(2),q(3:n),1;%對概率數(shù)組q進(jìn)行從小至大的排序，并且用l數(shù)組返回一個(gè)數(shù)組，該數(shù)組表示概率數(shù)組q排序前的順序編號%由數(shù)組l構(gòu)建一個(gè)矩陣，該矩陣表明概率合并時(shí)的順序，用于后面的編碼%將排序后的概率數(shù)組q的前兩項(xiàng)，即概率最小的兩個(gè)數(shù)加和，得到新的一組概率序列fori=1:n-1c(i,1:n*n)=blanks(n*n);fori=1:n-1c(i,1:n*n)=blanks(n*n);en

9、dc(n-1,n)=0;c(n-1,2*n)=1;end%生成一個(gè)n-1行n列，并且每個(gè)元素的的長度為n的空白數(shù)組，c矩陣用于進(jìn)行huffman編碼，并且在編碼中與a矩陣有一定的對應(yīng)關(guān)系%由于a矩陣的第n-1行的前兩個(gè)元素為進(jìn)行huffman編碼加和運(yùn)算時(shí)所得的最后兩個(gè)概率，因此其值為0或1，在編碼時(shí)設(shè)第n-1行的第一個(gè)空白字符為0，第二個(gè)空白字符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的第一個(gè)元素的n-1的字符賦值為對應(yīng)于a矩陣中第n-i+1行中值為1

10、的位置在c矩陣中的編碼值c(n-i,n)=0%根據(jù)之前的規(guī)則，在分支的第一個(gè)元素最后補(bǔ)0c(n-i,n+1:2*n-1)=c(n-i,1:n-1)%矩陣c的第n-i的第二個(gè)元素的n-1的字符與第n-i行的第一個(gè)元素的前n-1個(gè)符號相同，因?yàn)槠涓?jié)點(diǎn)相同c(n-i,2*n)=1forj=1:i-1%根據(jù)之前的規(guī)則，在分支的第一個(gè)元素最后補(bǔ)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的前面一個(gè)元素的位置在c矩陣中的編碼值endendend%完成huffman碼字的分配fori=1:nh(i,1:n)=c(1,n*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n)%用h表示最后的huffman編碼，矩陣h%計(jì)算每一個(gè)huffman編碼的長度%計(jì)算每一個(gè)huffman編碼的長度的第i行的元素對應(yīng)于矩陣c的第一行的第i個(gè)元素ll(i)=length(find(abs(h(i,:)=32)endl=sum(p.*ll);%計(jì)算平均碼長fprintf(nhuffmancode:n);hhh=sum(p.*(-log2(p);%計(jì)算信源熵fprintf