您好,欢迎访问三七文档
信息与编码实验教案数学与计算科学学院信息教研室2009年10月10日信息编码理论是信息计算科学专业的一门重要的专业基础课,对于提高学生的信息科学基础知识具有重要的作用。信息编码实验,是为了提高学生的应用技能,融汇计算机编程能力培养与信息编码基础理论的一个重要环节。实验包括四个:。信源熵的计算香农编码循环码有限域上插值多项式的构造信息编码实验要求用C语言完成。实验一、信源熵的计算实验背景:根据信源熵的性质,英语的信源熵的最大值为76.427log20H(比特/符号),但事实上,由于在英语中的字母并非等概出现(表1),实际的离散信源熵大概为03.41H(比特/符号),有些字母之间还有较强的依赖关系,为了进一步逼近实际情况,可对英语信源进行2维、三维等形式的统计,求得实际的熵,其中32.32H(比特/符号),1.33H(比特/符号)。容易推知,有依赖关系的字母数越多,输出的序列越接近于实际情况,当依赖关系延伸到无穷远时,信源输出的就是真正的英语。此时可求出马尔可夫信源的极限熵4.1H(比特/符号)。表127个英语符号出现的概率符号概率符号概率符号概率空格0.2S0.052Y,W0.012E0.105H0.047G0.011T0.072D0.035B0.0105O0.0654L0.029V0.008A0.063C0.023K0.003N0.059F,U0.0225X0.002I0.055M0.021J,Q,Z0.001R0.054P0.0175实验内容:1.将一大段英文文章作为要统计的样本文件2.对样本文件进行一维概率统计,并计算出信源熵及冗余度3.对样本文件进行二维概率统计,并计算出信源熵及冗余度在进行统计时,首先要在程序中打开文件,然后对文件中的字符读入程序中,进行统计。而在二维统计时,尤其要求对文件的指针操作要熟悉。如读入“newspaper”时,应该依次读入“neewwssppaappeer”,而如果使用fgetc()等命令读文件时,读入的是“newspape”为了依次读入“neewwssppaappeer”,就要求在每次调入fgetc()等命令后,再将文件指针往后退一步,即要求学生能熟练使用fseek()命令进行指针定位操作。二维信源熵程序如下:#includestdio.h#includemath.h#includestdlib.h#defineNULL0intcharge(charc){intn;if(c=65&&c=90)c=c+32;if(c+97&&c=122){n=c-97;returnn;}elsereturn-1;}voidmain(){intcount[26][26]={0};charzifu1,zifu2;inti,n,m,j;intsum=0;floatq,sum1=0;FILE*fp;If((fp=fopen(“file”,“rb”))==NULL){printf(“can’topenfile!\n”);exit(0);}while(!feof(fp)){zifu1=fgetc(fp);n=charge(zifu1);if(n!=-1){zifu2=fgetc(fp);m=charge(zifu2);if(m!=-1){count[n][m]++;fseek(fp,-1,1);}}}fclose(fp);for(i=0;i26;i++)for(j=0;j26;j++)sum=sum+count[i][j];printf(“thenumberofallthecodeis%d\n”,sum);q=(float)sum;for(i=0;i26;i++)for(j=0;j26;j++){if(j%3==0)printf(“\n”);printf(“%c%c,%4d,%6.5f%%”,i+97,j+97,count[i][j],count[i][j]*100/q);}printf(“\n”);for(i=0;i26;i++)for(j=0;j26;j++)if(count[i][j])sum1=sum1+(float)((count[i][j]/q)*log10(1/(double)(count[i][j]/q))/log10((double)(2)));printf(“\n信息熵为:H(x)=%f\n”,sum1);}实验要求:1)自己生成一个英文文件,可以在网上找,也可以自己生成。为了保证实验数据的可靠性,数据的量要比较大。为了保证二维信源统计的可靠性,建议文件的英文字符在十万以上。2)编写一维信源统计程序,得出一维统计频次,计算信源熵及剩余度。3)编写二维信源统计程序,得出二维统计频次,计算信源熵及剩余度。4)提交二维信源剩余度的实验报告,及实验体会心得。实验二、香农编码实验背景:Hfffman编码、Fano编码以及Shannon编码是重要的统计编码形式,在信源编码中具有重要的作用。由于Huffman编码在数据结构课程中已经出现。因此,选用Shannon编码为主要练习对象。实验内容:Shannon码编码步骤为:1.将信源S的所有符号按概率从大到小排列:qPPP212.对第i个信源符号is取整数码长11logiiPl,为取整运算3.计算累加概率)2(,0,111iPRRRikkii4.将iR变换成二进制数jjjixR21,并按步骤2中计算的长度il取iR的二进制系数jx,组合起来即为is的香农码字iW.程序如下:#includestdio.h#includeiostream.h#includemath.hdoubleP[6]={0.25,0.1,0.2,0.25,0.15,0.05},Pax[6],machang[6];voidmain(){doubletemp;for(inta=1;a6;a++){for(inti=0;i6-a;i++)if(P[i]P[i+1]){temp=P[i];P[i]=P[i+1];P[i+1]=temp;}}for(inti=0;i6;i++)coutP[i];coutendl;for(i=0;i6;i++){Pax[0]=0.0;Pax[i+1]=Pax[i]+P[i];}cout概率累加和为:endl;for(i=0;i6;i++)coutPax[i];coutendl;for(i=0;i6;i++){doublem=log(1/P[i])/log(2);if(m-int(m)==0)machang[i]=log(1/P[i])/log(2);elsemachang[i]=int(m)+1;coutP[i]的码长为:machang[i]endl;}for(i=0;i6;i++){for(intj=0;jmachang[i];j++){intn=int(Pax[i]*2);coutn;if((Pax[i]*2-1)0){Pax[i]=Pax[i]*2-1;continue;}if((Pax[i]*2-1)==0)Pax[i]=Pax[i]*2-1;elsePax[i]=Pax[i]*2;}coutendl;}}实验要求:1)熟练掌握香农编码的原理2)掌握二进制小数的输出方法3)如果时间允许,建议完成Huffman编码的程序设计。4)完成香农编码的实验报告及实验心得体会。实验三、循环码实验背景:循环码是线性分组码的一种,具有较好的数学特征,可以用代数理论对循环码进行研究。在循环码的编码与校验过程中,2F上多项式的除法是重要环节。在徐士良的《常用算法程序集(C语言描述)》中,有实系数的多项式除法。对其进行改进,使其系数定义在2F上,可很好地实现循环编码及校验的要求。实验内容:完成二进制多项式除法的设计,程序中012211)(pxpxpxpxPmmmm其中)10(2miFpi012211)(qxqxqxqxQnnnn其中)10(2niFqi,在循环码中,只需保留多项式相除的余式)(xR即可。下面的程序中,1)(5xxxP,1)(3xxxQ,最后余式2)(xxR#includestdio.hjiajian(a,b)inta,b;{if(a==1&&b==1)return(0);if(a==0&&b==1)return(1);if(a==1&&b==0)return(1);if(a==0&&b==0)return(0);}cheng(a,b)inta,b;{if(a==1&&b==1)return(1);if(a==0&&b==1)return(0);if(a==1&&b==0)return(0);if(a==0&&b==0)return(0);}chu(a,b)inta,b;{if(a==1&&b==1)return(1);if(a==0)return(0);}voidpdiv(p,m,q,n,s,k,r,l)intm,n,k,l,p[],q[],s[],r[];{inti,j,mm,ll,kk;for(i=0;i=k-1;i++)s[i]=0;ll=m-1;for(i=k;i=1;i--){s[i-1]=chu(p[ll],q[n-1]);mm=ll;for(j=1;jn;j++){kk=cheng(s[i-1],q[n-j-1]);p[mm-1]=jiajian(p[mm-1],kk);mm=mm-1;}ll=ll-1;}for(i=0;i=l-1;i++){r[i]=p[i];printf(%d,r[i]);}return;}main(){inti;staticintp[6]={1,1,0,0,0,1};staticintq[4]={1,1,0,1};ints[3],r[3];pdiv(p,6,q,4,s,3,r,3);}实验要求:1)熟练掌握CRC编码的原理2)领会二进制除法在CRC编码中的作用3)完成2F上多项式的除法的程序设计4)鼓励学生在以上程序的基础上,完成CRC编码、CRC译码的程序设计5)提交2F上多项式的除法的实验报告、实验心得体会实验四、有限域上插值多项式的构造实验背景:依据1n个点),(),,(,),,(),,(2211ccnnyxyxyxyx构造n次插值多项式nnxaxaaxA10)(,实质上是求解1n无非线性方程组,当插值点数不是很多的时候,可以在较短的时间内计算出插值多项式)(xA的系数),,,(10naaa,使之满足)(iixAy)1(ni。但通常的实数域上的计算,无法解决误差问题,为了避免误差问题,我们将插值多项式定义在有限域上,构造出无误差的插值多项式。当p为素数时,pF为有限域,记][xFp为有限域pF上的多项式。实验内容:例如:设7p,满足)2,1(),(00yx,)6,2(),(11yx,)5,4(),(22yx的插值多项式][252)(7210xFxxxaxaaxAnn.即求解方程组21021021016454262aaaaaaaaa得2,5,2210aaa解有限域上范德蒙方程组算法思想:Step0输入向量组1212(,,),(,,).TTnnaaaabbbb素数p.Step1对k=1,2,n-1,执行(i)对1,2,,ik执行[]iyib;对1,2,,ikn执行[][].iikbykyiaa(ii)如果abs(y[i])p,y[i]%=p;如果y[i]0;y[i]+=p;(确保运算的对象范围均在(0,p)上)(iii)对1,2,,in执行[].ibyiStep2对k=1,2,n-1,执行(i)[]nynb;对1,,innk执行[][1];inkyibabi(ii)如果abs(y[i])p,y[i]%=p;如果y[i]0;y[i
本文标题:信息与编码实验教案
链接地址:https://www.777doc.com/doc-5171770 .html