信息论上机报告.doc

目 录
一、实习一：设计程序判断唯一可译码…………………………………………2
1、题目分析………………………………………………………………………………2
1.1、问题描述…………………………………………………………………………2
1.2、基本要求…………………………………………………………………………2
2、算法分析………………………………………………………………………………2
2.1、数据结构…………………………………………………………………………2
2.2、算法基本原理……………………………………………………………………2
2.3、算法构造步骤……………………………………………………………………2
2.4、简要流程图………………………………………………………………………3
2.5、算法设计与实现…………………………………………………………………3
3、测试结果………………………………………………………………………………4
4、分析与探讨……………………………………………………………………………4
4.1、遇到的问题及解决方法…………………………………………………………4
4.2、其他实现方法……………………………………………………………………4
5、源代码 …………………………………………………………………………………4
二、实习二：香农编码…………………………………………………………………8
1、题目分析………………………………………………………………………………8
1.1、问题描述…………………………………………………………………………8
1.2、实验目的…………………………………………………………………………8
2、算法分析………………………………………………………………………………8
2.1、数据结构…………………………………………………………………………8
2.2、算法基本原理……………………………………………………………………8
2.3、主要函数设计及分析……………………………………………………………8
2.4、简要流程图………………………………………………………………………9
3、测试结果………………………………………………………………………………9
4、分析与探讨……………………………………………………………………………10
5、源代码………………………………………………………………………10
三、实习三：费诺编码…………………………………………………………………13
1、题目分析……………………………………………………………………13
1.1、问题描述…………………………………………………………………………13
1.2、实验目的…………………………………………………………………………13
2、算法分析………………………………………………………………………………13
2.1、数据结构…………………………………………………………………………13
2.2、算法基本原理……………………………………………………………………13
2.3、主要函数设计及分析……………………………………………………………13
2.4、简要流程图………………………………………………………………………14
3、测试结果………………………………………………………………………………14
4、分析与探讨……………………………………………………………………………15
5、源代码…………………………………………………………………………………15
实习一：设计程序判断唯一可译码
一、题目分析
1.1问题描述
设计一个程序实现判断输入码组是否为可译码组这一功能。

1.2基本要求：
（1）用适当的数据结构存放输入的码组；
（2）利用A.A.Sardinas和G.W.Patterson提出的算法思想实现该功能；
（3）输出判断结果。

二、算法分析
2.1、数据结构
根据问题可知，需要用一个数据结构来存储输入的码组，我选择了一个如下结构体Code来存放输入码组的码字及每个码字的长度，再用数组来存放对应的码字。
typedef struct
{
int data[M];
int len;
}Code;

2.2、算法基本原理

如上图所示，可知当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码。此时B1一定是A1的前缀，而A1的尾随后缀一定是另一码字B2的前缀；而B2的尾随后缀又是其他码字的前缀。最后，码符号序列的尾部一定是一个码字。将输入的码字存放在c数组中，将c中所有的尾随后缀组成一个集合f，当且仅当集合f中没有包含任一码字，便可判断c为唯一可译码。

2.3、算法构造步骤
（1）考查c中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中；
（2）考查C和Fi两个集合，若Wj∈C是Wi∈Fi的前缀或Wi∈Fi 是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；
（3）F=∪Fi即为码C的尾随后缀集合；
（4）若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。

2.4、简要流程图

2.5算法设计与实现
本程序用一个结构体来存放输入的码组的信息，其中data[M]存放码字的各个位，len表示码字的长度，也就是M的值，即len=M。
首先存入输入的码字，并计算克拉夫特不等式的值，若值大于1则直接输出“此码组不是唯一可译码组！”，反之则进行下一步计算。在这里，比较难处理的是码字的截断问题，我的实现方法如下：
1）比较c中两个码字的长度和首个数字；
2）若前一个码字的长度小于后一个码字的长度且首个数字相同，则用count计数记下相同位数的长度；
3）将后一个码字的count位至最后一个截断，存放进f数组中。

三、测试结果
3.1、测试数据为0、10、1100、1110、1011、1101

3.2、测试数据为1、01、011、0001

3.3、测试数据为1、01、001、0001

四、分析与探讨
4.1、遇到的问题及解决方法
在设计本程序的过程中遇到的最大的问题是尾随后缀的截断问题，刚开始时不知道以数字的形式实现如何截断尾随后缀，最后在自己的思考及实验下，采用计数器计数的方式来实现这个问题，使得这个问题得以较好的解决。
4.2、其他实现方法
还有一种比较普遍的实现方法就是用字符串来存储输入的码字和相关信息，通过调用不同的字符串操作函数来实现这个功能。

五、源代码
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 10
#define N 1000
typedef struct
{
int data[M];
int len;
}Code;

main()
{
int i,n,b,j,k,count=0,flag=0,flag1=1;
double sum=0;
char a[M];
Code c[N],f[N];
printf("请输入码字个数：");
scanf("%d",&n);
getchar();
printf("请依次输入每个码字：\n");
for(i=0;i<n;i++)
{
gets(a);
b=strlen(a);
for(j=0;j<b;j++)
c[i].data[j]=a[j]-'0';
c[i].len=b;
sum+=pow(2,-1*b);
}
if(sum>1) printf("此码组不是唯一可译码组！\n\n");
else
{
for(i=0;i<n-1;i++)
{
for(j=1;j<n;j++)
{
if(c[i].len>=c[j].len||c[i].data[0]!=c[j].data[0]) continue;
b=c[i].len;
while(b--)
{
if(c[i].data[b]==c[j].data[b]) flag=1;
else
{
flag=0;
break;
}
}
b=c[j].len-c[i].len;
while(flag--)
{
for(k=0;k<b;k++) f[count].data[k]=c[j].data[b+k];
f[count].len=b;
count+=1;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<count;j++)
{
if(c[i].len!=f[j].len)
{
if(c[i].len>f[j].len)
{
b=f[j].len;
while(b--)
{
if(c[i].data[b]==f[j].data[b]) flag=1;
else
{
flag=0;
break;
}
}
b=c[i].len-f[j].len;
while(flag--)
{
for(k=0;k<b;k++) f[count].data[k]=c[i].data[b+k];
f[count].len=b;
count+=1;
}
}
else
{
b=c[i].len;
while(b--)
{
if(c[i].data[b]==f[j].data[b]) flag=1;
else
{
flag=0;
break;
}
}
b=f[j].len-c[i].len;
while(flag--)
{
for(k=0;k<b;k++) f[count].data[k]=f[j].data[b+k];
f[count].len=b;
count+=1;
}
}
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<count;j++)
{
if(c[i].len==f[j].len)
{
for(k=0;k<c[i].len;k++)
{
if(c[i].data[k]==f[j].data[k])
{
flag1=0;
break;
}
else flag1=1;
}
}
if(flag1==0) break;
}
if(flag1==0) break;
}
if(flag1==0) printf("此码组不是唯一可译码组！\n\n");
else printf("此码组是唯一可译码组！\n\n");
memset(c,0,sizeof(c));
memset(f,0,sizeof(f));
main();
}
}

实习二：香农编码
一、 题目分析
1.1、问题描述
对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。

1.2、实验目的
掌握通过计算机实现香农编码。

二 、算法分析
2.1、数据结构
分别用数组p、q、k存放输入的概率，累加概率、码字长度；

2.2、算法基本原理
给定某个信源符号的概率分布，通过以下的步骤进行香农编码：
1）信源符号按概率从大到小排列；
2）对信源符号求累加和，表达式： Pi=Pi-1+p(xi)；
3）求自信息量，确定码字长度。自信息量I(xi)=-log(p(xi));码字长度取大于等于自信息量的最小整数；
4）将累加和用二进制表示，并取小数点后码字的长度的码 。

2.3、主要函数设计及分析
1）main()函数
这个函数主要包含以下几个功能：实现用户的输入和编码结果的输出；判断用户输入是否合法；调用冒泡排序法对输入的概率进行排序；计算累加概率；计算每个符号对应码字的码长；调用编码函数；最用调用main()函数实现用户的循环输入。在这里值得详细介绍的一段代码如下：
for(i=0;i<n;i++)
{
j=0;
a=-log(p[i]);
b=log(2);
while(a>=b)
{
j++;
a-=b;
}
if(a==0) k[i]=j;
else k[i]=j+1;
}
本段代码的功能是求每个符号概率对应码字的长度，由于在直接对概率求取以2为底的对数时不易判断出结果是否为整数，也就不易向上取整。本段代码的思想是：利用模拟手工除法进行计算，用概率的对数减去log2，判断结果是否大于log2，如果大于则继续做减法运算；如果等于0则停止计算；如果大于0且小于log2则计数器j加1即为向上取整的值，可以有效的克服判断结果是否需要加1这一困难。
2）array()函数
本函数的功能主要是利用冒泡排序法对用户输入的各个符号对应的概率进行降序排列，以便于计算累加概率和编码。
3）change()函数
本函数的功能主要是将累加概率转换为二进制，从而根据码长计算出相应的码字，在这里用到对浮点数转换为二进制的算法。

2.4、简要流程图

三、测试结果
3.1、测试数据为：0.20 0.19 0.17 0.15 0.10 0.01 0.18

3.2、测试数据为：0.32 0.22 0.18 0.16 0.08 0.04

3.3、上述两组测试数据的结果

四、分析与探讨
本程序实现上较为简单，在编程的过程中并没有遇到特别大的问题，只是在对概率取对数并向上取整时遇到一定的困难，经过思考，利用上述的模拟手工出发圆满的解决了这一难题，使得程序能够得以完成。

五、源代码
#include<stdio.h>
#include <math.h>
#include<string.h>
#define N 100
int k[N];
void array(double *a,int n)
{
int i,j,flag=1;
double temp;
for(i=0;i<n&&flag==1;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if(a[j]<a[j+1])
{
flag=1;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

void change(double p,int q)
{
int b[1000],t;
memset(b,0,sizeof(b));
p=p*2;
for(t=0;;t++)
{
if(p==0) break;
else if(p>=1)
{
b[t]=1;
p-=1;
p*=2;
}
else
{
b[t]=0;
p*=2;
}
}
for(t=0;t<k[q];t++) printf("%d",b[t]);
printf("\n");
}

void main()
{
int i,j,n;
double p[N],q[N],s=0,sum,a,b;
printf("请输入符号个数：");
scanf("%d",&n);
printf("请依次输入每个符号的概率：\n");
for(i=0;i<n;i++)
{
scanf("%lf",&p[i]);
s=s+p[i];
if(p[i]<=0||p[i]>=1) break;
}
if(s==1)
{
array(p,n);
sum=0;
for(i=0;i<n;i++)
{
q[i]=sum;
sum=sum+p[i];
}
for(i=0;i<n;i++)
{
j=0;
a=-log(p[i]);
b=log(2);
while(a>=b)
{
j++;
a-=b;
}
if(a==0) k[i]=j;
else k[i]=j+1;
}
printf("按概率降序码字依次为：\n");
for(i=0;i<n;i++)
{
printf("该码字对应累加概率为：%.3lf\t该码字码长为：%d\t\t码字为：",q[i],k[i]);
change(q[i],i);
}
}
printf("\n");
main();
}

实习三、费诺编码
一、 题目分析
1.1、问题描述
对于给定的信源的概率分布，按照费诺编码的方法进行计算机实现。

1.2、实习目的
掌握通过计算机实现费诺编码。

二、算法分析
2.1、数据结构
本程序采用一个结构体的数据类型来存储费诺编码的相关信息，具体的数据结构如下：
typedef struct
{
char data;
float P;
}Fano[MAX+1];//需要编码的结构体

2.2、算法基本原理
1）将概率按从大到小的顺序排列；
2）按编码进制数将概率分组，使每组概率和尽可能接近或相等；
3）给每组分配一位码元；
4）将每一分组再按同样原则划分，重复2）和3），直到概率不再可分为止。

2.3、函数详细设计及分析
1）main()函数
本函数实现的主要功能有：实现需要编码符号相关信息的输入；判断用户输入是否正确；调用冒泡排序法函数BubbleSort(fano,n)对输入的概率进行降序排序；调用费诺编码函数FanoCode(1,n,fano);对排序后的概率进行编码并输出编码结果。
2）BubbleSort()函数
本函数是根据数据结构书上的冒泡排序法改编而来，实现对输入的概率进行降序排序以便于费诺编码。
3）FanoCode()函数
本函数的主要功能是实现编码过程的2）和3）。因为本函数是一个递归函数，所以在本函数中，首先用一个标志flag来判断需要编码的长度是否为输入的长度。如果已经编码的符号个数为输入的符号个数，则编码结束返回主函数。将排序后的概率分为两组最接近的数，然后将单个概率较大的一组编码为0，另一组编码为1。对分组后的两个小组递归调用FanoCode()函数，直到找到程序的出口，即编码完成。
分组代码如下：
for(j=1;j<i+1;j++) a[j]=fano[j].P;
for(j=m;j<=n;j++) sum=sum+a[j];
k=m;
while(s<=sum-s)
{
s1=s;
s=s+fano[k++].P;
}
if((sum-2*s1)<=(2*s-sum)) k--;

2.4、简要流程图

三、测试结果
3.1、测试数据为：
a 0.20
b 0.19
c 0.17
d 0.15
e 0.10
f 0.01
g 0.18
运行结果为：

3.2、测试数据为：
a 0.32
b 0.22
c 0.18
d 0.16
e 0.08
f 0.04
运行结果为：

四、分析与探讨
在本次编码的过程中并没有遇到什么较大的问题，就是在验收程序的时候，老师说费诺编码应该是概率小的符号码字长度一定大于概率大的符号的码字长度，我回来思考并完成作业之后发现并不是那样的，符号码字的长度和概率的大小没有绝对的关系，只能说一般情况下，概率小的符号码字长度大于概率大的符号的码字长度。

五、源代码
#include<iostream.h>
#include<math.h>
#include<string.h>
#define MAX 20
char p[20][20];
typedef struct
{
char data;
float P;
}Fano[MAX+1];//需要编码的结构体

void BubbleSort(Fano fano,int n)//用冒泡排序法对输入的概率进行排序
{
int i,j,flag=1;
float temp;
char temp1;
for(i=2;i<n+1&&flag==1;i++)
{
flag=0;
for(j=1;j<=n+1-i;j++)
{
if(fano[j].P<=fano[j+1].P)
{
flag=1;
temp=fano[j+1].P;
fano[j+1].P=fano[j].P;
fano[j].P=temp;
temp1=fano[j+1].data;
fano[j+1].data=fano[j].data;
fano[j].data=temp1;
}
}
}
}

void FanoCode(int m,int n,Fano fano)//费诺编码
{
int j,k,i,flag=0;
float sum=0.0,s=0.0,s1,a[20];
flag++;
if(flag==1) i=n;
if(m==n) return;
for(j=1;j<i+1;j++) a[j]=fano[j].P;
for(j=m;j<=n;j++) sum=sum+a[j];
k=m;
while(s<=sum-s)
{
s1=s;
s=s+fano[k++].P;
}
if((sum-2*s1)<=(2*s-sum)) k--;
for(j=m;j<k;j++) strcat(p[j],"0");//编码为0
for(j=k;j<=n;j++) strcat(p[j],"1");//编码为1
FanoCode(m,k-1,fano);
FanoCode(k,n,fano);
}

void main()
{
int i=0,n,flag=1;
float sum=0;
Fano fano;
cout<<"请输入编码个数：";
cin>>n;
while(flag)
{
cout<<"请依次输入数据及概率："<<endl;
for(i=1;i<=n;i++)
{
cin>>fano[i].data;
cin>>fano[i].P;
sum+=fano[i].P;
}
if(sum==1.0000 )
{
cout<<"输入正确!"<<endl;
flag=0;
}
else
{
cout<<"输入错误，请重新输入!"<<endl;
flag=1;
}
}
BubbleSort(fano,n);
FanoCode(1,n,fano);
cout<<" 费诺编码"<<endl;
cout<<"数据"<<'\t'<<"概率"<<'\t'<<"编码"<<'\t'<<"编码长度"<<endl;
for(i=1;i<=n;i++)
{
cout<<fano[i].data;
cout<<'\t'<<fano[i].P;
cout<<'\t'<<p[i];
cout<<'\t'<<strlen(p[i]);
cout<<endl;
} //输出费诺编码
}
- 17 -