《信息与编码实验教案.doc》由会员分享，可在线阅读，更多相关《信息与编码实验教案.doc（11页珍藏版）》请在金锄头文库上搜索。
1、信息与编码实验教案桂林电子科技大学 数学与计算科学学院信息教研室 刘忆宁2009年10月10日信息编码理论是信息计算科学专业的一门重要的专业基础课，对于提高学生的信息科学基础知识具有重要的作用。信息编码实验，是为了提高学生的应用技能，融汇计算机编程能力培养与信息编码基础理论的一个重要环节。实验包括四个：。l 信源熵的计算l 香农编码l 循环码l 有限域上插值多项式的构造信息编码实验要求用C语言完成。实验一、信源熵的计算实验背景：根据信源熵的性质，英语的信源熵的最大值为(比特/符号)，但事实上，由于在英语中的字母并非等概出现(表1)，实际的离散信源熵大概为(比特/符号），有些字母之间还有较强的依
2、赖关系，为了进一步逼近实际情况，可对英语信源进行2维、三维等形式的统计，求得实际的熵，其中（比特/符号），（比特/符号）。容易推知，有依赖关系的字母数越多，输出的序列越接近于实际情况，当依赖关系延伸到无穷远时，信源输出的就是真正的英语。此时可求出马尔可夫信源的极限熵（比特/符号）。表1 27个英语符号出现的概率符号 概率符号 概率符号 概率空格 0.2S 0.052Y,W 0.012E 0.105H 0.047G 0.011T 0.072D 0.035B 0.0105O 0.0654L 0.029V 0.008A 0.063C 0.023K 0.003N 0.059F,U 0.0225X 0.
3、002I 0.055M 0.021J,Q,Z 0.001R 0.054P 0.0175实验内容：1. 将一大段英文文章作为要统计的样本文件2. 对样本文件进行一维概率统计，并计算出信源熵及冗余度3. 对样本文件进行二维概率统计，并计算出信源熵及冗余度在进行统计时，首先要在程序中打开文件，然后对文件中的字符读入程序中，进行统计。而在二维统计时，尤其要求对文件的指针操作要熟悉。如读入 “newspaper”时，应该依次读入 “ne ew ws sp pa ap pe er”，而如果使用fgetc()等命令读文件时，读入的是 “ne ws pa pe” 为了依次读入“ne ew ws sp pa a
4、p pe er”，就要求在每次调入fgetc()等命令后，再将文件指针往后退一步，即要求学生能熟练使用fseek()命令进行指针定位操作。二维信源熵程序如下：#include #include #include #define NULL 0int charge(char c)int n; if(c=65&c+97&c=122) n=c-97; return n; else return -1;void main() int count2626=0; char zifu1,zifu2; int i,n,m,j; int sum=0; float q, sum1=0; FILE *fp; If(f
5、p=fopen(“file”, “rb”)=NULL) printf(“ cant 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) countnm+; fseek(fp,-1,1); fclose(fp); for(i=0;i26;i+) for(j=0;j26;j+) sum=sum+countij; printf(“the number of all the code is %dn
6、”, 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,countij,countij*100/q); printf(“n”); for(i=0;i26;i+) for(j=0;j26;j+) if(countij)sum1=sum1+(float)(countij/q)*log10(1/(double)(countij /q)/log10(double)(2); printf(“n 信息熵为： H(x)=%fn”, su
7、m1);实验要求：1） 自己生成一个英文文件，可以在网上找，也可以自己生成。为了保证实验数据的可靠性，数据的量要比较大。为了保证二维信源统计的可靠性，建议文件的英文字符在十万以上。2） 编写一维信源统计程序，得出一维统计频次，计算信源熵及剩余度。3） 编写二维信源统计程序，得出二维统计频次，计算信源熵及剩余度。4） 提交二维信源剩余度的实验报告，及实验体会心得。实验二、香农编码实验背景：Hfffman编码、Fano编码以及 Shannon编码是重要的统计编码形式，在信源编码中具有重要的作用。由于 Huffman 编码在数据结构课程中已经出现。 因此，选用 Shannon编码为主要练习对象。实验
8、内容：Shannon 码编码步骤为：1. 将信源的所有符号按概率从大到小排列：2. 对第个信源符号取整数码长, 为取整运算3. 计算累加概率4. 将变换成二进制数，并按步骤2中计算的长度取的二进制系数，组合起来即为的香农码字.程序如下：#include#include#includedouble P6=0.25,0.1,0.2,0.25,0.15,0.05,Pax6,machang6;void main() double temp; for(int a=1;a6;a+) for(int i=0;i6-a;i+) if(PiPi+1) temp=Pi; Pi=Pi+1; Pi+1=temp; f
9、or(int i=0;i6;i+) coutPi ; coutendl; for(i=0;i6;i+) Pax0=0.0; Paxi+1=Paxi+Pi; cout概率累加和为:endl; for(i=0;i6;i+) coutPaxi ; coutendl; for(i=0;i6;i+) double m=log(1/Pi)/log(2); if(m-int(m)=0) machangi=log(1/Pi)/log(2); else machangi=int(m)+1; coutPi的码长为:machangiendl; for(i=0;i6;i+) for(int j=0;jmachangi
10、;j+) int n=int(Paxi*2); cout0) Paxi=Paxi*2-1; continue;if(Paxi*2-1)=0)Paxi=Paxi*2-1;elsePaxi=Paxi*2; coutendl; 实验要求：1） 熟练掌握香农编码的原理2） 掌握二进制小数的输出方法3） 如果时间允许，建议完成Huffman编码的程序设计。4） 完成香农编码的实验报告及实验心得体会。实验三、循环码实验背景：循环码是线性分组码的一种，具有较好的数学特征，可以用代数理论对循环码进行研究。在循环码的编码与校验过程中，上多项式的除法是重要环节。在徐士良的常用算法程序集（C语言描述）中，有实系数的
11、多项式除法。对其进行改进，使其系数定义在上，可很好地实现循环编码及校验的要求。实验内容：完成二进制多项式除法的设计，程序中 其中 其中, 在循环码中，只需保留多项式相除的余式即可。下面的程序中， ，最后余式#include stdio.hjiajian(a,b)int a,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)int a,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)int a,b; if (a=1&b=1) return(1); if(a=0) return(0);void pdiv(p, m, q, n, s, k, r, l)int m,n,k,l,p ,q ,s ,r ; int i,j,mm,ll,kk; for(i=0; i=1; i-) si-1=chu(pll,qn-1); mm=ll; for (j=1; jn; j+) kk=cheng(si-1,qn-j-1);pmm-1=jiajian
