信息論課程設計

電子科技大學電子工程學院信息論課程設計報告課程名稱：信息編碼與加密

課程設計報告學生姓名：農(nóng)瀚學號：20指導教師：李萬春一、課程設計名稱：編程實現(xiàn)霍夫曼、費諾、香農(nóng)編碼二、課設原理：1）霍夫曼編碼：霍夫曼編碼的平均碼長最短，是最佳編碼。編碼步驟如下：（1）將信源符號按概率大小排序；（2）對概率最小的兩個符號求其概率之和，同時給兩幅 號分別賦予碼元0和1；將概率之和當做一個新符號的概率。與剩下的概率一起，形成一個縮減信源，再重復上述步驟，直到概率和為1為止；按上述步驟實際上構成了一個碼樹，從根到端點經(jīng)過的樹枝即為碼字。2）費諾編碼：編碼步驟如下：將信源概率從大到小排序；將信源符號分成兩組，使兩組信源符號的概率之和近似相等，并給兩組信源符號分別賦0和1；再把各個小組的信源符號細分為兩組并賦碼元，方法與第一次分組相同；如此一直下去，直到每一個小組只含一個信源符號為止；由此可構造成一個碼樹，所有終端節(jié)點上的碼字組成費諾碼。3）香農(nóng)編碼：編碼方法如下：⑴

將信源消息符號按其出現(xiàn)的概率大小依次排列

p(u1)≥p(u2)≥…≥

p(un)⑵

確定碼長Ki

(整數(shù))

：

Ki=[]——取整⑶

為了編成唯一可譯碼，計算第i個消息的累加概率

⑷

將累加概率Pi變換成二進制數(shù)。⑸

取pi二進制數(shù)的小數(shù)點后Ki位即為該消息符號的二進制數(shù)。三、課設目的：通過編程實現(xiàn)三種方式的編碼，掌握三種編 碼方式的步驟。四、課設內(nèi)容：三種編碼方式的編程思路：1、霍夫曼編碼：（1）對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現(xiàn)算法，一般還要求以Ti的權值Wi的升序排列。）

（2）在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。

（3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。

（4）重復二和三兩步，直到集合F中只有一棵二叉樹為止。2、費諾編碼的編程思路：（1）先使用冒泡法對信源概率概率排序；（2）依次將按排好序的符號概率進行近似1:1分成兩大組；（3）對各組賦予一個二進制碼元“0”和“1”；（4）輸出符號,符號概率及編碼。3、香農(nóng)編碼：（1）對于一個給定的符號列表，制定了概率相應的列表或頻率計數(shù)，使每個符號的相對發(fā)生頻率是已知。（2）排序根據(jù)頻率的符號列表，最常出現(xiàn)的符號在左邊，最少出現(xiàn)的符號在右邊。（3）清單分為兩部分，使左邊部分的總頻率和盡可能接近右邊部分的總頻率和。（4）該列表的左半邊分配二進制數(shù)字0，右半邊是分配的數(shù)字1。這意味著，在第一半符號代都是將所有從0開始，第二半的代碼都從1開始。（5）對左、右半部分遞歸應用步驟3和4，細分群體，并添加位的代碼，直到每個符號已成為一個相應的代碼樹的葉。五、器材（設備、元器件）：計算機、visualstudio2017社區(qū)版六、設計代碼：見附錄九、實驗數(shù)據(jù)及結果根據(jù)上述實驗程序得到的實驗數(shù)據(jù)及結果如下：霍夫曼編碼：費諾編碼：香農(nóng)編碼：十、結論完成了20個非等概隨機信源的霍夫曼、費諾和香農(nóng)編碼，并給出了編碼效率和碼字。十一、總結及心得體會通過這次課程設計，我掌握了三種編碼方式的步驟，并能夠利用編程實現(xiàn)編碼，提高了自己的編程水平和對該知識點的掌握程度。附錄代碼：eight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } for(i=0;i<n;i++) { HuffNode[i].weight=Sp[i]; } for(i=0;i<n-1;i++) { m1=m2=MaxValue; x1=x2=0; for(j=0;j<n+i;j++) { if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1) { m2=m1; x2=x1; m1=HuffNode[j].weight; x1=j; } elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1) { m2=HuffNode[j].weight; x2=j; } } HuffNode[x1].parent=n+i; HuffNode[x2].parent=n+i; HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2; }}doubleCodEffi()arent; while(p!=-1) { if(HuffNode[p].lchild==c) []=0; else []=1; ; c=p; p=HuffNode[c].parent; } for(j=+1;j<n;j++) { HuffCode[i].bit[j]=[j]; } HuffCode[i].start=; } memset(coder,'\0',sizeof(coder)); inttemp=0; for(i=0;i<n;i++) { cout<<"信源"<<i<<"編碼為："; for(j=HuffCode[i].start+1;j<n;j++) { cout<<HuffCode[i].bit[j]; coder[i][temp]=char(HuffCode[i].bit[j]+48); temp++; } temp=0; cout<<"信源概率："<<Sp[i]; cout<<"字長："<<strlen(coder[i]); printf("\n"); bitlong[i]=strlen(coder[i]); } CodEffi(); cout<<"\n編碼效率:"<<CodEffi()*100<<"%\n"; return0;}pp:定義控制臺應用程序的入口點。=i; s[i].probability=Sp[i]; }}/***********用冒泡法排序**********/voidcode(intlow,intmid,inthigh){ inti; for(i=low;i<high;i++) { if(i<mid) { s[i].[s[i].]='0'; s[i].++; } else { s[i].[s[i].]='1'; s[i].++; } }}voidsort(intn){ doublet; chara; inti,j; for(i=1;i<n;i++) for(j=0;j<n-i;j++) if(s[j].probability<s[j+1].probability) { t=s[j].probability; a=s[j].c; s[j].probability=s[j+1].probability; s[j].c=s[j+1].c; s[j+1].probability=t; s[j+1].c=a; }}/************分組函數(shù)************/voidgroup(intn){ inti,pmid,plow,phigh; pmid=phigh=n; plow=0; for(i=0;i<n;i++) s[i].=0; group1(plow,pmid,phigh);}voidgroup1(intlow,intmid,inthigh){ doubled,dmin; d=0; inti; if(high==low+1) return; for(i=low;i<mid;i++) d+=s[i].probability; dmin=d-2*s[low].probability; for(i=low+1;i<high;i++) { d=fabs(dmin-2*s[i].probability); if(d<dmin) dmin=d; else break; } mid=i; code(low,mid,high); group1(low,mid,mid); group1(mid,high,high);}voidoutput(intn){ inti,j; printf("費諾編碼輸出信源,概率及編碼：\n\n"); for(i=0;i<n;i++) { cout<<"信源："<<s[i].c<<""<<"概率："<<s[i].probability<<""<<"編碼："; for(j=0;j<s[i].;j++) cout<<s[i].[j]; bitlong[i]=s[i].; cout<<""<<"字長"<<bitlong[i]; printf("\n"); }}doubleCodEffi(){ intAveraLong=0,SumLong=0; doubleH=0,CE=0; for(inti=0;i<SourNum;i++) { SumLong=SumLong+bitlong[i]; } AveraLong=SumLong/SourNum; for(intj=0;j<SourNum;j++) { H=(-Sp[j])*(log(Sp[j])/log(2))+H; } CE=H/AveraLong; returnCE;}voidmain()pp:定義控制臺應用程序的入口點。<x[j].p) { temp=x[j]; x[j]=x[i]; x[i]=temp; } }}voidcountpadd(structshanx[],intn){ addp=0; x[0].padd=0; for(i=0;i<n;i++) { addp+=x[i].p; x[i+1].padd=addp; }}voidcount_l(structshanx[],intn){ for(i=0;i<n;i++) { x[i].l_f=-log(x[i].p)/log(2); if((x[i].l_f-(int)x[i].l_f)>0) x[i].l=(int)x[i].l_f+1; elsex[i].l=(int)x[i].l_f; }}voidcovbit(doublea,intlc){ for(j=0;j<lc;j++) { b=(int)(a*2); bitw[j]=b+48; a=2*a-int(a*2); }}doubleCodEffi(){ intAveraLong=0,SumLong=0; doubleH=0,CE=0; for(inti=0;i<SourNum;i++) { SumLong=SumLong+bitlong[i]; } AveraLong=SumLong/SourNum; for(intj=0;