Fano编码的C语言实现.doc

信息论课程设计（费诺编码）班级学号姓名目录1课题描述22 信源编码的相关介绍33 费诺编码33.1 费诺编码算法33.2 费诺编码特点44 费诺编码的C程序实现44.1 程序设计44.2 运行结果9总 结9参考文献91课题描述本次课程设计主要是对这学期所学内容的检验。课程要求在vc+编译环境下编写费诺编码，输出各符号的编码，并求信源熵，平均码长以及编码效率，最后根据所给的简单二进制代码，译成信源输出符号。2 信源编码的相关介绍信息论奠基人香农，他给出了香农三大定理：无失真的信源编码定理，信道编码定理，限失真的信源编码定理。信源编码的研究落后于信道编码。无失真的信源编码定理由香农在1948年给出，并有相应的香农编码。1952年，费诺和哈弗曼分别提出了自己的编码方法，并被证明是最佳编码。至今，信息论还在快速发展中。信源编码是为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对信源输出的符号序列所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。信源编码有定长编码和变长编码。最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：香农编码，费诺编码，Huffman编码、算术编码、游程编码。现代一般采用变长编码，因为在要求无失真的传输时，定长编码要达到很长才能做到，而变长编码就有这样的优势，所需编码长度很短。通信系统模型：信源-信源编码-信道编码-信道传输+噪声-信道解码-信源解码-信宿。一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：使序列中的各个符号尽可能地互相独立；使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称为概率均匀化。3 费诺编码 费诺编码在1952年由费诺提出，它是一种即时码，但不一定是最佳编码。3.1 费诺编码算法 将信源消息符号按其出现的概率大小依次排列排列：。在程序中由sort()函数处理，此函数是一个冒泡排序法。若想改进，可用其它的排序算法。将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并且对各组赋予一个二进制码元“0”和“1”。将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似相同，并且对各组赋予一个二进制符号“0”和“1”。以上两部分在程序中，由code()函数及group()函数处理。如此重复，直到每个组只剩下一个信源符号为止。在程序中本部分采用递归思想，group1()。信源符号所对应的码字即为费诺编码。3.2 费诺编码特点费诺编码在构造码树时，是从树根开始到终端节点结束，这与哈夫曼编码相反（本程序并未采用树的结构来做费诺编码）。由于赋码元时的任意性，因此费诺编码编出的码字不惟一。费诺编码虽属于概率匹配范畴，但并未严格遵守匹配规则，即不全是按“概率大码长小、概率小码长大”来决定码长，有时会出现概率小码长反而小的情况。4 费诺编码的C程序实现 本程序由编码和译码两部分组成。4.1 程序设计 #include#include#include#define Bmax 10 /最长码长度#define Smax 20 /数组最大长度struct Bitchar bBmax;int last;typedef struct symbolchar c;float probability;struct Bit bit;sbl;sbl sSmax;void sort(int n)/排序float t;char a;int i,j;for(i=1;in;i+)for(j=0;jn-i;j+)if(babilitysj+1.probability)t=bability;a=sj.c;bability=sj+1.probability;sj.c=sj+1.c;sj+1.probability=t; sj+1.c=a;void code(int low,int mid,int high)/编码int i;for(i=low;ihigh;i+)if(imid)si.bit.bsi.bit.last=0; si.bit.last+;elsesi.bit.bsi.bit.last=1;si.bit.last+;void group1(int low,int mid,int high)/分组 float d,dmin;d=0;int i;if(high=low+1)return;for(i=low;imid;i+)d+=bability;dmin=d-2*bability;for(i=low+1;ihigh;i+)d=fabs(dmin-2*bability);if(ddmin)dmin=d;elsebreak;mid=i; code(low,mid,high);group1(low,mid,mid); group1(mid,high,high); void group(int n)int i,pmid,plow,phigh;pmid=phigh=n;plow=0;for(i=0;in;i+)si.bit.last=0; group1(plow,pmid,phigh);void input(int n)int i;char c;printf(请输入符号及符号概率n); c=getchar();for(i=0;in;i+)scanf(%c,&si.c);scanf(%f,&bability);c=getchar();void output(int n)/输出编码int i,j;printf(请输出符号,符号概率及编码n);for(i=0;in;i+)printf(%ct%ft,si.c,bability);for(j=0;jsi.bit.last;j+)printf(%c,si.bit.bj);printf(n);void qita(int n)int i,j;float sum,average,effiency;sum=average=0;for(i=0;in;i+)sum-=bability*log10(bability)/log10(2);/信源熵average+=bability*si.bit.last;/平均码长 effiency=sum/average;/编码效率printf(信源熵:%fn平均码长:%fn编码效率:%fn,sum,average,effiency);void decode(int n,char a100)/译码int i=0,j;char s2100;s20=0;while(istrlen(a)char temp2;temp0=ai;temp1=0;strcat(s2,temp);for(j=0;jn;j+)if(strcmp(s2,sj.bit.b)=0)printf(%c,sj.c);s20=0;break;i+;printf(n);void main()int n;char a100;printf(请注意当显示器再次输出“请输入符号个数时”说明输入的n值有误!n);doprintf(请输入符号个数0nSmax|n=0);input(n);sort(n);group(n);output(n);qita(n);printf(请输入要译的二进制代码n);scanf(%s,a);printf(输出译码结果n);decode(n,a);4.2 运行结果总 结本次课程设计使我更深刻理解费诺编码并对我的编程基础再次检验。本次实验代码已完成，但还有许多地方可以改进。如可以加一个函数处理输入一串字符，算出它们的概率并编码；本文采用的冒泡排序仅是最基本的排序方法，可以用更好的；本文对分组编码部分运用了递归思想，虽然本方法简单明了，但运行方面不如非递归；本文采