信息論霍夫曼、香農(nóng)-費諾編碼

1、信息論霍夫曼、香農(nóng)-費諾編碼信息論第二次作業(yè)數(shù)據(jù)壓縮算法的實現(xiàn)班別： 1307011 班學(xué)號：名：黃丹丹一、實驗?zāi)康模? 費諾編碼和霍夫通過該實驗，利用香農(nóng)編碼 曼編碼實現(xiàn)圖像數(shù)據(jù)壓縮。二、實驗原理：1、香農(nóng) - 費諾編碼首先 , 將信源符號 以概率遞減 的次序排 列進來，將排列好的信源符號劃分為兩大組， 使第組的 概率和近于 相同, 并各賦 于一個二 元碼符號” 0”和” 1”. 然后，將每一大組的 信源符號再分成兩組，使同一組的兩個小組 的概率和近于相同，并又分別賦予一個二元 碼符號。依次下去，直至每一個小組只剩下 一個信源符號為止。這樣，信源符號所對應(yīng) 的碼符號

2、序列則為編得的碼字。譯碼原理， 按照編碼的二叉樹從樹根開始，按譯碼序列 進行逐個的向其葉子結(jié)點走，直到找到相應(yīng) 的信源符號為止。之后再把指示標(biāo)記回調(diào)到 樹根，按照同樣的方式進行下一序列的譯碼 到序列結(jié)束。如果整個譯碼序列能夠完整的 譯出則返回成功，否則則返回譯碼失敗。2、霍夫曼編碼 霍夫曼編碼屬于碼詞長度可變的編碼 類，是霍夫曼在 1952 年提出的一種編碼方法， 即從下到上的編碼方法。同其他碼詞長度可 變的編碼一樣，可區(qū)別的不同碼詞的生成是 基于不同符號出現(xiàn)的不同概率。生成霍夫曼 編碼算法基于一種稱為“編碼樹” （ coding tree ）的技術(shù)。算法步驟如下： （ 1）初始化，根據(jù)符號概

3、率的大小按由大到 小順序?qū)Ψ栠M行排序。（ 2 ）把概率最小的兩個符號組成一個新符號 （節(jié)點），即新符號的概率等 于這兩個符號概率之和。（ 3）重復(fù)第 2 步，直到形成一個符號為止 （樹），其概率最后等于 1 。（ 4）從編碼樹的根開始回溯到原始的符號， 并將每一下分枝賦值為 1，上 分枝賦值為 0。三、實驗環(huán)境matlab7.1四、實驗內(nèi)容1、對于給定的信源的概率分布，用香農(nóng)- 費諾編碼實現(xiàn)圖像壓縮2、對于給定的信源的概率分布，用霍夫曼編 碼實現(xiàn)圖像壓縮五、實驗過程1. 香農(nóng) -費諾編碼編碼 1function c=shannon(p)%p=0.2 0.15 0.15 0.1 0.1 0.1

4、 0.1 0.1%shannon(p)p,index=sort(p)p=fliplr(p) n=length(p)pa=0for i=2:npa(i)= pa(i-1)+p(i-1) end k=ceil(-log2(p) c=cell(1,n) for i=1:nci= ” tmp=pa(i) for j=1:k(i) tmp=tmp*2 if tmp>=1 tmp=tmp-1 ci(j)='1'elseci(j) = '0'endendendc = fliplr(c)c(index)=c編碼 2clc;clear;A=0.4,0.3,0.1,0.09,

5、0.07,0.04;A=fliplr(sort(A);% 降序排列 m,n=size(A);for i=1:nB(i,1)=A(i);% 生成 B的第 1 列 end%生成 B第 2 列的元素a=sum(B(:,1)/2;for k=1:n-1 ifabs(sum(B(1:k,1)-a)<=abs(sum(B(1:k+1,1)-a)break;endendfor i=1:n%生成 B第 2 列的元素if i<=k B(i,2)=0; elseB(i,2)=1; end end %生成第一次編碼的結(jié)果END=B(:,2)'END=sym(END);%生成第 3 列及以后幾列的

6、各元素 j=3;while (j=0) p=1;while(p<=n) x=B(p,j-1); for q=p:n if x=-1 break; else if B(q,j-1)=x y=1;continue;else y=0; break;endendend if y=1 q=q+1;endif q=p|q-p=1 B(p,j)=-1;else if q-p=2 B(p,j)=0;END(p)=char(END(p),'0' B(q-1,j)=1;END(q-1)=char(END(q-1),'1' elsea=sum(B(p:q-1,1)/2;for

7、k=p:q-2ifabs(sum(B(p:k,1)-a)<=abs(sum(B(p:k+1, 1)-a);break;endendfor i=p:q-1if i<=kB(i,j)=0;END(i)=char(END(i),'0'elseB(i,j)=1;END(i)=char(END(i),'1'endendend endp=q;endC=B(:,j);D=find(C=-1);e,f=size(D);if e=nj=0;elsej=j+1;endendBAENDfor i=1:nu,v=size(char(END(i);L(i)=v;endavlen=sum(L.*A)2. 霍夫曼編碼 function c=huffman(p) n=size(p,2)if n=1c=cell(1,1)c1=''returnendp1,i1=min(p)index=(1:i1-1),(i1+1:n) p=p(index)n=n-1p2,i2=min(p)index2=(1:i2-1),(i2+1:n) p=p(index2);i2=index(i2) index