信息论第七讲率失真函数.ppt

算术编码是一种二元码的编码方法。在不考虑信源统计的情况下，不管统计是平稳的或非平稳的，编码的码率总能趋近于信源熵，每次迭代时的编码算法只处理一个数据符号，并且只有算术运算。 随着被编码数据流符号的输入，子区间宽度逐渐缩小。表示为数值精度逐渐提高，二进制代码逐渐加长。 新子区间的起始位置=前子区间的起始位置+当前符号的区间左端×前子区间长度； 0.5=0.5+0X0.2; 0.514=0.5+0.7X0.02 最后得到的子区间的长度(一个小数）决定了表示该区域内的某一个数所需的位数。 算术编码在编、译码的过程中，子区间的起始位置和长度值的小数点后的位数越来越长，实际中无法实现。因此较实用的改进算法是限制小数点后的位数。 例如：已知信源X=(0, 1);( 0.25, 0.75)　 试对1011进行算术编码. 最后的子区间起始位置 C＝（0.332）d=(0 b 最后的子区间左端长度 L＝（0d=(0.0111) b 编码取值为0.011　可编码为011 算术编码中需要注意问题： 由于实际计算机精度不可能无限长，运算中溢出是明显的问题，但多数机器都有16位、32位或者64位的精度，因此可使用比例缩放法解决。 算术编码器对消息只产生一个码字，这个码字是在[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错（误码扩散）。 算术编码可以是静态的或者自适应的。 静态算术编码中，信源符号的概率是固定的。 自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。 需要开发算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。 算术编码的特点： 不必预先定义概率模型，自适应模式具有独特的优点； 信源符号概率接近时，建议使用算术编码，这种情况下其效率高于Huffman编码。 算术编码实现方法复杂一些，但JPEG成员对多幅图像的测试结果表明，算术编码比Huffman编码提高了5%左右的效率，因此在JPEG扩展系统中用算术编码取代Huffman编码。 4.5 信源编码综述 算术编码思想： 针对序列进行编码，建立递推关系。 不用二整数代码来表示符号，而改用[0，1)半开区间中实数的二元小数序列来表示。 [0，1)可以分为n个子区间，每个宽度值等于一个符号的先验概率，符号表中的所有符号刚好布满整个[0，1)区间（概率和为1）。 编码过程就是把输入符号串（数据流）映射成[0，1)区间中对应子区间中的一个实数值。 4.5 信源编码综述 算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码。 算术编码用到两个基本的参数：符号概率和它的编码间隔。 编码效率取决于符号概率和编码间隔，编码间隔取决于符号概率和符号相关性，而这些间隔包含在0到1之间。 4.5 信源编码综述 编码举例 假设信源符号为{00, 01, 10, 11}，这些符号的先验概率分别为{ 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)， 二进制序列的输入为：10 00 11 00 10 11 01。 4.5 信源编码综述 4.5 信源编码综述 4.5 信源编码综述 4.5 信源编码综述 新子区间的长度=前子区间的长度×当前符号的概率（等价于范围长度）； 0.02=0.2X0.1; 0.0006=0.006X0.1 4.5 信源编码综述 4.5 信源编码综述 0.0 1.0 0.25 1 0 1 1 0.25 1.0 0.25 0.4375 0.296875 0.4375 00.4375 输出 4.5 信源编码综述 4.5 信源编码综述 4.5 信源编码综述 4.5 信源编码综述 * 4.4 率失真函数(Rate Distortion Function) 引言 上面我们介绍的编码也称为无失真编码（无损编码），另外一类编码称为限失真编码（有损编码）。 率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。 率失真信源编码定理（香农第三定理）指出：率失真函数R (D) 就是在给定失真测度条件下，对信源压缩的最低程度。也就是说：为了提高传输效率，可以给定一个失真度，求出在平均失真小