信息論課程設(shè)計(jì)

電子科技大學(xué)電子工程學(xué)院信息論課程設(shè)計(jì)報(bào)告課程名稱：信息編碼與加密

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

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

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

p(un)⑵

確定碼長(zhǎng)Ki

(整數(shù))

：

Ki=[]——取整⑶

為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率

⑷

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

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

（2）在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。

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

（4）重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。2、費(fèi)諾編碼的編程思路：（1）先使用冒泡法對(duì)信源概率概率排序；（2）依次將按排好序的符號(hào)概率進(jìn)行近似1:1分成兩大組；（3）對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和“1”；（4）輸出符號(hào),符號(hào)概率及編碼。3、香農(nóng)編碼：（1）對(duì)于一個(gè)給定的符號(hào)列表，制定了概率相應(yīng)的列表或頻率計(jì)數(shù)，使每個(gè)符號(hào)的相對(duì)發(fā)生頻率是已知。（2）排序根據(jù)頻率的符號(hào)列表，最常出現(xiàn)的符號(hào)在左邊，最少出現(xiàn)的符號(hào)在右邊。（3）清單分為兩部分，使左邊部分的總頻率和盡可能接近右邊部分的總頻率和。（4）該列表的左半邊分配二進(jìn)制數(shù)字0，右半邊是分配的數(shù)字1。這意味著，在第一半符號(hào)代都是將所有從0開始，第二半的代碼都從1開始。（5）對(duì)左、右半部分遞歸應(yīng)用步驟3和4，細(xì)分群體，并添加位的代碼，直到每個(gè)符號(hào)已成為一個(gè)相應(yīng)的代碼樹的葉。五、器材（設(shè)備、元器件）：計(jì)算機(jī)、visualstudio2017社區(qū)版六、設(shè)計(jì)代碼：見(jiàn)附錄九、實(shí)驗(yàn)數(shù)據(jù)及結(jié)果根據(jù)上述實(shí)驗(yàn)程序得到的實(shí)驗(yàn)數(shù)據(jù)及結(jié)果如下：霍夫曼編碼：費(fèi)諾編碼：香農(nóng)編碼：十、結(jié)論完成了20個(gè)非等概隨機(jī)信源的霍夫曼、費(fèi)諾和香農(nóng)編碼，并給出了編碼效率和碼字。十一、總結(jié)及心得體會(huì)通過(guò)這次課程設(shè)計(jì)，我掌握了三種編碼方式的步驟，并能夠利用編程實(shí)現(xiàn)編碼，提高了自己的編程水平和對(duì)該知識(shí)點(diǎ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<<"字長(zhǎng)："<<strlen(coder[i]); printf("\n"); bitlong[i]=strlen(coder[i]); } CodEffi(); cout<<"\n編碼效率:"<<CodEffi()*100<<"%\n"; return0;}pp:定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。=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("費(fèi)諾編碼輸出信源,概率及編碼：\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<<""<<"字長(zhǎng)"<<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:定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。<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;