信息与编码实验教案.doc

信息与编码实验教案 数学与计算科学学院 信息教研室 2009年10月10日 信息编码理论是信息计算科学专业的一门重要的专业基础课，对于提高学生的信息科学基础知识具有重要的作用。信息编码实验，是为了提高学生的应用技能，融汇计算机编程能力培养与信息编码基础理论的一个重要环节。 实验包括四个：。 信源熵的计算 香农编码 循环码 有限域上插值多项式的构造 信息编码实验要求用C语言完成。 实验一、信源熵的计算 实验背景： 根据信源熵的性质，英语的信源熵的最大值为(比特/符号)，但事实上，由于在英语中的字母并非等概出现(表1)，实际的离散信源熵大概为(比特/符号），有些字母之间还有较强的依赖关系，为了进一步逼近实际情况，可对英语信源进行2维、三维等形式的统计，求得实际的熵，其中（比特/符号），（比特/符号）。容易推知，有依赖关系的字母数越多，输出的序列越接近于实际情况，当依赖关系延伸到无穷远时，信源输出的就是真正的英语。此时可求出马尔可夫信源的极限熵（比特/符号）。 表1 27个英语符号出现的概率 符号 概率 符号 概率 符号 概率 空S ? 0.052 Y,W ?0.012 E ?0.105 H ? 0.047 G ? 0.011 T ? 0.072 D ? 0.035 B ?0.0105 O ?0.0654 L ? 0.029 V ? 0.008 A ?0.063 C ?0.023 K ?0.003 N ?0.059 F,U ?0.0225 X ? 0.002 I ?0.055 M ?0.021 J,Q,Z ?0.001 R ? 0.054 P ?0.0175 实验内容： 将一大段英文文章作为要统计的样本文件 对样本文件进行一维概率统计，并计算出信源熵及冗余度 对样本文件进行二维概率统计，并计算出信源熵及冗余度 在进行统计时，首先要在程序中打开文件，然后对文件中的字符读入程序中，进行统计。而 在二维统计时，尤其要求对文件的指针操作要熟悉。如读入 “newspaper”时，应该依次读入 “ne ew ws sp pa ap pe er”，而如果使用fgetc()等命令读文件时，读入的是 “ne ws pa pe” 为了依次读入“ne ew ws sp pa ap pe er”，就要求在每次调入fgetc()等命令后，再将文件指针往后退一步，即要求学生能熟练使用fseek()命令进行指针定位操作。 二维信源熵程序如下： #include stdio.h #include math.h #include stdlib.h #define NULL 0 int charge(char c) {int n; if(c=65c=90) c=c+32; if( c+97c=122) { n=c-97; return n; } else return -1; } void main() { int count[26][26]={0}; char zifu1,zifu2; int i,n,m,j; int sum=0; float q, sum1=0; FILE *fp; If((fp=fopen(“file”, “rb”))==NULL) { printf(“ can’t open file!\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(“the number of all the code is %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]