信息論與編碼實驗報告

1、實驗報告課程名稱：信息論與編碼姓 名:系: 專 業(yè): 年 級: 學(xué) 號: 指導(dǎo)教師： 職 稱:實驗一信源熵值的計算. 1實驗二Huffman 信源編碼. 6實驗三Shannon 編碼.12實驗四信道容量的迭代算法 . .16.實驗五率失真函數(shù). 20實驗六差錯控制方法. 29.實驗七漢明編碼.32.實驗一 信源熵值的計算、實驗?zāi)康? 進一步熟悉信源熵值的計算2 熟悉 Matlab 編程、實驗原理熵（平均自信息）的計算公式qiPiiog2 i 1PiPilOg2Pii 1sum( x.* log2(x);或者h h x(i )* log2(x(i)流程：第一步：打開一個名為“nan311”的 T

2、XT 文檔，讀入一篇英文文章存入一個 數(shù)組 temp，為了程序準(zhǔn)確性將所讀內(nèi)容轉(zhuǎn)存到另一個數(shù)組S,計算該數(shù)組中每個字母與空格的出現(xiàn)次數(shù)（遇到小寫字母都將其轉(zhuǎn)化為大寫字母進行計數(shù)），每出 現(xiàn)一次該字符的計數(shù)器+1 ；第二步：計算信源總大小計算出每個字母和空格出現(xiàn)的概率；最后，通過統(tǒng)計數(shù)據(jù)和信息熵公式計算出所求信源熵值（本程序中單位為奈特nat）。程序流程圖:三、實驗內(nèi)容1、寫出計算自信息量的 Matlab 程序H(x)MATLAB 實現(xiàn)：HX2、已知：信源符號為英文字母（不區(qū)分大小寫）和空格輸入：一篇英文的信源文檔。輸出：給出該信源文檔的中各個字母與空格的概率分布，以及該信源的熵。四、實驗環(huán)境M

3、icrosoft Win dows 7Matlab 6.5五、編碼程序#in cludestdio.h#in clude #i nclude #defi ne N 1000int main(v oid)char sN;int i,n=0;float num27=0;double result=0,p27=0;FILE *f;char *temp=new char485;f=fope n( nan 311.txt,r);while (!feof(f) fread(temp,1,486, f);fclose (f);s0=*temp;for(i=0;istrle n(temp);i+) si=te

4、mpi;for(i=0;i=a&si=A&si=Z)nu msi-65+;printf(文檔中各個字母出現(xiàn)的頻率:n);for(i=0;i26;i+)pi=nu mi/strle n(s); prin tf(%3c:%ft,i+65,pi); n+;if(n=3)prin tf(n);n=0;p26=nu m26/strle n(s);prin tf(空格:%ft,p26);prin tf(n);for(i=0;i27;i+)if (pi!=0) result=result+pi*log(pi);result=-result;printf(信息熵為:%f,result);pri

5、n tf(n);return 0;六、求解結(jié)果其中 nan311.txt 中的文檔如下：There is no hate without fear. Hate is crystallized fear, fear divide nd, fearobjectivized. We hate what we fear and so where hate is, fear is lurking. Thus we hatewhat threatens our person, our vanity and our dreams and plans for ourselves. If wecan isola

6、te this eleme nt in what we hate we may be able to cease from hati ng.七、實驗總結(jié)通過這次實驗，我們懂得了不必運行程序時重新輸入文檔就可以對文檔進行 統(tǒng)計，既節(jié)省了時間而且也規(guī)避了一些輸入錯誤。在實驗中，我們進一步了解到 信源熵的計算，理論和實踐的結(jié)合讓我們對這個知識點了解的更加深刻了。實驗二Huffman信源編碼一、實驗?zāi)康? .理解信源的最優(yōu)變長編碼的基本思想。2熟練掌握 Huffman 信源編碼方法。二、設(shè)計原理設(shè)信源 S=s1,s2.,sq,其對應(yīng)的概率分布為P(si)=p1,p2,p3,：,pq，則其編碼步驟如下：

7、(1)將 q 個信源符號按遞減方式排列。(2)用 0、1 碼符分別表示概率最小的兩個信源符號，并將這兩個符號合并成 一個新的符號，從而得到 q-1 個符號的新信源成為 S 信源的縮減信源 S1。(3)將縮減信源 S1 中的符號仍按遞減順序排列，再將最小兩個概率相加，合 并成一個符號，并分別用 0、1 碼表示，這樣有形成了 q-2 個縮減信源 S2。(4)依次繼續(xù)下去，直到縮減信源只剩下兩個符號為止，將最后兩個符號用 0、1 分別表示(5)從最后一次縮減信源開始，向前返回，沿信源縮減過程的反方向取出所編的馬元。三、實驗內(nèi)容計算定信源和輸入信號字母表的Huffman 編碼，并計算 Huffman

8、編碼的平均碼長。實驗具體要求如下：信源字母表的概率分布為：P= 0.15,0.12,0.2,0.08,0.04,0.18,0.02,0.09,0.04,0.02,0.06輸入信號字母表：U=0,1,2;1.獨立設(shè)計信源和輸入信號字母表進行Huffman 編碼，其中信源字母表元素個數(shù)要求是 8 以上，信號字母表元素個數(shù)是 2 以上；2. 輸出 Huffman 編碼的平均碼長。四、實驗環(huán)境Microsoft Win dows 7Matlab 6.5五、編碼程序MATLAB 編碼：fun ctio n h,L=huffma n( p,r)%變量 p 為符號出現(xiàn)概率所組成的概率向量%返回值 h 為利用

9、 Huffman 編碼算法編碼后最后得到編碼結(jié)果%返回值 L 為進行 Huffman 編碼后所得編碼的碼字長度if len gth(fi nd(p1)error(Not a prob.vector,comp onents do not add up to 1);end斷所有符號出現(xiàn)概率之和是否大于1,如果大于運行a=le ngth(p); %測定概率向量長度，將長度值賦給變量k=fix(a-1)/(r-1);l1=a-k* 葉 k;q=zeros(1,a);m=zeros(k+1,a);mp=m;q=p;m(1,:),mp(1,:)=sort(q);if (I11)s=sum(m(1,1:l1

10、),2);q=s,m(1,(l1+1):a),o nes(1,l1-1);m(2,:),mp(2,:)=sort(q);elsem(2,:)=m(1,:);mp(2,:)=1:1:a;endfor i=3:k+1s=sum(m(i-1,1:r),2);1 程序顯示出錯，終止q=s,m(i-1,r+1:a),o nes(1,r-1);m(i,:),mp(i,:)=sort(q);endn1=m;n 2=mp;for i=1:k+1n1(i,:)=m(k+2-i,:);n 2(i,:)=mp(k+2-i,:);endm=n1;mp=n2;c=cell(k+1,a);for j=1:rc1,j=nu

11、 m2str(j-1);endfor i=2:kp1=fi nd(mp(i-1,:)=1);for j=1:rci,j=strcat(ci-1,p1,i nt2str(j-1);endfor j=( r+1):(p1+r-1)ci,j=ci-1,j-r;end for j=(p1+r):aci,j=ci-1,j-r+1;endendif l1=1for j=1:ack+1,j=ck,j;endelsep1=fi nd(mp(k,:)=1);for j=1:l1ck+1,j=strcat(c Kp1),i nt2str(j-1); endfor j=(l1+1):(p1+l1)ck+1,j=ck

12、,mp(1,j-l1);endfor j=(p1(1)+l1+1):a ck+1,j=ck,mp(1,j-l1+1);endendfor j=1:al(j)=le ngth(ck+1,j);endh=cell(1,a);for j=1:ah1,j=ck+1,j;endL=sum(l.*m(k+1,:); %求平均碼長2、在 MATLAB 命令窗口中輸入：p=0.15,0.12,0.2,0.08,0.04,0.18,0.02,0.09,0.04,0.02,0.06;r=3;h,L=huffma n(p,r).六、運行結(jié)果Q. 15, 0. 12, 0.0. 0Ss0, 0備D. IS, 0, 0

13、2j D.09, 0. 04, 0.02,0. 06:r=3r=3：h, L=huffinan( (p, r)Colwna】through 7J212TJ212LJ21222llJ J10JTVColumns 3 through 11J12J J2J2曠J0JL二2-0600得出的結(jié)論為：概率編碼概率編碼0.1521200.02110.1221210.09120.221220.04200.082100.02220.042110.0600.1810L=2.0600七、實驗總結(jié)在 huffman 編碼的過程中，我們運用了平時熟悉的數(shù)學(xué)軟件 MATLAB 的運行 來實現(xiàn)，把書本上 huffman 的

14、算法運用編程來實現(xiàn)。通過這次實驗，使我更加清 晰地理解 huffman 編碼的原理及實現(xiàn)過程，并且能夠在 MATLAB 中熟練地進行 編碼運行。實驗三 Shannon 編碼、實驗?zāi)康?、熟悉離散信源的特點；2、學(xué)習(xí)仿真離散信源的方法3、學(xué)習(xí)離散信源平均信息量的計算方法4、熟悉 Matlab 編程、實驗原理給定某個信源符號的概率分布，通過以下的步驟進行香農(nóng)編碼1、信源符號按概率從大到小排列；P1P2Pn2、確定滿足下列不等式的整數(shù)碼長Ki為lb(Pi) Kilb(Pi) 13、為了編成唯一可譯碼，計算第 i 個消息的累加概率:i 1P P(aQ4、將累加概率R變換成二進制數(shù);5、取R二進制數(shù)的小

15、數(shù)點后Ki位即為該消息符號的二進制碼字三、實驗內(nèi)容1、 寫出計算自信息量的 Matlab 程序2、 寫出計算離散信源平均信息量的 Matlab 程序。3、 將程序在計算機上仿真實現(xiàn)，驗證程序的正確性并完成習(xí)題。四、實驗環(huán)境Microsoft Win dows 7Matlab 6.5五、編碼程序計算如下信源進行香農(nóng)編碼，并計算編碼效率：Xaa1a?a3a4a5aP0.2 0.190.180.17 0.150.10.01MATLAB 程序：(1) a=0.2 0.18 0.19 0.15 0.17 0.1 0.01;k=le ngth(a);y=0;for i=1:k-1for n=i+1:kif

16、 (a(i)a( n)t=a(i);a(i)=a( n);a( n)=t;endendends=zeros(k,1);b=zeros(k,1);for m=1:ks(m)=y;y=y+a(m);b(m)=ceil(-log2(a(m);z=zeros(b(m),1);x=s(m);p=b2d10(x);for r=1:b(m)z(r)=p(r);end disp( e?3?a1?aS5)dispC3?e?e),disp(a(m)disp( a?ey),disp(b(m)disp(X? d?),disp(z)end(2) function y=b2d10(x) for i=1:8temp=x.*

17、2;if(temp0，可設(shè);iexpRjIn(ik)(3) P(k1)ji 1,2, r(k)expPjInjiijC(k 1)Inr !(k)expPjInjiijC(k1)C(k)|(5)如果 一 r，轉(zhuǎn)向(7);C(6)置迭代序號 k 1 k，轉(zhuǎn)向(2)；(7)輸出P|(k 1)和C(k 1)的結(jié)果；(8)停止。三、實驗內(nèi)容1、 已知：信源符號個數(shù) r、新宿符號個數(shù) s、信道轉(zhuǎn)移概率矩陣 P；2、 輸入：任意的一個信道轉(zhuǎn)移概率矩陣，信源符號個數(shù)、信宿符號個數(shù)和 每一個具體的轉(zhuǎn)移概率在運行時從鍵盤輸入；3、輸出：最佳信源分布 P*信道容量 Co四、實驗環(huán)境Microsoft Windows

18、 7、Matlab 6.5五、編碼程序aa.m 文件：clear;r=input(輸入信源個數(shù)：);s=i nput(輸入信宿個數(shù)：)；deta=input(輸入信道容量的精度：);A=sum(Q,2);(k)PjPi(k)jiPjP(k),sIQ=rand(r,s);%創(chuàng)建 m*n 隨機分布矩陣B=repmat(A,1,s);disp(信源轉(zhuǎn)移概率矩陣：),p=Q./B%信源轉(zhuǎn)移概率矩陣i=1:1:r;q(i)=1/r；disp(原始信源分布：),qc=-10e-8;C=repmat(q,1,s);for k=1:1:100000m=p.*C;%后驗概率的分子部分a=sum(m);%后驗概率

19、的分母部分su1=repmat(a,r,1);t=m./su1;%后驗概率矩陣D=exp(sum(p.*log(t),2);%言源分布的分子部分su2=sum(D);%言源分布的分母部分q=D/su2;%信源分布C=repmat(q,1,s);c(k+1)=log(sum(exp(sum(p.*log(t),2)/log(2);kk=abs(c(k+1)-c(k)/c(k+1);if(kk=0.000001)break;endenddisp(最大信道容量時的信源分布：q=),disp(q)disp(最大信道容量：c= ),disp(c(k+1)六、實驗結(jié)果結(jié)果1) 檢驗：運行 aa.m輸入信源

20、的個數(shù)：2輸入信宿的個數(shù)：3輸入信道容量的精度：0.000001信宿轉(zhuǎn)移概率矩陣:p =0.50000.30000.20000.30000.50000.2000原始信源分布：q = 0.50000.5000最佳信源分布：q= 0.50000.5000最大信道容量：c= 0.03652) 計算信源個數(shù)為 3,信宿個數(shù)為 5 的信道容量：運行 aa.m輸入信源的個數(shù)：3輸入信宿的個數(shù)：5輸入信道容量的精度：0.000001信宿轉(zhuǎn)移概率矩陣:p =0.04840.13850.30580.28450.22270.21040.24710.10770.37620.05850.34300.08000.180

21、80.34280.0534原始信源分布： q = 0.33330.33330.3333最佳信源分布： q =0.46910.17940.3515最大信道容量： c =0.1559七、實驗總結(jié)通過實驗，我們對信道容量的理解更加深刻了。 信道容量是指信道能無錯誤 傳送的最大信息率。信道的輸入、輸出都取值于離散符號集，且都用一個隨機變 量來表示的信道就是離散單符號信道。由于信道中存在干擾，因此輸入符號在傳 輸中將會產(chǎn)生錯誤，這種信道干擾對傳輸?shù)挠绊懣捎脗鬟f概率來描述。 為了評價實際信道的利用率，應(yīng)具體計算已給信道的容量。這是一個求最大值的問題。由 于互信息對輸入符號概率而言是凸函數(shù)，其極值將為最大值

22、，因此這也就是求極 值的問題。對于離散信道，P(x)是一組數(shù)，滿足非負性和歸一性等條件，可用拉 格朗日乘子法求得條件極值。對于連續(xù)信道，P(x)是一函數(shù)，須用變分法求條件極值。實驗過程中，我們雖然也遇到了很多困難，但也正是因為如此，我們才能發(fā) 現(xiàn)自己基礎(chǔ)的薄弱點，學(xué)的更有方向。對于編程方面，我們也有了很大的提升。實驗五率失真函數(shù)、實驗?zāi)康尿炞C率失真函數(shù)的極值特性，理解相關(guān)參數(shù)的變化對率失真函數(shù)的影 響。、實驗原理(1)輸入 S，d 的初始值、條件概率、輸出分布等值;M(2) 計算輸出分布qjphpjij；i 1(3) 進入迭代，標(biāo)志為 0 或者誤差大于指定 eps 則迭代，否則退出迭代;M M

23、piipjiijlog 単)；i 1 j 1qjM(6)重算一次(4)，并計算D piipjijdj；i 1(7)重算(3)-(7)步驟，直到退出迭代;(4)計算一個互信息 l(qj；pji)(5)計算一個條件概率分布P(j;i)qje爼qkeSdik三、實驗環(huán)境Microsoft Windows 7、Visual Studio 2005 professi on四、編碼程序#i nclude #in clude #i nclude using n amespace std;/Defi ne some global varconst int M = 10;/M 元信源const double S

24、 = -50;/迭代算法中的中間量，S 越小，允許最大失真度 D 越小，當(dāng) S 很小時(例如-100)，R(D)=H(X)static int dMM;/ 失真函數(shù)static double qM, PjiMM;/輸出分布和條件概率分布static double PiM = 0.4, 0.1,0.25, 0.1,0.05, 0.05, 0.01,0.02, 0.005, 0.015;/初始化信源的概率分布const int systemDefine = 2;/定義進制(默認為 2 進制，結(jié)果為 bit，為 e 時，結(jié)果為 nat)const double eps = 1e-8;/ 允許誤差/計

25、算輸出分布(qj)void calcOutDistributio n()int i, j;for(j=0; jM; j+)qj=0；for(i=0; iM; i+)qj += Pii * Pjiij；/計算條件概率分布 pjivoid calcProbabilityDistributio n() int i, j, k;double temp = 0;for(i=0; iM; i+)temp = 0;for(k=0; kM; k+)temp = temp + qk * exp(S*dik);for(j=0; jM; j+)/設(shè)定一個初始的條件概率分布Pjiij = qj * exp(S*dij

26、)/temp;/取得 R(r,r)=l(qj;Pji)【實際上就是根據(jù)互信息量公式求互信息】double getSelfl nformatio n()int i, j;double I=0;for(i=0; iM; i+)for(j=0; jM; j+)I += Pii * Pjiij * log(Pjiij/qj)/log(systemDefine); / 求互信白旦息量return I;int main (i nt argc, char *argv)double probabilityCou nt = 0.0;/ 概率和for(i nt k=0; k eps)cout概率和不為 1，程序異

27、常退出!endl; return -1;/前兩個變量代表求的相鄰的兩個互信息R(r, r)和 R(r,葉 1); D 代表限定失真double mutuall nformati onl, mutuall nformati on2, D;int i, j, flag, nCount;/初始值 mutuall nformati on1 = 0;mutuall nformati on2 = 0;D = 0;flag = 0;nCou nt = 0;/迭代次數(shù)指示器if(i = j)dij = 0；elsedij = 1；/init mothod/輸出分布的初始化for(i=0; iM; i+)qi

28、= 0;/率失真函數(shù)的初始化，根據(jù)漢明失真距離來初始化for(i=0; iM; i+)for(j=0; jM; j+)for(i=0; iM; i+)for(j=0; j eps)coutsetprecision(20)endl第+nCount次迭代e ndl;flag = 1;/獲得一個互信息 R(r, r)mutualI nformati on1 = getSelfI nformati on();/計算下一個條件概率分布calcProbabilityDistributio n();/在上面的原來的輸出分布 q 和新生成的條件概率分布 Pji 的基礎(chǔ)上獲得新的互信息 R(r,葉 1)mutu

29、alI nformatio n2 = getSelfI nformati on();/再計算條件概率分布calcOutDistributio n();cout互信息 1: vvmutuallnformation1endl互信息 2：vvmutuall nformatio n2e ndl;for(i=0; iM; i+)for(j=0; jM; j+)/求最大允許失真度 DD = D + Pii*Pjiij*dij;coutD = vvDvve ndl;coutR(D) = vvmutuall nformatio n2e ndl;/ 這是利用迭代算法求出的最大允許失真度為 D 時的 R(D)co

30、utvv-=-e ndl;return 0;五、實驗結(jié)果運行實驗結(jié)果如下:六、實驗總結(jié)通過這次實驗，讓我們更好的掌握了率失真的求解方法，而且通過計算機解 決問題效率提高了很多，節(jié)省了很多繁瑣的步驟，更加直觀和方便的讓我們了解 到相關(guān)參數(shù)變化對率失真的影響。實驗六差錯控制方法一、實驗?zāi)康?、 了解糾錯編碼的基本原理2、 了解幾種常用編碼：奇偶校驗碼、正反碼等，線性分組碼、循環(huán)碼、卷積碼的編解碼原理3、重點掌握線性分組碼、循環(huán)碼、卷積碼的編解碼原理。二、實驗原理N 個重復(fù)碼是一種將輸入比特重復(fù) n 遍的編碼，假設(shè)信道的錯誤率為 p，接收端收到 n 個比特后進行譯碼，如果 n 個接收比特的“1”的個

31、數(shù)多于” “的個數(shù)，則譯碼為“1”反之為 0”，假設(shè)編碼輸入時等概的。(1)計算 n=5 的信道錯誤率與譯碼的錯誤率的關(guān)系；(2)用 matlab 仿真得到上述的曲線。三、實驗內(nèi)容n重復(fù)碼是一種將輸入比特重復(fù)n遍的編碼，假設(shè)信道的錯誤率為 p，接收 端收到n個比特后進行譯碼，如果n個接收比特的T的個數(shù)多于的個數(shù)，則 譯碼為 1”，反之為 0”。假設(shè)編碼輸入時等概的。(1) 計算n=5 時信道錯誤率與譯碼錯誤率的關(guān)系；(2) 用 Matlab 仿真得到上述的曲線；實驗步驟：(1)令 n1，n2 分別表示接收到的 n 個比特中 0”和 1”的個數(shù)，則誤碼率可以寫 成Pb=P (n 1n0|”0”)

32、P(0)當(dāng) n=5 時，編碼時“1”被映射成 11111 ”； 0”映射成 O0OOO”，信道錯誤率為 p，則P(n1n21)CP5C5(1Pe)PeC；(1 Pe)2p；P(n1n20)C?p；C5(1Pe)P：C；(1 Pe)2P3因此PbP；5p：(1 Pe) 10p；(1 Pe)2四、實驗環(huán)境Microsoft Win dows 7Matlab 6.5五、編碼程序MATLAB 編碼：n=5;m=0:-0.5:-3;pe=10.Am;Data d=(sig n(ra ndn (1,100000)+1)/2;s=d;d;d;d;d;s=reshape(s,1,5*le ngth(d);fo

33、r k=1:le ngth(pe)err=ra nd(1,le ngth(d)*5);err=err2; error(k)=sum(abs(dd-d)/le ngth(d); endloglog(pe,error)六、實驗結(jié)果七、實驗總結(jié)上的例題，學(xué)會了計算信道的錯誤率與譯碼錯誤率的關(guān)系，能更好的理解編碼、解碼原理。實驗七漢明編碼一、實驗?zāi)康?、 掌握線性分組碼的編碼原理2、 掌握漢明碼編碼方法3、 了解編碼對誤碼性能的改善二、實驗原理（n, k）線性分組碼的H矩陣是一個（n k） n r n階矩陣，這里 r n k 是校驗元的數(shù)目。顯然，r個校驗元能組成 2r列互不相同的r重矢量，其中非全

34、零矢量有 2r1 個。如果用這 2r1 個非全零矢量作為 H 矩陣的全部列，即令 H 矩 陣的列數(shù)n 2r1，則此 H矩陣的各列均不相同，且無全零列，由此可構(gòu)造一 個糾正單個錯誤的（n，k）線性分組碼。同時，2r1 是n所能取的最大值，因為如果n 2r1，那么 H 矩陣的n列中 必會出現(xiàn)相同的兩列，這樣就不能滿足對 H 矩陣的要求。而由于n 2r1是n所 能取的最大值，也就意味著碼率 R 取得了最大值，即通過本次實驗，掌握了差錯控制編碼的實驗原理與編碼過程。同時通過實驗解決了書本k n r rrR11-n nn 21這樣設(shè)計出來的碼是符合我們的要求的，這樣的碼就是漢明碼。定義若 H 矩陣的列是由非全零且互不相同的所有二進制r 重矢量組成，則由此得到的線性分組碼，稱為 GF（2 上的