信息论（课程设计）范文.doc

PAGE PAGE 10 信 息 论 课 程 设 计 报 告 信息与计算科学0701班 吝 芝 2010 年 7月 8日 目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc 1 课题描述 PAGEREF _Toc \h 3 HYPERLINK \l _Toc 2 信源编码的相关介绍 PAGEREF _Toc \h 3 HYPERLINK \l _Toc 3 霍夫曼编码 PAGEREF _Toc \h 3 HYPERLINK \l _Toc 3.1 霍夫曼编码算法 PAGEREF _Toc \h 3 HYPERLINK \l _Toc 3.2 霍夫曼编码特点 PAGEREF _Toc \h 4 HYPERLINK \l _Toc 3.3霍夫曼编码的优、缺点： PAGEREF _Toc \h 5 HYPERLINK \l _Toc 4 霍夫曼编码的C程序实现 PAGEREF _Toc \h 5 HYPERLINK \l _Toc 4.1 程序设计 PAGEREF _Toc \h 5 HYPERLINK \l _Toc 4.2 运行结果 PAGEREF _Toc \h 9 HYPERLINK \l _Toc 5 总结 PAGEREF _Toc \h 10 HYPERLINK \l _Toc 6参考文献 PAGEREF _Toc \h 10 1 课题描述 无失真信源编码—霍夫曼编码。 2 信源编码的相关介绍 将信源通过二元信道传输，把信源符号变换成由0,1符号组成的码符号序列，这个过程就是新源编码。 信源编码分为无失真和限失真，一般称无失真信源编码定理为第一极限定理；限失真信源编码定理称为第三极限定理。 信源编码的主要任务就是减少冗余、提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。 信源编码的基本途径有两个：使序列中的各个符号尽可能的互相独立，及解除相关性；使编码中各个符号出现的概率尽可能地相等，及概率均匀化。 信源编码的基础是信息论中的两个编码定理：无失真编码定理和限失真编码定理，前者是可逆编码的基础。无失真编码或可逆编码只适用于离散信源。对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据失真编码定理在失真受限制的情况下进行限失真编码。 信源编码的作用可归纳为：符号变换，是信源的输出符号与信道的输入符号相匹配；冗余度压缩，使编码效率等于或接近100%。 3 霍夫曼编码 3.1 霍夫曼编码算法 （1）.霍夫曼编码介绍 霍夫曼编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼编码同香农、费诺编码一样是一种通信编码，但是他们是按不同思路设计了各自的编码实现方法。 通信的根本问题是如何将信源输出的信息在接收端的信息精确或近似的复制出来。若接收端要求无失真地精确复制信源输出的消息，此信源编是无失真编码。只有对离散信源可以实现无失真编码，由于连续信源输出信息量可为无限大，故不可能实现无失真编码。霍夫曼编码就是一种无损压缩编码，在通信领域中应用非常广泛，因此我们用C语言的方式为让大家更好的认识和理解霍夫曼编码。 （2）.霍夫曼编码原理 霍夫曼码由霍夫曼树构造，平均码长是霍夫曼树的带权路径长度，由于霍夫曼树是权最小的树，故其压缩效果最好。霍夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的。 霍夫曼码是用概率匹配方法进行信源编码。有两个明显特点：一是保证了概率大的符号对应于短码，概率小的对应于长码，充分利用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码。 霍夫曼变长码的效率很高，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也易实