算术编码
实现算术编码及其译码
一、实验内容
借助C++编程来实现对算术编码的编码及其译码算法的实现
二、实验环境
1.计算机
2.VC++6.0
三、实验目的
1.进一步熟悉算术编码的原理，及其基本的算法；
2.通过编译，充分对于算术编码有进一步的了解和掌握；
3.掌握C++语言编程（尤其是数值的进制转换，数值与字符串之间的转换
等）
四、实验原理
算术编码
算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。
算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。
给定事件序列的算术编码步骤如下：
（1）编码器在开始时将“当前间隔”设置为[0，1)。
（2）对每一事件，编码器按步骤（a）和（b）进行处理
（a）编码器将“当前间隔”分为子间隔，每一个事件一个。
（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间
隔”。
（3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。
编码过程
假设信源符号为{A， B， C， D}，这些符号的概率分别为{ 0.1， 0.4， 0.2，0.3 }，根据这些概率可把间隔[0， 1]分成4个子间隔：[0， 0.1]， [0.1， 0.5]，
[0.5， 0.7]， [0.7， 1]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息可综合在表03-04-1中。
下表为信源符号，概率和初始编码间隔
如果二进制消息序列的输入为：C A D A C D B。编码时首先输入的符号是C，找到它的编码范围是[0.5，0.7]。由于消息中第二个符号A的编码范围是[0，0.1]，因此它的间隔就取[0.5， 0.7]的第一个十分之一作为新间隔[0.5，0.52]。依此类推，编码第3个符号D时取新间隔为[0.514， 0.52]，编码第4个符号A 时，取新间隔为[0.514， 0.5146]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。
编码和译码的全过程分别表示在下表。
编码过程
译码过程
五、实验设计：
算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码。而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤ n < 1.0)的小数n。所以用两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。
算术编码的算法思想如下：
（1）对一组信源符号按照符号的概率从大到小排序，将[0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。
（2）检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。
（3）仍然按照信源符号的概率序列在当前分析区间划分比例间隔。然后重复第
二步。直到“输入消息序列”检索完毕为止。
（4）最后的编码输出数就是编码好的数据。
六、实验程序：
#include
#include"math.h"
//定义所需要用到的变量及数组
char S[100], A[10];
float P[10],f[10],gFs;
//编码程序
void bianma(int a,int h)
{
int i,j;
float fr;
float ps=1;
float Fs=0;
float Sp[100],b[100],F[100];
//以待编码的个数和字符个数为循环周期，将待编码的字符所对应的概率存入到Fs中for(i=0;i { for(j=0;j { if(S[i]==A[j]) { Sp[i]=P[j]; fr=f[j];//将划分好的[0,1)区间的对应点赋值给fr } } Fs=Fs+ps*fr;//从选择的子区间中继续进行下一轮的分割。不断的进行这个过程， 直到所有符号编码完毕。 ps*=Sp[i]; //求Ps } cout<<"Fs="< gFs=Fs; float l=log(1/ps)/log(2);//计算算术编码的码字长度l if(l>(int)l)l=(int)l+1; else l=int(l); //将Fs转换成二进制的形式 int d[20]; int m=0; while(l>m) { Fs=2*Fs; if(Fs>1) { Fs=Fs-1; d[m]=1; } else if(Fs<1)d[m]=0; else {d[m]=1;break;} m++; } int z=m;//解决有关算术编码的进位问题,给二进制数加1 if(m>=l) { while(1) { d[m-1]=(d[m-1]+1)%2;//最后位加1 if(d[m-1]==1)break; else m--; } } cout<<"s="; for(int e=0;e cout< cout< } //解码程序 void jiema(int a,int h) { int i,j; float Ft,Pt; float Fs=0,Ps=1; for(i=0;i for(int j=a-1;j>-1;j--) { Ft=Fs; Pt=Ps; Ft+=Pt*f[j];//对进行逆编码 Pt*=P[j]; if(gFs>=Ft)//对其进行判断，并且将值存入到数组A中 { Fs=Ft; Ps=Pt; cout< break; } } } cout< } void main() { cout<<"输入所要编码的符号的个数，并按回车跳转："< int a,i,h=0; cin>>a; cout<<"请输入符号及其相对应的概率值，并按回车跳转："< for(i=0;i { char x; float y; cin>>x; A[i]=x;//将字符依次存入数组A中 cin>>y; P[i]=y;//将字符所对应的概率依次存入到数组P中 } for(i=1;i { f[0]=0; f[i]=f[i-1]+P[i-1];//将要编码的数据映射到一个位于[0,1)的实数区间中} cout<<"请输入所要编码的符号序列，并以*结尾："< while(1)//这个while语句的作用是将要编码的字符存入到数组S中 { char ss; cin>>ss; if(ss=='*')break;//在以“*”为结尾的时候结束存储 S[h++]=ss; } cout<<"输入的字符经过算术编码之后为："< bianma(a,h); cout<<"由上述所对应的解码为："< jiema(a,h); } 七、实验结果： 八、结果分析 首先根据显示输入所有的字符的个数，以及字符和其概率，经过对“CADACDB”编码之后，我们可以在屏幕上看到最终的编码结果为0.514388，与上式的分析结 果相同，进过转换之后产生的二进制代码为10000011101011110。同样也显示了 译码结果和输入的相同，即同为“CADACDB”。证明实验编码是可行的。 九、心得体会 这是第二次的信息论实验，借助上周编写的哈夫曼编码的知识和经验，以及在网络上的相关查阅，我也成功的做好了算术编码及其译码的实验，通过这个实验，让我对算术编码有了更进一步的了解，以及对C++的运用，因为我们之前都是使用C语言进行编写程序，对于知识有了新的吸收。受益匪浅啊。 实现算术编码及其译码 一、实验内容 借助C++编程来实现对算术编码的编码及其译码算法的实现 二、实验环境 1.计算机 2.VC++6.0 三、实验目的 1.进一步熟悉算术编码的原理，及其基本的算法； 2.通过编译，充分对于算术编码有进一步的了解和掌握； 3.掌握C++语言编程（尤其是数值的进制转换，数值与字符串之间的转换 等） 四、实验原理 算术编码 算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。 算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。 给定事件序列的算术编码步骤如下： （1）编码器在开始时将“当前间隔”设置为[0，1)。 （2）对每一事件，编码器按步骤（a）和（b）进行处理 （a）编码器将“当前间隔”分为子间隔，每一个事件一个。 （b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间 隔”。 （3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。 编码过程 假设信源符号为{A， B， C， D}，这些符号的概率分别为{ 0.1， 0.4， 0.2，0.3 }，根据这些概率可把间隔[0， 1]分成4个子间隔：[0， 0.1]， [0.1， 0.5]， [0.5， 0.7]， [0.7， 1]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息可综合在表03-04-1中。 下表为信源符号，概率和初始编码间隔 如果二进制消息序列的输入为：C A D A C D B。编码时首先输入的符号是C，找到它的编码范围是[0.5，0.7]。由于消息中第二个符号A的编码范围是[0，0.1]，因此它的间隔就取[0.5， 0.7]的第一个十分之一作为新间隔[0.5，0.52]。依此类推，编码第3个符号D时取新间隔为[0.514， 0.52]，编码第4个符号A 时，取新间隔为[0.514， 0.5146]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。 编码和译码的全过程分别表示在下表。 编码过程 算术编码工作原理 在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。 例: 对一个简单的信号源进行观察，得到的统计模型如下： ?60% 的机会出现符号中性 ?20% 的机会出现符号阳性 ?10% 的机会出现符号阴性 ?10% 的机会出现符号数据结束符. (出现这个符号的意思是该信号源'内部中止'，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了。) 算术编码可以处理的例子不止是这种只有四种符号的情况，更复杂的情况也可以处理，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q 或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应 更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。 一个简单的例子以下用一个符号串行怎样被编码来作一个例子：假如有一个以A、B、C三个出现机会均等的符号组成的串行。若以简单的分组编码会十分浪费地用2 bits 来表示一个符号：其中一个符号是可以不用传的(下面可以见到符号B正是如此)。为此，这个串行可以三进制的0和2之间的有理数表示，而且每位数表示一个符号。例如，“ABBCAB”这个串行可以变成0.011201(base3)(即0为A, 1为B, 2为C)。用一个定点二进制数字去对这个数编码使之在恢复符号表示时有足够的精度，譬如 0.001011001(base2) –只用了9个bit，比起简单的分组编码少(1 – 9/12)x100% = 25%。这对于长串行是可行的因为有高效的、适当的算法去精确地转换任意进制的数字。 编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据： ?下一个要编码的符号 ?当前的区间(在编第一个符号之前，这个区间是[0,1), 但是之后每次编码区间都会变化) ?模型中在这一步可能出现的各个符号的概率分布(像前面提到的一样，高阶或者自适应的模型中，每一步的概率并不必须一样) 编码其将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。 算术编码与解码 1、编码过程 算术编码方法是将被编码的一则消息或符号串（序列）表示成0和1之间的一个间隔（Interval），即对一串符号直接编码成[0,1]区间上的一个浮点小数。符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。信源中的符号序列仍然要根据某种模式生成概率的大小来减少间隔。可能出现的符号概率要比不太可能出现的符号减少范围小，因此，只正加较少的比特位。 在传输任何符号串之前，0符号串的完整范围设为[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。用图形表示就是： +-- 1.0000 | Pc = 1/3 | | +-- 0.6667 | Pb = 1/3 | | +-- 0.3333 | Pa = 1/3 | | +-- 0.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，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程。我的代码： publicstaticvoidBianMa(String info,StringDeal sd){ int i = 0, j = 0; //定义上下限 double low = 0, high = 1; double count = sd.getCount(); //定义初始各字符频率 double[] zifu = new double[(int)(count)]; for(i = 0;i < zifu.length;i++){ zifu[i] = 1; 简单短序列的算术编码的MATLAB实现 正确实现的算术编码算法压缩能力Shannond定理描述的理论极限，是目前已知的压缩能力最强的无损压缩算法。 不过，由于算术编码算法的实现比较复杂，使用它作为默认压缩算法的应用程序还相当少。在Unix平台上非常流行的bzip2(这个工具有命令行模式的Windows版本)使用的就是经过修改的算术编码算法。 目前为止还没有使用算术编码作为默认压缩算法的Windows应用程序，WinRAR和WinIMP能够支持bzip2的解压。除此之外，在最新的JPEG标准中也用到了经过修改的算术编码压缩算法，但JPEG所用的那种算法受专利保护，因此使用时必须获得授权。 在之后的文章会很好的研究这个算法的实现： 现在给出一个简单的实例： 运行过程如下： %I=imread('001.bmp') %imshow(I); clear I=[3 3 1 1 3 3 1 2;2 3 3 1 3 2 3 2;1 2 3 3 3 3 1 2]; %I=[1 1 1 1 0 0 1 0 1 1 1 0]; [m,n]=size(I); % 第一列为灰度值,第二列为个数,第三列为概率百分数，应该也可以用imhist table = tabulate(I(); % 注意的是，tabulate要求I的元素必须为非负整数 % 否则，以采用如下方法求解 % 如[1 2 3；1 2 2]，则统计出结果1是2个，2是3个，3是1个 % sortM=sort(M(); % uniqueM=([diff(sortM);1]>0); % count = [sortM(uniqueM) diff(find([1;uniqueM]))] % 即color,p如下所示 color = table(:,1)'; p = table(:,3)'/100; % 计算上下限 csump = cumsum(table(:,3)'); allLow =[0,csump(1:end-1)/100]; allHigh = csump/100; numberlow = 0; numberhigh = 1; for k = 1:m for kk = 1:n data = I(k,kk); low = allLow(data==color); high = allHigh(data==color); range = numberhigh-numberlow; tmp = numberlow; numberlow = tmp+range*low; numberhigh = tmp+range*high; end 转算术编码算法的分析与实现 [转]算术编码算法的分析与实现2011-06-09 14：20本论文题目：算术编码算法的分析与实现，作者：叶叶，于2010年10月16日在编程论坛上发表。页面地址：。本论文全文及相关配套程序可以在上述页面中下载。请尊重他人劳动成果，转载或引用时请注明出处。 目录 1前言2 2理论2 2.1编码2 2.2解码3 3改进4 3.1整数运算4 3.2正规化5 4实现8 4.1编码8 4.2解码10 4.3统计模型11 5分析12 6结束语12 参考文献13 附录13 算术编码算法的分析与实现 作者：叶叶(网名：yeye55) 摘要：分析了算术编码的理论基础，着重介绍WNC算法的实现方式。详细讨论了算术编码原理、正规化操作、WNC算法代码实现等技术。给出了一个切实可行的应用程序。 关键词：算术编码；正规化；Delphi 中图分类号：TP301.6 1前言 早在1948年C.E.Shannon提出信息论[1]的时候，就提出了算术编码的思想。但是经过多年的研究，许多学者认为算术编码是无法实现的。算术编码要求进行无限精度的实数运算，这在仅能进行有限精度运算的计算机系统上是无法进行的。随着研究的深入，终于在1987年Ian H.Witten、Radford M.Neal和John G.Cleary发表了一篇论文[2]，提出了一种基于整数运算的算术编码实现算法。该算法后来被命名为CACM87，并应用于ITU-T的H.236视频编码标准。也有学者根据作者姓名将该算法称之为WNC算法。WNC算法是一个实用性算法，它可以应用在许多方面。在Witten等人的论文[2]中给出了一个使用C语言编写的WNC算法实现程序的源代码(以下简称"WNC源代码")。在许多时候，WNC源代码已经作为算术编码的范本程序 实验1 算术编码算法的Matlab实现 实验学时：2 实验类型：（演示、验证、综合、√设计、研究） 实验要求：（√必修、选修） 一、实验目的 掌握算数编码原理。 二、实验内容 利用Matlab编写程序实现算数编码，包括： 1、对文件符号进行概率统计，生成编码表； 2、对文件进行压缩编码； 3、（选做）对文件进行解压缩，比较原始数据和解压后的数据之间是否有损耗。 三、实验仪器 1、计算机一台； 2、Matlab仿真软件。 四、实验原理 算术编码的编码对象是一则消息或一个字符序列，其编码思路是将该消息或字符序列表示成0和1之间的一个间隔(Interval)上的一个浮点小数。 在进行算术编码之前，需要对字符序列中每个字符的出现概率进行统计，根据各字符出现概率的大小，将每个字符映射到[0,1]区间上的某个子区间中。然后，再利用递归算法，将整个字符序列映射到[0,1]区间上的某个Interval中。在进行编码时，只需从该Interval中任选一个小数，将其转化为二进制数。 符号序列越长，编码表示它的Interval的间隔就越小，表示这一间隔所需的二进制位数就越多，编码输出的码字就越长。 五、实验步骤 对字符序列“state_tree”进行算术编码的步骤如下： 1、对文件符号“state_tree”进行概率统计，生成编码表； 2、初始化时，被分割范围的初始值是[0,1]，即被分割范围的下限为low=0，上限为high =1，该范围的长度为range_length=high-low =1。 3、对消息的第一字符s进行编码，如果s的概率范围的下限为Low=，上限为High=， 则下一个被分割范围的下限和上限分别为： next_low=low+range_length×Low=0+1×=； next_ high=low+range _length×High =0+1×=； low=next_low=，high=next_high=； range _length = high-low =； s将分割范围从[0,1]变成了[,]。 4、重复上述步骤，依次对字符t,a,t,e,_t,r,e,e进行编码； 5、编码结束，将最终得到的编码结果从一个十进制小数值转化为二进制数，从而得到 最终的编码码字。 算术编码算法的解码过程步骤如下： 1、将最终的算数编码结果（十进制小数值）与之前得到的编码表进行对比，确 定与该数值对应的概率范围，从而解码出字符序列的第一个字母。 2、利用公式(number-range_low)/range=>number_next进行解码，直到整个字符 序列解码完毕。其中number为字符序列的当前编码，number_next为下一步解码时的字符序列编码。 六、实验报告 1、对文件符号“state_tree”进行概率统计，得出编码表； 编程实现算术编码算法 中国地质大学计算机学院信息安全专业 信息论实验报告 实验三算术编码 一、实验内容 编程实现算术编码算法 二、实验环境 1.计算机 2.Windows 2000或以上 3.DEVC++ 三、实验目的 1.进一步熟悉算术编码算法； 2.掌握C语言编程（尤其是数值的进制转换，数值与字符串之间的转换等） 四、实验要求 1.提前预习实验，认真阅读实验原理。 2.认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老师的管理。 3.认真填写实验报告。 五、实验原理 算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。 1.算法流程 （1）输入信源符号个数，信源概率分布，还有需要编码的符号序列，（2）根据概率可以算出初始编码间隔， High——当前编码的上限， Low——当前编码的下限， high——中间变量，用来计算下一个编码符号的当前间隔的上限，low——中间变量，用来计算下一个编码符号的当前间隔的下限，d——当前间隔之间的距离。 （3）扫描需编码的符号序列，确定编码空间 第1个编码符号的当前间隔为其初始的编码间隔， 第i个编码符号的当前间隔为第i-1个编码后的[Low，High），第i+1个编码符号的当前间隔算法如下：high=Low+d*第i+1个初始编码符号对应的上限，low=Low+d*第i+1个编码符号对应的下限，然后High=high，Low=low，d=d*第i 个编码符号的概率。 六、参考书 1.《信息论——基础理论及应用》傅祖芸，电子工业出版社 七、源代码 #include 数字图像处理课程设计 题目：数字图像处理及算术编码 （或D C T压缩编码）仿真实现学生姓名： 学院：信息工程学院 系别：电子信息工程系 专业：电子信息工程 班级：电子09-2班 指导教师：韩建峰辛莉 2012 年 12月 17 日 数字图像处理课程设计 1、课程设计目的 通过本课程设计使学生了解数字图像的基本概念，掌握数字图像处理的基本内容，如图像点运算、几何变换、增强处理、图像复原、边缘检测以及图像压缩等的基本原理和Matlab实现方法。 通过本次课程设计，让学生掌握如何学习一门语言，如何进行资料查阅搜集，如何自己解决问题等方法，养成良好的学习习惯。扩展理论知识，培养学生的综合设计能力。 2、课程设计内容 2.1 图像处理基本功能 1）数字图像的变换：普通傅里叶变换(ft)与逆变换（ift）、快速傅里叶变 换（fft）与逆变换(ifft)、离散余弦变换（DCT），小波变换。 2) 数字图像直方图的统计及绘制等； 2.2 图像处理综合功能 1）图像平滑算法程序设计： 2）DCT压缩（保留不同系数），要求显示原图像、压缩后图像的文件大小、压缩比或算术编码压缩 3、课程设计的一般步骤 1）选题与搜集资料：选择课题，进行系统调查，搜集资料。 2）分析与设计：根据搜集的资料，进行功能分析，并对系统功能与模块划分等设计。 3）程序设计：运用掌握的语言，编写程序，实现所设计的功能。 4）调试与测试：自行调试程序，同学之间交叉测试程序，并记录测试情况。 5）验收与评分：指导教师对每个成员开发的程序进行综合验收，结合设计报告，根据课程设计成绩的评定方法，评出成绩。 4、要求 4.1总体要求 1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准 备工作。尤其是对编程软件的使用有基本的认识。 2、既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题， 独立思考，努力钻研，勤于实践，勇于创新。 3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容， 否则成绩以不及格计。 4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态 度，必须按时、按质、按量完成课程设计。 4.2 课程设计报告的内容及要求 在完成课题验收后，学生应在规定的时间内完成课程设计报告一份，报告的内容和要求如下： 1．目的与要求 这部分主要说明本课程设计的目的、任务和要求； 2．设计的内容 根据指导书的讲述，介绍系统中所设计的主要功能和原理方法； 3．各个功能的实现程序及结果 附各个功能的实现程序，需要在程序中做适当的注释，附处理前后效果图。 5．测试和调试 按课程设计要求，选用多幅图像（自己的照片）对程序进行测试，并提供系统的主要功能实现的效果图。并在调试中发现的问题做说明。 6．课程设计总结与体会 安徽大学 本科毕业论文（设计、创作）题目：哈夫曼编码与算术编码压缩效率比较 学生姓名：李伟学号：E20714134 院（系）：计算机科学与技术专业：软件工程 入学时间：2007年9月 导师姓名：韩莉职称/学位：讲师/硕士 导师所在单位：安徽大学计算机科学与技术学院 完成时间：2011年5月 哈夫曼编码与算术编码压缩效率比较 摘要 算术编码和哈夫曼编码都利用信源符号的概率分布特性进行编码，使平均码长逼近信息熵是压缩编码算法的第一要求，算术编码比哈夫曼编码逼近信息熵的能力要强，但是编码效率和实现往往是一对矛盾，编码效率的提高，往往要在实现上付出代价，所以，选择压缩算要权衡这两点。本论文开篇先引入了信息论的一些概念，因为编码理论发源于信息论，是各种编码算法的数学基础。然后在第2章分析了算术编码原理，并从无限精度的算术编码原理过渡到在计算机上能够实现的二进制编码原理。在第3章紧接着介绍了哈夫曼编码原理，并讨论了怎样把信源符号映射为对应的码字，过程中用到的哈夫曼编码表是编码与解码的关键。在第4章对两者的编码效率作了比较，主要是结合信息论中的一些概念从微观上对两者逼近信息熵的能力作了比较，并在这章最后对两者在文本文件的压缩效果的表现上给出了一些实验结果。最后，在5章，主要是对前面内容做了些补充和总结。 关键词：信息熵；算术编码；哈夫曼编码；编码效率 The comparison of Huffman Coding and Arithmetic Coding in File Compression Abstract Full use of the probability distribution of source symbols is the feature of the arithmetic encoding and Huffman encoding. Approaching the average code length to the information entropy come first when designing a compression algorithm. To the capacity of closing to information entropy, arithmetic encoding is stronger than Huffman encoding. However, the coding efficiency and implementation is often a contradiction: to improve coding efficiency, which means the algorithm implementation process needs to pay a higher price. Therefore, you need to weigh both when choosing a compression algorithm. In the beginning of this thesis, it first introduced some of the concepts of information theory. Because encoding algorithms are derived from information theory and information theory is the mathematical foundation of various coding algorithms. Then in Chapter 2, it introduces the principle of arithmetic coding. For better to understand the binary arithmetic coding principle, it first introduces the unlimited precision arithmetic coding. In Chapter 3, it describes the Huffman coding theory, and discusses how to map source symbol to the corresponding code word, among which Huffman coding and decoding table is the key. In Chapter 4, the coding efficiency of the two algorithms is compared. Mainly compare the capacities to approximate information entropy with some of the concepts in information theory. And the final part in this chapter, some experimental results are given to show the compression effect to compress a text file. Finally, in Chapter 5, it gives some additions and summary. Keywords:Information Entropy; Arithmetic Coding; Huffman Coding;Coding Efficiency % Author: Qu guangxiang 实验三算术编码 一、实验目的 1、复习C++语言基本编写方法，熟悉VC编程环境。 2、复习算术编码基本流程, 学会调试算术编码编码程序。 3、根据给出资料，自学自适应0阶算术编、解码方法。 二、实验内容 1．复习C++代码基本语法（类和虚函数等面向对象数据结构定义） 2．根据实验提供的源代码，学习算术编码实现流程，培养实际动手调试能力和 相应的编程技巧。 三、实验仪器、设备 1．计算机－系统最低配置256M 内存、P4 CPU。 2．C++ 编程软件－Visual C++ 7.0 （Microsoft Visual Studio 2003） Visual C++ 8.0 （Microsoft Visual Studio 2005） 四、实验原理 1．算术编码基本原理是将编码消息表示成实数0 和1 之间的一个间隔，消息 越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码 的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0 到1 之间。编码 过程中的间隔决定了符号压缩后的输出。如何解压缩呢？那就更简单了。解压缩之前仍然假定三个字符的概率相等。解压缩时面对的是二进制流 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。在压缩过程中不必再更新此概率分布，每次对区间的划分都依照此分布即可，对上例 也就是每次都平分区间。这样，压缩过程可以简单表示为： 输出区间的下限输出区间的上限 ------------------------------------------------------------------------ 压缩前 0.0 1.0 输入 b 0.0 0.5 输入 c 0.25 0.5 输入 c 0.375 0.5 输入 b 0.375 0.4375 算术编码与译码原理： 1、编码过程 算术编码方法是将被编码的一则消息或符号串（序列）表示成0和1之间的一个间隔（Interval），即对一串符号直接编码成[0,1]区间上的一个浮点小数。符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。信源中的符号序列仍然要根据某种模式生成概率的大小来减少间隔。可能出现的符号概率要比不太可能出现的符号减少范围小，因此，只正加较少的比特位。 在传输任何符号串之前，0符号串的完整范围设为[0,1]。当一个符号被处理时，这一范围就依据分配给这一符号的那一范围变窄。算术编码的过程，实际上就是依据信源符号的发生概率对码区间分割的过程。 举例说明如下： 假设一则消息“static_tree”具有如下的概率分布： 字符概率 --------------------------------------------------------------- ＿（space） 0.1 a 0.1 e 0.3 r 0.1 s 0.1 t 0.3 下面用算术编码方法给该消息编码。 一旦字符的概率已知，就沿着“概率线”为每一个单独的符号设定一个范围，哪一个被设定到哪一段范围并不重要，只要编码和解码都以同样方式进行就可以，这里所用的6个字符被分配的范围（range）如下： 字符概率范围 ＿(space) 0.1 0≤r<0.1 a 0.1 0.1≤r<0.2 e 0.3 0.2≤r<0.5 r 0.1 0.5≤r<0.6 s 0.1 0.6≤r<0.7 t 0.3 0.7≤r<1.0 ---------------------------------------------------------------- 对“state_tree”的算术编码过程为： （1）初始化时，被分割的范围range=high-low=[0,1）,下一个范围的低、高端分别由下式计算： Low=low + range×range low 视频编码技术实验报告-----算术编码算法的程序实现 学院： 班级： 姓名： 学号： 本实验通过编程实现简单的算术编码解码过程，加深对视频编码中熵编码原理及过程的理解，锻炼理论与实践相联系能力。 二、实验原理 算术编码是另一种常用的变字长编码，它也是利用信源概率分布特性、能够趋近熵极限的编码方法。它与Huffman 一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与Huffman 编码却不相同，而且在信源概率分布比较均匀的情况下其编码效率高于Huffman 编码。它和Huffman 编码最大的区别在于它不是使用整数码。Huffman 码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率[0，1] 区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。 三、实验过程 1.给定二进制符号序列：010110101111100110111100100011111111110100101101101101101 2.采用二元二进制算术编码进行编码，输出编码的结果。 3.采用自适应二元算术编码进行编码，输出编码结果。 4. 解码刚才编码的符号序列。 算术编码的C++实现 #include Context-Based Adaptive Binary Arithmetic Coding in the H.264/A VC 简称Cabac，H264中的一种熵编码方式：基于上下文的自适应二进制算术编码内容安排：1，介绍算术编码2，介绍二进制算术编码3介绍Cabac及其一些实用的实现方式（参考JSVM代码，也可以参考JM） 一，算术编码 算术编码是一种常用的变字长编码，它是利用信源概率分布特性、能够趋近熵极限的编码方法。它与Huffman 一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与Huffman 编码却不相同，而且在信源概率分布比较均匀的情况下其编码效率高于Huffman 编码。它和Huffman 编码最大的区别在于它不是使用整数码。Huffman 码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率[0，1] 区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。举例如下： S S S S为例 以符号 3324 在算术编码中通常采用二进制分数表示概率，每个符号所对应的概率区间都是半开区间，即该区间包括左端点，而不包括右端点，如S1对应[0, 0.001)，S2 对应[0.001, 0.01) 等。 算术编码产生的码字实际上是一个二进制数值的指针，指向所编的符号对应的概率区间。 S S S S…… 的第一个符号S3 用指向第3 个子区间的指针 符号序列 3324 实验一：算数编码实验 、实验目的 掌握算数编码原理。 、实验内容 利用Matlab 编写程序实现算数编码，包括： 1、对文件符号进行概率统计，生成编码表； 2、对文件进行压缩编码； 3、(选做)对文件进行解压缩，比较原始数据和解压后的数据之间是否有损耗。 三、实验仪器 1、计算机一台； 2、Matlab 仿真软件。 四、实验原理 算术编码的编码对象是一则消息或一个字符序列，其编码思路是将该消息或字符序列表示成0 和1 之间的一个间隔(Interval) 上的一个浮点小数。 在进行算术编码之前，需要对字符序列中每个字符的出现概率进行统计，根据各字符出现概率的大小，将每个字符映射到[0,1] 区间上的某个子区间中。然后，再利用递归算法，将整个字符序列映射到[0,1] 区间上的某个Interval 中。在进行编码时，只需从该Interval 中任选一个小数，将其转化为二进制数。 符号序列越长，编码表示它的Interval 的间隔就越小，表示这一间隔所需的二进制位数就越多，编码输出的码字就越长。 五、实验结果 算数编码的MATLAB 程序运行结果如下：请输入编码的字符串'state_tree' _ a e r s t 输入第1 符号的间隔左右边界： 输入第2 符号的间隔左右边界： 输入第3 符号的间隔左右边界： 输入第4 符号的间隔左右边界： 输入第5 符号的间隔左右边界：输入第6 符号的间隔左右边界：输入第7 符号的间隔左右边界：输入第8 符号的间隔左右边界：输入第9 符号的间隔左右边界：输入第10 符号的间隔左右边界： 算术编码程序代码如下： str=input('请输入编码的字符串'); l=0;r=1;d=1; %初始间隔 P=[ ]； %字符的概率分布，sum(p)=1 n=len gth(str); disp('_ a e r s t') disp( nu m2str(p)) for i=1: n switch str(i) case '_' m=1; case 'a' m=2; case 'e' m=3; case 'r' m=4; case 's' m=5; case 't' m=6; otherwise error('请不要输入其它字符！'); end %判断字符pl=0;pr=0; for j=1:m-1 pl=pl+p(j); end for j=1:m pr=pr+p(j); end %概率统计 l=l+d*pl; r=l+d*(pr-pl); strl=strcat(' 输入第',int2str(i),' 符号的间隔左右边界：'); disp(strl); format long disp(l);disp(r); d=r-l; end l=l+d*pl; r=l+d*(pr-pl); str1=strcat(' 输入第',int2str(i),' 符号的间隔左右边界：'); disp(strl); format long disp(l);disp(r); d=r-1; 算术编码原理 在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。 例: 对一个简单的信号源进行观察，得到的统计模型如下： ?60% 的机会出现符号中性 ?20% 的机会出现符号阳性 ?10% 的机会出现符号阴性 ?10% 的机会出现符号数据结束符. (出现这个符号的意思是该信号源'内部中止'，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了。) 算术编码可以处理的例子不止是这种只有四种符号的情况，更复杂的情况也可以处理，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。 一个简单的例子以下用一个符号串行怎样被编码来作一个例子：假如有一个以A、B、C三个出现机会均等的符号组成的串行。若以简单的分组编码会十分浪费地用2 bits来表示一个符号：其中一个符号是可以不用传的(下面可以见到符号B正是如此)。为此，这个串行可以三进制的0和2之间的有理数表示，而且每位数表示一个符号。例如，―ABBCAB‖ 这个串行可以变成0.011201(base3)(即0为A, 1 为B, 2为C)。用一个定点二进制数字去对这个数编码使之在恢复符号表示时有足够的精度，譬如0.001011001(base2) –只用了9个bit，比起简单的分组编码少(1 –9/12)x100% = 25%。这对于长串行是可行的因为有高效的、适当的算法去精确地转换任意进制的数字。 编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据： ?下一个要编码的符号 ?当前的区间(在编第一个符号之前，这个区间是[0,1), 但是之后每次编码区间都会变化)算术编码
算术编码工作原理
算术编码与解码
简单短序列的算术编码的MATLAB实现
转 算术编码算法的分析与实现
算术编码算法的Matlab实现
编程实现算术编码算法
数字图像处理和算术编码
算术编码与哈夫曼编码
算术编解码matlab实现
算术编码
算术编码+及译码原理
视频编码算术编码实验报告
cabac原理及其实现
算数编码实验
算术编码