信息論大作業(yè)new

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

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

3、數(shù)組總數(shù)的比例統(tǒng)計(jì)在數(shù)組p中;3. 找到最小的概率,相加直到等于1,把最小概率的序號(hào)存在tree第一列中,次小放在第二列,和放在p像素比例之后;4. C數(shù)組第一維表示值,第二維表示代碼數(shù)值大小,第三維表示代碼的位數(shù)；5. 把概率小的值為1標(biāo)識(shí)，概率大的值為0標(biāo)識(shí)；6. 計(jì)算信源的熵 ；7. 計(jì)算平均碼長 ；8. 計(jì)算編碼效率'；9. 計(jì)算冗余度。源程序：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); %生成一個(gè)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); %計(jì)算每一個(gè)huffman 編碼的長度endl=sum(p.*ll); %計(jì)算平均碼長fprintf('n Huffman編碼結(jié)果為:n'); hfprintf('n 編碼的平均碼長為:n'); lhh=sum(p.*(-log2(p); %計(jì)算信源熵fprintf('n 信源熵為:n'); hhfprintf('n 編碼效率為:n'); t=hh/l %計(jì)

7、算編碼效率運(yùn)行結(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碼:費(fèi)諾編碼屬于概率匹配編碼，但它不是最佳的編碼方法。不過有時(shí)也可以得到緊致碼的性能。信源符號(hào)以概率遞減的次序排列進(jìn)來,將排列好的信源符號(hào)劃分為兩大組,使第組的概率和近于相同,并各賦于一個(gè)二元碼符號(hào)”0”和”1”.然后,將每一大組的信源符號(hào)再分成兩組,使同一組的兩個(gè)小組的概率和近于

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

9、它編碼后的費(fèi)諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率達(dá)，編碼效率高，但它屬于概率匹配編碼它不是最佳的編碼方法。源程序：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)運(yùn)行結(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.