信息论与编码实验报告

本科生实验报告实验课程信息论与编码学院名称信息科学与技术学院专业名称通信工程学生姓名学生学号指导教师谢振东实验地点6C601实验成绩二〇一五年十一月二〇一五年十一月实验一：香农（Shannon）编码一、实验目的掌握通过计算机实现香农编码的方法。二、实验要求对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。三、实验基本原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码1、将信源消息符号按其出现的概率大小排列)()()(21nxpxpxp2、确定满足下列不等式的整数码长Ki；1)(log)(log22iiixpKxp3、为了编成唯一可译码，计算第i个消息的累加概率11)(ikkixpp4、将累加概率Pi变换成二进制数。5、取Pi二进制数的小数点后Ki位即为该消息符号的二进制码。四、源程序：#includemath.h#includeiostream#includeiomanip#includeconio.h#includestringusingnamespacestd;intmain(){intN;cout请输入信源符号个数：;cinN;cout请输入各符号的概率：endl;double*X=newdouble[N];//离散无记忆信源inti,j;for(i=0;iN;i++){coutX[i+1]=;cinX[i];}for(i=0;iN;i++)for(j=i+1;jN;j++)if(X[i]X[j]){doubletemp=X[i];X[i]=X[j];X[j]=temp;}int*K=newint[N];for(i=0;iN;i++){K[i]=int(-(log(X[i])/log(2)))+1;if(K[i]==(-(log(X[i])/log(2)))+1)}double*Pa=newdouble[N];Pa[0]=0.0;for(i=1;iN;i++)Pa[i]=Pa[i-1]+X[i-1];string*code=newstring[N];for(i=0;iN;i++)for(j=0;jN;j++){doubletemp=Pa[i]*2;if(temp=1){code[i]+=1;Pa[i]=Pa[i]*2-1;}elsecode[i]+=0;Pa[i]*=2;}}for(i=0;iN;i++)code[i]=code[i].substr(0,K[i]);coutsetw(12)信源setw(12)概率p(x)setw(12)累加概率Pa(x)setw(8)码长Ksetw(8)码字endl;for(i=0;iN;i++)coutsetw(12)i+1setw(12)X[i]setw(12)Pa[i]setw(8)K[i]setw(8)code[i]endl;delete[]X;delete[]Pa;delete[]K;delete[]code;getchar();return0;}五、程序设计的流程图六、调试过程中出现的错误：1、在源代码的基础上添加：#includemath.h#includeiostream#includeiomanip#includeconio.h#includestringusingnamespacestd;2、出现错误的语句开始输入信源符号的个数计算平均码长判断概率和s是否等于1按概率大小对信源排序计算平均码长计算编码效率计算累加概率计算自信息量将累加概率转化为二进制码字输出累加概率，码长，码字，自信息量，平均码长，编码，编码效率结束输出错误概率YNdouble*Pa=newdouble[N];pa[0]=0.0,pa[i]=pa[i-1]+X[i-1];红色部分应该改为和前面绿色的格式一样，不然编译程序时会出现红色部分为定义3、出现错误的语句：retuen0;retuen书写错误，应改为return。七、实验内容：1、对给定信源01.01.015.017.018.019.02.0)(7654321xxxxxxxXqX进行二进制香农编码，编码结果如下所示：2、对给定信源05.010.015.020.025.025.0)(654321xxxxxxXqX进行二进制香农编码，编码结果如下所示：3、自已选择一个例子进行香农编码，选择的例子为1.01.01.01.01.015.015.02.087654321xxxxxxxxXqX，编码结果如下所示：实验二：费诺编码一、实验目的掌握通过计算机实现费诺编码。二、实验要求对于给定的信源的概率分布,按照费诺编码的方法进行计算机实现。三、实验基本原理费诺编码的步骤:1、将概率按从大到小的顺序排列；2、按编码进制数将概率分组，使每组概率和尽可能接近或相等；3、给每组分配一位码元；4、将每一分组再按同样原则划分，重复2和3，直到概率不再可分为止。四、源程序：#includeiostream#includecmathusingnamespacestd;classDATA/{public:DATA(){next=NULL;pre=NULL;r=NULL;PXi=1;key[0]='\0';key[1]='\0';key[2]='\0';key[3]='\0';key[4]='\0';key[5]='\0';key[6]='\0';key[7]='\0';key[8]='\0';key[9]='\0';key[10]='\0';}charXi;doublePXi;charkey[11];DATA*next,*pre,*r;};DATA*head=newDATA,*p=head;intk=(-1);voidencoding(DATA*pp);DATA*sort(DATA*pp);DATA*HEAD=newDATA,*tt=HEAD,*T;voidinput(){doublel,sum=0;intn,i;charL;cout请输入信源个数:;cinn;for(i=0;in;i++){cout请输入一个字符的信源符号:endl;cinL;cout请输入概率:endl;cinl;p-Xi=L;p-PXi=l;sum=sum+p-PXi;p-next=newDATA;p-next-pre=p;/p-r=p-next;p=p-next;}if(sum!=1){cout所输入的概率之和是sum不为1，请重新输入endl;input();}T=sort(head);tt-next=T;tt-next-pre=tt;tt=tt-next;tt-next=newDATA;tt-next-pre=tt;tt=tt-next;HEAD-next-next-pre=NULL;HEAD=HEAD-next-next;cout对输入信源排序结果如下：endl;for(p=HEAD;p-next!=NULL;p=p-next)coutp-Xi:p-PXiendl;cout对输入信源编码结果如下：endl;encoding(HEAD);}/***********************编码************************/voidencoding(DATA*pp)/{doubley=1;k++;DATA*head1=pp,*head2;into=1;while(1){doublel=0,z=0;for(inti=1;i=o;i++){if(pp-next==NULL)break;l=l+pp-PXi;pp=pp-next;}head2=pp-pre;for(;pp-next!=NULL;pp=pp-next)z=z+pp-PXi;if(yfabs(l-z))/{y=fabs(l-z);pp=head1;o++;continue;}elseif(z==0&&i=2)//z=0,i1表示只有一个概率了{couthead1-Xi:head1-keyendl;break;}for(DATA*u=head1;u-next!=head2-next;u=u-next)u-key[k]='0';for(DATA*h=head2;h-next!=NULL;h=h-next)h-key[k]='1';head2-pre-next=newDATA;head2-pre-next-pre=head2-pre;encoding(head1);encoding(head2);break;}k--;}DATA*sort(DATA*pp){//函数递归后头变到HEAD-next-next.返回值得到最后个head2没有与tt相连，需另设．得不到结尾为空的（next=MULL）地址DATA*head1=pp,*head2=pp;if(pp-next==NULL)returnpp;for(;pp-next!=NULL;pp=pp-next){if(1-pp-PXi=1-head2-PXi)head2=pp;}if(head2-pre==NULL){head2-next-pre=NULL;head1=head1-next;}else{head2-pre-next=head2-next;head2-next-pre=head2-pre;}tt-next=sort(head1);tt-next-pre=tt;tt=tt-next;returnhead2;}voidmain(){cout************费诺编码************endl;input();coutendlendl\t\t\t\t\t\t\tendl;}五、程序设计的流程图六、实验内容：1、对给定信源01.01.015.017.018.019.02.0)(7654321xxxxxxxXqX进行二进开始输入信源概率概率按从大到小的顺序排列对应的符号也重新排列信源个数2？通过求累加和确定分组后每组概率累加和尽可能相等或相近第一组的信源码字加0，第二组的码字加1分组点即第一个编号？分组点为该组的第二个？以分组点为断点，重新编号分为两组分组点为新分组的第一个编号，其他依次.......分组点为新分组的最后一个编号，其他编号不变输出信源符号，概率，码字，码长结束YNNYY制费诺编码，编码结果如下所示：2、对给定信源05.010.015.020.025.025.0)(654321xxxxxxXqX进行二进制费诺编码，编码结果如下所示：3、自已选择一个例子进行费诺编码选择的例子为05.006.007.008.009.01.012.013.014.016.010987654321xxxxxxxxxxXqX，编码结果如下所示：实验三霍夫曼编码一、实验目的掌握通过计算机实现霍夫曼编码二、实验要求对于给定的信源的概率分布，按照霍夫曼编码的方法进行计算机实现。三、实验基本原理霍夫曼编码的步骤:1、把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度。2、在分配码字长度时，首先将出现概率最小的两个符号的概率相加合成一个概率3、把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止。4、完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为0，概率小的赋为1。四、源程序：#includestdio.h#includ