信息論與編碼實驗指導(dǎo)書

1、信息論與編碼實驗指導(dǎo)書1課程實驗?zāi)康谋菊n程是一門實踐性很強(qiáng)的專業(yè)課和核心課程，根據(jù)課程理論教學(xué)的需要安排了6學(xué)時的配套實驗教學(xué)，主要內(nèi)容涉及信息度量的計算方法、典型信源編碼方法、典型信道容量計算方法和數(shù)據(jù)壓縮方法四個實驗，這四個實驗的開設(shè)一方面有助于學(xué)生消化、鞏固課程理論教學(xué)的知識，另一方面乂可培養(yǎng)學(xué)生實踐動手能力，同時為后續(xù)課程做好準(zhǔn)備。2課程實驗要求2.1課程實驗準(zhǔn)備要求(1) 課程實驗主要為設(shè)計性實驗，要求學(xué)生熟悉掌握在VC環(huán)境下編寫和調(diào)試C+玳序的方法。(2) 要求學(xué)生在實驗前復(fù)習(xí)實驗所用到的預(yù)備知識?？梢圆殚喗滩幕蛘呦嚓P(guān)的參考資料，這需要學(xué)生有自主的學(xué)習(xí)意識和整理知識的能力。(3)

2、根據(jù)實驗項目，設(shè)計相關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法，再轉(zhuǎn)換為對應(yīng)的書面程序，并進(jìn)行靜態(tài)檢查，盡量減少語法錯誤和邏輯錯誤。上機(jī)前的充分準(zhǔn)備能高效利用機(jī)時，在有限的時間內(nèi)完成更多的實驗內(nèi)容。2.2課程實驗過程要求(1) 生成源代碼。將課前編寫好的書面代碼，利用VC自帶的編輯器盡快輸入為轉(zhuǎn)換為源代碼；(2) 程序調(diào)試和軟件測試。要求學(xué)生熟練掌握調(diào)試工具，調(diào)試正確后，認(rèn)真整理源程序和注釋，給出帶有完整注釋且格式良好的源程序活單和結(jié)果。完成實驗報告。根據(jù)實驗內(nèi)容和完成情況，按照附件1給定的格式完成課程實驗報告的編寫。2.3課程實驗報告要求在每次課程實驗后要及時進(jìn)行總結(jié)和整理，并編寫課程實驗報告。報告格式按7工西藍(lán)天

3、學(xué)院實驗報告紙格式填寫。實驗一二維隨機(jī)變量信息嫡的計算實驗?zāi)康恼莆斩兞慷喾N信息量的計算方法。實驗學(xué)時2學(xué)時實驗準(zhǔn)備1. 熟悉二變量多種信息量的計算方法，設(shè)計實驗的數(shù)據(jù)結(jié)構(gòu)和算法；2. 編寫計算二維隨機(jī)變量信息量的書面程序代碼。實驗內(nèi)容及步驟離散二維隨機(jī)變換嫡的計算說明：(1) 利用random函數(shù)和歸一化方法構(gòu)造一個二維離散隨機(jī)變量(X,0；(2) 分別計算X與Y的嫡、聯(lián)合嫡、條件嫡：H(X)、H(丫)、H(X,Y)H(X|Y)、I(X|Y);(3) 對測試通過的程序進(jìn)行規(guī)范和優(yōu)化；(4) 編寫本次實驗的實驗報告。附實驗一主要內(nèi)容及源程序?qū)嶒炓浑x散二維隨機(jī)變量信息嫡的計算1實驗內(nèi)容(1) 利

4、用random函數(shù)和歸一化方法構(gòu)造一個二維離散隨機(jī)變量(X,P；分別計算X與Y的嫡、聯(lián)合嫡、條件嫡：H(X)、H(丫)、H(X,Y)H(X|Y)、I(X|Y);2數(shù)據(jù)結(jié)構(gòu)與算法描述1. (1)函數(shù)的定義：函數(shù)的數(shù)據(jù)成員隨機(jī)生成函數(shù)的代碼：intk,n,t=0;doublea44,b=0,c=0;for(k=0;k<4;k+)for(n=0;n<4;n+)akn=rand()%100;t+=akn;cout<<"從到問隨機(jī)取得行歹U的random函數(shù)："<<endl;for(k=0;k<4;k+)for(n=0;n<4;n+)c

5、out<<setw(5)<<akn;cout<<endl;2. 函數(shù)歸一化代碼：cout<<"函數(shù)歸一化："<<endl;for(k=0;k<4;k+)(for(n=0;n<4;n+)(cout<<setw(12)<<akn/t;cout<<endl;3. H(Y)、H(X)計算代碼：cout<<"H(Y)計算："<<setw(20)<<"H(X)計算："<<endl;inte=1

6、;for(k=0;k<4;k+)(doublei=0,g=0;i+=(akn/t);g+=(ank/t);cout<<"P(Y"<<k+1<<)："<<i<<setw(8)<<"P(X"<<e<<):"<<g<<endl;+e;b-=(i*log(i)/log(2.0);c-=(g*log(g)/log(2.0);cout<<"H(Y)=-Ep(Y)logp(Y)="<&l

7、t;b<<endl;4. cout<<"H(X)=-Ep(X)logp(X)="<<c<<endl;聯(lián)合嫡H(X,Y)計算代碼：cout<<"聯(lián)合嫡H(X,Y)計算："<<endl;b=0;intr,u,h=0;for(k=0;k<4;k+)(for(n=0;n<4;n+)(if(akn!=0)(b-=(akn/t)*log(akn/t)/log(2.0);else(r=k,u=n;h=1;break;if(h#。)couAA=H(><YHMMp(>&l

8、t;Y)-ogP(XY)4abaendLQsecouaa=p(=aa_.+xa=-=aac+x*湍“書«-Aft=aend5»JT(X_Y)51-COUAA=»BH(X-Y)4W=aendbnphno*for(knok<4k+)doub-eli'ofor(彳號八今+for(彳號八今+if(akn!=O)b-=(akn/t)*log(akn/t)/i)/log(2.0);elseh=1:break;if(h=0)cout«"H(X|Y)=-EEP(X,Y)log(P(X,Y)/P(Y)="«b«endl

9、;)elsecout«"P("«r+1«","vvu+1v<r)為零,中斷，無值"«endl;cout«"l(X|Y)計算："«endl;if(h=0)cout«"I(X|Y)=H(X)-H(X|Y)="«c-b«endl;elsecout«"P("«r+1«","vvu+1v<r)為零,中斷，無值"«endl;(2

10、)主函數(shù)main()實現(xiàn)初始化操作，完成對子函數(shù)的調(diào)用因為整個程序是寫在main函數(shù)中，就不列出，會在下面源程序活單中給出程序。3實驗數(shù)據(jù)與實驗結(jié)果這里設(shè)定函數(shù)為4行4列的隨機(jī)矩陣。然后函數(shù)歸一化，即：把所有數(shù)字相加，再用每個數(shù)去除，就得到了歸一化后的矩陣而H(為、H(丫)、H(X,Y)H(X|Y)、I(X|Y)就根據(jù)課本上的公式，然后編程。輸出結(jié)果如下：4程序代碼活單：#include<stdio.h>#include<cmath>#include<iomanip>#include<time.h>#include<iostream>

11、usingnamespacestd;voidmain()intk,n,t=0;doublea44,b=0,c=0;srand(unsigned)time(NULL);for(k=0;k<4;k+)for(n=0;n<4;n+)akn=rand()%100;t+=akn;cout<<"從0到100間隨機(jī)取得行歹U的random函數(shù)："<<endl;for(k=0;k<4;k+)for(n=0;n<4;n+)cout<<setw(5)<<akn;cout<<endl;cout<<&q

12、uot;函數(shù)歸一化："<<endl;for(k=0;k<4;k+)(for(n=0;n<4;n+)(cout<<setw(12)<<akn/t;cout<<endl;cout<<"H(Y)計算："<<setw(20)<<"H(X)計算：”<<endl;inte=1;for(k=0;k<4;k+)(doublei=0,g=0;for(n=0;n<4;n+)(i+=(akn/t);g+=(ank/t);cout<<"P

13、(Y"<<k+1<<):"<<i<<setw(8)<<"P(X"<<e<<):"<<g<<endl;+e;b-=(i*log(i)/log(2.0);c-=(g*log(g)/log(2.0);cout<<"H(Y)=-Ep(Y)logp(Y)="<<b<<endl;<<c<<endl;cout<<"H(X)=-Ep(X)logp(X)=

14、"cout<<"聯(lián)合嫡H(X,Y)計算："<<endl;b=0;intr,u,h=0;for(k=0;k<4;k+)(for(n=0;n<4;n+)(if(akn!=0)(b-=(akn/t)*log(akn/t)/log(2.0);else(r=k,u=n;h=1;break;if(h=0)cout«"H(X,Y)=-EEp(X,Y)logp(X,Y)="«b«endl;elsecout«"P("«r+1«",&quo

15、t;«u+1«i')為零,中斷，無值"«endl;cout«"條件嫡H(X|Y)計算："«endl;b=O,h=O;for(k=0;k<4;k+)doublei=0;for(n=0;n<4;n+)i+=(akn/t);for(彳號八今+=h(竺k豆H。)bh(擋k=n>)*_og(竺k=n>)、M0g(2b)_QsehA_breaksif(h#o)couAA=H(x_YH-MMp(><Y)_og(p(><Y)、p(Y)H=abaendmQseCOUAA=p(=

16、aa_.+xa=-=aac+x*湍"書«A=aendcouaa=(x_y)-aa-if(hnno)couAA=(X-Y)nH(x)H(x-YH=acbaendLQseCOUAA=p(=aa_.+xa=-=aac+x*湍"書«A=aend實驗二簡單信源編碼方法實現(xiàn)實驗?zāi)康恼莆誋uffman編碼方法。實驗學(xué)時2學(xué)時實驗準(zhǔn)備1.熟悉離散信源的編碼方法，重點是Huffman編碼方法，設(shè)計Huffman編碼的數(shù)據(jù)結(jié)構(gòu)和算法；2.編寫Huffman編碼的書面程序代碼。實驗內(nèi)容及步驟離散信源的Huffman編、譯碼方法說明：(1) 利用random函數(shù)構(gòu)造一個一維離散

17、隨機(jī)變量分布P(X)；(2) 構(gòu)造離散隨機(jī)變量的概率壓縮表；(3) 根據(jù)概率壓縮表構(gòu)造Huffman編碼表，并實現(xiàn)Huffman編碼；(4) 完成Huffman譯碼；(4)編寫本次實驗的實驗報告。附實驗二實驗內(nèi)容及程序源程序?qū)嶒灦x散信源的Huffman編、譯碼方法1實驗內(nèi)容(1) 利用random函數(shù)構(gòu)造一個一維離散隨機(jī)變量分布P(X)；(2) 根據(jù)概率壓縮表構(gòu)造Huffman編碼表，并實現(xiàn)Huffman編碼;完成Huffman譯碼；2數(shù)據(jù)結(jié)構(gòu)與算法描述(1)函數(shù)的定義：函數(shù)的數(shù)據(jù)成員1. 隨機(jī)生成歸一化一維離散變量函數(shù)代碼：voidaa(intn)(doublew=0;a=newdoubl

18、en;srand(unsigned)time(NULL);cout<<"隨機(jī)生成歸一化一維離散變量："<<endl;for(inti=0;i<n;i+)ai=rand()%50;w+=ai;for(inti=0;i<n;i+)(ai=ai/w;doublep;for(inti=0;i<n-1;i+)(for(intj=n-2;j>=i;j-)(if(aj<aj+1)p=aj+1;aj+1=aj;aj=p；cout<<"P(X):"for(inti=0;i<n;i+)(cout.pre

19、cision(3);cout<<ai<<setw(8);2. Huffman譯碼函數(shù)代碼:voidhuffman(double*a,string*c,intn)elemmp;stacks(n);double*b;b=newdoublen;for(inti=0;i<n;i+)bi=ai;double*d;d=newdoublen;for(inti=0;i<n;i+)di=i;double*e;e=newdoublen;for(inti=0;i<n;i+)ei=i;stringt;for(intm=n;m>=2;m-)bm-2+=bm-1;mp.a2

20、=dm-2;mp.a3=dm-1;s.push(mp);doublemp,mp1;for(inti=0;i<n-1;i+)for(intj=n-2;j>=i;j-)mp=b|j+1;mp1=dj+1;bO+1=bU;dO+1=dj;bj=mp;dj=mp1;cout«left«setw(6)<<"nP(X):"for(inti=0;i<m-1;i+)cout.precision(3);cout«setw(8)«bi;while(!s.isEmpty()(mp=s.pop();for(inti=0;i<

21、;n;i+)(if(mp.a2=ei)(t=ci;for(inti=0;i<n;i+)(if(mp.a2=ei)ci+="0"elseif(mp.a3=ei)(ci=t;ci+="1"(2)主函數(shù)main()實現(xiàn)初始化操作，完成對子函數(shù)的調(diào)用voidmain()intn;cout<<"輸入N:cin>>n;c=newstringn;aa(n);huffman(a,c,n);cout<<endl;cout<<setw(6)<<"各項Huffman編碼為:"<

22、;<endl;for(inti=0;i<n;i+)cout.precision(3);cout<<setw(8)<<ai;cout.precision(0);cout<<setw(n+4)<<ci;cout<<endl;3實驗數(shù)據(jù)與實驗結(jié)果Huffman編碼。測試數(shù)據(jù)：隨機(jī)生成歸一化離散變量，如下圖數(shù)據(jù)，并計算出各項實驗結(jié)果：4程序代碼活單：#include<stdio.h>#include<cstdio>#include<iomanip>#include<time.h>#i

23、nclude<cassert>#include<string>#include<iostream>usingnamespacestd;double*a;string*c;structelemdoublea2;doublea3;；classstackintsize;inttop;elem*list;publicnewelemsz;stack(constintsz=0)size=sz;top=0;list=stack()(deletelist;voidclear()top=0;voidpush(constelem&item)assert(top<s

24、ize);listtop+=item;returnlist-top;elempop()(assert(!isEmpty();elemtopValue()constassert(!isEmpty();returnlisttop-1;boolisEmpty()constreturntop=0;voidaa(intn)doublew=0;a=newdoublen;srand(unsigned)time(NULL);cout<<"隨機(jī)生成歸一化一維離散變量："<<endl;for(inti=0;i<n;i+)ai=rand()%50;w+=ai;for

25、(inti=0;i<n;i+)(ai=ai/w;doublep;for(inti=0;i<n-1;i+)(for(intj=n-2;j>=i;j-)(if(aj<aj+1)(P=aj+1;aj+1=aj;aj=p;cout<<"P(X):"for(inti=0;i<n;i+)(cout.precision(3);cout<<ai<<setw(8);voidhuffman(double*a,string*c,intn)(elemmp;stacks(n);double*b;b=newdoublen;for(int

26、i=0;i<n;i+)bi=ai;double*d;d=newdoublen;for(inti=0;i<n;i+)di=i;double*e;e=newdoublen;for(inti=0;i<n;i+)ei=i;stringt;for(intm=n;m>=2;m-)(bm-2+=bm-1;mp.a2=dm-2;mp.a3=dm-1;s.push(mp);doublemp,mp1;for(inti=0;i<n-1;i+)(for(intj=n-2;j>=i;j-)(if(bj<bj+1)(mp=bj+1;mp1=dj+1;bj+1=bj;dj+1=dj

27、;bj=mp;dj=mp1;cout<<left<<setw(6)<<"nP(X):"for(inti=0;i<m-1;i+)cout.precision(3);cout<<setw(8)<<bi;while(!s.isEmpty()mp=s.pop();for(inti=0;i<n;i+)if(mp.a2=ei)(t=ci;for(inti=0;i<n;i+)(if(mp.a2=ei)(ci=t;ci+="0"elseif(mp.a3=ei)ci+="1voidma

28、in()(intn;cout<<"輸入N：”;cin>>n;c=newstringn;aa(n);huffman(a,c,n);cout<<endl;cout<<setw(6)<<"各項Huffman編碼為:"<<endl;for(inti=0;i<n;i+)(cout.precision(3);cout<<setw(8)<<ai;cout.precision(0);cout<<setw(n+4)<<ci;cout<<endl;

29、實驗三典型信道容量計算實驗?zāi)康恼莆沼眠f推算法計算典型信道的容量的方法。實驗學(xué)時2學(xué)時實驗準(zhǔn)備1. 熟悉二進(jìn)信道的概率轉(zhuǎn)移矩陣表示，掌握信道容量的遞推算法，設(shè)計用遞推算法計二二進(jìn)信道容量的數(shù)據(jù)結(jié)構(gòu)和算法；編寫用遞推算法計算二進(jìn)信道容量的書面程序代碼。實驗內(nèi)容及步驟用遞推算法計算二進(jìn)信道的容量說明：(1) 構(gòu)造各種二進(jìn)信道的概率轉(zhuǎn)移矩陣；用遞推算法計算各種二進(jìn)信道的容量；不斷調(diào)整誤差精度對系統(tǒng)進(jìn)行測試，并進(jìn)行對比分析；編寫本次實驗的實驗報告。附實驗三內(nèi)容及源程序?qū)嶒炄眠f推算法計算二進(jìn)信道的容量(1) 1實驗內(nèi)容構(gòu)造各種二進(jìn)信道的概率轉(zhuǎn)移矩陣；用遞推算法計算各種二進(jìn)信道的容量；不斷調(diào)整誤差精度對系

30、統(tǒng)進(jìn)行測試，并進(jìn)行對比分析;2數(shù)據(jù)結(jié)構(gòu)與算法描述(1)函數(shù)的定義：函數(shù)的數(shù)據(jù)成員1.隨機(jī)生成二元對稱信道函數(shù)代碼:voidaa()(doublee=0;cout<<"隨機(jī)生成二元對稱信道為："<<endl;inti=0;for(intj=0;j<2;j+)(a0j=rand()%100;e+=a0j;for(intj=0;j<2;j+)(a0j=a0j/e;a11=a00;a10=a01;for(inti=0;i<2;i+)(for(intj=0;j<2;j+)(cout<<setw(12)<<aij;

31、cout<<endl;2.隨機(jī)生成二元刪除信道函數(shù)代碼:voidcc()(doublee=0;cout<<"隨機(jī)生成二元刪除信道為："<<endl;for(intj=0;j<2;j+)(b0j=rand()%100;e+=b0j;for(intj=0;j<2;j+)(b0j=b0j/e;b02=0;b10=0;e=0;for(intj=1;j<3;j+)(b1j=rand()%100;e+=b1j;for(intj=1;j<3;j+)(b1j=b1j/e;for(inti=0;i<2;i+)(for(intj

32、=0;j<3;j+)(cout<<setw(12)<<bij;cout<<endl;2. 求二元對稱信道最大信道容量和最大容量時w的值的函數(shù)代碼:voidbb()(doublew=0;doublee2=(0,0;for(w=0;w<=1;w+=0.01)(doubletmp=0;tmp=(w*a00+(1-w)*a01)*(log(1/(w*a00+(1-w)*a01)/log(2.0)+(w*a01)+(1-w)*a00)*(log(1/(w*a01)+(1-w)*a00)/log(2.0)-(a00*(log(1/a00)/log(2.0)+

33、(a01*(log(1/a01)/log(2.0);if(e0<tmp)(e0=tmp;e1=w;cout<<"最大信道容量為："<<setw(6)<<e0<<"此時w勺值為："<<e1<<endl;cout<<endl;3. 求二元刪除信道最大信道容量和最大容量時w的值的函數(shù)代碼:voiddd()(doubleP22;P10=0;P11=1;doubletemp2=(0,1;dodoubletmp1=0,tmp=0;for(inti=0;i<2;i+)for

34、(intj=0;j<3;j+)if(bij!=0)tmp1+=P1i*bij*log(1.0/bij)/log(2.0);doubletemp223;for(inti=0;i<2;i+)(for(intj=0;j<3;j+)temp2ij=P1i*bij;for(intj=0;j<3;j+)temp20j=temp20j+temp21j;for(intj=0;j<3;j+)if(temp20j!=0)tmp-=temp20j*log(temp20j)/log(2.0);tmp-=tmp1;if(tmp>=temp0)temp0=tmp;temp1=P10;P

35、10+=0.01;P11-=0.01;while(P10<=1.00);cout<<"最大信道容量為："<<temp0<<"信源的w®為"<<temp1<<endl;(2)主函數(shù)main()實現(xiàn)初始化操作，完成對子函數(shù)的調(diào)用voidmain()(srand(unsigned)time(NULL);aa();bb();cc();dd();3實驗數(shù)據(jù)與實驗結(jié)果測試數(shù)據(jù)：隨機(jī)生成了2*2矩陣和2*3矩陣，并求得最大容量和w的值實驗結(jié)果：4程序代碼活單：#include<iostream>#include<iomanip>#include<c