电子科技大学信息论第4章 数据压缩.ppt

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