第5章 数据压缩.pptVIP

第5章 数据压缩 ①将信源发出消息xk k=1,2,…,Nn按概率降序排列 ②为概率最小的两条消息各自分配一个二进制码元 ③将概率最小的两条消息合并成一条新消息，用两者概率之和作为新消息的概率 1 0 重复① ② ③步骤，直到合并出新消息的概率为1时结束，分配给消息xk的全部码元作为该消息的码字ck k=1,2,…,Nn 1 0 1 0 1 0 * 数据压缩 为什么即时码是最优码？ 构造即时码的基本方法？ 5.1 即时码 定义 1、信源编码 信源符号序列到不等长码序列的映射 表示 不等长离散型随机变量序列C1C2…Cl 2、平均码长 信源各消息码字长度的数学期望，用L表示 定义 表示 信源编码及平均码长 例1 某种信源编码 平均码长 信源的熵 信源编码及平均码长 例2 某种信源编码 平均码长 信源的熵 3、非奇异码 定义 表示 信源发出的每条消息映射为不同的码字——一一对应 4、码的扩展编码 定义 表示 消息串的码字等于消息的码字串 5、唯一可译码 定义 表示 码的扩展编码为非奇异码 唯一可译码——由码字串可唯一译出消息串——自我间断码 6、即时码 定义 码表中无任何码字是其它码字的前缀 即时码可以用树图构造 二进制即时码0,10,11所对应的二叉树图 0 1 0 1 即时码——任何码字结束时即可译出的自我间断码 全体编码 非奇异码 唯一可译码 即时码 例3 11 011 01 1 x3 10 01 1 1 x2 0 0 0 0 x1 即时码 唯一可译码 非即时 非奇异码 非唯一可译 奇异码 例4 左移1位 =0？ =10？ 输出x1 Y 输出x2 Y N N 输出x3 左移2位 结束？ Y N 输入码字串 结束 5.2 克拉夫特不等式 定理 对于二进制即时码，码长l1,l2,…,lNn必定满足不等式 反之，给定满足以上不等式的一组码长，则存在相应的二进制即时码 二进制即时码第k个码字的码长为lk 考虑一棵lmax级二叉满树，在第lmax级共有2lmax个节点，在第lk级共有2lk个节点 根据即时码的定义，对lk≠lmax的第k个码字，在第lmax级不能用的节点数为2lmax-lk，对lk=lmax的第k个码字，第lmax级未用的节点数为1 构造二进制即时码的树图上总共不能用和未用的第lmax级节点总数 0 1 0 1 lmax=2,l1=1,l2=2,l3=2 第2级不能用的节点数为2lmax-l1=22-1=2，未用的节点数为2lmax-l2=22-2=1，2lmax-l3=22-2=1 反之，从树根出发由短及长依次按码长lk生长二叉树枝，即可构造出一颗lmax级二叉树，相应得到二进制即时码 5.3 最优码 定理 二进制即时码的平均码长必定满足不等式 当且仅当2-lk =P(xk) k=1,2, …,Nn，等式成立 对于n次扩展信源 n次扩展信源的编码效率 对于n次扩展信源 n次扩展信源的编码效率 5.4 最优码长的界 定理 二进制即时码的平均码长的取值范围在其下界与下界加1比特之间，即满足不等式 对于n次扩展信源 5.5 赫夫曼码 ①将信源发出消息xk k=1,2,…,Nn按概率降序排列 ②为概率最小的两条消息各自分配一个二进制码元 ③将概率最小的两条消息合并成一条新消息，用两者概率之和作为新消息的概率 编码步骤 重复① ② ③步骤，直到合并出新消息的概率为1时结束，分配给消息xk的全部码元作为该消息的码字ck k=1,2,…,Nn 编赫夫曼码并计算编码效率 例1 * 数据压缩