信息论算术编码实验报告

信息论课程实验三算术编码的实验报告 有算术编码的C语言代码和MATLAB源代码

实验三 算术编码

一、实验目的

1．进一步学习C++语言概念和熟悉VC 编程环境。

2．学习算术编码基本流程, 学会调试算术编码程序。

3. 根据给出资料，自学自适应0 阶算术编、解码方法。

二、实验内容与原理

（一）实验原理：

1．算术编码基本原理

这是将编码消息表示成实数0 和1 之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。 算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。首先借助下面一个简单的例子来阐释算术编码的基本原理。考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的信息为 bccb。 在没有开始压缩进程之前，假设对 a b c 三者在信息中的出现概率一无所知（采用的是自适应模型），暂认为三者的出现概率相等各为 1/3，将 0 - 1 区间按照概率的比例分配给三个字符，即 a 从 0.0000 到 0.3333，b 从 0.3333 到 0.6667，c 从 0.6667 到 1.0000。 进行第一个字符 b编码，b 对应的区间 0.3333 -0.6667。这时由于多了字符 b，三个字符的概率分布变成：Pa = 1/4，Pb = 2/4，Pc = 1/4。按照新的概率分布比例划分 0.3333 - 0.6667 这一区间，划分的结果可以用图形表示为： +-- 0.6667 Pc = 1/4 | +-- 0.5834 | | Pb = 2/4 | | | +-- 0.4167 Pa = 1/4 | +-- 0.3333 接着拿到字符 c，现在要关注上一步中得到的 c 的区间 0.5834 -0.6667。新添了 c 以后，三个字符的概率分布变成 Pa = 1/5，Pb = 2/5，Pc = 2/5。用这个概率分布划分区间 0.5834 - 0.6667： +-- 0.6667 | Pc = 2/5 | +-- 0.6334 | Pb = 2/5 || +-- 0.6001 Pa = 1/5 | +-- 0.5834 输入下一个字符 c，三个字符的概率分布为：Pa = 1/6，Pb = 2/6，Pc = 3/6。接着来划分 c 的区间 0.6334 - 0.6667： +-- 0.6667 | | Pc = 3/6 | | +-- 0.6501 | Pb = 2/6 | | +-- 0.6390 Pa = 1/6 | +-- 0.6334 输入最后一个字符 b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b 的区间为 0.6390 -0.6501，最后在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的 0 和小数点，可以输出 1010001111，这就是信息被压缩后的结果，由此完成了一次最简单的算术压缩过程。 如何解压缩呢？那就更简单了。解压缩之前仍然假定三个字符的概率相等。解压缩时面对的是二进制流1010001111，先在前面加上 0 和小数点把它变成小数0.1010001111，也就是十进制 0.64。这时我们发现 0.64 在分布图中落入字符 b 的区间内，立即输出字符 b，并得出三个字符新的概率分布。类似压缩时采用的方法，我们按照新的概率分布划分字符 b 的区间。在新的划分中，我们发现 0.64 落入了字符 c 的区间，我们可以输出字符 c。同理，我们可以继续输出所有的字符，完成全部解压缩过程。

2．小数存储方法

如果信息内容特别丰富，我们要输出的小数将会很长很长，该如何在内存中表示如此长的小数呢？其实，没有任何必要在内存中存储要输出的整个小数。从上面的例子可以知道，在编码的进行中，会不断地得到有关要输出小数的各种信息。具体地讲，当我们将区间限定在 0.6390 -0.6501 之间时，我们已经知道要输出的小数第一位（十进制）一定是 6，那么我们完全可以将 6 从内存中拿掉，接着在区间 0.390 - 0.501 之间继续我们的压缩进程。内存中始终不会有非常长的小数存在。使用二进制时也是一样的，我们会随着压缩的进行不断决定下一个要输出的二进制位是 0 还是 1，然后输出该位并减小内存中小数的长度，具体可以参考E1/E2/E3 放大原理，及它们之间关系的描述。

3．静态模型与自适应模型

（1）静态模型 上面的简单例子采用的是自适应模型，那么如何实现静态模型呢？其实很简单。对信息 bccb 我们统计出其中只有两个字符，概率分布为 Pb = 0.5，Pc = 0.5。在压缩过程中不必再

信息论课程实验三算术编码的实验报告 有算术编码的C语言代码和MATLAB源代码

更新此概率分布，每次对区间的划分都依照此分布即可，对上例也就是每次都平分区间。这样，压缩过程可以简单表示为： 输出区间的下限输出区间的上限压缩前 0.0 1.0 输入 b 0.0 0.5 输入 c 0.25 0.5 输入 c 0.375 0.5 输入 b 0.375 0.4375 最后的输出区间在 0.375 - 0.4375 之间，甚至连一个十进制位都没有确定，也就是说，整个信息根本用不了一个十进制位。

（2）自适应模型 既然使用静态模型可以很好地接近熵值，为什么还要采用自适应模型呢？要知道，静态模型无法适应信息多样性，例如，上面得出的概率分布没法在所有待压缩信息上使用，为了能正确解压缩，我们必须再消耗一定的空间保存静态模型统计出的概率分布，保存模型所用的空间将使我们重新远离熵值。其次，静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编码压缩更加缓慢。另外还有最重要的一点，对较长的信息，静态模型统计出的符号概率是该符号在整个信息中的出现概率，而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率，换句话说，自适应模型得到的概率分布将有利于对信息的压缩（可以说结合上下文的自适应模型的信息熵建立在更高的概率层次上，其总熵值更小），好的基于上下文的自适应模型得到的压缩结果将远远超过静态模型。

（3）自适应模型的阶 通常用“阶”(order)这一术语区分不同的自适应模型。前面例子中采用的是 0 阶自适应模型，该例子中统计的是符号在已输入信息中的出现概率，没有考虑任何上下文信息。如果我将模型变成统计符号在某个特定符号后的出现概率，那么，模型就成为了 1 阶上下文自适应模型。举个例子要对一篇英文文本进行编码，已经编码了 10000 个英文字符，刚刚编码的字符是 t，下一个要编码的字符是 h。我们在前面的编码过程中已经统计出前 10000 个字符中出现了 113 次字母 t，其中有 47 个 t 后面跟着字母 h。我们得出字符 h 在字符 t 后的出现频率是 47/113，我们使用这一频率对字符 h 进行编码，需要 -log2(47/113) = 1.266 bit。对比 0 阶自适应模型，如果前 10000 个字符中 h 的出现次数为 82 次，则字符 h 的概率是 82/10000，我们用此概率对 h 进行编码，需要 -log2(82/10000) = 6.930 bit。考虑上下文因素的优势显而易见。还可以进一步扩大这一优势，例如要编码字符 h 的前两个字符是 gt，而在已经编码的文本中 gt 后面出现 h 的概率是 80%，那么我们只需要 0.322 bit就可以编码输出字符 h。此时，使用的模型叫做 2 阶上下文自适应模型。最理想的情况是采用 3 阶自适应模型。此时，如果结合算术编码，对信息的压缩效果将达到惊人的程度。采用更高阶的模型需要消耗的系统空间和时间至少在目前还无法让人接受，使用算术压缩的应用程序大多数采用 2 阶或 3 阶的自适应模型。

（二）实验内容

1．复习C++代码基本语法（类和虚函数等面向对象数据结构定义）

2．根据实验提供的源代码，学习算术编码实现流程，培养实际动手调试能力和

相应的编程技巧。

三、实验仪器、设备

1． …… 此处隐藏：5845字，全部文档内容请下载后查看。喜欢就下载吧 ……