信息論與編碼matlab1

信息論實(shí)驗(yàn)報(bào)告姓名班級(jí)學(xué)號(hào)胡小輝電子信息工程0902實(shí)驗(yàn)?zāi)康?、掌握哈夫曼編碼、費(fèi)諾編碼、漢明碼原理；2、熟練掌握哈夫曼樹的生成方法；3、學(xué)會(huì)利用matlab、C語(yǔ)言等實(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編碼原理的步驟如下：首先將信源符號(hào)集中的符號(hào)按概率大小從大到小排列。用0和1表示概率最小的兩個(gè)符號(hào)?？捎?表示概率小的符號(hào)，也可用1表示概率小的符號(hào)，但整個(gè)編碼需保持一致。將這兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，合并符號(hào)概率為最小概率之和，將合并后的符號(hào)與其余符號(hào)組成一個(gè)N-1的新信源符號(hào)集，稱之為縮減符號(hào)集。對(duì)縮減符號(hào)集用步驟1,2操作以此類推，直到只剩兩個(gè)符號(hào)，將0和1分別賦予它們。根據(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)再分為兩組，使劃分后的兩個(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（mN2的正整數(shù)）重組成，則由此H矩陣得到的線性分組碼稱為［2m-1,2m-1-m，3］漢明碼。我們通過（7,4）漢明碼的例子來說明如何具體構(gòu)造這種碼。設(shè)分組碼（n，k）中，k=4，為能糾正一位誤碼，要求rN3。現(xiàn)取r=3，則n=k+r=7。我們用aaaaaaa表示這7個(gè)碼元，用S、S、S表示由三個(gè)監(jiān)督方程式計(jì)算得到的校123S1S2S3錯(cuò)碼位置001a0010ai100a123S1S2S3錯(cuò)碼位置001a0010ai100a2011a3S1S2S3錯(cuò)碼位置101a4110a5111a6000無錯(cuò)碼表1校正子和錯(cuò)碼位置關(guān)系由表可知，當(dāng)誤碼位置在a、a、a、a時(shí)，校正子S=1；否則S=0。因此有S2456111=a?a?a?a，同理有S=a十a(chǎn)十a(chǎn)十a(chǎn)和S=a十a(chǎn)十a(chǎn)十a(chǎn)。在編碼時(shí)a、654226531364306a、a、a為信息碼元，a、a、a為監(jiān)督碼元。則監(jiān)督碼元可由以下監(jiān)督方程唯543210一確定6542=0/…八a十a(chǎn)十a(chǎn)十a(chǎn)(1.1.1)也即Ca=a十a(chǎn)十a(chǎn)2654ya=a十a(chǎn)十a(chǎn)(1.1.2)aa十a(chǎn)十a(chǎn)J0=643由上面方程可得到表2所示的16個(gè)許用碼組。在接收端收到每個(gè)碼組后，計(jì)算出S「s2、s3,如果不全為0,則表示存在錯(cuò)誤，可以由表1確定錯(cuò)誤位置并予以糾正。舉個(gè)例子，假設(shè)收到碼組為0000011,可算出S1S2S3=011,由表1可知在氣上有一誤碼。通過觀察可以看出，上述(7,4)碼的最小碼距為1訕=3，糾正一個(gè)誤碼或檢測(cè)兩個(gè)誤碼。如果超出糾錯(cuò)能力則反而會(huì)因“亂糾”出現(xiàn)新的誤碼.信息位監(jiān)督位信息位監(jiān)督位aaaaaaaaaaaaaa654321065432100000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111表2(7,4)漢明碼的許用碼組3.1(7,4)漢明碼的編碼思路(7,4)漢明碼的編碼就是將輸入的四位信息碼編成七位的漢明碼，即加入三位監(jiān)督位。根據(jù)式(2.2.0)A=[a6a5a4a3]?G可知，信息碼與生成矩陣G的乘積就是編好以后的(7,4)漢明碼，而生成矩陣G又是已知的，由式(1.1.9)得所以，廠1000G=01000010V0001可以得111[110101011J出如下方程組

a3—a3a2a3—a3a2a1a0a5a4a+6a6+a6+a—a66—a5—a4a+a54a+a53a+a433.實(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);%空的編碼表(矩陣)fori—1:nB(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;forj-2:n-1%生成編碼表的其他各列fori—1:tB(i,j)—T(i);endK=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;%輸出編碼表END1=sym('[0,1]');%給最后一列的元素編碼END=END1;t=3;d=1;forj=n-2:-1:1%從倒數(shù)第二列開始依次對(duì)各列元素編碼fori=1:t-2ifi>1&B(i,j)==B(i-1,j)d=d+1;elsed=1;endB(B(n,j+1),j+1)=-1;temp=B(:,j+1);x=find(temp==B(i,j));END(i)=END1(x(d));endy=B(n,j+1);END(t-1)=[char(END1(y)),'0'];END(t)=[char(END1(y)),'1'];t=t+1;END1=END;endA%排序后的原概率序列END%編碼結(jié)果fori=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é)果：A=0.40000.30000.15000.1QQ00.0500END=LljOljOQLQQQOjQQQL]avlen=2.0500H二2.0087P=0.9799費(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);fori=1:nB(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(B(:,1))/2;fork=1:n-1ifabs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a)break;endendfori=1:n%生成B第2列的元素ifi<=kB(i,2)=0;elseB(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);forq=p:nifx==-1break;elseifB(q,j-1)==xy=1;continue;elsey=0;break;endendendify==1q=q+1;endifq=plq-p=1B(p,j)=-1；elseifq-p==2B(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;fork=p:q-2ifabs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a);break;endendfori=p:q-1ifi<=kB(i,j)=0;END(i)=[char(END(i)),'0'];elseB(i,j)=1;END(i)=[char(END(i)),'1'];endendendendp=q;endC=B(:,j);D=find(C==-1);[e,f]=size(D);ife==nj=0;elsej=j+1;endendBAENDfori=1:n[u,v]=size(char(END(i)));L(i)=v;endavlen=sum(L.*A)輸出結(jié)果:0.40000-1.0000-1.0000-1.0000-i.oaoo0.30001.00000-1.0000-1.0000-1.00000.15001.0000i.oaoo0-1.0000-i.oaoo0.10001.0000i.oaoo1.00000-i.oaoo0.05001.00001.OWNl.QOOQ1.0000-i.oaooA二0.40000.30000.1500O.10000.0500END二[0;10;1IO,1UOj1111]avlen=2.0500漢明碼:

clc;clear;close;N=100;display（'隨機(jī)產(chǎn)生二進(jìn)制信源消息序列:'）;[a]=randint(1,100);%************轉(zhuǎn)換矩陣[a]for%************轉(zhuǎn)換矩陣[a]forj=0:(4-1)P(i+1,j+1)=a(j+i*4+1);endend[P]%functiong=hammingdecod(R)%H=input('生成漢明碼:')；H=[1110100;1101010;1011001];%生成漢明碼G=[1000111;0100110;0010101;0001011]%(7,4)漢明碼的生成矩陣%t=input('輸入0或1:');%t=0則產(chǎn)生(7，4)漢明碼，t=1則對(duì)輸入序列進(jìn)行編碼%ift==1c=mod(P*G,2);%編碼的碼字c%function[X]=turnRow(c)n=size(c);fori=0:(n(1)-1)forj=0:(n(2)-1)X(j+i*n(2)+1)=c(i+1,j+1);endendX1=randerr(1,175,1);%************相加Q=mod(X1+X,2);%************轉(zhuǎn)換矩陣X1%**********編碼fori=0:(length(Q)/7-1)forj=0:(7-1)Q1(i+1,j+1)=Q(j+i*7+1);endenddisp（輸出編碼后序列為：'）;Q1Z=mod(Q1*H',2);%**********編碼n=size(Z);%T=T();fori=0:(n(1)-1)T(i+1)=4*Z(i+1,1)+2*Z(i+1,2)+Z(i+1,3);ifT(i+1)Q1(i+1,8-T(i+1))=1-Q1(i+1,8-T(i+1));endendT=Q1;disp('(經(jīng)過信道后變?yōu)椋?);T%**************譯碼functionC=yima(B,k)n=size(T);fori=1:n(1)forj=1:4C(i,j)=T(i,j);endenddisp('輸出譯碼序列:')；disp(C);輸出結(jié)果:1i011001]1011010011110111110101a00011010a0110001i101i00ai01ai01ii11□Q010101a001□q11ii01i010ai110i000（經(jīng)過信道后壹為:Q1=11101110011。1000100Qaoiiiaio1Q1100100011100111100LD10ol1a0ald]a]oo1o]logo]LD0]000aa0000000000000000000□a0a0a000000aa00Q0000aa00a0000000000i]L000□000000001101010100110011