第4章 數(shù)據(jù)壓縮

1、第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮4.1 即時碼即時碼1、信源編碼信源編碼n次擴展信源消息（符號序列）到碼表不等長二次擴展信源消息（符號序列）到碼表不等長二元碼字（碼元序列）的映射元碼字（碼元序列）的映射進制變換進制變換冗余壓縮冗余壓縮第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮)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的碼字為信源發(fā)出消息的取值隨機變量序列第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮nLl21kkknn21iiiN2 , 2 , 1k2 , 1k,k,kcccN, 2 , 1iN, 2 , 1i ,i ,ixxxl21n21kic碼字x記信源發(fā)出消息第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮2、平均碼長、平均碼長n次擴展信源各消息碼字長度的數(shù)學期望，用次擴展信源各消息碼字長度的數(shù)學期望，用L表表示示nnnN1kkkN1kkkN1kkkkl )x(P)c ( l )x(P)c ( l )c (

3、P)c ( l EL第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮求二次擴展信源信源編碼及平均碼長求二次擴展信源信源編碼及平均碼長1 . 09 . 0)X(P)X(PX1：二元信源例01. 009. 009. 081. 0)X(P)X(PX222第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮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章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮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章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮3、編碼效率、編碼效率信源的熵與信源編碼的碼率之比信源的熵與信源編碼的碼率之比1L)X(nHR)X(H從提高傳輸效率的角度，碼率越接近熵越好從提高傳輸效率的角度，碼率越接近熵越好第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮4、即時碼、即時碼信源發(fā)出的每條消息映射為不同的碼字信源發(fā)出的每條消息映射為不同的碼字

5、一一一一對應對應jijijjiiccxxcx,cx非奇異碼非奇異碼第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮碼的擴展編碼碼的擴展編碼消息序列的碼字等于消息的碼字序列消息序列的碼字等于消息的碼字序列n21n21nn2211cccxxxcx,cx,cx第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮唯一可譯碼唯一可譯碼碼的擴展編碼為非奇異碼碼的擴展編碼為非奇異碼1nj1jj1ni1ii1nj1jj1ni1ii1nj1jj1nj1jj1ni1ii1ni1iiccccccxxxxxxcccxxx,cccxxx唯一可譯碼唯一可譯碼由碼字序列可唯一譯出消息序列由碼字序列可唯一譯出消息序列自我間斷碼自我間斷碼第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮即時

6、碼即時碼碼表中無任何碼字是其它碼字的前綴碼表中無任何碼字是其它碼字的前綴即時碼可以用樹圖構(gòu)造即時碼可以用樹圖構(gòu)造二元即時碼二元即時碼00,10,11和和0,10,11各自所對應的二叉樹各自所對應的二叉樹圖圖010101010第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮即時碼即時碼任何碼字結(jié)束時即可譯出的自我間斷碼任何碼字結(jié)束時即可譯出的自我間斷碼全體編碼全體編碼非奇異碼非奇異碼唯一可譯碼唯一可譯碼即時碼即時碼第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮奇異碼奇異碼非奇異碼非奇異碼非唯一可譯非唯一可譯唯一可譯碼唯一可譯碼非即時非即時即時碼即時碼x10000 x2110110 x310101111可譯碼和即時碼唯一的奇異碼、非奇

7、異碼、：對應于消息例321x,x,x2第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮11c2x,10c1x, 0c0 x3332211：即時碼例010111101221000111002分別發(fā)出消息序列分別發(fā)出消息序列0122和和1002所對應的碼字序列及所對應的碼字序列及譯碼過程譯碼過程第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮211211111101111001011112110011000111100011左移左移1位位=0？=10？輸出輸出0Y輸出輸出1YNN輸出輸出2左移左移2位位結(jié)束？結(jié)束？YN輸入碼字序列輸入碼字序列結(jié)束結(jié)束第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮4.2 克拉夫特不等式克拉夫特不等式二元即時碼的碼長二元即時

8、碼的碼長l1,l2,lNn滿足不等式滿足不等式12nkN1kl反之，給定滿足以上不等式的一組碼長，存在相反之，給定滿足以上不等式的一組碼長，存在相應的二元即時碼應的二元即時碼第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮記二元即時碼第記二元即時碼第k個碼字的碼長為個碼字的碼長為lk考慮一棵考慮一棵lmax級二叉滿樹，在第級二叉滿樹，在第lk級共有級共有2lk個節(jié)點個節(jié)點根據(jù)即時碼的定義，對第根據(jù)即時碼的定義，對第k個碼字，在第個碼字，在第lmax級被級被用掉或不能用的節(jié)點數(shù)為用掉或不能用的節(jié)點數(shù)為2lmax-lk構(gòu)造二元即時碼的樹圖第構(gòu)造二元即時碼的樹圖第lmax級總共被用掉或不能級總共被用掉或不能用的節(jié)點總數(shù)

9、用的節(jié)點總數(shù)maxnkmaxlN1kll2212nkN1kl第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮第第2級被用掉或不能用的節(jié)點總數(shù)為級被用掉或不能用的節(jié)點總數(shù)為422322222l22222231kllmaxkmax2l , 2l , 2l , 2l221max0101001012l , 2l , 1l221422422222l22221231kllmaxkmax第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮反之，從樹根出發(fā)由短及長依次按碼長反之，從樹根出發(fā)由短及長依次按碼長lk生長二叉生長二叉樹枝，即可構(gòu)造出一顆樹枝，即可構(gòu)造出一顆lmax級二叉樹，相應得到二級二叉樹，相應得到二元即時碼元即時碼第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)

10、壓縮4.3 漸進最優(yōu)碼定理漸進最優(yōu)碼定理信源的熵為信源的熵為H(X)，對，對n次擴展信源進行二元異前置次擴展信源進行二元異前置碼編碼，對任意給定的碼編碼，對任意給定的 0，當，當n足夠大，碼率滿足夠大，碼率滿足足H(X) R H(X) +第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮限制下的條件極值在平均碼長12LnkN1klnN1ilN1iiikN, 2 , 1k012l )x(Plnin令nlkN, 2 , 1k02elog)x(PknklN, 2 , 1k)x(ePlog2k第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮1elog)x(ePlog2nnkN1kkN1klnkkN, 2 , 1k)x(PloglnklN, 2

11、 , 1k)x(P2k)X(nH)x(Plog)x(Pl )x(PLnnN1kkkN1kkk)X(HnLR第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮nkkN, 2 , 1k)x(Plogl選取nkkN, 2 , 1k1)x(Plogl1)x(Plog)x(Pl )x(PnnN1kkkN1kkk1)X(nHLn1)X(HnLR足夠大，當任意給定nn1第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮)X(HR)X(HR)X(H第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮4.4 赫夫曼碼赫夫曼碼將信源發(fā)出消息將信源發(fā)出消息xk k=1,2,Nn按概率降序排列按概率降序排列為概率最小的兩條消息各自分配一個碼元為概率最小的兩條消息各自分配一個碼元將概率

12、最小的兩條消息合并成一條新消息，用兩將概率最小的兩條消息合并成一條新消息，用兩者概率之和作為新消息的概率者概率之和作為新消息的概率編碼步驟編碼步驟重復重復 步驟，直到合并出新消息的概率為步驟，直到合并出新消息的概率為1時時結(jié)束，分配給消息結(jié)束，分配給消息xk的全部碼元作為該消息的碼字的全部碼元作為該消息的碼字ck k=1,2,Nn第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮8/18/14/12/1)X(P)X(PX1：四元信源例對信源編赫夫曼碼并計算編碼效率對信源編赫夫曼碼并計算編碼效率第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮將信源發(fā)出消息將信源發(fā)出消息xk k=1,2,Nn按概率降序排列按概率降序排列為概率最小的兩條消

13、息各自分配一個碼元為概率最小的兩條消息各自分配一個碼元將概率最小的兩條消息合并成一條新消息，用兩將概率最小的兩條消息合并成一條新消息，用兩者概率之和作為新消息的概率者概率之和作為新消息的概率8/1x8/1x4/1x2/1x)x(Px4321kk104/1x3第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮重復重復 步驟，直到合并出新消息的概率為步驟，直到合并出新消息的概率為1時時結(jié)束，分配給消息結(jié)束，分配給消息xk的全部碼元作為該消息的碼字的全部碼元作為該消息的碼字ck k=1,2,Nn4/1x2/1x21102/1x28/1x8/1x4/1x2/1x)x(Px4321kk104/1x32/1x1101x1111

14、cx,110cx,10cx, 0cx44332211第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮更緊湊的編碼過程描述更緊湊的編碼過程描述8/1x8/1x4/1x2/1x)x(Px4321kk4/12/11101010111cx,110cx,10cx, 0cx44332211第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮)bit(75. )x(PL41kkk)bit(75. 181log81241log4121log21)x(Plog)x(P)X(H41iii%10075. 175. 1L)X(HR)X(H第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮1 . 04 . 05 . 0)X(P)X(PX2：三元信源例分別對信

15、源和二次擴展信源編赫夫曼碼并計算編碼分別對信源和二次擴展信源編赫夫曼碼并計算編碼效率效率第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮(1)信源編赫夫曼碼并計算編碼效率信源編赫夫曼碼并計算編碼效率1 . 024 . 015 . 00)x(Pxkk5 . 011010112,101 ,00第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮)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章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮(

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章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮01. 02204. 02104. 01205. 02005. 00216. 0112 . 0102 . 00125. 000)x(Pxkk0.05100.09010.110010.19 010.350.410100.6101第第4

17、章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮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章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮)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章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮1 . 01 . 02 . 02 . 04 . 0)X(P)X(PX3：五元信源例用兩種排列方式進行赫夫曼編碼并計算平均碼長用兩種排列方式進行赫夫曼編碼并計算平均碼長第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮排列方式排列方式1合并后的新消息排在其它相同概率合并后的新消息排在其它相同概率消息之后消息之后1 . 0 x1 . 0 x2 . 0 x2 . 0 x4 . 0 x)x(Px54321kk0.2100.410100.61010011x,0010 x,000 x,01x, 1x54321第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮)bit( 2 . 241 . 0232 . 022 . 014 . 0l )x(PL51kkk第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮排列方式排列方式2合并后