基于算术编码的信源编码解码系统设计与仿真.doc

******************
实践教学
*******************

计算机与通信学院

通信系统仿真训练

题 目：基于算术编码的信源编码/解码系统设计与仿真

摘 要
随着社会的飞速发展，数字化已经成了现今通信技术的主流发展方向，而实现数字化的重要步骤就是对信源进行编码。信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：无失真信源编码定理和限失真信源编码定理。信源编码是以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。人们经过不断地探索，创造了许多种有效的信源编码的方法，比如说哈弗曼编码、算术编码、游程编码等，通过这些有效地信源编码方式，很好的提高了通信的有效性。
本文从算术编码原理、以及研究算术编码的目的意义等，到具体算术编码方案的分析比较以及其 MATLAB 语言的实现方案，有重点的对算术编码的编码过程进行了分析和阐述。具体说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字的序列的方法。设计利用MATLAB语言设计并实现了基于算术编码的信源编码/解码过程。算术编码是一种能够趋近于熵极限的最佳编码方式对出现概率较大的符号使用短码，对概率较小的符号使用长码。过本课程设计可以实现从键盘随意输入待传输信息，根据算术编码原理输出编码结果，如果选择译码，会输出之前输入的传输信息。

关键词 ： 算术编码 译码 MATLAB仿真
目 录

一、信源编码 1
1.1 信源编码的概念 1
1.2 信源编码简介 1
1.3信源编码的目的： 2
1.4信源编码的原理 2
二、算术解码的理论基础 7
2.1 算术编码算法的基本原理 7
2.2算术编码的特点 7
2.3 算术编码的分析过程 8
2.4算术编码举例 9
三、算术编码MATLAB仿真实现 15
3.1 MATLAB 仿真程序实现 15
3.2仿真设计流程图 15
3.3 算术编码仿真设计 16
3.4结果分析 21
设计总结 21
参考文献 23

2

一、 信源编码
1.1 信源编码的概念
信源编码是为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对信源输出的符号序列所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。既然信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。当然，这些都是广义的信源编码。
1.2 信源编码简介
信源编码是以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率，同样多的信息用较少的码率来传输，使单位时间内传送的平均信息来量增加，从而提高通信的有效性。
信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：无失真信源编码定理和限失真信源编码定理。前者是离散信源或数字编码的基础，后者则是连续信源或模拟信号的基础。
编码实质上就是对信源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。信源编码是为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对信源输出的符号序列所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。信源编码的基本途径有两个：使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。

1.3信源编码的目的：
1、信源存在冗余度。
2、原因是信源符号之间存在概率分布不均匀和相关性。
3、信源编码的主要任务就是减少冗余，提高编码效率。
4、信源编码是以提高通信的有效性为目的编码。
5、通常通过压缩信源的冗余度来实现。
6、即用较少的码字传送较多的信息，使单位时间内传送的平均信息量增加，从而提高通信的有效性。
1.4信源编码的原理
一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：①使序列中的各个符号尽可能地互相独立；②使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称为概率均匀化。
信源编码的一般问题可以表述如下：若某信源的输出为长度等于M的符号序列集合
式中符号A为信源符号表，它包含着K个不同的符号，A=｛ɑk|k=1,…,K｝，这个信源至多可以输出K个不同的符号序列。记‖U‖=K。所谓对这个信源的输出进行编码，就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U。若V的各个序列的长度等于 N，即
式中新的符号表B共含L个符号，B=｛bl|l=1,…,L｝。它总共可以编出L个不同的码字。类似地,记‖V‖＝L。为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应，至少应满足关系 ‖V‖＝L≥‖U‖＝K，或者 N/M≥logK/logL；
假若编码符号表B的符号数L与信源符号表A的符号数K相等，则编码后的码字序列的长度N必须大于或等于信源输出符号序列的长度M；反之，若有N＝M，则必须有L≥K。只有满足这些条件，才能保证无差错地还原出原来的信源输出符号序列(称为码字的唯一可译性)。可是，在这些条件下，码字序列的每个码元所载荷的平均信息量不但不能高于，反而会低于信源输出序列的每个符号所载荷的平均信息量。这与编码的基本目标是直接相矛盾的。下面的几个编码定理，提供了解决这个矛盾的方法。它们既能改善信息载荷效率，又能保证码字唯一可译。
离散无记忆信源的定长编码定理对于任意给定的ε＞0，只要满足条件 N/M≥(H(U)+ε)/logL
那么,当M足够大时,上述编码几乎没有失真;反之,若这个条件不满足，就不可能实现无失真的编码。式中H(U)是信源输出序列的符号熵。
通常,信源的符号熵H(U)＜logK，因此,上述条件还可以表示为 【H(U)+ε】/logL≤N/M≤logK/logL
特别,若有K＝L,那么,只要H(U)＜logK,就可能有N＜M，从而提高信息载荷的效率。由上面这个条件可以看出，H(U)离logK越远,通过编码所能获得的效率改善就越显著。实质上，定长编码方法提高信息载荷能力的关键是利用了渐近等分性,通过选择足够大的M,把本来各个符号概率不等［因而H(U)＜logK］的信源输出符号序列变换为概率均匀的典型序列，而码字的唯一可译性则由码字的定长性来解决。
离散无记忆信源的变长编码定理变长编码是指V的各个码字的长度不相等。只要V中各个码字的长度 Ni(i＝1，…，‖V‖)满足克拉夫特不等式。
这 ‖V‖个码字就能唯一地正确划分和译码。离散无记忆信源的变长编码定理指出：若离散无记忆信源的输出符号序列 ，式中 A＝｛ɑk|k=1,…,K｝,符号熵为H(U)，对U进行唯一可译的变长编码，编码字母表B的符号数为L,即B=｛bl|l=1,…,L｝,那么必定存在一种编码方法，使编出的码字Vi＝(vi1,…,viNi)，(i=1,…,‖V‖)，具有平均长度嚻： MH(U)/logL≤嚻＜MH(U)/logL+1若L=K，则当H(U)＜logK＝logL时,必有嚻＜M；H(U)离logK越远，则嚻越小于M。
具体实现唯一可译变长编码的方法很多，但比较经典的方法还是仙农编码法、费诺编码法和霍夫曼编码法。其他方法都是这些经典方法的变形和发展。所有这些经典编码方法，都是通过以短码来表示常出现的符号这个原则来实现概率的均匀化，从而得到高的信息载荷效率；同时，通过遵守克拉夫特不等式关系来实现码字的唯一可译。
霍夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来，求其中概率最小的两个序列的概率之和，并把这个概率之和看作是一个符号序列的概率，再与其他序列依概率递降顺序排列（参与求概率之和的这两个序列不再出现在新的排列之中），然后，对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列。最后，按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组，就可分别得到各该符号序列的码字。
　　例如，某个离散无记忆信源的输出符号序列及其对应的概率分布为

对这些输出符号序列进行霍夫曼编码的具体步骤和结果如表。

表1-1
由表中可以看出，在码字序列中码元0和1的概率分别为10/21和11/21，二者近乎相等，实现了概率的均匀化。同时，由于码字序列长度满足克拉夫特不等式 2×2+3×2+2×2＝1
因而码字是唯一可译的，不会在长的码字序列中出现划错码字的情况。
以上几个编码定理，在有记忆信源或连续信源的情形也有相应的类似结果。在实际工程应用中，往往并不追求无差错的信源编码和译码，而是事先规定一个译码差错率的容许值，只要实际的译码差错率不超过这个容许值即认为满意（见信息率-失真理论和多用户信源编码）。
针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。
1、解除相关性：使序列中的各个符号尽可能地互相独立。
2、概率均匀化：使编码中各个符号出现的概率尽可能地相等。
信源编码的实现方法：
离散信源编码有香农编码、费诺编码、赫夫曼编码、游程编码、冗余位编码；连续信源编码有最佳标量量化、矢量量化；相关信源编码的预测编码、差值编码；变换编码的子带编码、小波变换。
一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个： 一是使序列中的各个符号尽可能地互相独立；
二是使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称为概率均匀化。
信源编码的一般问题可以表述如下：若某信源的输出为长度等于M的符号序列集合

　　式中符号A为信源符号表，它包含着K个不同的符号，A=｛ɑk|k=1,…,K｝，这个信源至多可以输出K个不同的符号序列。记‖U‖=K。所谓对这个信源的输出进行编码，就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U。若V的各个序列的长度等于 I，即

式中新的符号表B共含L个符号，B=｛bl|l=1,…,L｝。它总共可以编出L个不同的码字。类似地,记‖V‖＝L。为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应，至少应满足关系 ‖V‖＝L≥‖U‖＝K，或者 N/M≥logK/logL；
　　假若编码符号表B的符号数L与信源符号表A的符号数K相等，则编码后的码字序列的长度N必须大于或等于信源输出符号序列的长度M；反之，若有N＝M，则必须有L≥K。只有满足这些条件，才能保证无差错地还原出原来的信源输出符号序列(称为码字的唯一可译性)。可是，在这些条件下，码字序列的每个码元所载荷的平均信息量不但不能高于，反而会低于信源输出序列的每个符号所载荷的平均信息量。这与编码的基本目标是直接相矛盾的。下面的几个编码定理，提供了解决这个矛盾的方法。它们既能改善信息载荷效率，又能保证码字唯一可译。
(1)离散无记忆信源的定长编码定理
对于任意给定的ε＞0，只要满足条件 N/M≥(H(U)+ε)/logL
　　那么,当M足够大时,上述编码几乎没有失真;反之,若这个条件不满足，就不可能实现无失真的编码。式中H(U)是信源输出序列的符号熵。
　　通常,信源的符号熵H(U)＜logK，因此,上述条件还可以表示为 【H(U)+ε】/logL≤N/M≤logK/logL。
　　特别,若有K＝L,那么,只要H(U)＜logK,就可能有N＜M，从而提高信息载荷的效率。由上面这个条件可以看出，H(U)离logK越远,通过编码所能获得的效率改善就越显著。实质上，定长编码方法提高信息载荷能力的关键是利用了渐近等分性,通过选择足够大的M,把本来各个符号概率不等［因而H(U)＜logK］的信源输出符号序列变换为概率均匀的典型序列，而码字的唯一可译性则由码字的定长性来解决。
(2)离散无记忆信源的变长编码定理
变长编码是指V的各个码字的长度不相等。只要V中各个码字的长度 Ni(i＝1，…，‖V‖)满足克拉夫特不等式。
这 ‖V‖个码字就能唯一地正确划分和译码。离散无记忆信源的变长编码定理指出：若离散无记忆信源的输出符号序列为 ，
　 式中 A＝｛ɑk|k=1,…,K｝,符号熵为H(U)，对U进行唯一可译的变长编码，编码字母表B的符号数为L,即B=｛bl|l=1,…,L｝,那么必定存在一种编码方法，使编出的码字Vi＝(vi1,…,viNi)，(i=1,…,‖V‖)，具有平均长度嚻： MH(U)/logL≤嚻＜MH(U)/logL+1；
若L=K，则当H(U)＜logK＝logL时,必有嚻＜M；H(U)离logK越远，则嚻越小于M。
　　具体实现唯一可译变长编码的方法很多，但比较经典的方法还是仙农编码法、费诺编码法和霍夫曼编码法。其他方法都是这些经典方法的变形和发展。所有这些经典编码方法，都是通过以短码来表示常出现的符号这个原则来实现概率的均匀化，从而得到高的信息载荷效率；同时，通过遵守克拉夫特不等式关系来实现码字的唯一可译。
编码的逆过程，利用不同编码方法实现的生成的码字通过其相应方法实现对码字的译码，还原出从信源输入的信息。进行编码是为了压缩信源符号的冗余度，在传输、译码后，还能恢复出原始信息。
二、 算术解码的理论基础
2.1 算术编码算法的基本原理
算术编码是一种无失真的编码方法，能有效地压缩信源冗余度，使编成的码率趋于信的熵 ，它是无损压缩的一种。算术编码的基本原理是：根据信源可能发现的不同符号序列的概率，把 [0 ，1) 区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列概率 。 这样信源发出的不同符号序列将与各子区间一一对应 ， 因此每个子区间内的任意个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。显然 ，串符号序列发生的概率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因相应的码字就越短。
算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的 。本课程设计中以静态算术编码算法进行仿真。在自适应算术编码中，自适应算术编码在对符号序列进行扫描的过程中，可一次完成两个过程，即根据恰当的概率估计模型和当前符号序列中各符号出现的频率，自适应地调整各符号的概率估计值，同时完成编码。信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率， 所能做的最有效的方法是在编码过程中估算概率。尽管从编码效率上看不如已知概率表的情况，但正是由于算术编码自适应的调整对个符号概率的估计值，这点比哈弗曼编码相比，具有实时性好 、 灵活性高 、 适应性强等特点，在图像压缩、视频图像编码等领域都得到了广泛的应用。
2.2算术编码的特点
算术编码的优点：
（1）不必预先定义概率模型，自适应模式具有独特的优点；
（2）信源符号概率接近时，建议使用算术编码，这种情况下其效率高于霍夫曼编码；
（3）算术编码绕过了用一个特定的代码替代一个输入符号的想法，用一个浮点输出数值
代替一个流的输入符号，较长的复杂的消息输出的数值中就需要更多的位数；
（4）算术编码实现方法复杂一些，但 JPEG 成员对多幅图像的测试结果表明，算术编码比霍夫曼编码提高了 10%左右的效率，因此在 JPEG 扩展系统中用算术编码取代霍夫曼编码。
算术编码虽然具有其独特的优点，但我们仍需要注意下面几个问题：
（1）由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多
数机器都有 16 位、32 位或者 64 位的精度，因此这个问题可使用比例缩放方法解决。
（2）算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，
因此译码器在接受到表示这个实数的所有位之前不能进行译码。
（3）算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消
息译错。算术编码随着序列长度的增加，相应子区间的宽度也不断缩小，要表示这段子区间所需精度，直观地说就是比特数也不断增加。这不但要占用相当大的存储空间，还增加了编码延时，这对实时系统是十分不利的。为了解决这些难点，针对不同的应用方向，人们对传统的算术编码方法进行了改进，在保证足够精度的前提下，提高了编码速度。基于算术编码算法人们提出了二进制自适应的算术编码以及 MQ 算术编码器，分别在软件及上提高编码的效率。
2.3 算术编码的分析过程
在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在 0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码的过程，实际上就是依据信源符号的发生概率对码区间分割的过程。
算术编码的编码分析框图如下：

图2.1 算术编码的编码分析框图
静态算术编码和自适应型算术编码在编码前都需要初始化概率空间，静态算术编码的字符概率是固定的，因此找到相应的概率空间可直接按区间分割进行编码；自适应型算术编码在编码前需要统计输入的文本信息的符号类型和每个符号的个数，期初假定每个符号概率相等，然后输入一个符号后，找到相应的概率空间所有的符号概率会进行更新，然后依次规律对输入信息进行编码。

图2.2 算术编码的译码分析框图
读取编码结果，找到所属区间范围从而译出码字。静态型算术编码的编码值是变化的然后找所对应的区间；自适应型算术编码的编码值是不变的，只需改变概率区间，然后用此编码值找到所对应的区间，从而译出码字。
2.4算术编码举例
（1） 静态算术编码举例
假设一则消息“static_tree”具有如下的概率分布：
字符 概率
 ------------------------------------------------------------------------------------------------
       _            0.1
       a                0.1
       e                      0.3
       r                        0.1
      s                      0.1
      t                      0.3
下面用算术编码方法给该消息编码。
一旦字符的概率已知，就沿着“概率线”为每一个单独的符号设定一个范围，哪一个被设定到哪一段范围并不重要，只要编码和解码都以同样方式进行就可以，这里所用的6个字符被分配的范围（range）如下：

字符           概率         范围
  ---------------------------------------------------------------------------------------------------------------
   _           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”的算术编码过程为：
初始化时，被分割的范围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.6752989,0.675307),[0.67530295,0.67530376),[0.675303112,0.675303355），[0.6753031606,0.6753032335）,[0.6753031824,0.6753032335）。最后选取最后区间的中点作为编码的输出结果0.6753032079。
通过编码，最后的下界值0.6753032079就是消息“state_tree”的唯一编码。然后解码过判断哪一个符号能拥有我们已编码的消息落在的空间来找出消息中的第一个符号。由于0.6753032079落在[0.6,0.7）之间，因此可解得第一个符号是s。在解出s后，由于我们知道s的范围的上界和下界，利用编码的逆作用，首先去掉s的下界值0.6，得0.075 3032079，然后用s的范围range=0.1去除所得到的0.075 3032079，即得到0.75 3032079，接着找出它所在的区间，就是t的原来范围[0.7,1.0）。去掉t的下界值0.7，得0.05 3032079，然后用t的range=0.3除该数得出0.176 772 02，该值所属范围就是字符a……如此操作下去便得到消息的准确译码综述，可以得到解码公式为：(Number-range low)/range=>number其中，number为符串的编码。
（2） 算术编码举例
在编码之前，假设每个信源符号的频率相等（如都等于1），并计算累积频率
从输入流中读入一个字符，并对该符号进行算术编码；
更新该符号的频率，并更新累积频率；
由于在解码之前，解码器不知道是哪个信源符号，所以概率更新应该在解码之后进行
对应的，编码器也应在编码后进行概率更新。
设某信源可能发出三种符号a，b，c，对符号序列bccb进行自适应算术编码：
初始时刻，我们对a，b，c，三者出现的概率一无所知（即采用自适应模型），认为三者出现的概率相等，暂时都为1/3，频率都为1，则累积频率为3。将区间[0,1)按概率分布划分给三个字符，如下图所示：

向编码器输入第一个字符b，落入区间[0.3333,0.6667)。此时b的频率增加了1变为2，累积频率也增加了1变为4；概率分布更新为：

再输入字符c，落入区间[0.5834,0.6667)。此时c的频率增加了1变为2，累积频率也增加了1变为5；概率分布更新为：

接着输入第三个字符c，落入区间[0.6334,0.6667)。此时c的频率又增加了1变为3，累积频率也又增加了1变为6；概率分布更新为：

最后输入字符b，锁定区间[0.6390,0.6501)，然后在这个区间内任意选择一个实数，例如0.64，再将其转化为二进制数l位（连续乘以2取整）。

即输出8位。最后的编码结果为：11011011。
译码过程和编码过程类似：
设信源符号a，b，c的原概率皆为1/3。

a. 11011011B=0.64D，落入区间[0.3333,0.6667)，所以译码器译为b，概率分布更新为：

b. 0.64落入区间[0.5834,0.6667)，译为c，概率分布更新为：

c. 0.64落入区间[0.6334,0.6667)，译为c，概率分布更新为：

d. 0.64落入区间[0.6501,0.6667)，译为b。
如果有停止位或者定长，则译码结束，译出的原序列为：bccb。一旦字符的概率已知，就沿着“概率线”为每一个单独的符号设定一个范围，哪一个被设定到哪一段范围并不重要，只要编码和解码都以同样方式进行就可以。
离散信源编码有香农编码、费诺编码、赫夫曼编码、游程编码、冗余位编码；连续信源编码有最佳标量量化、矢量量化；相关信源编码的预测编码、差值编码；变换编码的子带编码、小波变换。本章主要举例说明了算术编码的基本原理，让读者能够理解算术编码的基本应用方法。

三、 算术编码MATLAB仿真实现
3.1 MATLAB 仿真程序实现
MATLAB是由美国 mathworks 公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式 程序设计语言（ 如 C、Fortran） 的编辑模式，代表了当今国际科学计算软件的先进水平。
MATLAB 由一系列工具组成。这些工具方便用户使用 MATLAB的函数和文件，其中许多工具采用的是图形用户界面。包括 MATLAB 桌面和命令窗口、历史命令窗口、编辑器和调
试器、路径搜索和用于用户浏览帮助、工作空间 、文件的浏览器。随着 MATLAB 的商业化以及软件本身的不断升级，MATLAB 的用户界面也越来越精致，更加接近 Windows 的标准界面，人机交互性更强，操作更简单。而且新版本的 MATLAB 提供了完整的联机查询、帮助系统，极大的方便了用户的使用。简单的编程环境提供了比较完备的调试系统，程序不必经过编译就可以直接运行，而且能够及时地报告出现的错误及进行出错原因分析。
MATLAB7. 1 版本是在 2005 年更新的，本文主要应用 MATLAB7. 1 中发布的影像处理工具箱中的相关函数和命令来实现基于算术编码实现图像压缩理论算法的仿真。MATLAB7. 1是一套功能十分强大的工程计算及数据分析应用软件,广泛应用于工业、电子、控制、信号及图像处理等各领域。MATLAB7. 1 本身除了提供强大的图形绘制和输出功能外 ,同时还发布了影像处理工具箱(Image Processing Toolbox),专门用于图像的处理.在通常情况下，可以用它来代替底层编程语言，如 C 和 C++。在计算要求相同的情况下，使用 MATLAB 的编程工作量会大大减少。
3.2仿真设计流程图
本课程设计的软件算术编码输入的自符类型固定，每个字符的概率也是固定的。输入的自符类型有“abcdef”每次输入字符，更新字符的起始、终止区间。等最后一个字符编码完成后，取起始值和终至值的中点作为编码的结果输出。译码的时候，读取编码的输出结果，找到所在的区间，依次译出编码前输入的字符信息。完成译码过程；自适应算术编码的概率模型不固定，先统计编码的符号类型，以及每个符号的个数。译码前，假设每个符号的概率是相等的，然后每次输入一个字符，相应的字符概率发生变化，直至编出最后一个码字，选取区间中间结果作为编码的输出，译码时，读取中间结果，找到所属概率区间，译出码字，然后变更概率区间，重新定位码字。直至译出最后一个码字。

图3.1算术编码设计流程图

上图是算术编码设计流程图，无论是静态型还是自适应型算术编码在编码前都要初始化概率空间，但二者在编码时的概率空间却不一样，前者固定不变，后者概率随输入字符变化而变化。然后进行区间分割，将字符串编成一个浮点小数，然后转化为二进制，作为结果之后选择是否译码，确定是否译出信源符号。

3.3 算术编码仿真设计
（1） 、显示主界面程序段

menu={... '请按下列要求输入字符串：'
'1、字符串长度适宜；'
'2、可以输入的字符仅限于：a,b,c,d,e,f ；'
'3、输入的字符一定要用英文状态下的单引号引起来,例如：''efbfcafdcc''。'};
disp('%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%')
disp(menu)
disp('%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%')

图3.2算术编码仿真主界面
上图显示的是静态型算术编码的主界面，按要求输入字符串，例如’abcdef’。由于在转化为二进制时受限于字长，因此输入的字符串长度要适宜。

（2）编码程序段
for i=1:k %开始算术编码
if i==1 %为字符串的第一个字符编码，a1,a2分别表示个字符串区间的端点
switch 1 %用“开关语句”检测是什么字符，在做相应的编码处理
case string_s(i)=='a'
a1=0;
a2=0+pa;
case string_s(i)=='b'
a1=pa;
a2=pa+pb;
case string_s(i)=='c'
a1=pa+pb;
a2=pa+pb+pc;
case string_s(i)=='d'
a1=pa+pb+pc;
a2=pa+pb+pc+pd;
case string_s(i)=='e'
a1=pa+pb+pc+pd;
a2=pa+pb+pc+pd+pe;
case string_s(i)=='f'
a1=pa+pb+pc+pd+pe;
a2=1;
end
l=a2-a1; %计算各字符串编码区间的长度
end
if (i>=2)&&(i<=k) %在第一个字符已编码的基础上为后续字符编码
switch 1
case string_s(i)=='a'
aa=a1;
ab=a1+l*pa;
a1=aa;a2=ab;
case string_s(i)=='b'