信息与编码实验教案.doc

信息与编码实验教案桂林电子科技大学 数学与计算科学学院信息教研室 刘忆宁2009年10月10日信息编码理论是信息计算科学专业的一门重要的专业基础课，对于提高学生的信息科学基础知识具有重要的作用。信息编码实验，是为了提高学生的应用技能，融汇计算机编程能力培养与信息编码基础理论的一个重要环节。实验包括四个：。l 信源熵的计算l 香农编码l 循环码l 有限域上插值多项式的构造信息编码实验要求用C语言完成。实验一、信源熵的计算实验背景：根据信源熵的性质，英语的信源熵的最大值为(比特/符号)，但事实上，由于在英语中的字母并非等概出现(表1)，实际的离散信源熵大概为(比特/符号），有些字母之间还有较强的依赖关系，为了进一步逼近实际情况，可对英语信源进行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.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 ap 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(fp=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”, 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”, sum1);实验要求：1） 自己生成一个英文文件，可以在网上找，也可以自己生成。为了保证实验数据的可靠性，数据的量要比较大。为了保证二维信源统计的可靠性，建议文件的英文字符在十万以上。2） 编写一维信源统计程序，得出一维统计频次，计算信源熵及剩余度。3） 编写二维信源统计程序，得出二维统计频次，计算信源熵及剩余度。4） 提交二维信源剩余度的实验报告，及实验体会心得。实验二、香农编码实验背景：Hfffman编码、Fano编码以及 Shannon编码是重要的统计编码形式，在信源编码中具有重要的作用。由于 Huffman 编码在数据结构课程中已经出现。 因此，选用 Shannon编码为主要练习对象。实验内容：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; for(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;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语言描述）中，有实系数的多项式除法。对其进行改进，使其系数定义在上，可很好地实现循环编码及校验的要求。实验内容：完成二进制多项式除法的设计，程序中 其中 其中, 在循环码中，只需保留多项式相除的余式即可。下面的程序中， ，最后余式#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(pmm-1,kk);mm=mm-1; ll=ll-1; for (i=0; i p，yi % = p ；如果yi p，yi % = p ；如果yi 0；yi += p；对 执行（iii） 对执行Step3 输出范德蒙方程组的解x=b./ 看程序之前，请仔细阅读解有限域上范德蒙方程组算法思想，如上/ 运算过程确保每一步运算的数均在(0, p )内./#include stdio.h#include malloc.h#include stdlib.hint prime=7 ; /全局变量，确定上限素数void Vandermond(int n,int* x,int* y); /函数解范德蒙方程组，解即为所要求的系数int Inverse(int xx); /求逆元void main() /主函数入口int n=3;int x3=1, 2, 4;int y3=2, 6, 5;Vandermond(n, x, y); /调用函数求解系数，并存入数组y中void Vandermond(int n,int *x,int *y) /解范德蒙方程组，以获取系数，并存入原数组y中 int yy, xx; /定义中间变量, 以确保每一步运算中间产生的数均在（0，p）范围内. int temp; / for(int k=0;kk;-i) yy=yi-yi-1; xx=xi-xi-k-1; if(yy%xx=0) yi=yy/xx; /判断xx是否整除yy，否则取yy乘以其逆元 if(yiprime) yi%=prime; else if( yi =0; -k) for( int i=k; i prime) temp %= prime; if(tempprime) yi%=prime; if(yi0) yi%=prime;yi+=prime; printf(解为 : ); for(int i=0;in;+i) printf(%dt, yi); /输出系数 return;/ 求x的逆元/ 令i=1，2.p，如果