费诺编码论文

多媒体技术之费诺编码

通信

多媒体技术，即是计算机交互式综合处理多媒体信息----文本、图形、图像和声音，使多种信息建立逻辑连接，集成为一个系统并具有交互性。简言之，多媒体技术就是具有集成性、实时性和交互性的计算机综合处理声文图信息的技术。多媒体在我国也有自己的定义，一般认为多媒体技术指的就是能对多种载体(媒介) 上的信息和多种存储体(媒介) 上的信息进行处理的技术。近几年来，计算机多媒体技术快速发展并走向成熟，在微机上就可以实现许多传统模拟的数字化。使得视频、音频、图像、动画和图形文字一起在计算机中进行处理，因此，计算机所处理和表达的信息量急剧增加，从而为多媒体计算机在计算机辅助课堂教学中的应用提供了可能。

早期的数据压缩来自于人们对概率的了解。当对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，平均编码长度就能缩短不少。印象中的著名的Morse 电码就是一个范例。信息论之父C.E.Shannon 曾指出，任何信息都存在冗余，冗余大小与信息中每个符号的出现概率（不确定性）有关。他所提出的无失真信源编码定理奠定了数据压缩的理论基础。数据压缩的目的就是要消除信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。信息论是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。从DVD 到个人电脑，从卫星通信到文件，在我们今天的生活中，信息几乎在每个领域都扮演着重要角色。工程师克劳德·香农于1948年奠定了信息论的基础，他指出了通信的极限。基于这一理论产生了数据压缩技术、纠错技术等各种应用技术，这些技术提高了数据传输和存储的效率。信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源－信道隔离定理相互联系。当然，信息论的重大应用远不止于此。DNA 是一种信息存储物质，正是信息论帮助人们解开了生物基因组密码之谜。简单地说信息论包含了生命、宇宙乃至一切。

信息论对现代社会的影响是多方面的。首先, 在理论研究方面, 信息论所处的地位已远远超出了香农当年所界定的“通信的数学理论”的范畴, 得到了不断的扩充和发展, 出现了语义信息、语法信息与语用信息等研究与信息的意义有关的学科, 以及面向智能研究的全信息理论 。如今, 信息已成为与物质、能量并列的宇宙中的三个基本要素, 世间万物的发展变化可归结为物质、能量和信息的传递和转化过程。另一方面, 在科学和技术高度发展的今天, 信息的概念也被渗透到许多不同的学科和领域, 深入到了社会生活的各个方面, 成为可与相对论和量子力学并驾齐驱的新一代边缘交叉学科的重要组成部分。特别是以信息论、控制论和系统论为代表的“老三论”以及以普里高津(I.Prigogine)的耗散结构理论, 哈肯(H.Haken)的协同学和托姆(R.Thom)的突变论或艾根(M.Eigen)的超循环理论为代表的“新三论”的出现, 标志着一代新的边缘交叉学科的兴起。它们的形成和发展对现代科学的研究具有重要的方法论上的指导意义。

费诺编码是一种信源编码. 信源编码分为无失真信源编码和限失真信源编码。一般称无失真信源编码为第一机械定理；限失真信源编码定理称为第三极限定理。

由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个：使编码中各个符号出现的概率尽可能地相等，即概率均匀化。信源编码的基础是信息论中的两个编码定理：无失真编码定理和限失真编码定理。其中无失真编码定理是可逆编码的基础。可逆是指当信源符号转换成代码后，可从代码无失真地恢复信源符号。当已知信源符号的概率特性时，可计算它的符号熵，这表示每个信源符号所载有的信息量。编码定理不但证明了必定存在一种编码方法，可使代码的平均长度可任意接近但不低于符号熵，而且还阐明达到这目标的途径，就是使概率与码长匹配。无失真编码或可逆编码只适用于离散信源。对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据率失真编码定理在失真受限制的情况下进行限失真编码。信源编码定理出现后，编码方法就趋于合理化。

凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。能获得最佳码的编码方法主要有：香农码（Shannon) 、费诺(Fano)、哈夫曼(Huffman)编码等。费诺编码算法

1．将信源消息符号按其出现的概率大小依次排列：P1>=P2>=„>=Pn。

2．依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。

3．使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。

4．如此重复，直至每个组只剩下一个信源符号为止。

5．信源符号所对应的码字即为费诺码。

费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高，但它属于概率匹配编码它不是最佳的编码方法[。

费诺编码方法属于概率匹配编码，具有如下特点：

1、概率大，则分解次数小；概率小则分解次数多。这符合最佳码原则。

2、码字集合是唯一的。

3、分解完了，码字出来了，码长也有了, 即先有码字后有码长。

因此，费诺编码方法又称为子集分解法

费诺编码也是一种常见的信源编码方法。信源符号以概率递减的次序排列进来, 将排列好的信源符号划分为两大组, 使第组的概率和近于相同, 并各赋于一个二元码符号”0”和”1”. 然后, 将每一大组的信源符号再分成两组, 使同一组的两个小组的概率和近于相同, 并又分别赋予一个二元码符号. 依次下去, 直至每一个小组只剩下一个信源符号为止. 这样, 信源符号所对应的码符号序列则为编得的码字。本文将通过采用递归的思想进行费诺编码，求得了每个字符的二进制码字。并且对编码后的平均码长，以及编码的传输效率进行了求解。符合费诺编码的要求，得到了预期的编码结果。