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

******************实践教学*******************计算机与通信学院通信系统仿真训练题目：基于算术编码的信源编码/解码系统设计与仿真信源编码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×rangelow

High=low+range×rangehigh

其中等号右边的low为上一个被编码字符的范围低；rangelow和rangehigh分别为被编码符号已给定的字符出现概率范围的low和high。

（2）对消息第一字符s编码：s的rangelow=0.6，s的rangehigh=0.7因此，下一个区间的low和high为：

Low=low+range×rangelow=0+1×0.6=0.6

High=low+range×rangehigh=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的rangelow=0.7,rangehigh=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的rangelow=0.10,rangehigh=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的rangelow=0.70,rangehigh=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.0753032079，然后用s的范围range=0.1去除所得到的0.0753032079，即得到0.753032079，接着找出它所在的区间，就是t的原来范围[0.7,1.0）。去掉t的下界值0.7，得0.053032079，然后用t的range=0.3除该数得出0.17677202，该值所属范围就是字符a……如此操作下去便得到消息的准确译码综述，可以得到解码公式为：(Number-rangelow)/range=>number其中，number为符串的编码。算术编码举例在编码之前，假设每个信源符号的频率相等（如都等于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.1MATLAB仿真程序实现MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。MATLAB由一系列工具组成。这些工具方便用户使用MATLAB的函数和文件，其中许多工具采用的是图形用户界面。包括MATLAB桌面和命令窗口、历史命令窗口、编辑器和调试器、路径搜索和用于用户浏览帮助、工作空间、文件的浏览器。随着MATLAB的商业化以及软件本身的不断升级，MATLAB的用户界面也越来越精致，更加接近Windows的标准界面，人机交互性更强，操作更简单。而且新版本的MATLAB提供了完整的联机查询、帮助系统，极大的方便了用户的使用。简单的编程环境提供了比较完备的调试系统，程序不必经过编译就可以直接运行，而且能够及时地报告出现的错误及进行出错原因分析。MATLAB7.1版本是在2005年更新的，本文主要应用MATLAB7.1中发布的影像处理工具箱中的相关函数和命令来实现基于算术编码实现图像压缩理论算法的仿真。MATLAB7.1是一套功能十分强大的工程计算及数据分析应用软件,广泛应用于工业、电子、控制、信号及图像处理等各领域。MATLAB7.1本身除了提供强大的图形绘制和输出功能外,同时还发布了影像处理工具箱(ImageProcessingToolbox),专门用于图像的处理.在通常情况下，可以用它来代替底层编程语言，如C和C++。在计算要求相同的情况下，使用MATLAB的编程工作量会大大减少。3.2仿真设计流程图本课程设计的软件算术编码输入的自符类型固定，每个字符的概率也是固定的。输入的自符类型有“abcdef”每次输入字符，更新字符的起始、终止区间。等最后一个字符编码完成后，取起始值和终至值的中点作为编码的结果输出。译码的时候，读取编码的输出结果，找到所在的区间，依次译出编码前输入的字符信息。完成译码过程；自适应算术编码的概率模型不固定，先统计编码的符号类型，以及每个符号的个数。译码前，假设每个符号的概率是相等的，然后每次输入一个字符，相应的字符概率发生变化，直至编出最后一个码字，选取区间中间结果作为编码的输出，译码时，读取中间结果，找到所属概率区间，译出码字，然后变更概率区间，重新定位码字。直至译出最后一个码字。图3.1算术编码设计流程图上图是算术编码设计流程图，无论是静态型还是自适应型算术编码在编码前都要初始化概率空间，但二者在编码时的概率空间却不一样，前者固定不变，后者概率随输入字符变化而变化。然后进行区间分割，将字符串编成一个浮点小数，然后转化为二进制，作为结果之后选择是否译码，确定是否译出信源符号。3.3算术编码仿真设计、显示主界面程序段menu={...'请按下列要求输入字符串：''1、字符串长度适宜；''2、可以输入的字符仅限于：a,b,c,d,e,f；''3、输入的字符一定要用英文状态下的单引号引起来,例如：''efbfcafdcc''。'};disp('%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%')disp(menu)disp('%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%')图3.2算术编码仿真主界面上图显示的是静态型算术编码的主界面，按要求输入字符串，例如’abcdef’。由于在转化为二进制时受限于字长，因此输入的字符串长度要适宜。（2）编码程序段fori=1:k%开始算术编码ifi==1%为字符串的第一个字符编码，a1,a2分别表示个字符串区间的端点switch1%用“开关语句”检测是什么字符，在做相应的编码处理casestring_s(i)=='a'a1=0;a2=0+pa;casestring_s(i)=='b'a1=pa;a2=pa+pb;casestring_s(i)=='c'a1=pa+pb;a2=pa+pb+pc;casestring_s(i)=='d'a1=pa+pb+pc;a2=pa+pb+pc+pd;casestring_s(i)=='e'a1=pa+pb+pc+pd;a2=pa+pb+pc+pd+pe;casestring_s(i)=='f'a1=pa+pb+pc+pd+pe;a2=1;endl=a2-a1;%计算各字符串编码区间的长度endif(i>=2)&&(i<=k)%在第一个字符已编码的基础上为后续字符编码switch1casestring_s(i)=='a'aa=a1;ab=a1+l*pa;a1=aa;a2=ab;casestring_s(i)=='b'aa=a1+l*pa;ab=a1+l*(pa+pb);a1=aa;a2=ab;casestring_s(i)=='c'aa=a1+l*(pa+pb);ab=a1+l*(pa+pb+pc);a1=aa;a2=ab;casestring_s(i)=='d'aa=a1+l*(pa+pb+pc);ab=a1+l*(pa+pb+pc+pd);a1=aa;a2=ab;casestring_s(i)=='e'aa=a1+l*(pa+pb+pc+pd);ab=a1+l*(pa+pb+pc+pd+pe);a1=aa;a2=ab;casestring_s(i)=='f'aa=a1+l*(pa+pb+pc+pd+pe);ab=a1+l*(pa+pb+pc+pd+pe+pf);a1=aa;a2=ab;endl=a2-a1;%计算各字符串编码区间的长度endenddisp('编码区间的起始值是：');disp(a1)%显示编码区间的起始值disp('编码区间的终止值是：');disp(a2)%显示编码区间的终止值disp('本程序选择区间中点做为编码是：');disp((a1+a2)/2)%显示编码disp('本程序选择区间中点做为编码的二进制编码是：');y=yu((a1+a2)/2,50);图3.3编码仿真上图为静态编码仿真，通过对每一个字符编码，不断地进行区间分割，当编到最后一个字符的时候，选取该字符的区间中点作为编码结果，然后转化为二进制，输出。（3）、译码程序段whilei>=1&i<=k%译码对字符的确认switch1caseym==1bm0=(bm0-0)/pa;decode(i)=new_string(1);caseym==2bm0=(bm0-pa)/pb;decode(i)=new_string(2);caseym==3bm0=(bm0-pa-pb)/pc;decode(i)=new_string(3);caseym==4bm0=(bm0-pa-pb-pc)/pd;decode(i)=new_string(4);caseym==5bm0=(bm0-pa-pb-pc-pd)/pe;decode(i)=new_string(5);caseym==6bm0=(bm0-pa-pb-pc-pd-pe)/pf;decode(i)=new_string(6);endi=i+1;ym=YM(bm0);%调用单个字符译码子程序YM对第二个码元及以后各码元译码end图3.4算术编码译码仿真上图为算术编码译码图示，通过选择是否译码，确定对编码的码字是否译出。按1，则译出编码前输入的信息，得到编码的译码结果。3.4结果分析基于算术编码算法，运行MATLAB程序，算术编码输出结果为0.013706；输入的字符经过算术算法的解码，输出的符号串也是一致的，验证了算术编码算法是一种无失真的熵编码方式。由于在编程中用到了bin2dec函数，它只能将不多于52为的二进制数译成整数，因此输入的符号个数受到限制，否则后产生误码。由于输入的信息过多时，会产生误码，因此可以通过增加二进制位数来补偿误码率问题，但二进制位数前提是不多于52位。，我们知道算术编码是一种无失真的编码方法，能有效地压缩信源冗余度，属于熵编码的一种。算术编码的一个重要特点就是可以按分数比特近信源熵，突破了Haffman编码每个符号只不过能按整数个比特逼近信源熵的限制。设计总结经过几周的课程设计，让我对我的专业有了更加清楚的认识。当然，在设计的过程中出现了不少问题。例如，在应用算术编码算法的编程上，由于MATLAB编程知识的匮乏，导致编程的最终结果没有完全出来。最终在同学和老师的帮助下，我顺利解决了这些问题。同时，也经过这次自我学习，我学到了很多算术编码算法的知识。在课程设计的的过程中我学习到了很多东西，认识到了信源编码的基本目的是减少信源输出符号序列的剩余度、提高码字序列中码元的平均信息量等等相关知识。在编程的过程中，又一次熟悉了通信系统仿真软件Matlan的基本使用方法，能够在该软件的使用过程中解决随时出现的问题，最重要的是提高了我综合运用所学知识的能力和计算机的编程能力，为今后的工作和学习积累了宝贵的经验，对于以后的毕业设计以及之后的工作都有相当重要的意义。最后，特别感谢在这次课程设计过程中给予我指导和帮助的老师和同学，使我能顺利、按时完成本次课程设计，同时他们给予我的鼓励也使我很感激，在以后的学习生活中，我会以更加积极、乐观的心态去面对困难和挫折。

参考文献[1]郭斌,王维东,叶青青.基于概率估计更新的CABAC加速算法[J].中国图像学报，2009,14（3）：281-285[2]毕厚杰.新一代视频压缩编码标准-H.264/AVC[M].北京：人民邮电出版社，2006:141-147[3]欧阳合，韩军.H.264和MPEG-4视频压缩[M].国防科技大学出版社，2004:226-229[4]冯桂，林其伟，陈东华.信息论与编码技术（第二版）.北京：清华大学出版社，2011.6[5]胡海明,李金良.基于上下文的自适应二阶二进制算术编码算法[J].计算机工程与设计,2008,27（17）:3267-3269[6]余兆明，查日勇，黄磊，周海娇.图像编码标准H.264技术[M].北京：人民邮电出版社，2005:71-92[7]刘奇卫.基于JPEG2000二进制算术编码器的研究与设计[D].[硕士学位论文]浙江大学,2006.[8]贾铸.算术编码算法在图像压缩中的应用.电视技术，1999.11[9]江伟.H.264中基于上下文自适应二进制算术编码效率改进研究[D].[硕士学位论文]中南大学,2010.[10]张德丰.详解MATLAB数字图像处理.北京：电子工业出版社，2010.7[11]冯玉珉,邵玉明,张星.数据图像压缩编码.中国铁道出版社,1993,9:15～60[12]ISO/IECFCD15444-1,JPEG2000ImageCodingSystem,2000[13]曹青,吴乐南.静止图像无失真编码的新标准JPEG－LS.电子工程师.1999,2:12～14[15]陆桂富.H.264中自适应算术编码器的FPGA实现研究[D].[硕士学位论文]上海大学,2006.[16]高展宏,徐文波.基于MATLAB的图像处理案例教程.北京：清华大学出版社,2011.4[17]杨胜天.一个基于算术编码的灰度图象无损压缩算法.计算机工程与科学,2002,24(1):33～36[18]王新年,张涛.数字图像压缩技术实用教程.北京：机械工业出版社，2009.8基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究