数据压缩第3章统计编码.ppt

《数据压缩第3章统计编码.ppt》由会员分享，可在线阅读，更多相关《数据压缩第3章统计编码.ppt（125页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三章第三章 统计编码统计编码数据压缩的类型可逆的无失真编码可逆的无失真编码不可逆的有失真编码不可逆的有失真编码大多数计算机文件不允许在压缩过程中丢失信息。大多数计算机文件不允许在压缩过程中丢失信息。利用消息或消息序列出现概率的分布特性，注重寻找概率与利用消息或消息序列出现概率的分布特性，注重寻找概率与码字长度间的最优匹配。码字长度间的最优匹配。语音、图像或其他物理过程的量化采样。语音、图像或其他物理过程的量化采样。本章讨论的内容对于计算机文件对于计算机文件逻辑压缩逻辑压缩(Logical Compression)物理压缩物理压缩(Physical Compression)由数据自身特点及设计

2、者技巧来决定的由数据自身特点及设计者技巧来决定的“压缩表示法压缩表示法”，这种技巧在数据库的数据结构设计中特别有效。，这种技巧在数据库的数据结构设计中特别有效。减少计算机文件内部冗余度的统计编码方法。减少计算机文件内部冗余度的统计编码方法。本章讨论的内容1基本原理基本原理2霍夫曼编码霍夫曼编码 3游程编码游程编码 4算术编码算术编码 本章内容本章内容5基于字典的编码基于字典的编码 唯一可译码的构造4.14.1 基本原理基本原理 文件的冗余类型 编码器的数字描述 变长码的基本分析 唯一可译码的存在计算机文件字符集合(如文本);二进制符号集合(如数据);压缩必须“透明”，恢复后的文件不允许有任何失

3、真。文件的冗余度类型本节所指的冗余度，专指对数据解释一无所知时由数据流中即可观察到的，与具体应用背景无关的冗余。了解文件的冗余度，意在考虑有针对性的编码方法。冗余类型 字符分布(Character Distribution)字符重复(Character Repetition)在典型的字符串中，某些符号要比其他符号出现的更频繁，在一份具体的文件中字符不会以等概率出现，字符的分布明显地因文件而异，影响到字符的统计特性。对于字符重复所形成的符号串常常有更紧凑的编码方式，例如：格式化文件中的空白、报表中的空格串和零串、业务图表中的线图包含成片的空白等。高使用率模式(High-usage Pattern

4、s)位置冗余(Positional Redundancy)这四类冗余度之间有重叠某些符号序列会以较高的频率反复出现，可用较少的位数表示，从而得到时间和空间的净节约。若某些字符总是在各数据块中可预见的位置上出现，那么这些字符至少是部分冗余的，例如：光栅扫描图像中含有的竖线、报表文件中的某些字段的记录几乎总是相同的等等。图3.1 一份零件报表中的冗余度的类型零件名:HEX NUT 1/4 20说 明:STEEL,STANDARD THREAD颜色码:仓 库:45th STREET货 位:4R9存货量:0020再进货量:0010文字长度可变,字母分布不同;空字段同样的名字在文件中多次出现;数值字段,

5、有限的字符变化;编码器的数字描述X=x1,xnW=w1,wnA=a1,am编码器图3.2 编码器的描述实际信源的编码过程 消息集X：元素 x 叫做信号单元或消息；输出集W(代码、码组或码书)：元素 w叫做码字；码字的符号集A：元素 a 叫做码元或者符号 以符号 A 构建代码 W;建立 XW 对应关系;编码过程例3-1X=x1,x2,x3,A=0,1,W=w1,w2,w3A2=00,01,10,11假设用构成代码W,W 到 A2 的映射关系为 (完成步骤):R1=(w1,01),(w2,10),(w3,11)R2=(x1,w1),(x2,w2),(x3,w3)建立X 与 W 的映射关系为 (完成

6、步骤):若xi(dk,dk+1,1in,0kJ-1,为一模拟信号,该编码器实际就是一个量化器。编码，就是将不同的消息用 不同的码字来代替，或称为从消息集到码字集的一种映射(分组编码或块码的概念)。码长:组成码字的符号个数,Li=2,1i3,等长(或定长)编码:采用相同长度的不同码字去 代表一个消息集合中的不同消息;M元编码(或M进制):取M个不同字符来组成码字,最常用的有二元编码(或二进制)。变长码的基本分析对一个消息集合中的不同消息，采用不同长度的码字表示。不等长(或变长)编码：采用变长码可以提高编码效率，即对相同的信息量所需的平均编码长度可以短一些。平均码长：对对P(aj)大的大的aj 用

7、短码用短码;对对P(aj)小的小的aj 用长码用长码;当这些信息符号互不相关时当这些信息符号互不相关时,平均码长比等长编码的码长短平均码长比等长编码的码长短1843年，莫尔斯电报码：表3.1莫尔斯码莫尔斯码的形成:首先找到各消息符号的统计特性:再根据各符号出现的概率分布分 配不同长度的码字:变长码在编码时要预先知道各种信息符号出现的概率，解码也远比等长码复杂:正确识别码字起点不容易;存在唯一可译性问题;译码实时性问题;匀速输入输出匹配的缓存问题;定义定义 3-1若W 中任一有限长的码字序列(即有限长的一串W),可唯一地分割成一个一个码字,称为单义可译或唯一可译的,W 也叫做单义代码。单义可译码

8、例3-2考虑以下几种变长码：码A不是一一对应;码B是一一对应，但构成的序列不能被唯一分割;01110(0,1,1,1,0)(0,1,11,0)(0,11,1,0)(0,111,0)100111011010(10,0,111,0,110,10)码C是唯一可译的;码D是在码B各码字(除了w1)之前加一个码元“0”,成为唯一可译的,但平均码长增加0.5bit;码F 即使从尾开始判断,也不是唯一可译的;101111010(10,111,10,10)(101,111,0,10)问题:什么样的码才是唯一可译的?码E的译码要求等到收到全部序列,才能从尾开始进行判决,产生了时间上延时和存储容量的增加;0111

9、111 111(a1 1111)(a2111)(a311)唯一可译码的存在目前还没有一个明确的判断唯一可译码的准则,只有一个判断不是唯一可译码的准则。定理 3.1(Kraft不等式)长度为L1,L2,Ln 的 m 进制唯一可译码存在的充分必要条件是:含义：要求 Li 比较大(码长不能过短)，意味着码字可能的组合数多,不为别的码字的字首。(3.1-1)Kraft不等式：只涉及唯一可译码的存在问题而并不涉及具体的码。可用来判定某一组码不是唯一可译的，但不能判定是唯一可译的。不满足Kraft不等式的码肯定不是唯一可译码，而满足的也不一定就是唯一可译的，但可以肯定若按这样的Li 分配码组，则必存在有一

10、个唯一可译码(也可能不止一个)对应于信源符号。例3-3对于例3-2问题:如何来确定码字长度?如何在确定了码字长度后找出唯一可译码?定理 3.2(按符号)变长编码定理)对于符号熵为H(X)的离散无记忆信源进行m 进制不等长编码,一定存在一种无失真编码方法,其码字平均长度 l 满足:(3.1-2)小于上限的单义代码总是存在的。当m=2，有(二进制编码定理):此时l 叫编码速率,有时又叫比特率。对于m进制的不等长编码的编码速率定义为：(3.1-4)(3.1-3)定理3.2改述为：若H(X)R H(X)+,就存在唯一可译的变长码;若R 1.75 码长的一种设计为:L1=1,L2=2,L3=L4=3满足

11、上述码长设计的码如：例3.2中的码C、E、F（满足Kraft不等式）。如何做出具体的变长码是变长码的构造问题。唯一可译码的构造唯一可译码的基本要求:码字非续长对码字序列能做出唯一正确的分割。充分条件若W 中任一码字都不是另一个码字的字头；或换句话说,任一码字都不是由另一个码字加上若干个码元所构成，则W 就叫作非续长码字或异字头码(Prefix Condition Code)。定义 3-2码字非续长例3.2中:码A、码B、码D、码E和码F都含有续长码，或同字头码；码C是异字头码。不过非异字头码也并非一定不是唯一可译，码D和码E就唯一可译；码D：各码组靠“逗号”（码元0）分开；码E：为码C的“镜像

12、”，具有“异后尾”，从 后向前即具有唯一可译性。异字头条件保证译出的码字是唯一的且具有“即时性”，减少了译码延时。异字头性质只是码字可分离的充分条件，非续长码也只是单义可译代码集合的一个子集。单义可译码非续长码图3.3 单义可译码与非续长码二进制编码通常可用二进码树(二叉树)来表示各码字的构成(根)(节点)图3.4 二进码树C(节点)D(节点)串接的最大枝数为树的节数，图3.4的节数为3。用码树表述任何一个代码W,异字头条件就成为:W中所有的码字 wi 均只对应地配置在终端节点上。图3.5 码C的树结构(异字头码)根001110010110111根011100(011)(111)11(0)(0

13、1)码E的树结构(非异字头码)此时码C为用尽的异字头码,有:倘若有一码字为(0,10,110),则该码为非用尽的异字头码,有:按照Kraft 不等式的要求，对n个消息x1,x2,xn分配了编码长度L1,L2,Ln,即可用二进码树来生成异字头码,生成规律是:从根出发开始生出2枝;每一枝用一个码元aj A=0,1来表示;枝尽节来,节外生枝;在第Li级端节点(Li级节点共有2Li个)上,配置信 号单元 xi,i=1,2,n;从根开始直奔对应的端节点,沿途(联枝)所遇到 的码元 aj 所构成的符号,即为对应于该信号单元 xi 的码字 wi。异字头码无译码延时，构造简单。结论：任一唯一可译码，总可以用与

14、各相应码字长度一样的异字头码代替。异字头码虽然只是唯一可译码的一种，但它具有代表性和普遍意义，在信息保持编码中广泛应用。长度为L1,L2,Ln的M进制异字头码存在的充要条件，也使Kraft不等式成立。3.2 霍夫曼编码1952年，霍夫曼(D.A.Huffman)提出霍夫曼编码,又称最佳编码根据字符出现概率来构造平均长度最短的异字头码字。霍夫曼码的构造理论基础定理3.3在变长编码中,若码字长度严格按照所对应符号出现概率的大小逆序排列,则其平均长度最短。例3-6对一个7符号信源A=a1,a2,a7,求其霍夫曼编码信源符号 出现概率 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a

15、5 0.15 a6 0.10 a7 0.01 码长 码 字 2 11 2 10 3 011 3 010 3 001 4 0001 4 00000.26010.11010.35010.390110.61101.000编码步骤：将信源符号概率按递减顺序排列将信源符号概率按递减顺序排列;将两个最小的概率进行相加，并继续这一步骤，直到概率将两个最小的概率进行相加，并继续这一步骤，直到概率 达到达到1.0为止为止;在每对组合中的上部指定为在每对组合中的上部指定为1(或或0),下部指定为下部指定为0(或或1);画出每个信源符号概率到画出每个信源符号概率到1.0处的路径处的路径,记下沿路径的记下沿路径的1和

16、和0;对于每个信源符号都写出对于每个信源符号都写出1 1、0 0序列，则序列，则从右到左从右到左就得到霍就得到霍 夫曼编码。夫曼编码。011a3根例3-6的Huffman二进码树11a110a2010a4001a50001a60000a7例3-6的信源熵为:霍夫曼编码的平均字长为:编码效率:注意：在哈夫曼编码过程中，对缩减信源符号按概率注意：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，由大到小的顺序重新排列时，应使应使合并后的新符号尽合并后的新符号尽可能排在靠前的位置可能排在靠前的位置，这样可使合并后的新符号重复，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用

17、编码次数减少，使短码得到充分利用。Huffman编码和译码过程编码和译码过程编码输出Huffman码流Huffman码表传输接收的Huffman码流缓冲器信源符号序列解码解码后的字符序列Huffman码表 信源编码基本定理霍夫曼编码变长的代码(只能分配接近log2pj的整数长码字)定长的数据段当信源符号的概率 pj=2-k编码效率等于100%例3-7:对于二值图像，如传真机文件，输出非“黑”即“白”，有：X=x1，x2=白，黑，其概率与所传文件有关，假设对某页文件，有P(x1)=0.9,P(x2)=0.1。不考虑信号间的关联时，其信息熵为：此时W=0,1，无论用定长码还是最佳编码,平均码长至少

18、为l1=1(bit)；此时霍夫曼编码无压缩作用编码效率为1=H(X)/l1=46.9%解决办法:定理3.4(信源编码定理):A=a1,am;X K -X=x1,xn 的延长;W K-W=w1,wn 的延长,其平均长度为lK;P(wi)=P(xi),P(W)=P(wi),i=1,2,n;如果要求W K 为单义代码,则:(3.2-1)式(3.2-1)也叫做无失真编码的基本定理。含义：如果我们把 X 延长后再对 K 元组(K 为延长长度)进行编码，那么不必利用数据前后的关联，只要K 足够大，则代表每消息单元 X 的平均符号个数l/K 可以任意趋向于下限。例3-8:利用最佳编码,以例4-7来说明l/K

19、趋向于下限的情况。把 X 延长到 X 2 ，假定信源是离散无记忆信源，有图3.7所示 X 2 的最佳编码：图3.7 2单元延长信号的最佳编码P(x1,x1)=P(x1)P(x1)=0.81P(x1,x2)=P(x1)P(x2)=0.09P(x2,x1)=P(x2)P(x1)=0.09P(x2,x2)=P(x2)P(x2)=0.010.100.191.00111000W 2 010110111W 2平均长度为:l2=0.81+0.092+0.093+0.013=1.29 bit/pelW 2的每一个元素代表两个消息单元,因此平均每一个消息单元的符号个数是:l2/2=1.29/2=0.645 bi

20、t/pel2=H(X)/(l2/2)=72.7%编码效率提高到:把 X 延长到 X 3 ，有图3.8所示 X 3 的最佳编码：图3.8 3单元延长信号的最佳编码P(x1,x1,x1)=0.729P(x1,x1,x2)=0.081P(x1,x2,x1)=0.081P(x2,x1,x1)=0.0810.0100.109111000P(x1,x2,x2)=0.009P(x2,x1,x2)=0.009P(x2,x2,x1)=0.009P(x2,x2,x2)=0.0010.0180.0280.1620.2711.0000111001W 3111111111011101110101100011100W 3

21、平均长度为:l3=0.729+0.08133+5(30.09+0.001)=1.598 bit/pelW 3的每一个元素代表三个消息单元,因此平均每一个消息单元的符号个数是:l3/3=1.598/3=0.5327 bit/pel3=H(X)/(l3/3)=88.0%编码效率提高到:继续下去,就可使 lK/K 0.469,或=100%进一步减小 l/K,利用信号的前后关联减小下限,即利用:H(X,Y)H(X)+H(Y)H(X|Y)H(X)或:可以减小下限,从而减小l/K要求知道P(X),P(X,Y)或 P(X|Y)才能进行最佳编码。如果信号继续有关联可供利用，继续延长，会使下限变得很小。信源编码

22、理论：给定消息单元集合X、符号集合A和X的概率分布P(X)，可以采用最佳编码，使代码W 的平均长度满足;如果把X 延长至 X K,则不必考虑信号前后的关联性,就可以是代表一个消息单元的符号个数 l/K 任意接近 下限 H(X)/logm;如果利用延长信号X K的前后关联,可使下限减小。具体实现时，如果将信号延长得过长，会使实际设备复杂到不合理的程度。霍夫曼编码选择模型静态统计模型 在编码前统计要编码的信息中所有字符的出现概率，然后根据统计出的信息建立编码树，进行编码。缺点：对数据量较大的信息，静态统计要消耗大量的时间；必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且

23、，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）；静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。一种有效的“静态统计模型”的替代方案 如果要压缩的所有信息在分布上存在着共同的特征，使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。这种方

24、案除了适应性不太强以外，偶尔还会有一些尴尬的时候。缺点：If Youth，throughout all history，had a champion to stand up for it；to show a doubting world that a child can think；and，possibly，do it practically；you wouldnt constantly run across folks today who claim that a child dont know anything.-Gadsby by E.V.Wright,1939.发现什么问题了吗？整段话

25、中竟没有出现一次英文中出现频率最高的字母 e。对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。自适应模型无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。根据已经编码的符号频率决定下一个符号的编码。算术编码、字典编码等更为适合采用自适应模型 但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率

26、的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树，霍夫曼码的局限性霍夫曼编码文本文件压缩二进制文件压缩适用于经过符号合并局限性:输入符号数受限于可实现的霍夫曼码表尺寸;译码复杂度;需要知道输入符号集的概率分布；由于码长不等，还存在一个输入与输出的速率 匹配问题。3.3 游程编码游程长度(RL:Run Length,简称游程或游长)：由字符(或信号采样值)构成的数据流中各字符重复出现而形成的字符串的长度。用二进制码字给出形成串的字符、串的长度及串的位置等信息，以此来恢复出原来的数据流。游程长度编码(RLC)：游程编码类型：变长游程编码变长游程编码使用位数是固定的，即RL位

27、数是固定的，如果灰度连续相同的个数超过了固定位数所能表示的最大值，则进入下一轮游程编码；定长游程编码定长游程编码对不同范围的游程采用不同位数的编码，即表示RL位数不固定。基本的游程编码基本的RLC压缩方法：最初出现在 IBM 3780 BYSYNC(Binary Synchronous Communication)通信协议中。基本的RLC数据结构：XScRL数 据 流图3.9 基本的RLC数据结构其中X：代表数据字符；Sc：Sc X，表示有一个字符在此位置；RL：代表串（游程）的长度，字符重复出现的次数；只有当RL 3时,才有数据压缩效益。编码时：先判断RL值，再决定是否RLC；解码时：根据每

28、一X后的码字是否为Sc，再 决定下一个字的含义。Assumption:Long sequences of identical symbols.Example,RLC压缩效能:取决于数据流中重复字符出现次数、平均游程长度及所采用的编码结构。表3.2 基本的游程编码压缩比 二值图像的游程编码二值图像仅有黑(“1”代表)、白(“0”代表)两个亮度值的图像。经扫描仪得到的气象图、工程图、地图、线 路图等；文字组成的文件图像；灰度图像经过位平面分解或抖动处理后 的图像。最常用的传输方式：传真二值图像编码也往往指数字传真编码。二值图像的游程编码数据字符 X=白，黑对二值图像每一扫描行：白像素游程（白长）黑

29、像素游程（黑长）对不同长度的白长和黑长，按其出现概率的不同分别配以不同长度的码字。RLC利用多个像素之间的相关性，可得到较低的码率下限。二值图像的RLC的两种方式 不分白长和黑长，只根据长度进行编码 对白长和黑长分别编码(前CCITT建议)由于在实际图像中,白长和黑长的概率分布各异,此方法不是很有效;其最低比特率 满足:(3.3-1)其中：PW和PB分别是白像素和黑像素出现的概率;lW和lB分别是白长和黑长的平均像素数(平均长度);hWB为每个像素的熵值。编码过程：先对图像进行统计分别得出白长为 i 的 概率 PiW 和黑长为 i 的概率 PiB，然后根据霍夫曼原则按RL出现概率来分 配码字。

30、二值图像的RLC实为霍夫曼码的具体应用由于各种 RL 的出现概率在行间、页间都不相同，且为求得概率，需要存储数据并做统计计算，难以实时编码CCITT的T.4建议:推荐8幅标准传真样张为统计依据,根据各种RL的出现概率编出霍夫曼码表，称为改进型霍夫曼编码改进型霍夫曼编码(MHC)。MH编码规则:(见表4.7)RL=063，用一个相应的结尾码表示;RL=641728，用一个组合基干码加一个补充结尾码；RL(白)=128,补充结尾码为0(白)=00110101,其编码为:10010|00110101 RL(白)=129,补充结尾码为1(白)=000111,其编码为:10010|000111 规定每行

31、都从白游程开始，若实际扫描由黑开始，则 需在行首加零长度白游程；每行结束要加同步码EOL。游程编码的局限性 对二值图像最为有效，但对数据文件就不那 么显著，而对于课文实质已无使用价值;压缩字符与数值混合序列比较麻烦，要求区分 计数字段和常规字符；需要较大容量的缓冲和较低误码的优质信道。连续色调图像的二维编码前面介绍了二值图像的一维前面介绍了二值图像的一维MH编码，但对于多值或编码，但对于多值或连续色调图像，黑白游程已不适用，而基本连续色调图像，黑白游程已不适用，而基本RCL的的3元组也不能直接用。元组也不能直接用。引出前提引出前提JPEG标准的基本系统利用标准的基本系统利用Z型扫描，将二维量化

32、系型扫描，将二维量化系统矩阵转换成了一维数组统矩阵转换成了一维数组ZZ（k），数组的第一个元），数组的第一个元素素ZZ（0）为）为直流系数直流系数DC（在在4.2.3节截断霍夫曼编节截断霍夫曼编码中已经讨论过）码中已经讨论过）；ZZ（1）ZZ（63）元素为）元素为交流交流系数（系数（AC）。编码原理编码原理JPEG将其联合编码表示为将其联合编码表示为“NNNNSSSS+尾码尾码”，“NNNN”为当前非零值相对于前一个非零为当前非零值相对于前一个非零AC系数的系数的零游程计数，表示零游程计数，表示ZRL；这将；这将“NNNN/SSSS”组合为组合为一个新的前缀码，用二维霍夫曼编码。即为一个新的前

33、缀码，用二维霍夫曼编码。即为AC系数系数编码表示形式。编码表示形式。AC编码表示形式编码表示形式连续色调图像的二维编码求求出差分值出差分值DIFFDIFF，查书中，查书中P52P52表表4.24.2即可得即可得前缀码前缀码（用（用标准的霍夫曼编码标准的霍夫曼编码）。）。(1)DC系数编码系数编码若若ZZZZ（k k）为待编码的非零）为待编码的非零ACAC系数，系数，根据根据ZZZZ（k k）的幅度范）的幅度范围由围由P60P60表表4.84.8查出查出尾码的位数尾码的位数B=SSSSB=SSSS，按以下可求得，按以下可求得尾码尾码：(2)AC系数编码系数编码原码，若原码，若ZZZZ（k k）0

34、0反码，若反码，若ZZZZ（k k）015ZRL15，则先用，则先用ZRL=16ZRL=16即即NNNN/SSSS=F/0NNNN/SSSS=F/0得到码得到码字字，再对，再对ZRL=ZRL-16ZRL=ZRL-16继继续编码，得到续编码，得到NNNN/SSSSNNNN/SSSS码字，结合尾码就可得码字，结合尾码就可得ACAC系数编码。系数编码。连续色调图像的二维编码例题：设某亮度图像块的量化系数矩阵按例题：设某亮度图像块的量化系数矩阵按Z形扫描得到：形扫描得到：K 0 1 2 3 4 5 6 7 8 930 31 3263ZZ（k）12 5 -2 0 2 0 0 0 1 0 -1 0 而其前

35、一亮度块的量化而其前一亮度块的量化DC系数也为系数也为12，写出编码过程。，写出编码过程。解解(1)DC系数编码系数编码因为因为DIFF=0，查表，查表4.2得其码字即为得其码字即为前缀码前缀码“00”。(2)AC系数编码系数编码第一个非零值第一个非零值ZZ(1)=5，查表，查表4.8得得SSSS=3，根据规则得尾码为原码，根据规则得尾码为原码101；与；与ZZ(0)间无零系数，故间无零系数，故NNNN=0，NNNN/SSSS=0/3查表查表4.9码字码字100；从而；从而ZZ(1)=5的编码为的编码为“NNNN/SSSS+尾码尾码”即即100+101得得100101。第二个非零值第二个非零值

36、ZZ(2)=-2，SSSS=2，尾码为反码，尾码为反码01；又与；又与ZZ(1)无零系无零系数，所以数，所以NNNN/SSSS=0/2查表得码字为查表得码字为01；从而；从而ZZ(1)ZZ(2)编码为编码为0101。ZZ(3)ZZ(4)编码为编码为1101110。ZZ(5)ZZ(8)编码为编码为1110101。连续色调图像的二维编码例题：设某亮度图像块的量化系数矩阵按例题：设某亮度图像块的量化系数矩阵按Z形扫描得到：形扫描得到：K 0 1 2 3 4 5 6 7 8 930 31 3263ZZ（k）12 5 -2 0 2 0 0 0 1 0 -1 0 而其前一亮度块的量化而其前一亮度块的量化D

37、C系数也为系数也为12，写出编码过程。，写出编码过程。ZZ(31)=-1，查表得，查表得SSSS=1，尾码为反码，尾码为反码0；由于；由于NNNN=30-9+1=2215，故先编，故先编ZRL=16，NNNN/SSSS=F/0查表得码字；此后查表得码字；此后NNNN=22-16=615再编码，再编码，NNNN/SSSS=6/1查表得码字为查表得码字为1111011；所以；所以ZZ(9)ZZ(31)编码为。编码为。此后无非零值，最直接用一个此后无非零值，最直接用一个EOB结束本块结束本块，查表得码字为，查表得码字为1010。(3)综合前面综合前面(1)和和(2)，可知该图像块的编码为，可知该图像

38、块的编码为 00 100101 0101 1101110 1110101 1010(4)原始图像块要用原始图像块要用8*8*8=512位，压缩后为位，压缩后为49位，压缩比为位，压缩比为10.45:1。游程编码总结游程编码游程编码RCL是一种熵编码。是一种熵编码。（1）RCL仍需与其他前缀码结合才有望达到更仍需与其他前缀码结合才有望达到更好的效果。这种方法对于二值图最有效。好的效果。这种方法对于二值图最有效。（2）RCL仍是变长码，有其固有的缺点，即需仍是变长码，有其固有的缺点，即需要较大容量的缓冲和较低误码的优质信道。要较大容量的缓冲和较低误码的优质信道。（3）3.4 3.4 算算术编码(A

39、rithmetic Coding)3.4.1 多元符号算术编码原理多元符号算术编码原理 3.4.2 自适应模型算术编码自适应模型算术编码 3.4.3 二进制算术编码二进制算术编码 3.4.4 二进制算术解码二进制算术解码 3.4.5 算术编码评价算术编码评价 算术编码算术编码定义定义它是一种非分组编码算法。它是从全序列出发，采用递推形它是一种非分组编码算法。它是从全序列出发，采用递推形式的连续编码。它不是将单个的信源符号映射成一个码字，式的连续编码。它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据它们的概率映射为实数轴上而是将整个输入序列的符号依据它们的概率映射为实数轴上区间

40、区间0 1)0 1)内的一个小区间，再在该小区间内选择一个代表性内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出。的二进制小数，作为实际的编码输出。例如算术编码对某条信息的输出为例如算术编码对某条信息的输出为 1010001111，那么它表示，那么它表示小数小数 0.1010001111，也即十进制数，也即十进制数 0.64。85 3.4.1 3.4.1 多元符号算术编码多元符号算术编码1)码字刷新：码字刷新：C(sai)=C(s)+P(ai)A(s)2)区间刷新：区间刷新：A(sai)=p(ai)A(s)设输入符号串设输入符号串s取自符号集取自符号集S=a1,a2

41、,a3,am，p(ai)=p1,p2,p3,pm，s后跟符号后跟符号ai扩展成符号串扩展成符号串sai，算术编码的迭代关系为算术编码的迭代关系为:符号累积概率：符号累积概率：初始条件：初始条件：一、一、算术编码算术编码 多元符号算术编码多元符号算术编码当处理当处理ai时，区间时，区间A(s)宽度根据宽度根据ai出现概率出现概率p(ai)而变而变窄，符号序列越长，相应的子区间越窄，编码的位窄，符号序列越长，相应的子区间越窄，编码的位数越多。符号串每一步新扩展的码字数越多。符号串每一步新扩展的码字C(sai)都是由原都是由原符号串的码字符号串的码字C(s)与新区间宽度与新区间宽度A(sai)的算术

42、相加，的算术相加，“算术码算术码”由此得名。由此得名。算术编码在传输任何信号算术编码在传输任何信号ai之前，信号的完整范围是之前，信号的完整范围是多元符号算术编码多元符号算术编码例例题题1：设设某某信信源源取取自自符符号号集集S=a,b,c,d,e,!，!表表示示编编码码结结束束，各各符符号号概概率率和和初初始始子子区区间间如如下下，设设待待编编码码的的为为“dead！”，编码器和解码器的初值区间，编码器和解码器的初值区间0，1)表表1多元符号算术编码多元符号算术编码编码第一个字符编码第一个字符d时时编码第二个字符编码第二个字符e时时 多元符号算术编码多元符号算术编码编码第三个字符编码第三个字

43、符a时时 依此类推，结果如下表依此类推，结果如下表 多元符号算术编码多元符号算术编码最后在区间最后在区间0.61804,0.6184)中任取一个代中任取一个代表性的小数，譬如表性的小数，譬如0.6183，转化成二进制，转化成二进制小数小数0.1001111，最后编码输出，最后编码输出1001111。91多元符号算术编码多元符号算术编码编码多元符号算术编码多元符号算术编码二、二、算术解码算术解码解码器首先输入符号及区间，重构解码器首先输入符号及区间，重构表表1.然后输入其然后输入其余码字。比如第一个数字是余码字。比如第一个数字是“6”，解码器立即知，解码器立即知道是形如道是形如0.6的数字。该数

44、字位于的数字。该数字位于d的子区间的子区间0.4,0.7)中，所以第一个符号就是中，所以第一个符号就是d。然后从该数字。然后从该数字中减去中减去d子区间的低端值子区间的低端值0.4，再除以，再除以d子区间宽度子区间宽度0.3，以消除符号，以消除符号d对码字的影响。结果是对码字的影响。结果是0.727667，告诉解码器下一个符号是，告诉解码器下一个符号是e(因为因为e的子区间是的子区间是0.7,0.9)。93为了从码字中消除符号为了从码字中消除符号x的影响，解码器执行的影响，解码器执行 Code:=(Code-LowRange(x)/Range的操作，的操作，Range是符号是符号x的子区间宽度

45、。表的子区间宽度。表2总结了本例解码步骤。总结了本例解码步骤。表表2 算术解码过程算术解码过程94二进制算术编码二进制算术编码一、基本工作原理一、基本工作原理设编码初始化子区间为设编码初始化子区间为0，1)MPS与与LPS分配如图分配如图 大概率大概率 Pe MPS（Most Probable Symbol）小概率小概率 Qe LPS（Least Probable Symbol）Pe=1-Qe 设置（设置（C，A）,令令C=0 A=1 C 寄存器的值为子区域的起始位置寄存器的值为子区域的起始位置 A 寄存器的值为子区域的宽度寄存器的值为子区域的宽度9596例题例题1:设输入信源为设输入信源为1

46、1011111，对其编码，对其编码0为为 LPS,Qe=（0.001）b;1为为MPS,Pe=（0.111）b初始状态：初始状态：C=0,A=11)1 为为MPS C=C+AQe=0+1 0.001=0.001 A=APe=1 0.111=0.1113.4.2 3.4.2 二进制算术编码二进制算术编码0.0010.11197 2)1 为MPS C=C+AQe=0.001+0.111 0.001=0.001111 A=APe=0.111 0.111=0.1100010.0011110.1100013.4.2 3.4.2 二进制算术编码二进制算术编码3)0 为LPS C=C=0.001111;A=

47、A Qe=0.110001 0.001=0.0001100010.0011110.00011000198 头头 0.0101 orign_len+1)7.Di 1=Di 1+ch;8.Di=Dk;/*生成本行字符串的前一部分*/9.write(Dk);/*输出还原后的数据*/10.i:=i+1;p压缩码为：1,2,4,3,5,1,9,10 n首先将单字符放入字典。a 1b 2c 3 norign_len=length(D)=3;n i=orign_len+1=4;n read(k);k=1;n ch=first_char(Dk)=a;ni orign_len+1 nD4=D1;i=i+1=5a

48、 4 LZW解压缩算法p压缩码为：1,2,4,3,5,1,9,10 a 1b 2c 3 a 4 ni=5nread(k);k=2;nch=first_char(Dk)=b;n i orign_len+1 n Di 1=Di 1+ch，即，D4=ab;nD5=D2=b;ni=i+1=6;bb 5 LZW解压缩算法n压缩码为：1,2,4,3,5,1,9,10 a 1b 2c 3 ab 4 b 5 pi=6pread(k);k=4;pch=first_char(D4)=a;p i orign_len+1 p Di 1=Di 1+ch，即，D5=ba;pD6=D4=ab;pi=i+1=7;aab 6 n剩下的以此类推。LZW解压缩算法例4-15p设有输入字符流“ababcbababaaaaaaa”，试对其进行LZW编码。习题与思考题 习题：4.2思考题：4-12