電子科技大學-信息論課程設(shè)計(霍夫曼-費諾-香農(nóng))

電子科技大學信息與通信工程學院信息論與編碼課程設(shè)計報告課程設(shè)計報告課程設(shè)計名稱：利用編程語言實現(xiàn)霍夫曼、費諾、香農(nóng)編碼課設(shè)要求：1）、霍夫曼編碼：實現(xiàn)任意Q符號的N重序列信源的最優(yōu)R進制編碼，這里：2）、費諾、香農(nóng)編碼：實現(xiàn)任意Q符號信源的二進制編碼，這里：三、課設(shè)原理分析：1）Q信源N進制霍夫曼編碼：霍夫曼編碼的平均碼長最短，是最佳編碼。編碼步驟如下：（1）由q=(r-1)*θ+r；其中θ為縮進次數(shù)，為整數(shù)，找出q>=Q的最小整數(shù)（2）將信源符號擴展到q且q>Q信源概率為0，q個符號按概率大小排序；（3）對概率最小的N個符號求其概率之和，同時給N符號分別賦予碼元0、1、2、、、N-1；（4）將N個符號的概率之和作為一個新的符號與剩下的概率一起，形成一個縮減信源，再重復上述步驟，直到概率和為1為止；（5）按上述步驟實際上構(gòu)成了一個碼樹，從根到端點經(jīng)過的樹枝即為碼字。2）費諾編碼：編碼步驟如下：將信源概率從大到小排序；將信源符號分成兩組，使兩組信源符號的概率之和近似相等，并給兩組信源符號分別賦0和1；再把各個小組的信源符號細分為兩組并賦碼元，方法與第一次分組相同；如此一直下去，直到每一個小組只含一個信源符號為止；由此可構(gòu)造成一個碼樹，所有終端節(jié)點上的碼字組成費諾碼。3）香農(nóng)編碼：編碼方法如下：⑴

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

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

p(un)⑵

確定碼長Ki

(整數(shù))

：

Ki=[log1⑶

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

pi⑷

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

取pi二進制數(shù)的小數(shù)點后Ki位即為該消息符號的二進制數(shù)。三、課設(shè)目的：通過編程實現(xiàn)三種方式的編碼，掌握三種編 碼方式的步驟。四、課設(shè)思路：三種編碼方式的編程思路：1、Q信源二進制霍夫曼編碼：（1）對給定的q個權(quán)值{W1,W2,W3,...,Wi,...,Wq}構(gòu)成q叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tq}，其中每棵二叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點，它的左右子樹均為空。（我們直接在c語言中用typedef來定義數(shù)據(jù)類型）

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

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

（4）重復二和三兩步，直到集合F中只有一棵二叉樹為止。2、Q信源r進制霍夫曼編碼 用typedef來定義數(shù)據(jù)類型，如下圖定義父節(jié)點，子節(jié)點其中有5個，可以滿足2進制到5進制內(nèi)編碼要求（如3進制時僅選擇lchild、zhong和rchild為子節(jié)點，parent為父節(jié)點，weight為權(quán)重，可以進行編碼，當輸入為Q時，利用由q=(r-1)*θ+r；其中θ為縮進次數(shù)，為整數(shù)，找出q>=Q的最小整數(shù),對q信源符號進行r進制編碼，lchild為0，zhong為1，rchild為2，parent的權(quán)值為這三個權(quán)值之和，再進行排序，直到僅剩一個三叉樹）3、Q信源R進制N重信源的霍夫曼編碼 如下圖，（下圖為n信源q進制，寫的時候順手了，沒有改），當為二重編碼時，對信源權(quán)值進行分步乘積得到新的信源權(quán)值，信源個數(shù)為Q的二次方，再對其進行編碼進行編碼效率計算時，q重序列，信源熵為原來的q倍4、費諾編碼的編程思路：（1）先使用冒泡法對信源概率概率排序；（2）依次將按排好序的符號概率進行近似1:1分成兩大組；（3）對各組賦予一個二進制碼元“0”和“1”；（4）輸出符號,符號概率及編碼。5、香農(nóng)編碼：（1）對于一個給定的符號列表，制定了概率相應的列表或頻率計數(shù)，使每個符號的相對發(fā)生頻率是已知。（2）排序根據(jù)頻率的符號列表，最常出現(xiàn)的符號在左邊，最少出現(xiàn)的符號在右邊。（3）清單分為兩部分，使左邊部分的總頻率和盡可能接近右邊部分的總頻率和。（4）該列表的左半邊分配二進制數(shù)字0，右半邊是分配的數(shù)字1。這意味著，在第一半符號代都是將所有從0開始，第二半的代碼都從1開始。（5）對左、右半部分遞歸應用步驟3和4，細分群體，并添加位的代碼，直到每個符號已成為一個相應的代碼樹的葉。五、器材（設(shè)備、元器件）：計算機、visualc++6.0六、設(shè)計代碼：見附錄七、實驗數(shù)據(jù)及結(jié)果根據(jù)上述實驗程序得到的實驗數(shù)據(jù)及結(jié)果如下：霍夫曼編碼：當進行8信源2進制1重霍夫曼編碼時得到如下結(jié)果結(jié)果與手動計算一致進行15信源5進制1重霍夫曼編碼結(jié)果如下圖所示，計算結(jié)果正確進行8信源2進制2重編碼，結(jié)果如下，結(jié)果正確中間碼子太多，不一一粘貼過來費諾編碼：進行10信源費諾編碼，結(jié)果如下經(jīng)驗算結(jié)果正確香農(nóng)編碼：進行12信源編碼，結(jié)果如下，驗算正確八、結(jié)論完成的3種編碼中霍夫曼編碼編碼效率最高，費諾編碼其次，香農(nóng)編碼效率最低九、總結(jié)及心得體會通過這次課程設(shè)計，我掌握了三種編碼方式的步驟，并能夠利用編程實現(xiàn)編碼，提高了自己的編程水平和對該知識點的掌握程度，特別掌握了typedef關(guān)鍵字的應用，對c++程序與我們所學習的課程之間的相輔相成的關(guān)系更加了解。附錄代碼：霍夫曼編碼#include<stdlib.h>#include<iostream>#include<algorithm>#include<math.h>usingnamespacestd;#defineMAXBIT100#defineMAXVALUE1000#defineMAXLEAF100#defineMAXNODEMAXLEAF*3-1#defineN1000typedefstruct//定義節(jié)點{doubleweight; doubleweightq;intparent; intlup; intzhong; intrup;intlchild;intrchild;charvalue;}HNodeType;typedefstruct//定義編碼類型{intbit[MAXBIT];//存儲01編碼的數(shù)組intstart;//編碼在數(shù)組中開始的位置,從最后往前減小}HCodeType;HNodeTypeHuffNode[MAXNODE];//定義一個足夠大的節(jié)點數(shù)組HCodeTypeHuffCode[MAXLEAF];voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn,intz,intr,intq)//構(gòu)造霍夫曼樹{inti,j,t,e,x1,x2,x3,x4,x5;doublem1,m2,m3,m4,m5;for(i=0;i<(r*z-1)/(r-1);i++)//初始化節(jié)點數(shù)據(jù){HuffNode[i].weight=0; HuffNode[i].weightq=0;HuffNode[i].parent=-1;HuffNode[i].lchild=-1; HuffNode[i].zhong=-1; HuffNode[i].lup=-1; HuffNode[i].rup=-1;HuffNode[i].rchild=-1;} cout<<"輸入各信源符號概率"<<endl;;for(i=0;i<n;i++)//輸入節(jié)點數(shù)據(jù){cin>>HuffNode[i].value>>HuffNode[i].weightq;} if(q==1) { for(i=0;i<n;i++) { HuffNode[i].weight=HuffNode[i].weightq; } for(i=n;i<z;i++) { HuffNode[i].value=i; HuffNode[i].weight=0.0; } } elseif(q==2) { e=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) {HuffNode[e].value=HuffNode[i].value+HuffNode[j].value; HuffNode[e].weight=(HuffNode[i].weightq*HuffNode[j].weightq); e=e+1; if(e==n*n) break; } if(e==n*n) break; } for(e=n*n;e<z;e++) { HuffNode[e].value=e; HuffNode[e].weight=0.0; } } elseif(q==3) { e=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) { for(t=0;t<n;t++) {HuffNode[e].value=HuffNode[i].value+HuffNode[j].value+HuffNode[t].value; HuffNode[e].weight=(HuffNode[i].weightq*HuffNode[j].weightq*HuffNode[t].weightq); e=e+1; if(e==n*n*n) break; } if(e==n*n*n) break; } if(e==n*n*n) break; } for(e=n*n*n;e<z;e++) { HuffNode[e].value=e; HuffNode[e].weight=0.0; } } if(r==2) { for(i=0;i<z-1;i++)//循環(huán)合并n-1次 {m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<z+i;j++)//在已有的節(jié)點里找權(quán)重最小的且沒有parent的節(jié)點{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;}}//最后m1,m2為最新權(quán)重節(jié)點的權(quán)重,x1,x2為其位置HuffNode[x1].parent=z+i;HuffNode[x2].parent=z+i;HuffNode[z+i].weight=m1+m2;HuffNode[z+i].lchild=x1;HuffNode[z+i].rchild=x2; } } elseif(r==3) { for(i=0;i<((z-1)/(r-1));i++)//循環(huán)合并n-1次 { m1=m2=m3=MAXVALUE; x1=x2=x3=0; for(j=0;j<z+i;j++)//在已有的節(jié)點里找權(quán)重最小的且沒有parent的節(jié)點 { if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1) { m3=m2; m2=m1; x3=x2; x2=x1; m1=HuffNode[j].weight; x1=j; } elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1) { m3=m2; x3=x2; m2=HuffNode[j].weight; x2=j; } elseif(HuffNode[j].weight<m3&&HuffNode[j].parent==-1) { m3=HuffNode[j].weight; x3=j; } }//最后m1,m2為最新權(quán)重節(jié)點的權(quán)重,x1,x2為其位置 HuffNode[x1].parent=z+i; HuffNode[x2].parent=z+i; HuffNode[x3].parent=z+i; HuffNode[z+i].weight=m1+m2+m3; HuffNode[z+i].lchild=x1; HuffNode[z+i].zhong=x2; HuffNode[z+i].rchild=x3; } } elseif(r==4) { for(i=0;i<((z-1)/(r-1));i++)//循環(huán)合并n-1次 { m1=m2=m3=m4=MAXVALUE; x1=x2=x3=x4=0; for(j=0;j<z+i;j++)//在已有的節(jié)點里找權(quán)重最小的且沒有parent的節(jié)點 { if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1) { m4=m3; m3=m2; m2=m1; x4=x3; x3=x2; x2=x1; m1=HuffNode[j].weight; x1=j; } elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1) { m4=m3; x4=x3; m3=m2; x3=x2; m2=HuffNode[j].weight; x2=j; } elseif(HuffNode[j].weight<m3&&HuffNode[j].parent==-1) { m4=m3; x4=x3; m3=HuffNode[j].weight; x3=j; } elseif(HuffNode[j].weight<m4&&HuffNode[j].parent==-1) { m4=HuffNode[j].weight; x4=j; } }//最后m1,m2為最新權(quán)重節(jié)點的權(quán)重,x1,x2為其位置 HuffNode[x1].parent=z+i; HuffNode[x2].parent=z+i; HuffNode[x3].parent=z+i; HuffNode[x4].parent=z+i; HuffNode[z+i].weight=m1+m2+m3+m4; HuffNode[z+i].lchild=x1; HuffNode[z+i].lup=x2; HuffNode[z+i].rup=x3; HuffNode[z+i].rchild=x4; } } elseif(r==5) { for(i=0;i<((z-1)/(r-1));i++)//循環(huán)合并n-1次 { m1=m2=m3=m4=m5=MAXVALUE; x1=x2=x3=x4=x5=0; for(j=0;j<z+i;j++)//在已有的節(jié)點里找權(quán)重最小的且沒有parent的節(jié)點 { if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1) { m5=m4; x5=x4; m4=m3; m3=m2; m2=m1; x4=x3; x3=x2; x2=x1; m1=HuffNode[j].weight; x1=j; } elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1) { m5=m4; x5=x4; m4=m3; x4=x3; m3=m2; x3=x2; m2=HuffNode[j].weight; x2=j; } elseif(HuffNode[j].weight<m3&&HuffNode[j].parent==-1) { m5=m4; x5=x4; m4=m3; x4=x3; m3=HuffNode[j].weight; x3=j; } elseif(HuffNode[j].weight<m4&&HuffNode[j].parent==-1) { m5=m4; x5=x4; m4=HuffNode[j].weight; x4=j; } elseif(HuffNode[j].weight<m5&&HuffNode[j].parent==-1) { m5=HuffNode[j].weight; x5=j; } }//最后m1,m2為最新權(quán)重節(jié)點的權(quán)重,x1,x2為其位置 HuffNode[x1].parent=z+i; HuffNode[x2].parent=z+i; HuffNode[x3].parent=z+i; HuffNode[x4].parent=z+i; HuffNode[x5].parent=z+i; HuffNode[z+i].weight=m1+m2+m3+m4+m5; HuffNode[z+i].lchild=x1; HuffNode[z+i].zhong=x3; HuffNode[z+i].lup=x2; HuffNode[z+i].rup=x4; HuffNode[z+i].rchild=x5; } }}voidHuffmanCode(HCodeTypeHuffCode[MAXLEAF],intn,intz,intr)//對生成的樹進行編碼{HCodeTypecd;//臨時結(jié)構(gòu)體inti,j,c,p;for(i=0;i<z;i++){cd.start=(z-1)/(r-1);c=i;p=HuffNode[c].parent;//p為遍歷過程中每個節(jié)點的parent值 while(p!=-1&&r==2)//如果未到根節(jié)點{if(HuffNode[p].lchild==c)//為parent的左節(jié)點則在該處編碼為0cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;//編碼長度加1,start位置減1c=p;p=HuffNode[c].parent;}while(p!=-1&&r==3)//如果未到根節(jié)點{if(HuffNode[p].lchild==c)//為parent的左節(jié)點則在該處編碼為0cd.bit[cd.start]=0;elseif(HuffNode[p].zhong==c)cd.bit[cd.start]=1; else cd.bit[cd.start]=2;cd.start--;//編碼長度加1,start位置減1c=p;p=HuffNode[c].parent;} while(p!=-1&&r==4)//如果未到根節(jié)點{if(HuffNode[p].lchild==c)//為parent的左節(jié)點則在該處編碼為0cd.bit[cd.start]=0;elseif(HuffNode[p].lup==c)cd.bit[cd.start]=1; elseif(HuffNode[p].rup==c)cd.bit[cd.start]=2; else cd.bit[cd.start]=3;cd.start--;//編碼長度加1,start位置減1c=p;p=HuffNode[c].parent;} while(p!=-1&&r==5)//如果未到根節(jié)點{if(HuffNode[p].lchild==c)//為parent的左節(jié)點則在該處編碼為0cd.bit[cd.start]=0; elseif(HuffNode[p].lup==c)cd.bit[cd.start]=1; elseif(HuffNode[p].zhong==c)cd.bit[cd.start]=2; elseif(HuffNode[p].rup==c)cd.bit[cd.start]=3; else cd.bit[cd.start]=4;cd.start--;//編碼長度加1,start位置減1c=p;p=HuffNode[c].parent;}for(j=cd.start+1;j<((z+r-2)/(r-1));j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;//將臨時變量復制到編碼結(jié)構(gòu)體}}intmain(){inti,j,n,r,q,M[N]; doublez,p,H=0.0,K=0.0;cout<<"請輸入信源符號個數(shù)Q"<<endl;cin>>n; cout<<"請輸入R進制編碼"<<endl; cin>>r; cout<<"需要生成N重序列"<<endl; cin>>q; if(q==1) { z=n;} elseif(q==2) { z=n*n;} elseif(q==3) { z=n*n*n;} p=(z-r)/(r-1); while((p-int(p))!=0) { z=z+1; p=(z-r)/(r-1); }HuffmanTree(HuffNode,n,z,r,q);HuffmanCode(HuffCode,n,z,r); if(q==1) { cout<<"霍夫曼編碼如下："<<endl;for(i=0;i<n;i++){ M[i]=0;cout<<HuffNode[i].weight<<"：碼子為：";for(j=HuffCode[i].start+1;j<((z+r-2)/(r-1));j++) {cout<<HuffCode[i].bit[j];M[i]++; } cout<<"：碼長為："<<M[i];cout<<endl;} for(i=0;i<n;i++) {H=-(HuffNode[i].weightq*log(HuffNode[i].weightq)/log(2))+H; }cout<<"信源熵H(X)="<<H<<"(比特/符號)"<<endl; for(i=0;i<n;i++) {K=HuffNode[i].weight*M[i]+K; }cout<<"平均碼長K="<<K<<"(比特/符號)"<<endl; } if(q==2) { cout<<"霍夫曼編碼如下："<<endl;for(i=0;i<n*n;i++){ M[i]=0;cout<<HuffNode[i].weight<<":碼子為:";for(j=HuffCode[i].start+1;j<((z+r-2)/(r-1));j++) {cout<<HuffCode[i].bit[j];M[i]++; } cout<<"：碼長為："<<M[i];cout<<endl;} for(i=0;i<n;i++) {H=-(HuffNode[i].weightq*log(HuffNode[i].weightq)/log(2))+H; }cout<<"信源熵H(X)="<<H<<"(比特/符號)"<<endl; for(i=0;i<n*n;i++) {K=HuffNode[i].weight*M[i]+K; }cout<<"平均碼長K="<<K<<"(比特/符號)"<<endl; } if(q==3) { cout<<"霍夫曼編碼如下："<<endl;for(i=0;i<n*n*n;i++){ M[i]=0;cout<<HuffNode[i].weight<<":馬長為:";for(j=HuffCode[i].start+1;j<((z+r-2)/(r-1));j++) {cout<<HuffCode[i].bit[j];M[i]++; } cout<<"：碼長為："<<M[i];cout<<endl;} for(i=0;i<n;i++) {H=-(HuffNode[i].weightq*log(HuffNode[i].weightq)/log(2))+H; }cout<<"信源熵H(X)="<<H<<"(比特/符號)"<<endl; for(i=0;i<n*n*n;i++) {K=HuffNode[i].weight*M[i]+K; }cout<<"平均碼長K="<<K<<"(比特/符號)"<<endl; } cout<<"編碼效率為"<<((H*q)/(K*log(r)/log(2)))*100<<"%"<<endl; system("pause");return0;}費諾編碼#include<stdlib.h>#include<iostream.h>#include<math.h>#defineN30intpa[N][N];voidfano(floatp[],inta[N][N],intn,intm,intk){floatg=0.0,h=0.0,d,b,c;inti,j,flase;if(n<m){for(i=n;i<=m;i++) {g=p[i]+g; }g=g/2;for(i=n;i<=m;i++){h=h+p[i];if(h>g){d=h-p[i];b=h-g;c=g-d; if(c>b) { for(j=n;j<=i;j++)a[j][k]=0; fano(p,a,n,i,k+1); for(j=i+1;j<=m;j++)a[j][k]=1; fano(p,a,i+1,m,k+1); } else { for(j=n;j<=i-1;j++)a[j][k]=0; fano(p,a,n,i-1,k+1); for(j=i;j<=m;j++)a[j][k]=1; fano(p,a,i,m,k+1); } break;}}}}voidmain(){inti,j,k[N],n,flase=0;floatp[N],m,H=0.0,K=0.0,sum=0.0;cout<<"輸入信源符號個數(shù)"<<endl;cin>>n;cout<<"輸入各信源符號概率"<<endl;for(i=1;i<=n;i++) { cin>>p[i]; }for(i=1;i<=n;i++) {sum=sum+p[i]; }for(i=1;i<=n;i++) { if(p[i]<0.0) {cout<<"inputgailverror!";flase=1;break;} } if(flase==0) { for(i=0;i<=n;i++)for(j=0;j<=n;j++) {pa[i][j]=10;}fano(p,pa,1,n,1); cout<<"信源費諾編碼如下：\n";for(i=1;i<=n;i++) {k[i]=0; cout<<"x"<<i<<"="<<p[i]<<"\t碼字為\t"; for(j=1;j<=n;j++) { if(pa[i][j]!=10) {cout<<pa[i][j];k[i]++;} } cout<<"\t碼長為\t"<<k[i]<<endl; } for(i=1;i<=n;i++) {H=-(p[i]*log(p[i])/log(2))+H; }cout<<"信源熵H(X)="<<H<<"(比特/符號)"<<endl;for(i=1;i<=n;i++) {K=p[i]*k[i]+K; }cout<<"平均碼長K="<<K<<"(比特/符號)"<<endl;cout<<"編碼效率為"<<(H/K)*100<<"%"<<endl; }//if(flase==0) cout<<endl; system("pause");}香農(nóng)編碼#include<stdlib.h>#include<iostream.h>#include<math.h>#include<iomanip.h>#include<stdlib.h>classT{public:T(){}~T();voidCreate();voidCoutpxj();void