费诺编码代码说明

信息论与编码上机作业二进制Fano编码姓名：学号：班级：一、题目要求已知：信源符号个数q、信源符号s0,...,sq−1、信源概率分布p0,...,pq−1。算法：(a)将q个信源符号按其概率递减排序：p0≥p1≥...≥pq−1(b)将依次排列的信源符号依概率分为两组，使两组的概率和之差最小。并对各组分别赋予二进制码符号“0”和“1”。(c)将每一组的信源符号进一步再分成两组，使划分后的两个组的概率和之差最小。再次分别赋予各组二进制码符号“0”和“1”。(d)如此重复，直至每组只剩下一个信源符号为止。(e)信源符号si所对应的从左至右的码符号序列即为码字wi。要求：(a)输入：信源符号个数q，信源概率分布p0,...,pq−1。(b)输出：信源符号si与码字wi的对应关系表（编码表）。二、程序运行流程输入信源符号个数费诺编码输入信源符号概率降序排序输出结果是否是否是正整数是否是是否在0至1之间是否是概率和是否为1YYYNNYN三、费诺编码流程图输入信源符号个数num，和对应概率p降序排列是否是通过求和累加确定分组后每组概率和尽可第一组码字加0，第二组码字加1分组点位新分组的第一个编号，其他依次以分组点为断点，重新编号分为两组分组点为新分组的最后一个编号，其他不变输出信源符号，概率和码字信源个数大于2？是否是分组点即第一个编号？是否是分组点即该组倒数第二个？YYYNNN四、运行结果正确结果:错误提示：五、代码及注释1.#includestdio.h2.#includestring.h3.#includestdlib.h4.#includemath.h5.6.intnum1;//费诺编码中使用的信源符号个数7.charcode[50][50];//费诺编码8.intflag1=0;//是否已经编码9.10.voidmain()11.{12.intnum;//信源符号个数13.floatp[50];//信源符号的概率14.floatsum=0.0;//概率之和15.floattemp;//排序所使用的中间变量16.inti,j;17.intflag=0;//是否已经输入完毕概率18.interr1=0,err2=0;//错误类型19.voiderr(inte1,inte2);//错误函数20.voidfano(intm,intn,floatp[50]);//费诺编码21.22.printf(\n---------------费诺编码----------------\n\n输入信源符号个数和概率可以得到费诺编码。\n);23.do24.{25.printf(\n\n请输入信源符号个数(输入0退出)：);26.scanf(%d,&num);27.if(num==0)exit(0);28.while(num0)29.{30.printf(请重新输入一个正整数！\n);31.printf(请输入信源符号个数：);32.scanf(%d,&num);33.if(num==0)exit(0);34.}35.while(flag==0)36.{37.flag=1;38.printf(请输入信源概率：);39.for(i=1;inum+1;i++)//输入概率40.{41.scanf(%f,&p[i]);42.if((p[i]0)||(p[i]1))//检查错误:概率取值0至143.{44.err1=1;45.flag=0;46.}47.elsesum=sum+p[i];48.}49.if(sum!=1.0)//检查错误：概率和等于150.{51.err2=1;52.flag=0;53.sum=0;54.}55.err(err1,err2);//显示错误提示56.err1=0;//清空错误记录57.err2=0;58.}59.for(i=1;inum;i++)//冒泡排序，递减60.for(j=i+1;jnum+1;j++)61.if(p[i]p[j]){62.temp=p[i];63.p[i]=p[j];64.p[j]=temp;65.}66.fano(1,num,p);//调用函数编码67.printf(\n\n费诺编码为：\n\n);68.printf(概率\t\t\t费诺编码\n\n);69.for(i=1;inum+1;i++)//输出结果70.{71.printf(%.3f\t\t\t,p[i]);72.printf(%s\n,code[i]);73.}74.flag=0;//一次编码完成，参数恢复初始状态75.flag1=0;76.sum=0;77.for(i=1;inum;i++)p[i]=0;78.}while(1);79.exit(0);80.}81.82.voiderr(inte1,inte2)//输入错误提示83.{84.if(e1==1)printf(概率必须是0至1之间的数！\n);85.if(e2==1)printf(概率之和必须为1！\n);86.}87.88.voidfano(intm,intn,floatp[50])//m是本组信源符号起始位置，n结束位置，p是每一组里信源符号的概率。89.{90.floatsum=0,s=0,s1,p1[50];//p1是整个待编码的信源符号序列的所有概率。91.inti,j;//j是分组的界限92.flag1++;93.if(flag1==1)//第一次调用此函数时给num1赋值。第一次分组时信源符号序列结束位置就是总的信源符号个数。94.num1=n;95.if(m==n)//迭代停止条件，当每组里只有一个信源符号为止。96.return;97.for(i=1;inum1+1;i++)//给p1赋值98.p1[i]=p[i];99.for(i=m;i=n;i++)//计算总的概率和sum100.sum=sum+p1[i];101.j=m;//j从序列的起始端开始102.do103.{104.s1=s;105.s+=p[j++];106.}107.while(s=sum-s);//比较第一组的概率和与第二组的概率和108.if((sum-2*s1)=(2*s-sum))109.j--;110.for(i=m;ij;i++)111.strcat(code[i],0);//第一组赋值0112.for(i=j;i=n;i++)113.strcat(code[i],1);//第二组赋值1114.fano(m,j-1,p);//将每一组的信源符号进一步再分成两组115.fano(j,n,p);116.}六、实验总结与体会通过这次实验，我彻底明白了费诺编码的原理，并且对其中逻辑也有了更深刻地体会。我也深刻体会到信息论是一门需要很多学科作为基础的学科，编码的思想和二叉树息息相关，在编码过程中使用的迭代算法又要求对C语言很熟悉。总而言之，这次上机作业带给我很多收获，看到了理论转变为能够实际应用的成品也很令我激动。此外，我也会在课余时间去编程实践其他几种编码，一旦入门，就能感受到编码的乐趣。最后，感谢老师的细心教学和指导！