信息论与编码-课程设计报告

目录一：实验原理----------------------------1二：程序源代码--------------------------1三：实验分析-----------------------------6四：实验结论---------------------------7赫夫曼编码一：实验原理哈夫曼编码的具体步骤归纳如下：①概率统计（如对一幅图像，或m幅同种类型图像作灰度信号统计），得到n个不同概率的信息符号。②将n个信源信息符号的n个概率，按概率大小排序。③将n个概率中，最后两个小概率相加，这时概率个数减为n-1个。④将n-1个概率，按大小重新排序。⑤重复③，将新排序后的最后两个小概率再相加，相加和与其余概率再排序。⑥如此反复重复n-2次，得到只剩两个概率序列。⑦以二进制码元(0.1)赋值，构成哈夫曼码字。编码结束。哈夫曼码字长度和信息符号出现概率大小次序正好相反，即大概信息符号分配码字长度短，小概率信息符号分配码字长度长。C、哈夫曼编码的特点(1)哈夫曼编码的构造顺序明确，但码不是唯一的(因以大赋1还是小的赋1而异；(2)哈夫曼编码的字长参差不齐，硬件实现不方便；(3)只有在概率分布很不均匀时，哈夫曼编码才有显著的效果，而在信源分布均匀时，一般不使用哈夫曼编码。二：程序源代码：#defineMAXVALUE10000#defineMAXLEAF30#defineMAXNODE59#defineMAXBIT10#defineLENTH30#includestdio.h#includeiostreamtypedefstruct{floatgailv;intflag;intparent;intlchild;intrchild;charch;intt;}HNodeType;typedefstruct{intbit[MAXBIT];intstart;}HCodeType;typedefstruct{floatgailv;charletter;}mytype;/*it'sthetypeofdatasaveinfile*/typedefstructfilehuff{intcount;mytypemydata[MAXLEAF];filehuff(){count=0;};};filehufffiledata;charcode[MAXVALUE];HNodeTypeHuffNode[MAXNODE];voidsavetofile(){FILE*fp;if((fp=fopen(datafile.txt,wb))==NULL){printf(打开失败....);return;}if(fwrite(&filedata,sizeof(filedata),1,fp)!=1)printf(写入文件失败....);fclose(fp);}voidopenfile(){FILE*fp;if((fp=fopen(datafile.txt,rb))==NULL){return;}fread(&filedata,sizeof(filedata),1,fp);}voidtranslate(){charc;inti,j,k=0,m,n=0;printf(请输入你想要译码的二进制序列);printf(\n);getchar();scanf(%c,&c);for(i=0;(iMAXVALUE)&&(c=='1'||c=='0');i++){code[i]=c;scanf(%c,&c);}printf(对应的信源符号为：);for(j=0;j=MAXVALUE&&HuffNode[j].parent!=-1;j++)m=j+1;for(j=0,k=m;j=i;j++){if(code[j]=='0'){n=HuffNode[k].lchild;if(n==-1){printf(%c,HuffNode[k].ch);k=m;j--;continue;}k=n;}else{n=HuffNode[k].rchild;if(n==-1){printf(%c,HuffNode[k].ch);k=m;j--;continue;}k=n;}}}voidHuffman(){HCodeTypeHuffCode[MAXLEAF],cd;inti,j,m1,m2,x1,x2,c,p,m;if(filedata.count==0){printf(\n输入信源符号总数:);scanf(%d,&m);filedata.count=m;for(i=0;i2*m-1;i++){HuffNode[i].gailv=0;HuffNode[i].parent=-1;HuffNode[i].flag=0;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].ch='a';}for(i=0;im;i++){printf(请输入(概率,信源符号):);scanf(%f%c,&HuffNode[i].gailv,&HuffNode[i].ch);filedata.mydata[i].gailv=HuffNode[i].gailv;filedata.mydata[i].letter=HuffNode[i].ch;savetofile();}}else{m=filedata.count;for(i=0;i2*m-1;i++){HuffNode[i].gailv=0;HuffNode[i].parent=-1;HuffNode[i].flag=0;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].ch=3;}for(i=0;im;i++){HuffNode[i].gailv=filedata.mydata[i].gailv;HuffNode[i].ch=filedata.mydata[i].letter;}}for(i=0;im-1;i++){m1=m2=MAXVALUE;x1=x2=0;for(j=0;jm+i;j++){if(HuffNode[j].gailvm1&&HuffNode[j].flag==0){m2=m1;x2=x1;m1=HuffNode[j].gailv;x1=j;}elseif(HuffNode[j].gailvm2&&HuffNode[j].flag==0){m2=HuffNode[j].gailv;x2=j;}}HuffNode[x1].parent=m+i;HuffNode[x2].parent=m+i;HuffNode[x1].flag=1;HuffNode[x2].flag=1;HuffNode[m+i].gailv=HuffNode[x1].gailv+HuffNode[x2].gailv;HuffNode[m+i].lchild=x1;HuffNode[m+i].rchild=x2;}for(i=0;im;i++){cd.start=m-1;c=i;p=HuffNode[c].parent;while(p!=-1){if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HuffNode[c].parent;}for(j=cd.start+1;jm;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}printf(对应的赫夫曼编码如下：);printf(\n信源符号概率编码\n);for(i=0;im;i++){printf(%c%f,HuffNode[i].ch,HuffNode[i].gailv);for(j=HuffCode[i].start+1;jm;j++)printf(%d,HuffCode[i].bit[j]);printf(\n);}printf(按任意键继续......\n);}main(){charyn;printf(\n);printf(\n);printf(信息论与编码实验\n);openfile();Huffman();for(;;){printf(\n是否想要把序列译码为信源符号?:(输入yorn));scanf(%c,&yn);if(yn=='y'||yn=='Y')translate();elsebreak;}return0;system(pause);}三：实验分析编码实例如下：由图中可以看出，符合基本的赫夫曼编码的原理，概率大的用短码，概率小的用长码。选择译码：结果如下：四：实验结论哈夫曼的具体实现，在数据结构的相关课程曾做相应的实验，所以无论在理解上或是实现上，都不是很困难，程序上实现哈夫曼的编码与译码，由于哈夫曼自身的特点，编码与译码均不是唯一，但是相同的编译码规则还是能实现正确的译码的。本实验，除了实现编译码的具体实现，还实现数据的存储与读取，这给实验实现方便，不必每次从命令提示符输入数据。总的来说，通过本次实验，对哈夫曼的编译码有了一个更好的认识。通过本次试验，对书上的理论知识有了进一步的认识，但是由于对编程软件的知识欠缺，导致有很多地方还是搞不懂，只能向同学学习，讨论。当然最终还是有一定的欠缺。对于哈夫曼编码的认识，是在以前的数据结构课程中就接触到的，但是当时只是知道哈夫曼树的编码而已。仅限于表面上的只是，并未曾想过用程序来实现它。所以对于此次试验并未有太大的帮助。通过实验，学到了很多东西，相信对以后的学习会更有帮助的。