信息传输基础07课件

1、4 统计编码统计编码主要内容1基本原理基本原理2霍夫曼编码3游程编码4算术编码5基于字典的编码6哥伦布编码4.2 霍夫曼编码 1925-1999 戴维霍夫曼，数学家，计算机科学领域的先驱。霍夫曼一生中作出的重要贡献有：有限状态机，开关切换电路，综合程序，信号设计等。 霍夫曼在MIT一直工作到1967年。之后他转入加州大学的Santa Cruz分校，是该校计算机科学系的创始人，19701973年任系主任。1994年霍夫曼退休。霍夫曼码的编码定理 【定理4.3】 在变长编码中，若各码字长度严格按照所对应符号出现概率的大小逆序排序，则其平均长度为最小。 按上述定理可得霍夫曼码的编码步骤： 1）将信源

2、符号出现概率按照减小的顺序排列； 2）将两个最小的概率进行组合相加，并继续这一步骤，始终将较高的概率分支放在上部，直到概率达到1.0为止； 对每对组合中的上边一个指定为1，下边一个指定为0（霍相反，对上边一个指定为0，对下边一个指定为1）； 画出由每个信源符号概率到1.0处的路径，记下沿路径的0和1； 对于每个信源符号都写出1、0序列，则从右到左就得到了霍夫曼码例4-6 对一个7符号信源 ，其霍夫曼编码如图4-6127,Aa aa另例关键在每一步，总是将最低概率的两个符号构成一对关键在每一步，总是将最低概率的两个符号构成一对两种霍夫曼编码的异同 对一个5符号信源 ，其霍夫曼编码如下图所示 请使

3、用霍夫曼码进行编码 采用两种方式进行编码； 求其平均码长；125,Aa aa12345()0.10.1XaaaaaP X两种霍夫曼编码的异同 引入码字长度偏离平均码长的方差的概念： 方差小的编码方法得到的码字结构更紧凑，码的变化小， 22521iiiiElLp alL霍夫曼码的编法并不唯一 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可以得到不同的码字。 不同的码元分配，得到的具体码字不同，但是平均码长不变4.2.2 信源编码基本定理 例4-7：对于二值图像，如传真机，输出非“黑”即“白”，有 ，其概率与所传文件有关，假设对某页文件，有12,Xx x

4、白，黑10.9P x20.1P x不考虑信号间的关联时，其信息熵为：0.9 log0.90.1 log0.10.469H Xbit pel 此时霍夫曼编码无压缩作用1146.9%H Xl编码效率为基本途径之四： 如果把X延长后在对K元组（K为延长长度）进行编码，那么只要K足够大，则代表每消息单元X的平均符号个数 可以任意趋向于小界l K【定理4.4（信源编码的基本定理）】设如果要求码字单义可译，则也叫作无失真编码的基本定理 121212,;,1,2, ;mKnKnKiiiAa aaXXx xxWWw wwlP wP xP WP win的延长；的延长，其平均长度为 ；，()1loglogH Xl

5、H XmKmK例4-8 把例4-7中的码元延长到X2，此时可以获得图4.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.00111000W 2 010110111W 2平均长度为:l2 =0.81+0.092+0.093+0.013=1.29 bit/pelW 2的每一个元素代表两个消息单元,因此平均每一个消息单元的符号个数是:l2 /2 = 1.29/2 = 0.

6、645 bit/pel2 =H(X)/ l2=72.7 %编码效率提高到:图4.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 3111111111011101110101100011100把把 X

7、延长到延长到 X 3 ，有图有图4.8所示所示 X 3 的最佳编码：的最佳编码：W 3平均长度为: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=88.0 %编码效率提高到:还能经一步压缩码？还能经一步压缩码？H(X, Y )H(X)+H(Y)(3.2-13)H(X | Y )H(X)(3.2-11b)或:要求知道P(X), P(X,Y) 或 P(X|Y) 才能进行最佳编码。信源编码理论

8、 给定消息单元集合X、符号集合A和X的概率分布P(X)， 可以采用最佳编码，使代码W 的平均长度满足; 如果把X 延长至 X K ,则不必考虑信号前后的关联性, 就可以是代表一个消息单元的符号个数 l /K 任意接近 下限 H(X)/logm; 如果利用延长信号X K的前后关联,可使下限减小。1log)(,log)(mXHmXHl静态统计模型 在编码前统计要编码的信息中所有字符的出现概率，然后根据统计出的信息建立编码树，进行编码 。 对数据量较大的信息，静态统计要消耗大量的时间； 必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必

9、须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）； 静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。缺点 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 constan

10、tly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。自适应模型将自适应模型与霍夫曼编码结合起来的问题是重建霍夫曼树是一个非常昂贵的过程。为了让自适应方案高效，有必要在每一个字符出现之后调整霍夫曼编码。直到霍夫曼编码第一次开发的 20 年之后，执行自适应霍夫曼自

11、适应霍夫曼编码编码的算法都没有发布。即使在现在，最好的自适应霍自适应霍夫曼编码夫曼编码算法仍然相当耗时间和金钱。主要内容1基本原理基本原理2霍夫曼编码3游程编码4算术编码5基于字典的编码6哥伦布编码4.3 游程编码游程长度(RL: Run Length,简称游程或游长)： 由字符(或信号采样值)构成的数据流中各字符重复出现而形成的字符串的长度。用二进制码字给出形成串的字符、串的长度及串的位置等信息，以此来恢复出原来的数据流。是在控制论中对于二值图像而言是一种编码方法，对连续的黑、白像素数(游程)以不同的码字进行编码。 游程长度编码(RLC)：基本的RLC压缩方法：最初出现在 IBM 3780

12、BYSYNC (Binary Synchronous Communication)通信协议中。基本的RLC数据结构：XScRL数 据 流图4.9 基本的RLC数据结构游程编码的压缩效能平均重复长度重复出现10次的压缩比重复出现20次的压缩比重复出现30次的压缩比重复出现40次的压缩比重复出现50次的压缩比41.0101.0201.0311.0421.05351.0201.0421.0641.0731.11161.0311.0641.0991.1361.17671.0421.0871.1361.1901.25081.0531.1111.1761.2501.33391.0641.1361.2201.3161.429101.0751.1631.2661.3841.538表4.2 基本的游程编码压缩比二值图像的编码过程 先对图像进行统计分别得出白长为 i 的 概率 PiW 和黑长为 i 的概率 PiB， 然后根据霍夫曼原则按RL出现概率来分 配码字。二值图像的RLC实为霍夫曼码的具体应用修正霍夫曼编码MH编码规则: (见表4.3) RL=063，