最新精编医学专题—算术编码.doc

实现算术编码及其译码实验内容借助C++编程来实现对算术编码的编码及其译码算法的实现二、实验环境计算机VC++6.0三、实验目的进一步熟悉算术编码的原理及其基本的算法；通过编译充分对于算术编码有进一步的了解和掌握；掌握C++语言编程（尤其是数值的进制转换数值与字符串之间的转换等）四、实验原理算术编码算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔消息越长编码表示它的间隔就越小表示这一间隔所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率也决定编码过程中信源符号的间隔而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。给定事件序列的算术编码步骤如下：（1）编码器在开始时将“当前间隔”设置为[01)。（2）对每一事件编码器按步骤（a）和（b）进行处理（a）编码器将“当前间隔”分为子间隔每一个事件一个。（b）一个子间隔的大小与下一个将出现的事件的概率成比例编码器选择子间隔对应于下一个确切发生的事件相对应并使它成为新的“当前间隔”。（3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。编码过程假设信源符号为{ABCD}这些符号的概率分别为{0.10.40.20.3}根据这些概率可把间隔[01]分成4个子间隔：[00.1][0.10.5][0.50.7][0.71]其中[xy]表示半开放间隔即包含x不包含y。上面的信息可综合在表03-04-1中。下表为信源符号概率和初始编码间隔符号ABCD概率0.10.40.20.3初始编码间隔[00.1)[0.10.5)[0.50.7)[0.71]如果二进制消息序列的输入为：CADACDB。编码时首先输入的符号是C找到它的编码范围是[0.50.7]。由于消息中第二个符号A的编码范围是[00.1]因此它的间隔就取[0.50.7]的第一个十分之一作为新间隔[0.50.52]。依此类推编码第3个符号D时取新间隔为[0.5140.52]编码第4个符号A时取新间隔为[0.5140.5146]…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。编码和译码的全过程分别表示在下表。编码过程步骤输入符号编码间隔编码判决1C[0.50.7]符号的间隔范围[0.50.7]2A[0.50.52][0.50.7]间隔的第一个1/103D[0.5140.52][0.50.52]间隔的最后一个1/104A[0.5140.5146][0.5140.52]间隔的第一个1/105C[0.51430.51442][0.5140.5146]间隔的第五个1/10开始二个1/106D[0.5143840.51442][0.51430.51442]间隔的最后3个1/107B[0.51438360.514402][0.5143840.51442]间隔的4个1/10从第1个1/10开始8从[0.51438760.514402]中选择一个数作为输出：0.5143876译码过程步骤间隔译码符号译码判决1[0.50.7]C0.51439在间隔[0.50.7)2[0.50.52]A0.51439在间隔[0.50.7)的第1个1/103[0.5140.52]D0.51439在间隔[0.50.52)的第7个1/104[0.5140.5146]A0.51439在间隔[0.5140.52]的第1个1/105[0.51430.51442]C0.51439在间隔[0.5140.5146]的第5个1/106[0.5143840.51442]D0.51439在间隔[0.51430.51442]的第7个1/107[0.514390.5143948]B0.51439在间隔[0.514390.5143948]的第1个1/108译码的消息：CADACDB五、实验设计：算术编码是一种无损数据压缩方法也是一种熵编码的方法。和其它熵编码方法不同的地方在于其他的熵编码方法通常是把输入的消息分割为符号然后对每个符号进行编码。而算术编码是直接把整个输入的消息编码为一个数一个满足(0.0≤n<1.0)的小数n。所以用两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率也决定编码过程中信源符号的间隔而这些间隔包含在0到1之间。算术编码的算法思想如下：（1）对一组信源符号按照符号的概率从大到小排序将[01)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。（2）检索“输入消息序列”锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔将此