信息论与编码实验指导书

信息论与编码实验指导书1 课程实验目的本课程是一门实践性很强的专业课和核心课程，根据课程理论教学的需要安排了 6 学 时的配套实验教学，主要内容涉及信息度量的计算方法、典型信源编码方法、典型信道容 量计算方法和数据压缩方法四个实验，这四个实验的开设一方面有助于学生消化、巩固课 程理论教学的知识，另一方面又可培养学生实践动手能力，同时为后续课程做好准备。2 课程实验要求2.1 课程实验准备要求(1) 课程实验主要为设计性实验，要求学生熟悉掌握在VC环境下编写和调试C+程序 的方法。( 2)要求学生在实验前复习实验所用到的预备知识。可以查阅教材或者相关的参考资 料，这需要学生有自主的学习意识和整理知识的能力。( 3)根据实验项目，设计相关的数据结构和算法，再转换为对应的书面程序，并进行 静态检查，尽量减少语法错误和逻辑错误。上机前的充分准备能高效利用机时，在有限的 时间内完成更多的实验内容。2.2 课程实验过程要求(1)生成源代码。将课前编写好的书面代码，利用 VC自带的编辑器尽快输入为转换 为源代码；( 2)程序调试和软件测试。要求学生熟练掌握调试工具，调试正确后，认真整理源程 序和注释，给出带有完整注释且格式良好的源程序清单和结果。(3)完成实验报告。根据实验内容和完成情况，按照附件 1 给定的格式完成课程实验 报告的编写2.3 课程实验报告要求在每次课程实验后要及时进行总结和整理，并编写课程实验报告。报告格式按江西蓝 天学院实验报告纸格式填写。实验一 二维随机变量信息熵的计算 实验目的 掌握二变量多种信息量的计算方法。 实验学时 2 学时 实验准备 1熟悉二变量多种信息量的计算方法，设计实验的数据结构和算法；2编写计算二维随机变量信息量的书面程序代码。 实验内容及步骤 离散二维随机变换熵的计算说明：(1) 利用random函数和归一化方法构造一个二维离散随机变量(X, Y)；(2) 分别计算X与丫的熵、联合熵、条件熵：H(X)、H(Y、H(X,Y)H(X|Y)、I(X|Y)；(3) 对测试通过的程序进行规范和优化；( 4 )编写本次实验的实验报告。附实验一主要内容及源程序实验一 离散二维随机变量信息熵的计算1 实验内容(1) 利用random函数和归一化方法构造一个二维离散随机变量(X, Y)；(2) 分别计算X与丫的熵、联合熵、条件熵：H( X)、H( Y)、H( X,Y) H( X|Y)、I( X|Y)；2 数据结构与算法描述( 1)函数的定义：函数的数据成员1. 随机生成函数的代码：int k,n,t=0;double a44,b=0,c=0;for (k=0;k4;k+)for (n=0;n4;n+)akn=rand()%100;t+=akn;coutvv从到间随机取得行列的random函数：endl;for (k=0;k4;k+)for (n=0;n4;n+)coutsetw(5)akn;coutendl;2. 函数归一化代码：cout 函数归一化： endl;for (k=0;k4;k+)for (n=0;n4;n+)coutsetw(12)akn/t; coutendl;3. H(Y) 、 H(X) 计算代码：coutvv H(Y)计算：vvsetw(20)vv H(X)计算：endl;int e=1;for (k=0;k4;k+)double i=0,g=0;for (n=0;n4;n+)i+=(akn/t);g+=(ank/t);cout P(Y k+1) ： isetw(8) P(Xe) ： gendl;+e;b-=(i*log(i)/log(2.0);c-=(g*log(g)/log(2.0);coutH(Y)二 刀p(Y)log p(Y)=bendl;coutH(X)二 刀 p(X)log p(X)=cendl;4. 联合熵H (X,Y)计算代码：coutvv联合熵 H (X,Y)计算：endl;b=0;int r,u,h=0;for (k=0;k4;k+)for (n=0;n4;n+)if (akn!=0)b-=(akn/t)*log(akn/t)/log(2.0);elser=k,u=n;h=1;break ;if (h=0)coutH(X,Y)二刀刀 P(X,Y)log p(X,Y)=bendl;else cout P( r+1, u+1勺 为零，中断，无值endl;5. 条件熵H (X|Y)计算代码：coutvv条件熵 H (X|Y)计算：endl;b=0,h=0;for (k=0;k4;k+)double i=0;for (n=0;n4;n+)i+=(akn/t);for (n=0;n4;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)二刀刀 P(X,Y)log(P(X,Y)/P(Y)=bendl;else cout P( r+1, u+1勺 为零，中断,无值endl;coutl (X|Y)计算：endl;if (h=0)cout I (X|Y) =H(X)-H(X|Y)= c-bendl;else cout P( r+1, u+1勺 为零，中断，无值endl;( 2)主函数 main() 实现初始化操作，完成对子函数的调用因为整个程序是写在 main 函数中，就不列出，会在下面源程序清单中给出程序。3 实验数据与实验结果这里设定函数为 4行 4 列的随机矩阵。然后函数归一化，即：把所有数字相加，再用每个数去除，就得到了归一化后的矩阵而H (X)、H (Y)、H (X,Y) H (X|Y)、I (X|Y)就根据课本上的公式，然后编程。输出结果如下：4 程序代码清单：#include #include #include #include #include using namespacestd;void main()int k,n,t=0;double a44,b=0,c=0;srand( unsigned )time(NULL);for (k=0;k4;k+)for (n=0;n4;n+)akn=rand()%100; t+=akn;cout从0到100间随机取得行列的random函数：endl;for (k=0;k4;k+)for (n=0;n4;n+)coutsetw(5)akn;coutendl;cout函数归一化：e ndl;for (k=0;k4;k+)for (n=0;n4;n+)coutsetw(12)akn/t;coutendl;coutvv H(Y)计算：vvsetw(20)vv H(X)计算：endl;int e=1;for (k=0;k4;k+)double i=0,g=0;for (n=0;n4;n+)i+=(akn/t);g+=(ank/t);cout P(Y k+1) ： isetw(8) P(Xe) ： gendl;+e;b-=(i*log(i)/log(2.0);c-=(g*log(g)/log(2.0);coutH(Y)二 刀p(Y)log p(Y)=bendl;coutH(X)二 刀 p(X)log p(X)=cendl;coutvv联合熵 H (X,Y)计算：endl; b=0;int r,u,h=0;for (k=0;k4;k+)for (n=0;n4;n+)if (akn!=0)b-=(akn/t)*log(akn/t)/log(2.0);elsebGaKocouaa=h(x-y)卩匕X p(x-Y)-og p(x-yh= AAbAAendre-se COUAA =p(= AA_.+XA=-= AAC+X #-出血=八八马2八COUAA=BH (X-Y)斗wi UAAend-八bHphHO 八for (kHO八 k4八 k+)宀doub-e -Ho-for (nH05n+)for (nH05n+)=h(asrmHo)bhaassKTogaassuowogRome-se 宀 hA八 break=h(hHHO)宀 COUAA =H(X_Y)卩 xMp(XY)_og(p(XY)、p(Y)H=仝 b 仝end_ e-se COUAA =p(= AA_.+XA=-= AAC+X #-出血=八八马2 八 couAd_(x_Y)斗w-=仝 endif (hHHO)couAl-(X_Y) hh(x)士(x_yh=仝 cbAAendr e-se COUAA =p(= AA_.+XA=-= AAC+X #-出血=八八马2 八实验二 简单信源编码方法实现 实验目的 掌握 Huffman 编码方法。 实验学时 2 学时 实验准备 1熟悉离散信源的编码方法，重点是Huffman编码方法，设计Huffman编码的数据结构和算法；2编写 Huffman 编码的书面程序代码。 实验内容及步骤 离散信源的 Huffman 编、译码方法说明：(1) 利用random函数构造一个一维离散随机变量分布 P (X)；(2) 构造离散随机变量的概率压缩表；( 3)根据概率压缩表构造 Huffman 编码表，并实现 Huffman 编码；( 4)完成 Huffman 译码；(4)编写本次实验的实验报告。附实验二实验内容及程序源程序实验二 离散信源的 Huffman 编、译码方法1 实验内容(1)利用 random 函数构造一个一维离散随机变量分布 P(X)；( 2)根据概率压缩表构造 Huffman 编码表，并实现 Huffman 编码；( 3)完成 Huffman 译码；2 数据结构与算法描述(1)函数的定义：函数的数据成员1. 随机生成归一化一维离散变量函数代码：void aa( int n)double w=0;a=new double n;srand( unsigned )time(NULL);cout 随机生成归一化一维离散变量： endl;for (int i=0;in;i+)ai=rand()%50;w+=ai;for (int i=0;in;i+)ai=ai/w;double p;for (int i=0;i=i;j-)if (ajaj+1)p=aj+1;aj+1=aj;aj=p;cout P(X): ;for (int i=0;in;i+)cout.precision(3);coutaisetw(8);2. Huffman 译码函数代码：void huffman( double *a,string *c, int n)elem mp;stack s(n);double *b;b= new double n; for (int i=0;in;i+)bi=ai;double *d;d= new double n; for (int i=0;in;i+)di=i;double *e;e= new double n; for (int i=0;i=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=i;j-)if (bjbj+1)mp=bj+1; mp1=dj+1;bj+1=bj; dj+1=dj;bj=mp;dj=mp1;nP(X):coutleftsetw(6)for (int i=0;im-1;i+)cout.precision(3);coutsetw(8)bi;while (!s.isEmpty()mp=s.pop();for (int i=0;in;i+)if (mp.a2=ei)t=ci;for (int i=0;in;i+)if (mp.a2=ei)ci=t;ci+= 0 ;else if (mp.a3=ei)ci=t;ci+= 1( 2)主函数 main() 实现初始化操作，完成对子函数的调用 void main()int n;coutn;c=newstringn;aa(n);huffman(a,c,n);coutendl;coutsetw(6)vv 各项 Huffman编码为:endl;for (int i=0;in;i+) cout.precision(3);coutsetw(8)ai;cout.precision(0);coutsetw(n+4)ci;coutendl;3 实验数据与实验结果Huffman 编码。测试数据：随机生成归一化离散变量，如下图数据，并计算出各项 实验结果：4 程序代码清单：#include #include #include #include #include #include #include using namespacestd;double *a;string *c;struct elemdouble a2;double a3;class stackint size;int top;elem *list;publicstack( const int sz=0)size=sz;top=0;list= newelemsz;stack() delete list;void clear()top=0;void push( const elem& item)assert(topsize);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 double n;srand( unsigned )time(NULL);cout 随机生成归一化一维离散变量： endl;for (int i=0;in;i+)ai=rand()%50;w+=ai;for (int i=0;in;i+)ai=ai/w;double p;for (int i=0;i=i;j-)if (ajaj+1)p=aj+1;aj+1=aj;aj=p;cout P(X): ;for (int i=0;in;i+)cout.precision(3);coutaisetw(8);int n)void huffman( double *a,string *c,elem mp;stack s(n);double *b;b= new double n; for (int i=0;in;i+)bi=ai;double *d;d= new double n; for (int i=0;in;i+)di=i;double *e;e= new double n; for (int i=0;i=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=i;j-)if (bjbj+1)mp=bj+1; mp1=dj+1;bj+1=bj; dj+1=dj;bj=mp;dj=mp1;coutleftsetw(6) nP(X):for (int i=0;im-1;i+)cout.precision(3);coutsetw(8)bi;while (!s.isEmpty()mp=s.pop();for (int i=0;in;i+)if (mp.a2=ei)t=ci;for (int i=0;in;i+)if (mp.a2=ei)ci=t;ci+= 0 ;else if (mp.a3=ei)ci=t;ci+= 1void main()int n;coutn;c=newstringn;aa(n);huffman(a,c,n);coutendl;coutsetw(6)vv 各项 Huffman编码为:endl;for (int i=0;in;i+)cout.precision(3);coutsetw(8)ai;cout.precision(0);coutsetw(n+4)ci;coutendl;实验三 典型信道容量计算 实验目的 掌握用递推算法计算典型信道的容量的方法。 实验学时 2 学时 实验准备 1熟悉二进信道的概率转移矩阵表示，掌握信道容量的递推算法，设计用递推算法计 算二进信道容量的数据结构和算法；2编写用递推算法计算二进信道容量的书面程序代码。 实验内容及步骤 用递推算法计算二进信道的容量说明：（1）构造各种二进信道的概率转移矩阵；（2）用递推算法计算各种二进信道的容量；（3）不断调整误差精度对系统进行测试，并进行对比分析；（4）编写本次实验的实验报告。附实验三内容及源程序实验三 用递推算法计算二进信道的容量1 实验内容（1）构造各种二进信道的概率转移矩阵；（2）用递推算法计算各种二进信道的容量；（3）不断调整误差精度对系统进行测试，并进行对比分析；2 数据结构与算法描述（1）函数的定义：函数的数据成员1. 随机生成二元对称信道函数代码：void aa（）double e=0;cout 随机生成二元对称信道为： endl;int i=0;for (int j=0;j2;j+)a0j=rand()%100;e+=a0j;for (int j=0;j2;j+)a0j=a0j/e;a11=a00;a10=a01;for (int i=0;i2;i+)for (int j=0;j2;j+)coutsetw(12)aij;coutendl;2. 随机生成二元删除信道函数代码：void cc()double e=0; endl;cout 随机生成二元删除信道为：for (int j=0;j2;j+)b0j=rand()%100;e+=b0j;for (int j=0;j2;j+)b0j=b0j/e;b02=0;b10=0;e=0;for (int j=1;j3;j+)b1j=rand()%100;e+=b1j;for (int j=1;j3;j+)b1j=b1j/e;for (int i=0;i2;i+)for (int j=0;j3;j+)coutsetw(12)bij;coutendl;w的值的函数代码:3. 求二元对称信道最大信道容量和最大容量时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)*a00)*(log(1/(w*a01)+(1-w)*a00)/log(2.0)-(a00*(log(1/a00)/log(2.0)+(a01*(log(1/a01)/log(2.0) );if (e0tmp)e0=tmp;e1=w;e1endl;coutvv最大信道容量为：vvsetw(6)vve0vv 此时W勺值为:coutendl;4. 求二元删除信道最大信道容量和最大容量时w的值的函数代码：void dd()double P22;P10=0;P11=1;double temp2=0,1;dodouble tmp1=0,tmp=0;for (int i=0;i2;i+)for (int j=0;j3;j+)if (bij!=0)tmp1+=P1i*bij*log(1.0/bij)/log(2.0);double temp223;for (int i=0;i2;i+)for (int j=0;j3;j+)temp2ij=P1i*bij;for (int j=0;j3;j+)temp20j=temp20j+temp21j;for (int j=0;j=temp0)temp0=tmp;temp1=P10;P10+=0.01;P11-=0.01; while (P10=1.00);cout最大信道容量为：temp0vv信源的w值为temp1vvendl;(2)主函数 main() 实现初始化操作，完成对子函数的调用void main()srand( unsigned)time(NULL);aa();bb();cc();dd();3 实验数据与实验结果测试数据：随机生成了 2*2矩阵和2*3矩阵，并求得最大容量和 w的值实验结果：4 程序代码清单：#include #include #include #include using namespacestd;double a22;double b23;void aa()double e=0; endl;cout 随机生成二元对称信道为：int i=0;for (int j=0;j2;j+)a0j=rand()%100;e+=a0j;for (int j=0;j2;j+)a0j=a0j/e;a11=a00;a10=a01;for (int i=0;i2;i+)for (int j=0;j2;j+)coutsetw(12)aij;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)*a00)*(log(1/(w*a01)+(1-w)*a00)/log(2.0)-(a00*(log(1/a00)/log(2.0)+(a01*(log(1/a01)/log(2.0);if (e0tmp)e0=tmp;e1=w;coutvv最大信道容量为：vvsetw(6)vve0vv 此时W勺值为：e1endl;coutendl;void cc()double e=0; endl;cout 随机生成二元删除信道为：for (int j=0;j2;j+)b0j=rand()%100;e+=b0j;for (int j=0;j2;j+)b0j=b0j/e;b02=0;b10=0;e=0;for (int j=1;j3;j+)b1j=rand()%100;e+=b1j;for (int j=1;j3;j+)b1j=b1j/e;for (int i=0;i2;i+)for (int j=0;j3;j+)coutsetw(12)bij;void dd()double P22;P10=0;P11=1;double temp2=0,1;dodouble tmp1=0,tmp=0;for (int i=0;i2;i+)for (int j=0;j3;j+)if (bij!=0)tmp1+=P1i*bij*log(1.0/bij)/log(2.0);double temp223;for (int i=0;i2;i+)for (int j=0;j3;j+)temp2ij=P1i*bij;for (int j=0;j3;j+)temp20j=temp20j+temp21j;for (int j=0;j=temp0)temp0=tmp;temp1=P10;P10+=0.01;P11-=0.01; while (P10=1.00);cout最大信道容量为：temp0vv信源的w值为temp1vvendl;void main()srand( unsigned )time(NULL);aa();bb();cc();dd();