信息论与编码课程设计.docx
《信息论与编码课程设计.docx》由会员分享,可在线阅读,更多相关《信息论与编码课程设计.docx(18页珍藏版)》请在冰点文库上搜索。
信息论与编码课程设计
信息论与编码课程设计
信息论与编码课程设计报告
设计题目:
判断唯一可译码、香农编码
专业班级电信12-03
学号311208000607
学生姓名曹琳
指导教师成凌飞
教师评分
2015年3月21日
中出现C中的元素就终止,这也是在本题的要求中需要注意的问题。
2、香农编码
香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编
码使平均码长达到极限值,这是一个很重要的极限定理。
香农第一定理指出,选择每个码字的长度Ki满足下式:
I(xi)≤K﹤I(xi)+1,
就可以得到这种码。
这种编码方法就是香农编码。
香农编码法有重要的理论意义。
编码步骤如下:
(1)将信源消息符号按其出现的概率大小依次排列:
p(x1)≥p(x2)≥···≥p(xn)
(2)确定满足下列不等式整数码长Ki:
-log2p(xi)≤Ki<-log2p(xi)+1
(3)为了编成唯一可译码,计算第i个消息的累加概率;
(4)将累加概率Pi变成二进制数;
(5)取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。
三、设计流程图
1、判断唯一可译码
其框图如下:
2、香农编码
其框图如下:
四、程序运行及结果
1、判断唯一可译码
其运行结果如下图所示:
2、香农编码
其运行结果如下图所示:
五、心得体会
这次信息论与编码的程序设计,对于我来说是一个挑战。
课程设计是培养学生综合运用所学知识,发现问题、提出问题、分析问题和解决问题的过程,锻炼学生的逻辑思维能力和实践能力,是对学生实际工作能力的具体训练和考察过程。
在整个课程程序中,我们充分应用和调用各个程序模块,从而部分实现了此次程序设计的所应该有的功能。
就是我在课程设计是比较成功的方面,而在这个过程中,让我感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识,充分的发挥了我们的主动性,使我们学会了自主学习,和独立解决问题的能力。
这次的程序软件基本上运行成功,可以简单的输入进行压缩,并且运用简单的数字告诉程序的操作者下一步该如何进行,使得程序规模相对较小,即功能还不很全面,应用也不很普遍。
总而言之,这次数据结构课程设计让我们感触很深,使我们每个人都了解到学习不应该只局限于课本,因为课本上告诉我们的只是很有限的一部分,只是理论上的死知识,所涉及的范围也是狭窄的。
我们若想在有限的范围内学习到无限的知识,就要我们自己懂得争取,懂得自学,懂得充分利用身边的任何资源。
在我们的程序中有一部分查找许多该方面的资料,我竭力将所获得的信息变成自己的资源。
我动手上机操作的同时,在了解和看懂的基础上对新学的知识进行改进和创新,但是在我们的程序软件中还有很多的不足,需要加以更新。
通过这次课程设计,我们都意识到了自己动手实践的弱势,特别是在编程方面,于是我们知道了计算机的实践操作是很重要的,只有通过上机编程才能充分的了解自己的不足。
通过这次的课程设计,我们深刻意识到自己在学习中的弱点,同时也找到了克服这些弱点的方法,这是在此活动中得到的一笔很大的财富。
同时也感谢老师给我们这次机会,发现自身存在的缺点与不足,从而在以后的大学生活中更好的提升和完善自我。
参考文献
[1]曹雪虹.信息论与编码[M].北京:
清华大学出版社,2009.2
[2]河南理工大学概率论与数理统计教研组.概率论与数理统计[M].北京:
高等教育出版社,2013.4
[3]贾宗璞.C语言程序设计[M].北京:
北京邮电大学出版社,2010
附录:
源程序
1、判断唯一可译码
#include
#include
#include
structstrings
{
char*string;
structstrings*next;
};
structstringsFstr,*Fh,*FP;
//输出当前集合
voidoutputstr(strings*str)
{
do
{
cout<string<str=str->next;
}while(str);
cout<}
inlineintMIN(inta,intb)
{returna>b?
b:
a;}
inlineintMAX(inta,intb)
{returna>b?
a:
b;}
#definelength_a(strlen(CP))
#definelength_b(strlen(tempPtr))
//判断一个码是否在一个码集合中,在则返回0,不在返回1
intcomparing(strings*st_string,char*code)
{
while(st_string->next)
{
st_string=st_string->next;
if(!
strcmp(st_string->string,code))
return0;
}
return1;
}
//判断两个码字是否一个是另一个的前缀,如果是则生成后缀码
voidhouzhui(char*CP,char*tempPtr)
{
if(!
strcmp(CP,tempPtr))
{
cout<<"集合C和集合F中有相同码字:
"<<<<"不是唯一可译码码组!
"<exit
(1);
}
if(!
strncmp(CP,tempPtr,MIN(length_a,length_b)))
{
structstrings*cp_temp;
cp_temp=new(structstrings);
cp_temp->next=NULL;
cp_temp->string=newchar[abs(length_a-length_b)+1];
char*longstr;
longstr=(length_a>length_b?
CP:
tempPtr);//将长度长的码赋给longstr
//取出后缀
for(intk=MIN(length_a,length_b);kcp_temp->string[k-MIN(length_a,length_b)]=longstr[k];
cp_temp->string[abs(length_a-length_b)]=NULL;
//判断新生成的后缀码是否已在集合F里,不在则加入F集合
if(comparing(Fh,cp_temp->string))
{
FP->next=cp_temp;
FP=FP->next;
}
}
}
voidmain()
{
//功能提示和程序初始化准备
cout<<"\t\t唯一可译码的判断!
\n"<structstringsCstr,*Ch,*CP,*tempPtr;
Ch=&Cstr;
CP=Ch;
Fh=&Fstr;
FP=Fh;
charc[]="C:
";
Ch->string=newchar[strlen(c)];
strcpy(Ch->string,c);
Ch->next=NULL;
charf[]="F:
";
Fh->string=newchar[strlen(f)];
strcpy(Fh->string,f);
Fh->next=NULL;
//输入待检测码的个数
intCnum;
cout<<"输入待检测码的个数:
";
cin>>Cnum;
cout<<"输入待检测码"<for(inti=0;i{
cout<
";
chartempstr[10];
cin>>tempstr;
CP->next=new(structstrings);
CP=CP->next;
CP->string=newchar[strlen(tempstr)];
strcpy(CP->string,tempstr);
CP->next=NULL;
}
outputstr(Ch);
CP=Ch;
while(CP->next->next)
{
CP=CP->next;
tempPtr=CP;
do
{
tempPtr=tempPtr->next;
houzhui(CP->string,tempPtr->string);
}while(tempPtr->next);
}
outputstr(Fh);
structstrings*Fbegin,*Fend;
Fend=Fh;
while
(1)
{
if(Fend==FP)
{
cout<<"是唯一可译码码组!
"<exit
(1);
}
Fbegin=Fend;
Fend=FP;
CP=Ch;
while(CP->next)
{
CP=CP->next;
tempPtr=Fbegin;
for(;;)
{
tempPtr=tempPtr->next;
houzhui(CP->string,tempPtr->string);
if(tempPtr==Fend)
break;
}
}
outputstr(Fh);//输出F集合中全部元素
}
}
2、香农编码
#include
#include
#include
#include
classT
{
public:
T(){}
~T();
voidCreate();
voidCoutpxj();
voidCoutk();
voidCoutz();
voidPrint();
protected:
intn;
double*p;
double*pxj;
int*k;
double*mz;
};
voidT:
:
Create()
{
cout<<"请输入信源符号个数:
";
cin>>n;
p=newdouble[n];
cout<<"请分别输入这"<\n";
for(inti=0;icin>>p[i];
pxj=newdouble[n];
k=newint[n];
mz=newdouble[n];
doublesum=0.0;
for(i=0;isum+=p[i];
if(sum!
=1.0)
throw1;
else
{
for(i=0;i{
intk=i;
for(intj=i+1;jif(p[k]
doublem=p[i];
p[i]=p[k];
p[k]=m;
}
}
}
T:
:
~T()
{
deletep;
deletepxj;
deletek;
deletemz;
}
voidT:
:
Coutpxj()
{
pxj[0]=0;
for(inti=1;i{
pxj[i]=0;
for(intj=0;j
pxj[i]+=p[j];
}
}
voidT:
:
Coutk()
{
for(inti=0;i{
doubled=(-1)*(log(p[i])/log
(2));
if(d-(int)d>0)k[i]=(int)d+1;
elsek[i]=(int)d;
}
}
voidT:
:
Print()
{
cout<<"Xi"<<<<<for(inti=0;i{cout<<"X"<
<(2)<
<(2)<<mz[i]=pxj[i];
for(intj=0;j{
if(2*mz[i]-1>=0)
{
cout<<1;
mz[i]=2*mz[i]-1;
}
else
{
cout<<0;
mz[i]=2*mz[i];
}
}
cout<}
doubleK=0.0,H=0.0,Y;
for(i=0;i{
K+=(double)p[i]*k[i];
H+=(-1)*p[i]*(log10(p[i])/log10(2.0));
}
Y=H/K;
cout<<"平均码长:
"<cout<<"信源熵:
"<cout<<"编码效率:
"<}
voidmain()
{
Tt;inte;
try
{
t.Create();
t.Coutpxj();
t.Coutk();
t.Print();
}
catch(inte)
{if(e==1)cout<<"输入错误,请重新运行";}
}