信息論課程設(shè)計

電子科技大學(xué)電子工程學(xué)院信息論課程設(shè)計報告課程名稱：信息編碼與加密課程設(shè)計報告學(xué)生姓名：農(nóng)瀚學(xué)號：20指導(dǎo)教師：李萬春一、課程設(shè)計名稱：編程實現(xiàn)霍夫曼、費(fèi)諾、香農(nóng)編碼二、課設(shè)原理：1）霍夫曼編碼：霍夫曼編碼的平均碼長最短，是最佳編碼。編碼步驟如下：（1）將信源符號按概率大小排序；（2）對概率最小的兩個符號求其概率之和，同時給兩幅號分別賦予碼元0和1；（3）將概率之和當(dāng)做一個新符號的概率。與剩下的概率一起，形成一個縮減信源，再重復(fù)上述步驟，直到概率和為1為止；（4）按上述步驟實際上構(gòu)成了一個碼樹，從根到端點經(jīng)過的樹枝即為碼字。/2）費(fèi)諾編碼：編碼步驟如下：（1）將信源概率從大到小排序；（2）將信源符號分成兩組，使兩組信源符號的概率之和近似相等，并給兩組信源符號分別賦0和1；（3）再把各個小組的信源符號細(xì)分為兩組并賦碼元，方法與第一次分組相同；（4）如此一直下去，直到每一個小組只含一個信源符號為止；（5）由此可構(gòu)造成一個碼樹，所有終端節(jié)點上的碼字組成費(fèi)諾碼。3）香農(nóng)編碼：編碼方法如下：⑴將信源消息符號按其出現(xiàn)的概率大小依次排列@p（u1）Np（u2）N???Np（un）⑵確定碼長Ki（整數(shù)）:1^—Ki=[Pi]——取整⑶為了編成唯一可譯碼，計算第i個消息的累加概率J-1Pi-XpM⑷將累加概率Pi變換成二進(jìn)制數(shù)。⑸取pi二進(jìn)制數(shù)的小數(shù)點后Ki位即為該消息符號的二進(jìn)制數(shù)。三、課設(shè)目的：通過編程實現(xiàn)三種方式的編碼，掌握三種編碼方式的步驟。四、課設(shè)內(nèi)容：三種編碼方式的編程思路：】1、霍夫曼編碼：（1）對給定的n個權(quán)值{W1,W2,W3,...,Wi,...,Wn構(gòu)成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點，它的左右子樹均為空。（為方便在計算機(jī)上實現(xiàn)算法，一般還要求以Ti的權(quán)值Wi的升序排列。）（2）在F中選取兩棵根結(jié)點權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點的權(quán)值為其左右子樹的根結(jié)點的權(quán)值之和。（3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。（4）重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。2、費(fèi)諾編碼的編程思路：（1）先使用冒泡法對信源概率概率排序；（2）依次將按排好序的符號概率進(jìn)行近似1:1分成兩大組；（3）對各組賦予一個二進(jìn)制碼元“0”和“1”；（4）輸出符號,符號概率及編碼。3、香農(nóng)編碼：（1）對于一個給定的符號列表，制定了概率相應(yīng)的列表或頻率計數(shù)，使每個符號的相對發(fā)生頻率是已知。（2）排序根據(jù)頻率的符號列表，最常出現(xiàn)的符號在左邊，最少出現(xiàn)的符號在右邊。（3）清單分為兩部分，使左邊部分的總頻率和盡可能接近右邊部分的總頻率和。（4）該列表的左半邊分配二進(jìn)制數(shù)字0，右半邊是分配的數(shù)字1。這意味著，在第一半符號代都是將所有從0開始，第二半的代碼都從1開始。（（5）對左、右半部分遞歸應(yīng)用步驟3和4,細(xì)分群體，并添加位的代碼，直到每個符號已成為一個相應(yīng)的代碼樹的葉。

五、器材（設(shè)備、元器件）：計算機(jī)、visualstudio2017社區(qū)版六、設(shè)計代碼：見附錄九、實驗數(shù)據(jù)及結(jié)果根據(jù)上述實驗程序得到的實驗數(shù)據(jù)及結(jié)果如下:霍夫曼編碼：C\Window5\system32\cn：d.exe言源ism:言源蝙碼為:言源3編碼為:'言源濡碼為:'言源S編碼為：音燎盤福為：'言源7編碼為：言源，編碼為=言源9編碼為：1。編碼為::11編碼為」修編碼為;1魏碼為r1編磚為*15編碼為『16編碼為:"編碼丸1R編碼丸19喘甜為'言源10Q100Q1001Q01010100010101100101頑61QQ101G1110Q110000誡100100011011.0011110001100llpl1U.01111信源概率信源概率『信源概率、信源概率;.信源概率，信源概率，信源概率：信源概率；信源概率頊信源概率：信源概率，信源概率，信源概率，信源概率：信源概率：信源概率：信源撇奉，信源概率：信源概率，.0.00695822:O'.00753807.0.01049S40.01440470.0156S650.Q2331616.&352.9B0.Q2975550.0424512.0432447O'源如SB0.04477070.04644920.0552690.05551320.06357010.07565540.QSQ59940.0215760.08542137—7/kZV-555544444444444芋字長長長，字字字字字字字汗字字字襯字字字字釧字狷碼效率：9Q.9645%青按任意鍵M續(xù)..?費(fèi)諾編碼:dews?:ystervii2\czrid.e:<e賈浴嗣寄怛炬瓦源源岸原岸源握原源源泉源京源源源源源原原e^14=-.-昌一口j--;!￡.b,/=■■■日成口j.=H=■■!!信jl.f-u=>IR信Mls-Jr□=■■■日成口MU3167131L51s417sO4-529Hi1101611i.08355970.032&4410.08102660.0，仃5410.07434310.0601520.05339570.05246130.05038610.04599140.04533；0/03344230.02203410.02117980.015167?0.0146134：0.0132145C.007S737SC.(07538070.00375370；：ooo

OOLI：010.；OLIO011110001001LOLO，:101111001W11011111佩:111010；1L1Q1L

111100:;ill1010:1111011土L111LC%Ll：l：l7—766■■何知工長長長*出;?邕點富；」<.-'E&^鉗字字衽U字銖U彗A字字字子案瑪4率：89.m>

請技任鼬峻.一香農(nóng)編碼:■C:\U5s-ri^hasee^docurr?nEs\'?15ua:sEudid2D""^Prc'je'ztiXH^^^^pehLi=■信薄符號,苗特S瞞、符號信源隔信源時信源甕號，些驟件，信源符號,信源砰WJ；

信源時

信源濘號「信源符號，1者何!仍砰，I信褓舞率;L信源概率，17信源概率5信源撩率;L6信源概率信源概率,U信源壕率0信源概率,19信源襟率6信源概率，10信源概率15僖源概率信源攜率信源擢率;2佰轉(zhuǎn)嗥率，信源概率,1.1信源褓率LS信源概率信源撬率0.082338^0.0E056S90.07S40210.0564592C.05264^40.05209510.043951.70.|：4852440.0482142(.0405S960.03952150.0299997G.02676470.02459790.018891.0.0L7487L0.0L6G222C.CC92L6590.00S02637累加概率0,0033155累加格率口.1時湖果加概率二24C223紫加概率口,的費(fèi)器累加概率口，3S1085累加概辱0,433729累加癖率口.4B5S24累加概剽,5捉灑累忙概^0.5038

累加概率D.626514票加概率Q,667104累加概率0,706626累加R^O.736625祟加概率Q,76339累加概率0.7S70BS累加概率0,S06B7t累加概率0,834366|景加撩率口，340388累加糠率匕B49605774-4555666455556￡E-rEEL-_k^-rbrE-h--Lzly圭霍lll字字國字:0001碼字:DDLO弱字,0011碼學(xué)；01010甬字"U其俱字；Q1101科禮01111碼字，10001碼字;10010碼字*1DL0I明字，10101智字；W11Q1碼字：10LLLL碼字;110000祥尹110010碼字I110011色字：110100包宇，110LOLL瑪字，110110073.9097%十、結(jié)論完成了20個非等概隨機(jī)信源的霍夫曼、費(fèi)諾和香農(nóng)編碼，并給出了編碼效率和碼字。十^一、總結(jié)及心得體會通過這次課程設(shè)計，我掌握了三種編碼方式的步驟，并能夠利用編程實現(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:定義控制臺應(yīng)用程序的入口點。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){/*分組函數(shù)*/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;elsebreak;】}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<<""<<"字長"<<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:定義控制臺應(yīng)用程序的入口點。<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(structshan[],inti){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)[i].l_f+1;elsex[i].l=(int)[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(i