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

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

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

p(un)⑵

確定碼長Ki

(整數)

：

Ki=[log1⑶

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

pi⑷

將累加概率Pi變換成二進制數。⑸

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

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

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

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