Fano编码的C语言实现

《Fano编码的C语言实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息论课程设计（费诺编码）班级学号姓名目录1课题描述22信源编码的相关介绍33费诺编码33.1费诺编码算法33.2费诺编码特点44费诺编码的C程序实现44.1程序设计44.2运行结果9总结9参考文献91课题描述本次课程设计主要是对这学期所学内容的检验。课程要求在vc++编译环境下编写费诺编码，输出各符号的编码，并求信源熵，平均码长以及编码效率，最后根据所给的简单二进制代码，译成信源输出符号。2信源编码的相关介绍信息论奠基人——香农，他给出了香农三大定理：无失真的信源编码定理，信道编码定理，限失真的信源编码定理。信源编码的研究落后于信道编码。无失真的信源编码定理由香农在1948年给

2、出，并有相应的香农编码。1952年，费诺和哈弗曼分别提出了自己的编码方法，并被证明是最佳编码。至今，信息论还在快速发展中。信源编码是为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对信源输出的符号序列所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。信源编码有定长编码和变长编码。最原始的信源

3、编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：香农编码，费诺编码，Huffman编码、算术编码、游程编码。现代一般采用变长编码，因为在要求无失真的传输时，定长编码要达到很长才能做到，而变长编码就有这样的优势，所需编码长度很短。通信系统模型：[信源]->[信源编码]->[信道编码]->[信道传输+噪声]->[信道解码]->[信源解码]->[信宿]。一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：①使序列中的各个符号尽可能地互相独立；②使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称

4、为概率均匀化。3费诺编码费诺编码在1952年由费诺提出，它是一种即时码，但不一定是最佳编码。3.1费诺编码算法将信源消息符号按其出现的概率大小依次排列排列：。在程序中由sort()函数处理，此函数是一个冒泡排序法。若想改进，可用其它的排序算法。将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并且对各组赋予一个二进制码元“0”和“1”。将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似相同，并且对各组赋予一个二进制符号“0”和“1”。以上两部分在程序中，由code()函数及group()函数处理。如此重复，直到每个组只剩下一个信源符号为止。在程序中本

5、部分采用递归思想，group1()。信源符号所对应的码字即为费诺编码。3.2费诺编码特点费诺编码在构造码树时，是从树根开始到终端节点结束，这与哈夫曼编码相反（本程序并未采用树的结构来做费诺编码）。由于赋码元时的任意性，因此费诺编码编出的码字不惟一。费诺编码虽属于概率匹配范畴，但并未严格遵守匹配规则，即不全是按“概率大码长小、概率小码长大”来决定码长，有时会出现概率小码长反而小的情况。4费诺编码的C程序实现本程序由编码和译码两部分组成。4.1程序设计#include#include#include#defineBmax10//最

6、长码长度#defineSmax20//数组最大长度structBit{charb[Bmax];intlast;};typedefstructsymbol{charc;floatprobability;structBitbit;}sbl;sbls[Smax];voidsort(intn)//排序{floatt;chara;inti,j;for(i=1;i

7、.probability;s[j].c=s[j+1].c;s[j+1].probability=t;s[j+1].c=a;}}voidcode(intlow,intmid,inthigh)//编码{inti;for(i=low;i