1、信息論大作業(yè)電子工程學院班號1. Huffman編碼1 Huffman 編碼原理：將信源符號按概率從大到小的順序排列，令p(x1) p(x2) p(xn)給兩個概率最小的信源符號p(xn-1)和p(xn)各分配一個碼位“0”和“1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含(n1)個信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號仍按概率從大到小順序排列，重復步驟2，得到只含(n2)個符號的縮減信源S2。重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編

2、碼路徑向前返回，就得到各信源符號所對應的碼字。 2. 霍夫曼編碼優(yōu)缺點：1) 編出來的碼都是異字頭碼，保證了碼的唯一可譯性。2) 由于編碼長度可變。因此譯碼時間較長，使得霍夫曼編碼的壓縮與還原相當費時。3) 編碼長度不統(tǒng)一，硬件實現(xiàn)有難度。4) 對不同信號源的編碼效率不同，當信號源的符號概率為2的負冪次方時，達到100的編碼效率；若信號源符號的概率相等，則編碼效率最低。5) 由于0與1的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能。3.編碼流程： 讀入一幅圖像的灰度值;1. 將矩陣的不同數(shù)統(tǒng)計在數(shù)組c的第一列中;2. 將相同的數(shù)占站整個

3、數(shù)組總數(shù)的比例統(tǒng)計在數(shù)組p中;3. 找到最小的概率,相加直到等于1,把最小概率的序號存在tree第一列中,次小放在第二列,和放在p像素比例之后;4. C數(shù)組第一維表示值,第二維表示代碼數(shù)值大小,第三維表示代碼的位數(shù)；5. 把概率小的值為1標識，概率大的值為0標識；6. 計算信源的熵 ；7. 計算平均碼長 ；8. 計算編碼效率'；9. 計算冗余度。源程序：p=input('請輸入數(shù)據(jù):'); n=length(p);for i=1:n if p(i)<0 fprintf('n 提示：概率值不能小于0!n'); p=input('請重新輸入數(shù)據(jù)

4、:'); endend if abs(sum(p)>1 fprintf('n 哈弗曼碼中概率總和不能大于1!n'); p=input('請重新輸入數(shù)據(jù):'); endq=p;a=zeros(n-1,n); %生成一個n-1 行n 列的數(shù)組 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*n); endc(n-1,n)='0' c(n-1,2*n)=

5、9;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)='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-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);endend %完成huffman 碼字的分配for i=1:nh

6、(i,1:n)=c(1,n*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n); ll(i)=length(find(abs(h(i,:)=32); %計算每一個huffman 編碼的長度endl=sum(p.*ll); %計算平均碼長fprintf('n Huffman編碼結(jié)果為:n'); hfprintf('n 編碼的平均碼長為:n'); lhh=sum(p.*(-log2(p); %計算信源熵fprintf('n 信源熵為:n'); hhfprintf('n 編碼效率為:n'); t=hh/l %計

7、算編碼效率運行結(jié)果為：請輸入數(shù)據(jù):0.1,0.1,0.1,0.2,0.1,0.1,0.2,0.1 Huffman編碼結(jié)果為:h = 1100 1101 010 111 011 000 10 001 編碼的平均碼長為:l = 3 信源熵為:hh = 2.9219 編碼效率為:t =0.97402.fano編碼：Fano碼:費諾編碼屬于概率匹配編碼，但它不是最佳的編碼方法。不過有時也可以得到緊致碼的性能。信源符號以概率遞減的次序排列進來,將排列好的信源符號劃分為兩大組,使第組的概率和近于相同,并各賦于一個二元碼符號”0”和”1”.然后,將每一大組的信源符號再分成兩組,使同一組的兩個小組的概率和近于

8、相同,并又分別賦予一個二元碼符號.依次下去,直至每一個小組只剩下一個信源符號為止.這樣,信源符號所對應的碼符號序列則為編得的碼字。費諾碼編碼的一般步驟如下：（1）將信源消息符號按其出現(xiàn)的概率大小依次排列排列：。（2）將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近似相同，并且對各組賦予一個二進制碼元“0”和“1”。（3）將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之和近似相同，并且對各組賦予一個二進制符號“0”和“1”。以上兩部分在程序中。（4）如此重復，直到每個組只剩下一個信源符號為止。在程序中本部分采用遞歸思想。信源符號所對應的碼字即為費諾編碼。費諾編碼特點費諾編碼，

9、它編碼后的費諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率達，編碼效率高，但它屬于概率匹配編碼它不是最佳的編碼方法。源程序：A=input('input the A:');A=fliplr(sort(A);%降序排列m,n=size(A);for i=1:n encoding(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(encoding(:,1)/2;for k=1:n-1 if abs(sum(encoding(1:k,1)-a)<=abs(sum(encoding(1:k+1,1)-a) break; endendfor i=1:n%生成B第2

10、列的元素 if i<=k encoding(i,2)=0; else encoding(i,2)=1; endend%生成第一次編碼的結(jié)果CODE=encoding(:,2)'CODE=sym(CODE);%生成第3列及以后幾列的各元素j=3;while (j=0) p=1; while(p<=n) x=encoding(p,j-1); for q=p:n if x=-1 break; else if encoding(q,j-1)=x y=1; continue; else y=0; break; end end end if y=1 q=q+1; end if q=p|

11、q-p=1 encoding(p,j)=-1; else if q-p=2 encoding(p,j)=0; CODE(p)=char(CODE(p),'0' encoding(q-1,j)=1; CODE(q-1)=char(CODE(q-1),'1' else a=sum(encoding(p:q-1,1)/2; for k=p:q-2 if abs(sum(encoding(p:k,1)-a)<=abs(sum(encoding(p:k+1,1)-a); break; end end for i=p:q-1 if i<=k encoding(i

12、,j)=0; CODE(i)=char(CODE(i),'0' else encoding(i,j)=1; CODE(i)=char(CODE(i),'1' end end end end p=q; end C=encoding(:,j); D=find(C=-1); e,f=size(D); if e=n j=0; else j=j+1; endendencodingACODEfor i=1:n u,v=size(char(CODE(i); L(i)=v;endavlen=sum(L.*A)運行結(jié)果：input the A:0.3,0.1,0.2,0.3,0.1encoding = 0.3000 0 0 -1.0000 -1.0000 0.3000 0 1.0000 -1.0000 -1.0000 0.2000 1.0000 0 -1.0000 -1.0000 0.1000 1.0000 1.0000 0 -1.0000 0.1000 1.0000 1.0000 1.0000 -1.0000A = 0.3000 0.3000 0.2000 0.1000 0.