算术编码+及译码原理
算术编码与译码原理：
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
High=low + range×range high
其中等号右边的low为上一个被编码字符的范围低；range low和range high分别为被编码符号已给定的字符出现概率范围的low和high。
（2）对消息第一字符s编码：s的range low=0.6， s的range high=0.7因此，下一个区间的low和high为：
Low=low + range×range low=0+1×0.6=0.6
High=low + range×range high=0+1×0.7=0.7
Range=high-low=0.7-0.6=0.1
S将区间[0,1）=>[0.6,0.7）
(3)对第二个字符t编码，使用的新生范围为[0.6,0.7），因为t的range
low=0.7,range high=1.0,因此下一个low,high分别为
Low=0.6+0.1×0.7＝0.67
High=0.6+0.1×1.0＝0.70
Range=0.7-0.67=0.03
t将[0.6,0.7）=>[0.67,0.70）
(4)对第三个字符a编码，在新生成的[0.67,0.70）中进行分割，因为a的range low=0.10,range high=0.2,因此下一个low,high分别为
Low=0.67+0.03×0.1＝0.673
High=0.67+0.03×0.2＝0.676
Range=0.676-0.673=0.003
a将[0.67,0.70）=>[0.673,0.676）
(5)对第四个字符t编码，在新生成的[0.673,0.676）上进行分割。因为t的range low=0.70,range high=1.0,则下一个low,high分别为
Low=0.673+0.003×0.7＝0.6751
High=0.673+0.003×1.0＝0.676
Range=0.0009
t将[0.673,0.676）=>[0.6751,0.676）
同理得到下面各字符e,＿,s,t,r,e,e编码所得到的范围分别为
[0.67528,0.67555），[0.67528,0.675307），[0.675 298 9,0.675 307），[0.675 302 95,0.675 303 76），[0.675 303 112,0.675 303 355），[0.675 303 160 6,0.675 303 233 5）将编码后的区间范围综合如下：
2、解码过程
解码是编码的逆过程，了解了编码过程后，理解解码过程的操作就相对容易了。通过编码，最后的下界值0.675 303 160 6就是消息“state_tree”的唯一编码。然后解码时，通过判断哪一个符号能拥有我们已编码的消息落在的空间来找出消息中的第一个符号。由于0.675 303 160 6落在[0.6,0.7）之间，因此可解得第一个符号是s。
在解出s后，由于我们知道s的范围的上界和下界，利用编码的逆作用，首先去掉s的下界值0.6，得0.075 303 160 6，然后用s的范围range=0.1去除所得到的0.075 303 160 6，即得到0.753 031 606，接着找出它所在的区间，就是t的原来范围[0.7,1.0）。去掉t的下界值0.7，得0.053 031 606，然后用t的range=0.3除该数得出0.176 772 02，该值所属范围就是字符a……如此操作下去便得到消息的准确译码。
综述，可以得到解码公式为：
(Number-range low)/range=>number
其中，number为字符串的编码。
matlab 程序:
%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
end
% the result range
fprintf('算术编码范围下限为%16.15f\n\n',numberlow);
fprintf('算术编码范围上限为%16.15f\n\n',numberhigh);
% decoding
Mat = zeros(m,n);
for k = 1:m
for kk = 1:n
indx = numberlow indx = [indx 1]; ind = diff(indx); ind = logical(ind); Mat(k,kk) = color(ind); low = allLow(ind); high = allHigh(ind); range = high - low; numberlow = numberlow-low; numberlow = numberlow/range; end end fprintf('原矩阵为:\n') disp(I); fprintf('\n'); fprintf('解码矩阵:\n'); disp(Mat); 实现算术编码及其译码 一、实验内容 借助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所示。 编码和译码的全过程分别表示在下表。 编码过程 编码器、译码器及应用电路设计 一、实验目的： 1、掌握中规模集成编码器、译码器的逻辑功能测试和使用方法； 2、学会编码器、译码器应用电路设计的方法； 3、熟悉译码显示电路的工作原理。 二、实验原理： 1、什么是编码： 教材说：用文字、符号、或者数字表示特定对象的过程称为编码 具体说：编码的逻辑功能是把输入的每个高、低电平信号编成对应的二进制代码 2、编码器74LS147的特点及引脚排列图： 74LS147是优先编码器，当输入端有两个或两个以上为低电平，它将对优先级别相对较高的优先编码。其引脚排列图： 3、什么是译码：译码是编码的逆过程，把给定的代码进行“翻译”，变成相应的状态，使输出通道中相应的一路有信号输出，译码器广泛用于代码转换、终端的数字显示、数据分配、组合控制信号等。 译码器按照功能的不同，一般分为三类：二进制译码器、二—十进制译码器、显示译码器。 （1）变量译码器（用以表示输入变量的状态） 74LS138的特点及其引脚排列图：反码输出。 ABC是地址输入端，Y0—Y7是输出端，G1、G2A’、G2B’为 使能端，只有当G1=G2A’=G2B’=1时，译码器才工作。 （2）码制变换译码器：用于同一个数据的不同代码之间的相互转换，代表是4—10线译码器 译码器74LS42的特点及其引脚排列图： 译码器74LS42的功能是将8421BCD码译成10个对象 其原理与74LS138类同，只不过它有四个输入端， 十个输出端，4位输入代码0000—1111十六种状态组合 其中有1010—1111六个没有与其对应的输出端， 这六组代码叫做伪码，十个输出端均为无效状态。 （3）数码显示与七段译码驱动器：将数字、文字、符号的代码译成数字、文字、符号的电路 a、七段发光二极管数码显示管的特点：（共阴极） b、七段译码驱动器： 4、在本数字电路实验装置上已完成了译码器74LS48和数码管之间的连接图。 三四五脚接高电频，数码管的单独端接低电频。 算术编码工作原理 在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。 例: 对一个简单的信号源进行观察，得到的统计模型如下： ?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.掌握译码器、编码器的工作原理和特点。 2.熟悉常用译码器、编码器的逻辑功能和它们的典型应用。 二、实验原理和电路 按照逻辑功能的不同特点，常把数字电路分两大类：一类叫做组合逻辑电路，另一类称为时序逻辑电路。组合逻辑电路在任何时刻其输出的稳态值，仅决定于该时刻各个输入信号取值组合的电路。在这种电路中，输入信号作用以前电路所处的状态对输出信号无影响。通常，组合逻辑电路由门电路组成。 组合逻辑电路的分析方法：根据逻辑图进行二步工作： a.根据逻辑图，逐级写出函数表达式。 b.进行化简：用公式法、图形法或真值表进行化简、归纳。 组合逻辑电路的设计方法：就是从给定逻辑要求出发，求出逻辑图。一般分四步进行。 a.分析要求；将问题分析清楚，理清哪些是输入变量，哪些是输出函数。 b.列真值表。 c.进行化简：变量比较少时，用图形法。变量多时，可用公式化简。 d.画逻辑图：按函数要求画逻辑图。 进行前四步工作，设计已基本完成，但还需选择元件——集成电路，进行实验论证。 值得注意的是，这些步骤并不是固定不变的程序，实际设计时，应根据具体情况和问题难易程度进行取舍。 1.译码器 译码器是组合电路的一部分，所谓译码，就是把代码的特定含义“翻译”出来的过程，而实现译码操作的电路称为译码器。译码器分成三类： a.二进制译码器：如中规模2—4线译码器74LS139。，3—8线译码器74LS138等。 b.二—十进制译码器：实现各种代码之间的转换，如BCD码—十进制译码器74LS145等。 c.显示译码器：用来驱动各种数字显示器，如共阴数码管译码驱动74LS48，（74LS248），共阳数码管译码驱动74LS47（74LS247）等。 2.编码器 编码器也是组合电路的一部分。编码器就是实现编码操作的电路，编码实际上是译码相反的过程。按照被编码信号的不同特点和要求，编码器也分成三类： a.二进制编码器：如用门电路构成的4—2线，8—3线编码器等。 b.二—十进制编码器：将十进制的0～9编成BCD码，如：10线十进制—4线BCD码编码器74LS147等。 c.优先编码器：如8—3线优先编码器74LS148等。 三、实验内容及步骤 1.译码器实验 （1）将二进制2-4线译码器74LS139，及二进制3-8译码器74LS138分别插入实验系统IC 空插座中。 按图1.3.1接线，输入G、A、B信号（开关开为“1”、关为“0”），观察LED输出Yo、Y1、Y2、Y3的状态(亮为“1”，灭为“0”)，并将结果填入表1.3.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、编码过程 算术编码方法是将被编码的一则消息或符号串（序列）表示成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; 实验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) 熟悉掌握集成译码器和编码器的应用； (3) 掌握集成译码器的扩展方法。 二、实验设备 数字电路实验箱，74LS20，74LS138。 三、实验内容 (1) 74LS138译码器逻辑功能的测试。将74LS138输出??接数字实验箱LED 管，地址输入接实验箱开关，使能端接固定电平（或GND）。电路图如Figure 1所示： Figure 2 ??????????????时，任意拨动开关，观察LED显示状态，记录观察结果。 ??????????????时，按二进制顺序拨动开关，观察LED显示状态，并与功能表对照，记录观察结果。 用Multisim进行仿真，电路如Figure 3所示。将结果与上面实验结果对照。 Figure 4 (2) 利用3-8译码器74LS138和与非门74LS20实现函数： ?? 四输入与非门74LS20的管脚图如下： 对函数表达式进行化简： ?? ?? A ? ??????????? ???? 按Figure 5所示的电路连接。并用Multisim进行仿真，将结果对比。 Figure 6 (3) 用两片74LS138组成4-16线译码器。 因为要用两片3-8实现4-16译码器，输出端子数目刚好够用。 而输入端只有 A、、三个，故要另用使能端进行片选使两片138译码器 进行分时工作。而实验台上的小灯泡不够用，故只用一个灯泡，而用连接灯泡的导线测试?，在各端子上移动即可。在multisim中仿真电路连接如Figure 7所示（实验台上的电路没有接下面的两个8灯LED）： Figure 8 四、实验结果 (1) 74LS138译码器逻辑功能的测试。 当输入 A时，应该是输出低电平，故应该第一个小灯亮。实际用实验台测试时，LE0灯显示如Figure 9所示。当输入 A时，应该是输出低电平，故理论上应该第二个小灯亮。实际用实验台测试时，LE0灯显示如Figure 6所示。 Figure 10 数字图像处理课程设计 题目：数字图像处理及算术编码 （或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 实验六编码器、译码器及应用电路设计 一、实验目的： 1、掌握中规模集成编码器、译码器的逻辑功能测试和使用方法； 1、学会编码器、译码器应用电路设计的方法； 3、熟悉译码显示电路的工作原理。 二、实验原理： 编码是用文字、符号或者数字表示特定对象的过程，在数字电路中是用二进制数进行编码的，相应的二进制数叫二进制代码。编码器就是实现编码操作的电路。本实验使用的是优先编码器74LS147，当输入端有两个或两个以上为低电平时，将对输入信号级别相对高的优先编码，其引脚排列如图6—1所示。 图6—1 74LS147引脚排列图图6—2 74LS138引脚排列图译码是编码的逆过程，是把给定的代码进行“翻译”，变成相应的状态，使输出通道中相应的一路有信号输出。译码器在数字系统有广泛的用途，不仅用于代码的转换、终端的数字显示，还用于数据分配和组合控制信号等。不同的功能可选用不同种类的译码器。 译码器按照功能的不同，一般分为三类： 1、变量译码器（二进制译码器）：用以表示输入变量的状态，如2—4线、3—8线、4—16线译码器。以3—8线译码器74LS138为例介绍： 图6—2为74LS138的引脚图，其中，A2A1A0为地址输入端，为译码器输出端，为使能端（只有当时，才能进行译码）。 图6—3 74LS42引脚排列图图6—5为CC4511引脚排列图 2、码制变换译码器：用于同一个数据的不同代码之间的相互变换。这种译码器的代表是4—10线译码器，它的功能是将8421BCD码译为十个对象，如74LS42等。它的原理与 74LS138译码器类同，只不过它有四个输入端，十个输出端。4位输入代码共有0000—1111 目录 1设计目的与要求 (1) 1.1 设计的目的 (1) 1.2 设计要求 (1) 2 VHDL的简单介绍 (2) 2.1 VHDL的简介 (2) 2.2 VHDL的特点 (2) 2.3 VHDL的优势 (3) 2.4 VHDL的设计步骤 (4) 3 EDA的简单介绍 (5) 3.1 EDA的简介 (5) 3.2 EDA设计方法与技巧 (5) 4 设计过程 (7) 4.1编码器的原理 (7) 4.2译码器的原理 (7) 4.3课程设计中各部分的设计 (7) 5 仿真 (10) 5.1八-三优先编码器仿真及分析 (10) 5.2三-八译码器仿真及分析 (11) 5.3二-四译码器仿真及分析 (14) 心得体会 (13) 参考文献 (16) 附录 (17) 摘要 随着社会的发展，科学技术也在不断的进步。计算机从先前的采用半导体技术实现的计算器到现在广泛应用的采用高集成度芯片实现的多功能计算器。计算机电路是计算机的重要组成部分，了解计算机电路的知识是促进计算机的发展的先决条件。而编码器和译码器是计算机电路中的基本器件，对它们的了解可以为以后的进一步深化研究打下一个良好的基础。本设计主要介绍的是一个基于超高速硬件描述语言VHDL对计算机电路中编码器和译码器进行编程实现。 关键字：计算机编码器译码器 编码器和译码器的设计 1 设计目的与要求 随着社会的进一步发展，我们的生活各个地方都需要计算机的参与，有了计算机，我们的生活有了很大的便利，很多事情都不需要我们人为的参与了，只需要通过计算机就可以实现自动控制。由此，计算机对我们的社会对我们每个人都是很重要的。所以我们要了解计算机得组成，内部各种硬件，只有了解了计算机基本器件已经相应的软件，才能促进社会的发展。编码器和译码器的设计是计算机的一些很基础的知识，通过本次对于编码器和译码器的设计，可以让我知道究竟这种设计是如何实现的，这种设计对我们的生活有什么帮助，这种设计可以用到我们生活的哪些方面，对我们的各种生活有什么重大的意义。 1.1 设计的目的 本次设计的目的是通过简单的编码器和译码器的设计掌握基本的计算机的一些有关的知识，通过查资料已经自己的动手设计去掌握EDA技术的基本原理已经设计方法，并掌握VHDL硬件描述语言的设计方法和思想。以计算机组成原理为指导，通过将理论知识，各种原理方法与实际结合起来，切实的亲手设计，才能掌握这些非常有用的知识。通过对编码器和译码器的设计，巩固和综合运用所学知识，提高IC设计能力，提高分析、解决计算机技术实际问题的独立工作能力。也能通过这种自主设计，增强自己的动手能力，将理论知识切实应用的能力，这对我们将来的发展是很有帮助的。 1.2 设计要求 根据计算机组成原理中组合逻辑电路设计的原理，利用VHDL设计计算机电路中编码器和译码器的各个模块，并使用EDA 工具对各模块进行仿真验证和分析。编码器由八-三优先编码器作为实例代表，而译码器则包含三-八译码器和二-四译码器两个实例 实验二编码器和译码器的应用 一．实验目的： 1.学会正确使用中规模集成组合逻辑电路。掌握编码器、译码器、BCD七段 译码器、数码显示器的工作原理和使用方法。 2.掌握译码器及其应用, 学会测试其逻辑功能。 二．实验仪器及器件： 1. TPE—D6Ⅲ型数字电路实验箱 1台 2.数字万用表 1块 3.器件：74LS20 二4输入与非门 1片 74LS04 六反相器 1片 74LS147 10线—4线优先编码器 1片 74LS138 3线—8线译码器 1片 74LS139 双2线—4线译码器 1片 74LS47 七段显示译码器 1片 三．实验预习： 1.复习编码器、译码器、BCD七段译码器、数码显示器的工作原理。 2.熟悉编码器74LS147及译码器74LS138、74LS139各引脚功能和使用方法， 列出74LS138、74LS139的真值表，画出所要求的具体实验线路图。四．实验原理： 在数字系统中，常常需要将某一信息变换为特定的代码,有时又需要在一定的条件下将代码翻译出来作为控制信号，这分别由编码器和译码器来实现。 1.编码：用一定位数的二进制数来表示十进制数码、字母、符号等信息的过 程。编码器：实现编码功能的电路。 编码器功能：从m个输入中选中一个,编成一组n位二进制代码并行输出。 编码器特点：(1)多输入、多输出组合逻辑电路。 (2)在任何时候m个输入中只有一个输入端有效（高电平或 低电平）对应有一组二进制代码输出。 编码器分类：二进制、二─十进制、优先编码器。2.译码：是编码的反过程，是将给定的二进制代码翻译成编码时赋予的原意。 译码器：实现译码功能的电路。译码器特点：(1)多输入、多输出组合逻辑电路。 (2)输入是以n位二进制代码形式出现，输出是与之对应的 电位信息。 编程实现算术编码算法 中国地质大学计算机学院信息安全专业 信息论实验报告 实验三算术编码 一、实验内容 编程实现算术编码算法 二、实验环境 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 实验三算术编码 一、实验目的 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 视频编码技术实验报告-----算术编码算法的程序实现 学院： 班级： 姓名： 学号： 本实验通过编程实现简单的算术编码解码过程，加深对视频编码中熵编码原理及过程的理解，锻炼理论与实践相联系能力。 二、实验原理 算术编码是另一种常用的变字长编码，它也是利用信源概率分布特性、能够趋近熵极限的编码方法。它与Huffman 一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与Huffman 编码却不相同，而且在信源概率分布比较均匀的情况下其编码效率高于Huffman 编码。它和Huffman 编码最大的区别在于它不是使用整数码。Huffman 码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率[0，1] 区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。 三、实验过程 1.给定二进制符号序列：010110101111100110111100100011111111110100101101101101101 2.采用二元二进制算术编码进行编码，输出编码的结果。 3.采用自适应二元算术编码进行编码，输出编码结果。 4. 解码刚才编码的符号序列。 算术编码的C++实现 #include 算术编码
编码器和译码器的应用
算术编码工作原理
译码器和编码器实验
简单短序列的算术编码的MATLAB实现
转 算术编码算法的分析与实现
算术编码与解码
算术编码算法的Matlab实现
编码器和译码器实验报告
数字图像处理和算术编码
算术编码与哈夫曼编码
编码器、译码器及应用电路设计
编码器和译码器的设计
实验二编码器和译码器的应用
编程实现算术编码算法
算术编码
视频编码算术编码实验报告