信息编码实验指导书.doc

《信息编码理论》

实验指导书

孙可 编

桂林电子科技大学
数学与计算科学学院
2016年9月23日

实验一 信源剩余度计算
一、实验目的
1、掌握信息熵的计算方法
2、掌握文件操作方法以及文件指针操作方法。
二、实验课时：2个课时
三、实验准备
1、熟悉信源熵计算方法；
2、熟悉信源剩余压计算方法；
3、熟悉文件操作命令。
4、熟悉文件指针操作命令。
四、实验内容
用C语言完成二维信源剩余度的计算程序。（必做）

根据信源熵的性质，英语的信源熵的最大值为(比特/符号)，但事实上，由于在英语中的字母并非等概出现(表1)，实际的离散信源熵大概为(比特/符号），有些字母之间还有较强的依赖关系，为了进一步逼近实际情况，可对英语信源进行2维、三维等形式的统计，求得实际的熵，其中（比特/符号），（比特/符号）。容易推知，有依赖关系的字母数越多，输出的序列越接近于实际情况，当依赖关系延伸到无穷远时，信源输出的就是真正的英语。此时可求出马尔可夫信源的极限熵（比特/符号）。
对于以上信源冗余度的知识，可以设置如下程序训练。
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 <stdio.h>
#include <math.h>
#include <stdlib.h>
#define NULL 0
int 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 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;i<26;i++)
for(j=0;j<26;j++)
sum=sum+count[i][j];
printf(“the number of all the code is %d\n”, sum);
q=(float)sum;
for(i=0;i<26;i++)
for(j=0;j<26;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;i<26;i++)
for(j=0;j<26;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. 调试信源的二维剩余度
5. 写出心得体会
实验二 香农编码
一、实验目的
1、掌握香农编码算法。
2、了解位运算方法。
3、培养编程与上机调试能力。
二、实验课时：2个课时
三、实验准备
Shannon 码编码步骤为：
1. 将信源的所有符号按概率从大到小排列：
2. 对第个信源符号取整数码长, 为取整运算
3. 计算累加概率
4. 将变换成二进制数，并按步骤2中计算的长度取的二进制系数，组合起来即为的香农码字.
四、实验内容
程序如下：　
#include<stdio.h>
#include<iostream.h>
#include<math.h>
double P[6]={0.25,0.1,0.2,0.25,0.15,0.05},Pax[6],machang[6];
void main()
{ double temp;
for(int a=1;a<6;a++)
{
for(int i=0;i<6-a;i++)
if(P[i]<P[i+1])
{
temp=P[i];
P[i]=P[i+1];
P[i+1]=temp;
}
}
for(int i=0;i<6;i++)
cout<<P[i]<<" ";
cout<<endl;
for(i=0;i<6;i++)
{
Pax[0]=0.0;
Pax[i+1]=Pax[i]+P[i];
}
cout<<"概率累加和为:"<<endl;
for(i=0;i<6;i++)
cout<<Pax[i]<<" ";
cout<<endl;
for(i=0;i<6;i++)
{
double m=log(1/P[i])/log(2);
if(m-int(m)==0)
machang[i]=log(1/P[i])/log(2);
else
machang[i]=int(m)+1;
cout<<P[i]<<"的码长为:"<<machang[i]<<endl;
}
for(i=0;i<6;i++)
{
for(int j=0;j<machang[i];j++)
{
int n=int(Pax[i]*2);
cout<<n;
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;
else
Pax[i]=Pax[i]*2;
}
cout<<endl;
}
}
五、实验报告的撰写要求
1. 写出实验课程名称、课号，任课老师；
2. 写出姓名、学号、日期；
3. 写出实验目的、实验内容；
4. 调通程序，并对上述程序写出程序注释
5. 写出心得体会；
6. 递交上次的实验报告。
实验三 上多项式除法
一、实验目的
1、掌握CRC校验中多项式的除法。
2、用C语言完成上多项式的除法。
二、实验课时：4个课时
三、实验准备
循环码是线性分组码的一种，具有较好的数学特征，可以用代数理论对循环码进行研究。在循环码的编码与校验过程中，上多项式的除法是重要环节。文献[2]中，有实系数的多项式除法。我们对其进行改进，使其系数定义在上，可很好地实现循环编码及校验的要求。
程序中 其中
其中, 在循环码中，只需保留多项式相除的余式即可。
四、实验内容
，，最后余式
五、实验主要步骤
#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&&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++) 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; j<n; 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()
{ int i;
static int p[6]={1,1,0,0,0,1};
static int q[4]={1,1,0,1};
int s[3],r[3];
pdiv(p,6,q,4,s,3,r,3);
}

六、实验报告的撰写要求
1. 写出实验课程名称、课号，任课老师；
2. 写出姓名、学号、日期；
3. 写出实验目的、实验内容；
4. 调通程序，并写出程序注释;
5. 写出心得体会；
6. 递交上次的实验报告。