电子科技大学-信息论课程设计(霍夫曼-费诺-香农)

电子科技大学信息与通信工程学院信息论与编码课程设计报告课程设计报告课程设计名称：利用编程语言实现霍夫曼、费诺、香农编码课设要求：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