信息論和編碼課程設(shè)計(jì)匯本報(bào)告

1、目錄一：實(shí)驗(yàn)原理 1二：程序源代碼1三：實(shí)驗(yàn)分析6四:實(shí)驗(yàn)結(jié)論7赫夫曼編碼二實(shí)驗(yàn)原理哈夫曼編碼的具體步驟歸納如下： 概率統(tǒng)計(jì)如對(duì)一幅圖像，或m幅同種類型圖像作灰度信號(hào)統(tǒng)計(jì), 得到n個(gè)不同概率的信息符號(hào)。 將n個(gè)信源信息符號(hào)的n個(gè)概率，按概率大小排序。 將n個(gè)概率中，最后兩個(gè)小概率相加，這時(shí)概率個(gè)數(shù)減為n-1個(gè)。 將n-1個(gè)概率，按大小重新排序。 重復(fù)，將新排序后的最后兩個(gè)小概率再相加， 相加和與其余概率 再排序。 如此反復(fù)重復(fù)n-2次，得到只剩兩個(gè)概率序列。 以二進(jìn)制碼元(0.1)賦值，構(gòu)成哈夫曼碼字。編碼完畢。哈夫曼碼字長(zhǎng)度和信息符號(hào)出現(xiàn)概率大小次序正好相反，即大概信息 符號(hào)分配碼字長(zhǎng)度短，

2、小概率信息符號(hào)分配碼字長(zhǎng)度長(zhǎng)。C、哈夫曼編碼的特點(diǎn)(1) 哈夫曼編碼的構(gòu)造順序明確，但碼不是唯一的 (因以大賦1還是小的賦1而異；(2) 哈夫曼編碼的字長(zhǎng)參差不齊，硬件實(shí)現(xiàn)不方便；(3) 只有在概率分布很不均勻時(shí)，哈夫曼編碼才有顯著的效果，而在信 源分布均勻時(shí)，一般不使用哈夫曼編碼。1：程序源代碼:#defi ne MAXVALUE 10000#defi ne MAXLEAF 30#defi ne MAXNODE 59#defi ne MAXBIT 10#define LENTH 30#include "stdio.h"#in clude<iostream>ty

3、pedef structfloat gailv;int flag;int pare nt;int lchild;int rchild;char ch;int t;HNodeType;typedef structint bitMAXBIT;int start;HCodeType;typedef structfloat gailv;char letter;mytype; /*it's the type of data save in file*/ typedef struct filehuffint count;mytype mydataMAXLEAF; filehuff()cou nt=

4、0; ;filehuff filedata;char codeMAXVALUE;HNodeType HuffNodeMAXNODE;void savetofile()FILE *fp;if(fp=fope n("datafile.txt","wb")=NULL)printf("翻開(kāi)失敗.");return;if(fwrite(&filedata,sizeof(filedata),1,fp)!=1)printf("寫(xiě)入文件失敗.")；fclose(fp);void ope nfile() FILE *fp;i

5、f(fp=fope n("datafile.txt","rb")=NULL)return;fread(&filedata,sizeof(filedata),1,fp);void tran slate()char c;int i,j,k=0,m, n=0;printf("請(qǐng)輸入你想要譯碼的二進(jìn)制序列");prin tf("n");getchar();sca nf("%c",&c);for(i=0;(i<MAXVALUE )&&( c='1'|c

6、='0');i+) codei=c;sca nf("%c",&c);printf("對(duì)應(yīng)的信源符號(hào)為:");for(j=0;j<=MAXVALUE&&HuffNodej.pare nt!=-1;j+) m=j+1;for(j=0,k=m;j<=i;j+)if(codej='0')n=HuffNodek.lchild;if(n=-1)prin tf("%c",HuffNodek.ch);k=m;j-;co nti nue;k=n;elsen=HuffNodek.rchi

7、ld;if(n=-1)prin tf("%c",HuffNodek.ch); k=m;j-;co nti nue;k=n;void Huffma n()HCodeType HuffCodeMAXLEAF,cd;int i,j,m1,m2,x1,x2,c,p,m;if(filedata.co un t=0) printf("n輸入信源符號(hào)總數(shù):");sca nf("%d",&m);filedata.co un t=m;for(i=0;i<2*m-1;i+) HuffNodei.gailv=0;HuffNodei.pare

8、nt=-1;HuffNodei.flag=0;HuffNodei.lchild=-1;HuffNodei.rchild=-1;HuffNodei.ch='a'for(i=0;i<m;i+) printf("請(qǐng)輸入(概率，信源符號(hào)):");sca nf("%f %c",&HuffNodei.gailv,&HuffNodei.ch);filedata.mydatai.gailv=HuffNodei.gailv; filedata.mydatai.letter=HuffNodei.ch; savetofile();else

9、 m=filedata.co unt;for(i=0;i<2*m-1;i+) HuffNodei.gailv=0;HuffNodei.pare nt=-1;HuffNodei.flag=0;HuffNodei.lchild=-1;HuffNodei.rchild=-1;HuffNodei.ch=3;for(i=0;i<m;i+) HuffNodei.gailv=filedata.mydatai.gailv;HuffNodei.ch=filedata.mydatai.letter;for(i=0;i<m-1;i+) m1=m2=MAXVALUE;x仁 x2=0;for(j=0;

10、j<m+i;j+) if(HuffNodej.gailv<m1 &&HuffNodej.flag=0) m2=m1;x2=x1;m仁 HuffNodej.gailv;x1=j;else if(HuffNodej.gailv<m2&&HuffNodej.flag=0) m2=HuffNodej.gailv;x2=j;HuffNodex1.pare nt=m+i;HuffNodex2.pare nt=m+i;HuffNodex1.flag=1;HuffNodex2.flag=1;HuffNodem+i.gailv=HuffNodex1.gailv+

11、HuffNodex2.gailv;HuffNodem+i.lchild=x1;HuffNodem+i.rchild=x2; for(i=0;i<m;i+) cd.start=m-1;c=i;p=HuffNodec.pare nt;while(p!=-1) if(HuffNodep.lchild=c)cd.bitcd.start=0;else cd.bitcd.start=1;cd.start-;c=p;p=HuffNodec.pare nt;for(j=cd.start+1;j<m;j+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start

12、; printf("對(duì)應(yīng)的赫夫曼編碼如下： printf("n信源符號(hào) for(i=0;i<m;i+)prin tf("%c概率%fII);編碼n");”,HuffNodei.ch,HuffNodei.gailv);for(j=HuffCodei.start+1;j<m;j+) prin tf("%d",HuffCodei.bitj);prin tf("n");printf（"按任意鍵繼續(xù)n"）;mai n()char yn;prin tf("n");prin t

13、f("n");printf(”信息論與編碼實(shí)驗(yàn)n");ope nfile();Huffma n();for(;)printf("n是否想要把序列譯碼為信源符號(hào)？：(輸入y or n)");sea nf("%c", &yn);if(y n='y'|y n='Y')tran slate();elsebreak;return 0;system("pause");三：實(shí)驗(yàn)分析編碼實(shí)例如下:由圖中可以看出，符合根本的赫夫曼編碼的原理，概率大的用短碼，概率小的用長(zhǎng)碼。信畠論與編

14、魚(yú)實(shí)驗(yàn)F-A, i-i4任童犍繼續(xù),!= *立r-電0.1500008.2606000.300000編碼11011100H110辰否想要把序列譯碼為信源符號(hào)?： £端入選擇譯碼：結(jié)果如下:是否想斜巴匡列譯碼為信猱符號(hào)?： t輸入y or n) y 請(qǐng)輸入裱擔(dān)要譯科的二進(jìn)制序列對(duì)應(yīng)旳信源符弓為；eddcedcee是否想妥把序列譯碼為信源符號(hào)?=瞞入y “ n四：實(shí)驗(yàn)結(jié)論哈夫曼的具體實(shí)現(xiàn)，在數(shù)據(jù)構(gòu)造的相關(guān)課程曾做相應(yīng)的實(shí)驗(yàn)， 所 以無(wú)論在理解上或是實(shí)現(xiàn)上，都不是很困難，程序上實(shí)現(xiàn)哈夫曼的編 碼與譯碼，由于哈夫曼自身的特點(diǎn)，編碼與譯碼均不是唯一，但是一 樣的編譯碼規(guī)那么還是能實(shí)現(xiàn)正確的譯碼的。 本實(shí)驗(yàn)，除了實(shí)現(xiàn)編譯 碼的具體實(shí)現(xiàn)，還實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)與讀取，這給實(shí)驗(yàn)實(shí)現(xiàn)方便，不必 每次從命令提示符輸入數(shù)據(jù)?？偟?/p>