信息論與編碼實(shí)驗(yàn)指導(dǎo)書(shū)

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

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

3、進(jìn)行總結(jié)和整理，并編寫(xiě)課程實(shí)驗(yàn)報(bào)告。報(bào)告格式按江西藍(lán)天學(xué)院實(shí)驗(yàn)報(bào)告紙格式填寫(xiě)實(shí)驗(yàn)一 二維隨機(jī)變量信息熵的計(jì)算 實(shí)驗(yàn)?zāi)康?掌握二變量多種信息量的計(jì)算方法。 實(shí)驗(yàn)學(xué)時(shí) 2 學(xué)時(shí) 實(shí)驗(yàn)準(zhǔn)備 1熟悉二變量多種信息量的計(jì)算方法，設(shè)計(jì)實(shí)驗(yàn)的數(shù)據(jù)結(jié)構(gòu)和算法； 2編寫(xiě)計(jì)算二維隨機(jī)變量信息量的書(shū)面程序代碼。 實(shí)驗(yàn)內(nèi)容及步驟 離散二維隨機(jī)變換熵的計(jì)算 說(shuō)明：(1) 利用 random 函數(shù)和歸一化方法構(gòu)造一個(gè)二維離散隨機(jī)變量( X ，Y )；(2) 分別計(jì)算X與丫的熵、聯(lián)合熵、條件熵：H (X )、H (丫)、H (X,Y ) H (X|Y )、 I(X|Y)；(3) 對(duì)測(cè)試通過(guò)的程序進(jìn)行規(guī)范和優(yōu)化； ( 4 )

4、編寫(xiě)本次實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。附實(shí)驗(yàn)一主要內(nèi)容及源程序?qū)嶒?yàn)一 離散二維隨機(jī)變量信息熵的計(jì)算1 實(shí)驗(yàn)內(nèi)容(1)利用 random 函數(shù)和歸一化方法構(gòu)造一個(gè)二維離散隨機(jī)變量(X ，丫 )；(2 )分別計(jì)算X與丫的熵、聯(lián)合熵、條件熵： H (X )、H (丫)、H (X,Y ) H (X|Y )、I (X|Y );2 數(shù)據(jù)結(jié)構(gòu)與算法描述( 1)函數(shù)的定義：函數(shù)的數(shù)據(jù)成員1. 隨機(jī)生成函數(shù)的代碼：int k,n,t=0;double a44,b=0,c=0;for (k=0;k<4;k+) for (n=0;n<4;n+)akn=rand()%100;t+=akn;coutvv "從到

5、間隨機(jī)取得行列的 random函數(shù)："vvendl;for (k=0;k<4;k+)for (n=0;nv4;n+)coutvvsetw(5)vvakn;coutvvendl;2. 函數(shù)歸一化代碼：coutvv " 函數(shù)歸一化： "vvendl;for (k=0;kv4;k+)for (n=0;nv4;n+)coutvvsetw(12)vvakn/t;coutvvendl;3. H(Y) 、 H(X) 計(jì)算代碼：coutvv "H(Y) 計(jì)算： "vvsetw(20)vv "H(X) 計(jì)算： "vvendl;int e

6、=1;for (k=0;kv4;k+)double i=0,g=0;for (n=0;nv4;n+)i+=(akn/t);g+=(ank/t);coutvv"P(Y" vvk+1vv") ： "vvivvsetw(8)vv "P(X" vvevv") ： "vvgvvendl; +e;b-=(i*log(i)/log(2.0);c-=(g*log(g)/log(2.0);coutvv "H(Y)=-刀 p(Y)log p(Y)="<<bvvendl;coutvv "H(X)

7、=-刀 p(X)log p(X)="vvcvvendl;4.聯(lián)合熵H ( X,Y)計(jì)算代碼：coutvv "聯(lián)合熵 H (X,Y)計(jì)算："vvendl;b=0;int r,u,h=0;for (k=0;kv4;k+)for (n=0;nv4;n+)if (akn!=0) b-=(akn/t)*log(akn/t)/log(2.0);elser=k,u=n;h=1; break ;if (h=0)coutvv "H(X,Y)=- EE p(X,Y)log p(X,Y)=" vvbvvendl;else cout« "P(&qu

8、ot; vv葉 1<<"," vvu+1<<')為零，中斷,無(wú)值"<<endl;5.條件熵H ( X|Y)計(jì)算代碼： coutvv " 條件熵 H( X|Y )計(jì)算： "vvendl;b=0,h=0;for (k=0;kv4;k+)double i=0;for (n=0;nv4;n+) i+=(akn/t);for (n=0;nv4;n+)if (akn!=0) b-=(akn/t)*log(akn/t)/i)/log(2.0);else h=1; break;if (h=0)coutvv "

9、;H(X|Y)=- EE P(X,Y)log(P(X,Y)/P(Y)=" vvbvvendl; else coutvv "P(" <<葉 1<<"," <<口+1<<')為零，中斷,無(wú)值"<<endl; coutvv "I (X|Y)計(jì)算："vvendl;if (h=0)coutvv "I ( X|Y)=H(X)-H(X|Y)=" vvc-bvvendl;else coutvv "P(" vv葉ivv&quo

10、t;," vvu+1vV)為零，中斷,無(wú)值"vvendl;( 2)主函數(shù) main () 實(shí)現(xiàn)初始化操作，完成對(duì)子函數(shù)的調(diào)用 因?yàn)檎麄€(gè)程序是寫(xiě)在 main 函數(shù)中，就不列出，會(huì)在下面源程序清單中給出程序。3 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果 這里設(shè)定函數(shù)為 4 行 4 列的隨機(jī)矩陣。 然后函數(shù)歸一化，即：把所有數(shù)字相加，再用每個(gè)數(shù)去除，就得到了歸一化后的矩陣。而 H(X)、 H(Y)、 H(X,Y ) H(X|Y)、 I(X|Y )就根據(jù)課本上的公式，然后編程。輸出結(jié)果如下：4 程序代碼清單：#include <stdio.h>#include <cmath>#i

11、nclude <iomanip>#include <time.h>#include <iostream>using namespace std;void main()int k,n,t=0;double a44,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;coutvv "從0到100間隨機(jī)取得行列的random函數(shù)："<<endl;for (k=0;k<4;k+)for

12、(n=0;nv4;n+) coutvvsetw(5)vvakn;coutvvendl;coutvv "函數(shù)歸一化： "vvendl;for (k=0;kv4;k+)for (n=0;nv4;n+) coutvvsetw(12)vvakn/t;coutvvendl;coutvv "H(Y)計(jì)算："vvsetw(20)vv "H(X)計(jì)算："<<endl; int e=1;for (k=0;kv4;k+)double i=0,g=0;for (n=0;nv4;n+)i+=(akn/t); g+=(ank/t);cout<

13、< "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);coutvv "H(Y)=-刀 P(Y)log p(Y)="vvbvvendl;coutvv "H(X)=-刀 p(X)log p(X)="

14、vvcvvendl;coutvv "聯(lián)合熵 H ( X,Y)計(jì)算："vvendl;b=0;int r,u,h=0;for (k=0;kv4;k+)for (n=0;nv4;n+)if (akn!=0) b-=(akn/t)*log(akn/t)/log(2.0);elser=k,u=n;h=1; break ;if (h=0)coutvv "H(X,Y)=- EE p(X,Y)log p(X,Y)=" vvbvvendl;else coutvv "P(" vv葉ivv"," vvu+1vV)為零，中斷，無(wú)值&quo

15、t;vvendl;coutvv "條件熵 H ( X|Y)計(jì)算："vvendl;b=0，h=0;for (k=0;kv4;k+)double i=0;for (n=0;nv4;n+) i+=(akn/t);for (n=0;nv4;n+)if (akn!=0)b-=(akn/t)*log(akn/t)/i)/log(2.0);else h=1; break ;if (h=0)cout<<"H(X|Y)=- EE P(X,Y)log(P(X,Y)/P(Y)=" vvbvvendl;else cout« "P(" &

16、lt;<葉 1<<"," <<u+1«')為零，中斷,無(wú)值"<<endl; cout<< "I (X|Y)計(jì)算："endl;if (h=0)cout<< "I ( X|Y) =H(X)-H(X|Y)=" <<c-b<<endl;else cout« "P(" <<葉 1<<"," <<u+1«')為零，中斷,無(wú)值&q

17、uot;<<endl;實(shí)驗(yàn)二 簡(jiǎn)單信源編碼方法實(shí)現(xiàn) 實(shí)驗(yàn)?zāi)康?掌握 Huffman 編碼方法。 實(shí)驗(yàn)學(xué)時(shí) 2 學(xué)時(shí) 實(shí)驗(yàn)準(zhǔn)備 1熟悉離散信源的編碼方法，重點(diǎn)是 Huffman 編碼方法，設(shè)計(jì) Huffman 編碼的數(shù)據(jù)結(jié)構(gòu) 和算法；2編寫(xiě) Huffman 編碼的書(shū)面程序代碼。 實(shí)驗(yàn)內(nèi)容及步驟 離散信源的 Huffman 編、譯碼方法說(shuō)明：(1) 利用random函數(shù)構(gòu)造一個(gè)一維離散隨機(jī)變量分布 P (X)；(2) 構(gòu)造離散隨機(jī)變量的概率壓縮表；( 3)根據(jù)概率壓縮表構(gòu)造 Huffman 編碼表，并實(shí)現(xiàn) Huffman 編碼；( 4)完成 Huffman 譯碼；( 4 )編寫(xiě)本次實(shí)驗(yàn)

18、的實(shí)驗(yàn)報(bào)告。附實(shí)驗(yàn)二實(shí)驗(yàn)內(nèi)容及程序源程序?qū)嶒?yàn)二 離散信源的 Huffman 編、譯碼方法1 實(shí)驗(yàn)內(nèi)容(1)利用random函數(shù)構(gòu)造一個(gè)一維離散隨機(jī)變量分布 P( X)；( 2)根據(jù)概率壓縮表構(gòu)造 Huffman 編碼表，并實(shí)現(xiàn) Huffman 編碼；( 3)完成 Huffman 譯碼；2 數(shù)據(jù)結(jié)構(gòu)與算法描述(1)函數(shù)的定義：函數(shù)的數(shù)據(jù)成員1. 隨機(jī)生成歸一化一維離散變量函數(shù)代碼：void aa( int n)double w=0;a=new double n;srand( unsigned )time(NULL);cout<< "隨機(jī)生成歸一化一維離散變量： "

19、 <<endl;for ( int i=0;i<n;i+)ai=rand()%50;w+=ai;for ( int i=0;i<n;i+)ai=ai/w;double p;for ( int i=0;i<n-1;i+)for ( int j=n-2;j>=i;j-)if (aj<aj+1)p=aj+1;aj+1=aj;aj=p;cout<< "P(X):" ;for ( int i=0;i<n;i+)cout.precision(3);cout<<ai<<setw(8);2. Huffman

20、 譯碼函數(shù)代碼：void huffman( double *a,string *c, int n)elem mp;stack s(n);double *b;b= new double n; for (int i=0;i<n;i+)bi=ai; double *d;d= new double n; for (int i=0;i<n;i+)di=i; double *e;e= new double n; for (int i=0;i<n;i+)ei=i; string t;for ( int m=n;m>=2;m-)bm-2+=bm-1;mp.a2=dm-2;mp.a3=d

21、m-1;s.push(mp);double mp,mp1;for ( int i=0;i<n-1;i+)for (int j=n-2;j>=i;j-)if (bj<bj+1)mp=bj+1; mp1=dj+1;bj+1=bj; dj+1=dj; bj=mp;dj=mp1; cout<<left<<setw(6)<< "nP(X):" ; for ( int i=0;i<m-1;i+)cout.precision(3);cout<<setw(8)<<bi;while (!s.isEmpty()

22、mp=s.pop();for (int i=0;i<n;i+)if (mp.a2=ei)t=ci;for (int i=0;i<n;i+)if (mp.a2=ei)ci=t;ci+= "0" ;else if (mp.a3=ei)ci=t; ci+= "1" ;( 2)主函數(shù) main() 實(shí)現(xiàn)初始化操作，完成對(duì)子函數(shù)的調(diào)用 void main()int n;cout<< "輸入 N："cin>>n; c=newstringn;aa(n); huffman(a,c,n); cout<<e

23、ndl;cout<<setw(6)<< " 各項(xiàng) Huffman 編碼為 :" <<endl;for ( int i=0;i<n;i+)cout.precision(3); cout<<setw(8)<<ai;cout.precision(0); cout<<setw(n+4)<<ci;cout<<endl;3 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果 測(cè)試數(shù)據(jù)：隨機(jī)生成歸一化離散變量，如下圖數(shù)據(jù)，并計(jì)算出各項(xiàng) Huffman 編碼。 實(shí)驗(yàn)結(jié)果：4 程序代碼清單：#include <std

24、io.h>#include <cstdio>#include <iomanip>#include <time.h>#include <cassert>#include <string>#include <iostream>using namespace std;double *a;string *c;struct elemdouble a2;double a3; ;class stackint size;int top;elem *list;public :stack( const int sz=0)size=sz;

25、top=0;list= newelemsz; stack() delete list;void clear()top=0;void push( const elem& item)assert(top<size);listtop+=item; elem pop()assert(!isEmpty(); return list-top; elem topValue() const assert(!isEmpty(); return listtop-1; bool isEmpty() const return top=0;void aa( int n)double w=0;a=new d

26、ouble n;srand( unsigned )time(NULL);cout<< "隨機(jī)生成歸一化一維離散變量： " <<endl;for ( int i=0;i<n;i+)ai=rand()%50; w+=ai;for ( int i=0;i<n;i+)ai=ai/w;double p;for ( int i=0;i<n-1;i+)for ( int j=n-2;j>=i;j-)if (aj<aj+1) p=aj+1; aj+1=aj; aj=p;cout<< "P(X):" ;fo

27、r ( int i=0;i<n;i+)cout.precision(3); cout<<ai<<setw(8); void huffman( double *a,string *c, int n)elem mp;stack s(n);double *b;b= new double n; for (int i=0;i<n;i+)bi=ai; double *d;d= new double n; for (int i=0;i<n;i+)di=i; double *e;e= new double n; for (int i=0;i<n;i+)ei=i;

28、 string t;for ( int m=n;m>=2;m-)bm-2+=bm-1;mp.a2=dm-2;mp.a3=dm-1;s.push(mp);double mp,mp1;for ( int i=0;i<n-1;i+)for (int j=n-2;j>=i;j-)if (bj<bj+1)mp=bj+1; mp1=dj+1; bj+1=bj; dj+1=dj; bj=mp;dj=mp1;cout<<left<<setw(6)<< "nP(X):" ;for ( int i=0;i<m-1;i+)cout

29、.precision(3);cout<<setw(8)<<bi;while (!s.isEmpty()mp=s.pop();for (int i=0;i<n;i+)if (mp.a2=ei)t=ci;for (int i=0;i<n;i+)if (mp.a2=ei)ci=t;ci+= "0" ;else if (mp.a3=ei)ci=t;ci+= "1" voidmain()int n;cout<< "輸入 N："cin>>n;c=newstringn;aa(n);huff

30、man(a,c,n);cout<<endl;cout<<setw(6)<< " 各項(xiàng) Huffman 編碼為 :" <<endl;for ( int i=0;i<n;i+)cout.precision(3);cout<<setw(8)<<ai;cout.precision(0);cout<<setw(n+4)<<ci;cout<<endl;實(shí)驗(yàn)三 典型信道容量計(jì)算 實(shí)驗(yàn)?zāi)康?掌握用遞推算法計(jì)算典型信道的容量的方法。 實(shí)驗(yàn)學(xué)時(shí) 2 學(xué)時(shí) 實(shí)驗(yàn)準(zhǔn)備 1熟悉二進(jìn)信道的

31、概率轉(zhuǎn)移矩陣表示，掌握信道容量的遞推算法，設(shè)計(jì)用遞推算法計(jì)算二進(jìn)信道容量的數(shù)據(jù)結(jié)構(gòu)和算法；2編寫(xiě)用遞推算法計(jì)算二進(jìn)信道容量的書(shū)面程序代碼 實(shí)驗(yàn)內(nèi)容及步驟 用遞推算法計(jì)算二進(jìn)信道的容量說(shuō)明：（1）構(gòu)造各種二進(jìn)信道的概率轉(zhuǎn)移矩陣；（2）用遞推算法計(jì)算各種二進(jìn)信道的容量；（3）不斷調(diào)整誤差精度對(duì)系統(tǒng)進(jìn)行測(cè)試，并進(jìn)行對(duì)比分析；（4）編寫(xiě)本次實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告。附實(shí)驗(yàn)三內(nèi)容及源程序?qū)嶒?yàn)三 用遞推算法計(jì)算二進(jìn)信道的容量1 實(shí)驗(yàn)內(nèi)容（1）構(gòu)造各種二進(jìn)信道的概率轉(zhuǎn)移矩陣；（2）用遞推算法計(jì)算各種二進(jìn)信道的容量；（3）不斷調(diào)整誤差精度對(duì)系統(tǒng)進(jìn)行測(cè)試，并進(jìn)行對(duì)比分析；2 數(shù)據(jù)結(jié)構(gòu)與算法描述（1）函數(shù)的定義：函數(shù)的數(shù)據(jù)

32、成員1. 隨機(jī)生成二元對(duì)稱信道函數(shù)代碼：void aa（）double e=0;cout<< "隨機(jī)生成二元對(duì)稱信道為： " <<endl;int i=0;for （ int j=0;j<2;j+）a0j=rand（）%100;e+=a0j;for （ int j=0;j<2;j+）a0j=a0j/e;a11=a00;a10=a01;for （ int i=0;i<2;i+）for （ int j=0;j<2;j+）cout<<setw（12）<<aij;cout<<endl;2. 隨機(jī)生成

33、二元?jiǎng)h除信道函數(shù)代碼：void cc()double e=0;cout<< "隨機(jī)生成二元?jiǎng)h除信道為： " <<endl;for ( int j=0;j<2;j+)b0j=rand()%100;e+=b0j;for ( int j=0;j<2;j+)b0j=b0j/e;b02=0;b10=0;e=0;for ( int j=1;j<3;j+)b1j=rand()%100;e+=b1j;for ( int j=1;j<3;j+)b1j=b1j/e;for ( int i=0;i<2;i+)for ( int j=0;j&l

34、t;3;j+)cout<<setw(12)<<bij;cout<<endl;3. 求二元對(duì)稱信道最大信道容量和最大容量時(shí) w 的值的函數(shù)代碼：void bb()double w=0;double e2=0,0;for (w=0;w<=1;w+=0.01)double tmp=0;tmp=(w*a00+(1-w)*a01)*(log(1/(w*a00+(1-w)*a01)/log(2.0)+(w*a01)+(1-w)*a 00)*(log(1/(w*a01)+(1-w)*a00)/log(2.0)-(a00*(log(1/a00)/log(2.0)+(a

35、01*(log(1/ a01)/log(2.0);if (e0<tmp)e0=tmp;e1=w;coutvv "最大信道容量為："v<setw(6)vve0vv "此時(shí) W勺值為："v<e1v<endl;cout<<endl;4. 求二元?jiǎng)h除信道最大信道容量和最大容量時(shí) w 勺值勺函數(shù)代碼：void dd()double P22;P10=0;P11=1;double temp2=0,1;dodouble tmp1=0,tmp=0;for ( int i=0;iv2;i+)for ( int j=0;jv3;j+)if

36、(bij!=0)tmp1+=P1i*bij*log(1.0/bij)/log(2.0);double temp223;for ( int i=0;iv2;i+)for ( int j=0;jv3;j+)temp2ij=P1i*bij;for ( int j=0;jv3;j+)temp20j=temp20j+temp21j;for ( int j=0;jv3;j+)if (temp20j!=0)tmp-=temp20j*log(temp20j)/log(2.0); tmp-=tmp1;if (tmp>=temp0)temp0=tmp;temp1=P10;P10+=0.01;P11-=0.0

37、1;while (P10v=1.00);coutvv "最大信道容量為:"vvtemp0vv "信源的 w值為"vvtemp1vvendl;( 2)主函數(shù) main() 實(shí)現(xiàn)初始化操作，完成對(duì)子函數(shù)的調(diào)用void main()srand( unsigned )time(NULL);aa();bb();cc();dd();3 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果測(cè)試數(shù)據(jù)：隨機(jī)生成了 2*2 矩陣和 2*3 矩陣，并求得最大容量和 w 的值 實(shí)驗(yàn)結(jié)果：4 程序代碼清單：#include <iostream>#include <time.h>#inclu

38、de <iomanip>#include <cmath>using namespace std;double a22;double b23;void aa()double e=0;cout<< "隨機(jī)生成二元對(duì)稱信道為： " <<endl;int i=0;for ( int j=0;j<2;j+)a0j=rand()%100; e+=a0j;for ( int j=0;j<2;j+)a0j=a0j/e; a11=a00;a10=a01;for ( int i=0;i<2;i+)for ( int j=0;j<2;j+)cout<<setw(12)<<aij;cout<<endl;void bb()double w=0;double e2=0,0;for (w=0