信息论与编码实验指导书.doc

信息论与编码实验指导书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与Y的熵、联合熵、条件熵：H（X）、H（Y）、H（X,Y）H（X|Y）、I（X|Y）；（3）对测试通过的程序进行规范和优化；（4）编写本次实验的实验报告。附实验一主要内容及源程序实验一 离散二维随机变量信息熵的计算1 实验内容（1）利用random函数和归一化方法构造一个二维离散随机变量（X，Y）；（2）分别计算X与Y的熵、联合熵、条件熵：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;cout从到间随机取得行列的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)计算代码：coutH(Y)计算：setw(20)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);coutP(Yk+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）计算代码：cout联合熵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);else r=k,u=n;h=1;break;if(h=0)coutH(X,Y)=-p(X,Y)log p(X,Y)=bendl;else coutP(r+1,u+1)为零，中断,无值endl;5. 条件熵H（X|Y）计算代码：cout条件熵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)coutH(X|Y)=-P(X,Y)log(P(X,Y)/P(Y)=bendl;else coutP(r+1,u+1)为零，中断,无值endl;coutI（X|Y）计算：endl;if(h=0)coutI（X|Y）=H(X)-H(X|Y)=c-bendl;else coutP(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#includeusing namespace std;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函数归一化：endl;for(k=0;k4;k+)for(n=0;n4;n+)coutsetw(12)akn/t; coutendl;coutH(Y)计算：setw(20)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);coutP(Yk+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;cout联合熵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);else r=k,u=n;h=1;break;if(h=0)coutH(X,Y)=-p(X,Y)log p(X,Y)=bendl;else coutP(r+1,u+1)为零，中断,无值endl;cout条件熵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)coutH(X|Y)=-P(X,Y)log(P(X,Y)/P(Y)=bendl;else coutP(r+1,u+1)为零，中断,无值endl;coutI（X|Y）计算：endl;if(h=0)coutI（X|Y）=H(X)-H(X|Y)=c-bendl;else coutP(r+1,u+1)为零，中断,无值endl;实验二 简单信源编码方法实现实验目的掌握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 doublen;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;coutP(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 doublen;for(int i=0;in;i+)bi=ai;double *d;d=new doublen;for(int i=0;in;i+)di=i;double *e;e=new doublen;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+=1; （2）主函数main（） 实现初始化操作，完成对子函数的调用void main()int n;coutn;c=new stringn;aa(n);huffman(a,c,n);coutendl;coutsetw(6)各项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#includeusing 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;top=0;list=new elemsz;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() constassert(!isEmpty();return listtop-1;bool isEmpty() constreturn top=0;void aa(int n)double w=0;a=new doublen;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;coutP(X):;for(int i=0;in;i+)cout.precision(3);coutaisetw(8);void huffman(double *a,string *c,int n)elem mp;stack s(n);double *b;b=new doublen;for(int i=0;in;i+)bi=ai;double *d;d=new doublen;for(int i=0;in;i+)di=i;double *e;e=new doublen;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+=1; void main()int n;coutn;c=new stringn;aa(n);huffman(a,c,n);coutendl;coutsetw(6)各项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;cout随机生成二元删除信道为：endl;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;3.求二元对称信道最大信道容量和最大容量时w的值的函数代码：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;cout最大信道容量为:setw(6)e0 此时w的值为：e1endl;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最大信道容量为:temp0 信源的w值为temp1endl; （2）主函数main（） 实现初始化操作，完成对子函数的调用void main()srand(unsigned)time(NULL);aa();bb();cc();dd();3 实验数据与实验结果 测试数据：随机生成了2*2矩阵和2*3矩阵，并求得最大容量和w的值。 实验结果：4 程序代码清单：#include#include #include #includeusing namespace std;double a22;double b23;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;void bb()double w=0;double e2=0,0;for(w=0;w=1