信息論與編碼matlab1

1、信息論實(shí)驗(yàn)報(bào)告姓名 胡小輝 班級(jí) 電子信息工程0902學(xué)號(hào) 0909091112 1. 實(shí)驗(yàn)?zāi)康?1、掌握哈夫曼編碼、費(fèi)諾編碼、漢明碼原理；2、熟練掌握哈夫曼樹的生成方法；3、學(xué)會(huì)利用matlab、C語言等實(shí)現(xiàn)Huffman編碼、費(fèi)諾編碼以及hamming編碼。2. 實(shí)驗(yàn)原理Huffman編碼：哈夫曼樹的定義：假設(shè)有n個(gè)權(quán)值，試構(gòu)造一顆有n個(gè)葉子節(jié)點(diǎn)的二叉樹，每個(gè)葉子帶權(quán)值為wi，其中樹帶權(quán)路徑最小的二叉樹成為哈夫曼樹或者最優(yōu)二叉樹； 實(shí)現(xiàn)Huffman編碼原理的步驟如下：1.首先將信源符號(hào)集中的符號(hào)按概率大小從大到小排列。2.用0和1表示概率最小的兩個(gè)符號(hào)。可用0表示概率小的符號(hào)，也可用1表

2、示概率小的符號(hào)，但整個(gè)編碼需保持一致。3.將這兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，合并符號(hào)概率為最小概率之和，將合并后的符號(hào)與其余符號(hào)組成一個(gè)N-1的新信源符號(hào)集，稱之為縮減符號(hào)集。4.對(duì)縮減符號(hào)集用步驟1,2操作5.以此類推，直到只剩兩個(gè)符號(hào)，將0和1分別賦予它們。6.根據(jù)以上步驟，得到0,1賦值，畫出Huffman碼樹，并從最后一個(gè)合并符號(hào)回朔得到Huffmaan編碼。 費(fèi)諾編碼： 費(fèi)諾編碼的實(shí)現(xiàn)步驟：1、將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列： 。2、將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和“1”。3、將每一大組的信源符號(hào)再分

3、為兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制符號(hào)“0”和“1”。4、如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。5、信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。hamming編碼： 若一致監(jiān)督矩陣H 的列是由不全為0且互不相同的所有二進(jìn)制m(m2的正整數(shù))重組成，則由此H矩陣得到的線性分組碼稱為2m-1,2m-1-m，3漢明碼。 我們通過（7，4）漢明碼的例子來說明如何具體構(gòu)造這種碼。設(shè)分組碼（n，k）中，k = 4，為能糾正一位誤碼，要求r3。現(xiàn)取r3，則nkr7。我們用a0ala2a3a4a5a6表示這7個(gè)碼元，用S1、S2、S3表示由三個(gè)監(jiān)督方程式計(jì)算得到的校正子，并假設(shè)三位S

4、1、S2、S3校正子碼組與誤碼位置的對(duì)應(yīng)關(guān)系如表1所示。S1S2S3錯(cuò)碼位置S1S2S3 錯(cuò)碼位置 001 a0 101 a4 010 al 110 a5 100 a2 111 a6 011 a3 000 無錯(cuò)碼 表1 校正子和錯(cuò)碼位置關(guān)系由表可知，當(dāng)誤碼位置在a2、a4、a5、a6時(shí)，校正子S11；否則S10。因此有S1a6a5a4a2，同理有S2a6a5a3a1和S3a6a4a3a0。在編碼時(shí)a6、a5、a4、a3為信息碼元，a2、a1、a0為監(jiān)督碼元。則監(jiān)督碼元可由以下監(jiān)督方程唯一確定 a6a5a4a2 = 0 a6a5a3a1 = 0 (1.1.1) a6a4a3a0 = 0 也即a2

5、a6a5a4 a1a6a5a3 （ 1.1.2）a0 = a6a4a3由上面方程可得到表2所示的16個(gè)許用碼組。在接收端收到每個(gè)碼組后，計(jì)算出S1、S2、S3，如果不全為0，則表示存在錯(cuò)誤，可以由表1確定錯(cuò)誤位置并予以糾正。舉個(gè)例子，假設(shè)收到碼組為0000011，可算出S1S2S3=011,由表1可知在a3上有一誤碼。通過觀察可以看出，上述（7，4）碼的最小碼距為dmin3，糾正一個(gè)誤碼或檢測(cè)兩個(gè)誤碼。如果超出糾錯(cuò)能力則反而會(huì)因“亂糾”出現(xiàn)新的誤碼. 信息位 監(jiān)督位 信息位 監(jiān)督位 a6a5a4a3 a2a1a0 a6a5a4a3 a2a1a000000001 0010 0011 0100 0

6、101 01100111 000 011 101 110 110 101 011 00010001001101010111100110111101111 111100010001001010100111 表2 （7,4）漢明碼的許用碼組3.1 (7,4)漢明碼的編碼思路(7,4)漢明碼的編碼就是將輸入的四位信息碼編成七位的漢明碼，即加入三位監(jiān)督位。根據(jù)式(2.2.0）A = a6 a5 a4 a3 G可知，信息碼與生成矩陣G的乘積就是編好以后的(7,4)漢明碼，而生成矩陣G又是已知的，由式(1.1.9)得1 0 0 0 1 1 1 G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1

7、 0 0 0 1 0 1 1所以，可以得出如下方程組 a6 = a6 a5 = a5 a4 = a4 a3 = a3 a2 = a6 + a5 + a4 a1 = a6 + a5 + a3 a0 = a6 + a4 + a3根據(jù)此式子編出編碼程序。3. 實(shí)驗(yàn)過程及結(jié)果1、 哈弗曼編碼例如：當(dāng)p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4則根據(jù)其原理得到的matlab程序如下：clc;clear;A=0.3,0.15,0.05,0.1,0.4;%信源消息的概率序列A=fliplr(sort(A);%按降序排列T=A;m,n=size(A);B=zeros(n,n-1);

8、%空的編碼表（矩陣）for i=1:n B(i,1)=T(i);%生成編碼表的第一列endr=B(i,1)+B(i-1,1);%最后兩個(gè)元素相加T(n-1)=r;T(n)=0;T=fliplr(sort(T);t=n-1;for j=2:n-1%生成編碼表的其他各列 for i=1:t B(i,j)=T(i); end K=find(T=r); B(n,j)=K(end);%從第二列開始，每列的最后一個(gè)元素記錄特征元素在%該列的位置 r=(B(t-1,j)+B(t,j);%最后兩個(gè)元素相加 T(t-1)=r; T(t)=0; T=fliplr(sort(T); t=t-1;endB;%輸出編碼

9、表END1=sym(0,1);%給最后一列的元素編碼END=END1;t=3;d=1;for j=n-2:-1:1%從倒數(shù)第二列開始依次對(duì)各列元素編碼 for i=1:t-2 if i1 & B(i,j)=B(i-1,j) d=d+1; else d=1; end B(B(n,j+1),j+1)=-1; temp=B(:,j+1); x=find(temp=B(i,j); END(i)=END1(x(d); end y=B(n,j+1); END(t-1)=char(END1(y),0; END(t)=char(END1(y),1; t=t+1; END1=END;end A%排序后的原概率序

10、列 END%編碼結(jié)果for i=1:n a,b=size(char(END(i); L(i)=b;endavlen=sum(L.*A)%平均碼長(zhǎng) H1=log2(A);H=-A*(H1)%熵P=H/avlen%編碼效率輸出結(jié)果：費(fèi)諾編碼： 同樣，例如：p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4時(shí) 根據(jù)其原理所得到的matlab程序如下： clc;clear;A=0.3,0.15,0.05,0.1,0.4;A=fliplr(sort(A);%降序排列m,n=size(A);for i=1:n B(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=su

11、m(B(:,1)/2;for k=1:n-1 if abs(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; else B(i,2)=1; endend%生成第一次編碼的結(jié)果END=B(:,2);END=sym(END);%生成第3列及以后幾列的各元素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

12、; break; end end end if y=1 q=q+1; end if 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; else a=sum(B(p:q-1,1)/2; for k=p:q-2 if abs(sum(B(p:k,1)-a)=abs(sum(B(p:k+1,1)-a); break; end end for i=p:q-1 if i=k B(i,j)=0; END(i)=char(END(i),0; else

13、 B(i,j)=1; END(i)=char(END(i),1; end end end end p=q; end C=B(:,j); D=find(C=-1); e,f=size(D); if e=n j=0; else j=j+1; endendBAENDfor i=1:n u,v=size(char(END(i); L(i)=v;endavlen=sum(L.*A)輸出結(jié)果：漢明碼：clc;clear;close;N=100;display(隨機(jī)產(chǎn)生二進(jìn)制信源消息序列:);a=randint(1,100); %*轉(zhuǎn)換矩陣afor i=0:(length(a)/4-1) for j=0:(

14、4-1) P(i+1,j+1)=a(j+i*4+1); endendP%function g=hammingdecod(R)%H=input(生成漢明碼:);H=1 1 1 0 1 0 0;1 1 0 1 0 1 0;1 0 1 1 0 0 1;%生成漢明碼G=1 0 0 0 1 1 1;0 1 0 0 1 1 0;0 0 1 0 1 0 1;0 0 0 1 0 1 1 %(7,4)漢明碼的生成矩陣%t=input(輸入0或1:); %t=0則產(chǎn)生（7，4）漢明碼，t=1則對(duì)輸入序列進(jìn)行編碼%if t=1 c=mod(P*G,2); %編碼的碼字c %function X=turnRow(c) n=size(c);for i=0:(n(1)-1) for j=0:(n(2)-1) X(j+i*n(2)+1)=c(i+1,j+1); endend X1=randerr(1,175,1); %*相加 Q=mod(X1+X,2); %*轉(zhuǎn)換矩陣X1 %*編碼 for i=0:(length(Q)/7-1) for j=0:(7-1) Q1(i+1,j+1)=Q(j+i*7+1); end enddisp(輸出編碼后序列為：);Q1Z=mod(Q1*H,2);Z%*編碼n=size(Z);%T=T()