成都理工大学信息理论与编码实验指导书

1实验一：香农（Shannon）编码一、实验目的掌握通过计算机实现香农编码的方法。二、实验要求对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。三、实验基本原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码1.将信源消息符号按其出现的概率大小排列)()()(21nxpxpxp2．确定满足下列不等式的整数码长Ki；1)(log)(log22iiixpKxp3．为了编成唯一可译码，计算第i个消息的累加概率11)(ikkixpp4．将累加概率Pi变换成二进制数。5．取Pi二进制数的小数点后Ki位即为该消息符号的二进制码。四实验内容1．对给定信源01.01.015.017.018.019.02.0)(7654321xxxxxxxXqX进行二进制香农编码。2．对给定信源05.010.015.020.025.025.0)(654321xxxxxxXqX进行二进制香农编码。3．自已选择一个例子进行香农编码。五、实验设备PC计算机，C++六、实验报告要求21、画出程序设计的流程图，2、写出程序代码，3、写出在调试过程中出现的问题，4、对实验的结果进行分析。七、参考程序(仅供参考)//香农（Shannon）编码参考程序intmain(){intN;cout”请输入信源符号个数：”；cinN;cout”请输入各符号的概率：”endl；double*X=newdouble[N];//离散无记忆信源inti,j;for(i=0;iN;i++){cout”X[”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;//确认码长为1-log2(p(xi))if(K[i]==(-(log(X[i])/log(2)))+1)//当K[i]=-log2(p(xi))时，K[i]--K[i]--;}3//累加概率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)//累加概率乘2大于1,对应码字加1,累加概率自身取余{code[i]+=”1”;Pa[i]=Pa[i]*2-1;}else//累加概率乘2小于1时,对应码字加0,累加概率自身取余{code[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)”码长K”setw(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;4delete[]X;delete[]Pa;delete[]K;delete[]code;getch();retuen0;}5实验二费诺编码一、实验目的掌握通过计算机实现费诺编码。二、实验要求对于给定的信源的概率分布,按照费诺编码的方法进行计算机实现。三、实验基本原理费诺编码的步骤:1．将概率按从大到小的顺序排列；2．按编码进制数将概率分组，使每组概率和尽可能接近或相等；3．给每组分配一位码元；4．将每一分组再按同样原则划分，重复2和3，直到概率不再可分为止。四实验内容1．对给定信源01.01.015.017.018.019.02.0)(7654321xxxxxxxXqX进行二进制费诺编码。2．对给定信源05.010.015.020.025.025.0)(654321xxxxxxXqX进行二进制费诺编码。3．自已选择一个例子进行费诺编码。五、实验设备PC计算机，C++六、实验报告要求1、画出程序设计的流程图，2、写出程序代码，3、写出在调试过程中出现的问题，4、对实验的结果进行分析。6七、参考程序(仅供参考)//********费诺编码参考程序1****//全局变量定义intn;string*sign;double*p;string*code;voidfano(inta,intb)//费诺编码函数{if((b-a)=1)//判断该组中符号个数是否大于2{doublesum=0;for(inti=a;i=b;i++)sum+=p[i];//计算该组概率累加和doubles1=0,*s=newdouble[10];for(inti=a;i=b;i++){s1+=p[i];s[i]=fabs(2*s1-sum)/sum;}doublemin=s[a];intc;for(inti=a;i=b;i++)if(s[i]=min){min=s[i];c=i;//定位使两组概率和尽可能相近或相等的位置c}for(inti=a;i=b;i++){if(i=c)code[i]+=”0”;//码字加“0”elsecode[i]+=”1”;//码字加“1”7}//判断分组点位置，进而分情况自身调用if(c==a)fano(c+1,b);elseif(c==b-1)fano(a,c);else{fano(a,c);fano(c+1,b);}}}voidmain(){cout””请输入信源符号个数n:”;cinn;p=newdouble[n];sign=newstring[n];code=newstring[n];cout”请输入信源符号:”;for(inti=0;in;i++)cinsign[i];cout”请输入信源符号的概率:”;for(inti=0;in;i++)cinp[i];for(inti=0;in;i++)for(intj=i+1;jn;j++)if(p[i]p[j]){doubletemp=p[i];p[i]=p[j];p[j]=temp;stringm=sign[i];sign[i]=sign[j];sign[j]=m;}8fano(0,n-1);//费诺编码coutendlendlsetw(8)”信源符号”setw(8)”概率”setw(8)”码字”setw(8)”码长”endl;for(inti=0;in;i++)coutsetw(8)sign[i]setw(8)p[i]setw(8)code[i].length()endl;delete[]p;delete[]sign;delete[]code;}//***********费诺编码参考程序2*************#includeiostream#includecmathusingnamespacestd;classDATA//数据类,采用双向表{public://初始化PXi=1是为了在排序迭代时方便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;//排序函数用9voidinput()//输入数据{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);//因为sort要改变tt，故需要一个中间变量tt-next=T;//由于迭代产生的链表格式不规范，以下句用来整理sort函数的返回结果tt-next-pre=tt;tt=tt-next;tt-next=newDATA;10tt-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;//y定义为1是因为概率最多为1k++;//递归自增值，用于字符数组定位DATA*head1=pp,*head2;into=1;while(1)//分01组{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;//从这里分01段for(;pp-next!=NULL;pp=pp-next)z=z+pp-PXi;11if(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为上一段结束位置head2-pre-next-pre=head2-pre;encoding(head1);//递归encoding(head2);break;}k--;//迭代还原到上一个数