信息与编码实验教案

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.

3、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. 对样本文件进行二维概率统计，并计算出信源熵及冗余度在进行统计时，首先要在程序中打开文件，然后对文件中的字符读入程序中

4、，进行统计。而在二维统计时，尤其要求对文件的指针操作要熟悉。如读入 “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

5、 NULL 0int charge(char c)int n; if(c>=65&&c<=90) c=c+32; if( 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

6、(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;i<26;i+) for(j=0;j<26;j+) sum=sum+countij; printf(“the number of all the code is %dn”, sum); q=(float)sum; for(i=0;i<26;i+) for(j=0;j&

7、lt;26;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;i<26;i+) for(j=0;j<26;j+) if(countij)sum1=sum1+(float)(countij/q)*log10(1/(double)(countij /q)/log10(double)(2); printf(“n 信息熵为： H(x)=%fn”, sum1);实验要求：1） 自己生成一个英文文件，可以在网上找，也可以自己生成

8、。为了保证实验数据的可靠性，数据的量要比较大。为了保证二维信源统计的可靠性，建议文件的英文字符在十万以上。2） 编写一维信源统计程序，得出一维统计频次，计算信源熵及剩余度。3） 编写二维信源统计程序，得出二维统计频次，计算信源熵及剩余度。4） 提交二维信源剩余度的实验报告，及实验体会心得。实验二、香农编码实验背景：Hfffman编码、Fano编码以及 Shannon编码是重要的统计编码形式，在信源编码中具有重要的作用。由于 Huffman 编码在数据结构课程中已经出现。 因此，选用 Shannon编码为主要练习对象。实验内容：Shannon 码编码步骤为：1. 将信源的所有符号按概率从大到小排

9、列：2. 对第个信源符号取整数码长, 为取整运算3. 计算累加概率4. 将变换成二进制数，并按步骤2中计算的长度取的二进制系数，组合起来即为的香农码字.程序如下：#include<stdio.h>#include<iostream.h>#include<math.h>double P6=0.25,0.1,0.2,0.25,0.15,0.05,Pax6,machang6;void main() double temp; for(int a=1;a<6;a+) for(int i=0;i<6-a;i+) if(Pi<Pi+1) temp=Pi;

10、 Pi=Pi+1; Pi+1=temp; for(int i=0;i<6;i+) cout<<Pi<<" " cout<<endl; for(i=0;i<6;i+) Pax0=0.0; Paxi+1=Paxi+Pi; cout<<"概率累加和为:"<<endl; for(i=0;i<6;i+) cout<<Paxi<<" " cout<<endl; for(i=0;i<6;i+) double m=log(1/Pi)

11、/log(2); if(m-int(m)=0) machangi=log(1/Pi)/log(2); else machangi=int(m)+1; cout<<Pi<<"的码长为:"<<machangi<<endl; for(i=0;i<6;i+) for(int j=0;j<machangi;j+) int n=int(Paxi*2); cout<<n;if(Paxi*2-1)>0) Paxi=Paxi*2-1; continue;if(Paxi*2-1)=0)Paxi=Paxi*2-1;el

12、sePaxi=Paxi*2; cout<<endl; 实验要求：1） 熟练掌握香农编码的原理2） 掌握二进制小数的输出方法3） 如果时间允许，建议完成Huffman编码的程序设计。4） 完成香农编码的实验报告及实验心得体会。实验三、循环码实验背景：循环码是线性分组码的一种，具有较好的数学特征，可以用代数理论对循环码进行研究。在循环码的编码与校验过程中，上多项式的除法是重要环节。在徐士良的常用算法程序集（C语言描述）中，有实系数的多项式除法。对其进行改进，使其系数定义在上，可很好地实现循环编码及校验的要求。实验内容：完成二进制多项式除法的设计，程序中 其中 其中, 在循环码中，只需保

13、留多项式相除的余式即可。下面的程序中， ，最后余式#include "stdio.h"jiajian(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&&

14、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<=k-1; i+) si=0; ll=m-1; for(i=k; i>=1; i-) si-1=chu(pll,qn-1); mm=ll; for (j=1; j<n; j+)

15、 kk=cheng(si-1,qn-j-1);pmm-1=jiajian(pmm-1,kk);mm=mm-1; ll=ll-1; for (i=0; i<=l-1; i+) ri=pi; printf("%d ",ri); return;main() int i;static int p6=1,1,0,0,0,1;static int q4=1,1,0,1;int s3,r3;pdiv(p,6,q,4,s,3,r,3);实验要求：1） 熟练掌握CRC编码的原理2） 领会二进制除法在CRC编码中的作用3） 完成上多项式的除法的程序设计4） 鼓励学生在以上程序的基础上，完

16、成CRC编码、CRC译码的程序设计5） 提交上多项式的除法的实验报告、实验心得体会实验四、有限域上插值多项式的构造实验背景：依据个点构造次插值多项式，实质上是求解无非线性方程组，当插值点数不是很多的时候，可以在较短的时间内计算出插值多项式的系数，使之满足。但通常的实数域上的计算，无法解决误差问题，为了避免误差问题，我们将插值多项式定义在有限域上，构造出无误差的插值多项式。当为素数时，为有限域，记为有限域上的多项式。实验内容：例如：设,满足, 的插值多项式.即求解方程组得解有限域上范德蒙方程组算法思想：Step0 输入向量组素数p.Step1 对k=1, 2,n-1, 执行（i） 对执行 ；对执

17、行 （ii） 如果abs (yi) > p，yi % = p ；如果yi < 0；yi += p；（确保运算的对象范围均在( 0, p ) 上）（iii） 对 执行Step2 对k=1, 2,n-1, 执行(i) ;对执行（ii） 如果abs (yi) > p，yi % = p ；如果yi < 0；yi += p；对 执行（iii） 对执行Step3 输出范德蒙方程组的解x=b./ 看程序之前，请仔细阅读解有限域上范德蒙方程组算法思想，如上/ 运算过程确保每一步运算的数均在(0, p )内./#include "stdio.h"#include &q

18、uot;malloc.h"#include "stdlib.h"int 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;k<n-1;+k) for(int i=n-1;i>k;-i) yy=yi-yi-1; xx=xi-xi-k-1; if(yy%xx=0) yi=yy/xx; /判断xx是否整除yy，否则取yy乘以其逆元 if(yi<0) yi%=prime; yi+=prime; else yi=yy*Inverse(xx); if(yi>prime) yi%=p