信息论实验报告

PAGEPAGE2《信息论基础教程》报告实验名称

信息论基础教程上机作业学院计通学院专业班级

计算机1003

姓

名

翟文洁

学

号

41050270

2012年11月实验一唯一可译码判别准则实验目的进一步熟悉唯一可译码判决准则；掌握C语言字符串处理程序的设计和调试技术。实验要求已知：信源符号个数q、码字集合C。输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。输出：判决（是唯一可译码/不是唯一可译码）。实验原理算法：考察C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀码放在集合考察C和Fi两个集合，若Wi∈C是Wj∈Fi的前缀或Wi∈Fi是WjF=iFi即为码若F中出现了C的元素，则算法终止，返回假（C不是唯一可译码）；否则，若F中没有出现新的元素，则返回真。实验环境Microsoftvisualc++实验文件程序代码：#include<iostream>#include<string>#include<vector>#include<algorithm>usingnamespacestd;usingstd::vector;boolrecursion(vector<string>c,vector<string>fi);vector<string>f;intmain(){ intn; vector<string>c,fj; stringtemp; boolout; cout<<"请输入码字个数:\t"; cin>>n; cout<<endl; cout<<"请输入具体码字:\t(用回车键结束每个码字的输入)"<<endl; for(inti=0;i<n;i++){ cin>>temp; c.push_back(temp); fj.push_back(temp); } cout<<endl; out=recursion(c,fj); if(out==false){ cout<<"该码字集合不是唯一可译码!"<<endl; }else{ cout<<"该码字集合是唯一可译码!"<<endl; } return0;}boolrecursion(vector<string>c,vector<string>fi){ strings,s1,s2; intmin; vector<string>fj; vector<string>::iteratoriter_c,iter_fi,iter_find,iter_fj; for(iter_c=c.begin();iter_c!=c.end();iter_c++){for(iter_fi=fi.begin();iter_fi!=fi.end();iter_fi++){s=*iter_c; s1=*iter_fi; if(s==s1){ continue; } min=s.length()<s1.length()?s.length():s1.length(); if(pare(0,min,s1,0,min)==0){ if(s.length()==min){ s=s1; } s2=s.substr(min,s.length()-min); iter_find=find(fj.begin(),fj.end(),s2); if(iter_find!=fj.end()){ continue; } fj.push_back(s2); iter_find=find(c.begin(),c.end(),s2); if(iter_find!=c.end()){ returnfalse; } }else{ continue; } } } for(iter_fj=fj.begin();iter_fj!=fj.end();iter_fj++){ iter_find=find(f.begin(),f.end(),*iter_fj); if(iter_find==f.end()){ for(iter_fj=fj.begin();iter_fj!=fj.end();iter_fj++){ iter_find=find(f.begin(),f.end(),*iter_fj); if(iter_find==c.end()){ f.push_back(*iter_fj); } } returnrecursion(c,fj); } } returntrue;}实验结果实验二Huffman编码实验目的进一步熟悉Huffman编码过程；掌握C语言递归程序的设计和调试技术。实验要求输入：信源符号个数r、信源的概率分布P;输出：每个信源符号对应的Huffman编码的码字。实验原理实验算法将q个信源符号按其概率的递减次序排列：p(s0)≥p(s1)≥┄≥p(计算出各个信源符号的累加概率：F(si)=按下式计算第i个消息的二元代码组的码长lili=[将累加概率（十进制小数）变换为二进制小数。根据码长取小数点后个二进制符号作为第i个消息的码字。实验环境Microsoftvisualc++实验文件程序源代码：#include<iostream>#include<string>#include<algorithm>#include<vector>usingnamespacestd;usingstd::vector;typedefstructunit{ intnum; doublep; stringhuf;}unit;vector<unit>Huffman(vector<unit>);boolcomp(unit,unit);intmain(){ while(true){ while(true){ intr; doublep,sum=0; unittemp; boolflag=true; vector<unit>s; cout<<"Huffman编码\n"; cout<<"请输入信源符号个数r:"; cin>>r; cout<<endl<<"请输入信源的概率分布P:\n"; for(inti=0;i<r;i++){ cin>>p; if(p<0||p>1){ cout<<endl<<"信源符号概率输入值应在0~1之间,请重新输入。"<<endl; cout<<"\n\n"; flag=false; break; } sum+=p; temp.num=i+1; temp.p=p; s.push_back(temp); } if(flag==false){ break; } cout<<endl; if(sum>1||sum<1){ cout<<"信源符号概率分布和应为1,请重新输入。"<<endl; cout<<"\n\n"; break; } s=Huffman(s); //执行Huffman编码算法 cout<<"该信源的Huffman编码如下所示:"<<endl<<endl; cout<<"符号"<<"\t"<<"概率"<<"\t"<<"Huffman编码"<<endl; for(i=0;i<r;i++){ cout<<"s"<<s.at(i).num<<"\t"<<s.at(i).p<<"\t"<<s.at(i).huf<<endl; } cout<<"\n\n"; break; } charcont; cout<<"是否继续？(y/n)"; cin>>cont; if(cont=='y'||cont=='Y'){ cout<<endl; continue; }else{ cout<<endl; return0; } }} vector<unit>Huffman(vector<unit>s){ vector<unit>::iteratoriter; sort(s.begin(),s.end(),comp); if(s.size()==1){ s.back().huf="0"; returns; } if(s.size()==2){ s.front().huf="0"; s.back().huf="1"; returns; } unittemp,temp1,temp2; temp1=s.back(); s.pop_back(); temp2=s.back(); s.pop_back(); temp.num=temp1.num; temp.p=temp1.p+temp2.p; s.push_back(temp); s=Huffman(s); for(iter=s.begin();iter!=s.end();iter++){ if((*iter).num==temp1.num){ tem