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

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