第4章 数据压缩

1、第第4章章 数据压缩数据压缩第第4章章 数据压缩数据压缩第第4章章 数据压缩数据压缩4.1 即时码即时码1、信源编码信源编码n次扩展信源消息（符号序列）到码表不等长二次扩展信源消息（符号序列）到码表不等长二元码字（码元序列）的映射元码字（码元序列）的映射进制变换进制变换冗余压缩冗余压缩第第4章章 数据压缩数据压缩)xxx(P)xxx(P)xxx(P)xxx(P)ccc (P)cc (P)cc (P)c (P)c (P)CCC(P)CCC(PCCCNNN311211111222211121l21l21l21码表的模型码表的模型不等长不等长l维二元离散型随机变量序维二元离散型随机变量序列列C1C2

2、ClP(C1C2Cl)N, 2 , 1i ,i ,i2 , 1k,k,kxxxcccCCCn21l21iiikkkl21n21l21的码字为信源发出消息的取值随机变量序列第第4章章 数据压缩数据压缩nLl21kkknn21iiiN2 , 2 , 1k2 , 1k,k,kcccN, 2 , 1iN, 2 , 1i ,i ,ixxxl21n21kic码字x记信源发出消息第第4章章 数据压缩数据压缩2、平均码长、平均码长n次扩展信源各消息码字长度的数学期望，用次扩展信源各消息码字长度的数学期望，用L表表示示nnnN1kkkN1kkkN1kkkkl )x(P)c ( l )x(P)c ( l )c (

3、P)c ( l EL第第4章章 数据压缩数据压缩求二次扩展信源信源编码及平均码长求二次扩展信源信源编码及平均码长1 . 09 . 0)X(P)X(PX1：二元信源例01. 009. 009. 081. 0)X(P)X(PX222第第4章章 数据压缩数据压缩101c11x,100c10 x,11c01x, 0c00 x44332211某种信源编码某种信源编码平均码长平均码长)bit(29. 13)01. 009. 0(209. 0181. 0l )x(PL41kkk信源的熵信源的熵)bit(469. 01 . 0log1 . 09 . 0log9 . 0)x(Plog)x(P)X(H21iii第

4、第4章章 数据压缩数据压缩469. 0)X(H645. 0229. 1nLR码率码率225. 029. 129. 029. 1201. 0309. 0L) 1c (L) 1c (P775. 029. 1129. 1101. 0209. 0181. 0L) 0c (L) 0c (P第第4章章 数据压缩数据压缩3、编码效率、编码效率信源的熵与信源编码的码率之比信源的熵与信源编码的码率之比1L)X(nHR)X(H从提高传输效率的角度，码率越接近熵越好从提高传输效率的角度，码率越接近熵越好第第4章章 数据压缩数据压缩4、即时码、即时码信源发出的每条消息映射为不同的码字信源发出的每条消息映射为不同的码字

5、一一一一对应对应jijijjiiccxxcx,cx非奇异码非奇异码第第4章章 数据压缩数据压缩码的扩展编码码的扩展编码消息序列的码字等于消息的码字序列消息序列的码字等于消息的码字序列n21n21nn2211cccxxxcx,cx,cx第第4章章 数据压缩数据压缩唯一可译码唯一可译码码的扩展编码为非奇异码码的扩展编码为非奇异码1nj1jj1ni1ii1nj1jj1ni1ii1nj1jj1nj1jj1ni1ii1ni1iiccccccxxxxxxcccxxx,cccxxx唯一可译码唯一可译码由码字序列可唯一译出消息序列由码字序列可唯一译出消息序列自我间断码自我间断码第第4章章 数据压缩数据压缩即时

6、码即时码码表中无任何码字是其它码字的前缀码表中无任何码字是其它码字的前缀即时码可以用树图构造即时码可以用树图构造二元即时码二元即时码00,10,11和和0,10,11各自所对应的二叉树各自所对应的二叉树图图010101010第第4章章 数据压缩数据压缩即时码即时码任何码字结束时即可译出的自我间断码任何码字结束时即可译出的自我间断码全体编码全体编码非奇异码非奇异码唯一可译码唯一可译码即时码即时码第第4章章 数据压缩数据压缩奇异码奇异码非奇异码非奇异码非唯一可译非唯一可译唯一可译码唯一可译码非即时非即时即时码即时码x10000 x2110110 x310101111可译码和即时码唯一的奇异码、非奇

7、异码、：对应于消息例321x,x,x2第第4章章 数据压缩数据压缩11c2x,10c1x, 0c0 x3332211：即时码例010111101221000111002分别发出消息序列分别发出消息序列0122和和1002所对应的码字序列及所对应的码字序列及译码过程译码过程第第4章章 数据压缩数据压缩211211111101111001011112110011000111100011左移左移1位位=0？=10？输出输出0Y输出输出1YNN输出输出2左移左移2位位结束？结束？YN输入码字序列输入码字序列结束结束第第4章章 数据压缩数据压缩4.2 克拉夫特不等式克拉夫特不等式二元即时码的码长二元即时

8、码的码长l1,l2,lNn满足不等式满足不等式12nkN1kl反之，给定满足以上不等式的一组码长，存在相反之，给定满足以上不等式的一组码长，存在相应的二元即时码应的二元即时码第第4章章 数据压缩数据压缩记二元即时码第记二元即时码第k个码字的码长为个码字的码长为lk考虑一棵考虑一棵lmax级二叉满树，在第级二叉满树，在第lk级共有级共有2lk个节点个节点根据即时码的定义，对第根据即时码的定义，对第k个码字，在第个码字，在第lmax级被级被用掉或不能用的节点数为用掉或不能用的节点数为2lmax-lk构造二元即时码的树图第构造二元即时码的树图第lmax级总共被用掉或不能级总共被用掉或不能用的节点总数

9、用的节点总数maxnkmaxlN1kll2212nkN1kl第第4章章 数据压缩数据压缩第第2级被用掉或不能用的节点总数为级被用掉或不能用的节点总数为422322222l22222231kllmaxkmax2l , 2l , 2l , 2l221max0101001012l , 2l , 1l221422422222l22221231kllmaxkmax第第4章章 数据压缩数据压缩反之，从树根出发由短及长依次按码长反之，从树根出发由短及长依次按码长lk生长二叉生长二叉树枝，即可构造出一颗树枝，即可构造出一颗lmax级二叉树，相应得到二级二叉树，相应得到二元即时码元即时码第第4章章 数据压缩数据

10、压缩4.3 渐进最优码定理渐进最优码定理信源的熵为信源的熵为H(X)，对，对n次扩展信源进行二元异前置次扩展信源进行二元异前置码编码，对任意给定的码编码，对任意给定的 0，当，当n足够大，码率满足够大，码率满足足H(X) R H(X) +第第4章章 数据压缩数据压缩限制下的条件极值在平均码长12LnkN1klnN1ilN1iiikN, 2 , 1k012l )x(Plnin令nlkN, 2 , 1k02elog)x(PknklN, 2 , 1k)x(ePlog2k第第4章章 数据压缩数据压缩1elog)x(ePlog2nnkN1kkN1klnkkN, 2 , 1k)x(PloglnklN, 2

11、 , 1k)x(P2k)X(nH)x(Plog)x(Pl )x(PLnnN1kkkN1kkk)X(HnLR第第4章章 数据压缩数据压缩nkkN, 2 , 1k)x(Plogl选取nkkN, 2 , 1k1)x(Plogl1)x(Plog)x(Pl )x(PnnN1kkkN1kkk1)X(nHLn1)X(HnLR足够大，当任意给定nn1第第4章章 数据压缩数据压缩)X(HR)X(HR)X(H第第4章章 数据压缩数据压缩4.4 赫夫曼码赫夫曼码将信源发出消息将信源发出消息xk k=1,2,Nn按概率降序排列按概率降序排列为概率最小的两条消息各自分配一个码元为概率最小的两条消息各自分配一个码元将概率

12、最小的两条消息合并成一条新消息，用两将概率最小的两条消息合并成一条新消息，用两者概率之和作为新消息的概率者概率之和作为新消息的概率编码步骤编码步骤重复重复 步骤，直到合并出新消息的概率为步骤，直到合并出新消息的概率为1时时结束，分配给消息结束，分配给消息xk的全部码元作为该消息的码字的全部码元作为该消息的码字ck k=1,2,Nn第第4章章 数据压缩数据压缩8/18/14/12/1)X(P)X(PX1：四元信源例对信源编赫夫曼码并计算编码效率对信源编赫夫曼码并计算编码效率第第4章章 数据压缩数据压缩将信源发出消息将信源发出消息xk k=1,2,Nn按概率降序排列按概率降序排列为概率最小的两条消

13、息各自分配一个码元为概率最小的两条消息各自分配一个码元将概率最小的两条消息合并成一条新消息，用两将概率最小的两条消息合并成一条新消息，用两者概率之和作为新消息的概率者概率之和作为新消息的概率8/1x8/1x4/1x2/1x)x(Px4321kk104/1x3第第4章章 数据压缩数据压缩重复重复 步骤，直到合并出新消息的概率为步骤，直到合并出新消息的概率为1时时结束，分配给消息结束，分配给消息xk的全部码元作为该消息的码字的全部码元作为该消息的码字ck k=1,2,Nn4/1x2/1x21102/1x28/1x8/1x4/1x2/1x)x(Px4321kk104/1x32/1x1101x1111

14、cx,110cx,10cx, 0cx44332211第第4章章 数据压缩数据压缩更紧凑的编码过程描述更紧凑的编码过程描述8/1x8/1x4/1x2/1x)x(Px4321kk4/12/11101010111cx,110cx,10cx, 0cx44332211第第4章章 数据压缩数据压缩)bit(75. )x(PL41kkk)bit(75. 181log81241log4121log21)x(Plog)x(P)X(H41iii%10075. 175. 1L)X(HR)X(H第第4章章 数据压缩数据压缩1 . 04 . 05 . 0)X(P)X(PX2：三元信源例分别对信

15、源和二次扩展信源编赫夫曼码并计算编码分别对信源和二次扩展信源编赫夫曼码并计算编码效率效率第第4章章 数据压缩数据压缩(1)信源编赫夫曼码并计算编码效率信源编赫夫曼码并计算编码效率1 . 024 . 015 . 00)x(Pxkk5 . 011010112,101 ,00第第4章章 数据压缩数据压缩)bit( 5 . 121 . 024 . 015 . 0l )x(PL31kkk)bit(36. 11 . 0log1 . 04 . 0log4 . 05 . 0log5 . 0)x(Plog)x(P)X(H31iii%7 .905 . 136. 1L)X(HR)X(H第第4章章 数据压缩数据压缩(

16、2)二次扩展信源编赫夫曼码并计算编码效率二次扩展信源编赫夫曼码并计算编码效率01. 004. 005. 004. 016. 02 . 005. 02 . 025. 0)X(P)X(PX22201. 004. 004. 005. 005. 016. 02 . 02 . 025. 0)X(P)X(222第第4章章 数据压缩数据压缩01. 02204. 02104. 01205. 02005. 00216. 0112 . 0102 . 00125. 000)x(Pxkk0.05100.09010.110010.19 010.350.410100.6101第第4

17、章章 数据压缩数据压缩01. 02204. 02104. 01205. 02005. 00216. 0112 . 0102 . 00125. 000)x(Pxkk0.05100.09010.110010.19 010.350.410100.610100010122,00010021,0001112,0000120,0000002,00111,1110,1001,0100第第4章章 数据压缩数据压缩)bit(78. 26)01. 004. 0(5)04. 005. 02(316. 02) 2 . 0225. 0(l )x(PL91kkk%9 .9778. 236. 12L)X(nHR)X(H第第

18、4章章 数据压缩数据压缩1 . 01 . 02 . 02 . 04 . 0)X(P)X(PX3：五元信源例用两种排列方式进行赫夫曼编码并计算平均码长用两种排列方式进行赫夫曼编码并计算平均码长第第4章章 数据压缩数据压缩排列方式排列方式1合并后的新消息排在其它相同概率合并后的新消息排在其它相同概率消息之后消息之后1 . 0 x1 . 0 x2 . 0 x2 . 0 x4 . 0 x)x(Px54321kk0.2100.410100.61010011x,0010 x,000 x,01x, 1x54321第第4章章 数据压缩数据压缩)bit( 2 . 241 . 0232 . 022 . 014 . 0l )x(PL51kkk第第4章章 数据压缩数据压缩排列方式排列方式2合并后