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

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

过本课程设计可以实现从键盘随意输入待传输信息，根据算术编码原理输出编码结果，如果选择译码，会输出之前输入的传输信息关键词 ： 算术编码 译码 MATLAB仿真目 录一、信源编码 11.1 信源编码的概念 11.2 信源编码简介 11.3信源编码的目的： 21.4信源编码的原理 2二、算术解码的理论基础 72.1 算术编码算法的基本原理 72.2算术编码的特点 72.3 算术编码的分析过程 82.4算术编码举例 9三、算术编码MATLAB仿真实现 153.1 MATLAB 仿真程序实现 153.2仿真设计流程图 153.3 算术编码仿真设计 163.4结果分析 21设计总结 21参考文献 232一、 信源编码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。