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

1、第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮4.1 即時(shí)碼即時(shí)碼1、信源編碼信源編碼n次擴(kuò)展信源消息（符號(hào)序列）到碼表不等長(zhǎng)二次擴(kuò)展信源消息（符號(hào)序列）到碼表不等長(zhǎng)二元碼字（碼元序列）的映射元碼字（碼元序列）的映射進(jìn)制變換進(jì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碼表的模型碼表的模型不等長(zhǎng)不等長(zhǎng)l維二元離散型隨機(jī)變量序維二元離散型隨機(jī)變量序列列C1C2

2、ClP(C1C2Cl)N, 2 , 1i ,i ,i2 , 1k,k,kxxxcccCCCn21l21iiikkkl21n21l21的碼字為信源發(fā)出消息的取值隨機(jī)變量序列第第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、平均碼長(zhǎng)、平均碼長(zhǎng)n次擴(kuò)展信源各消息碼字長(zhǎng)度的數(shù)學(xué)期望，用次擴(kuò)展信源各消息碼字長(zhǎng)度的數(shù)學(xué)期望，用L表表示示nnnN1kkkN1kkkN1kkkkl )x(P)c ( l )x(P)c ( l )c (

3、P)c ( l EL第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮求二次擴(kuò)展信源信源編碼及平均碼長(zhǎng)求二次擴(kuò)展信源信源編碼及平均碼長(zhǎng)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某種信源編碼某種信源編碼平均碼長(zhǎng)平均碼長(zhǎng))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、即時(shí)碼、即時(shí)碼信源發(fā)出的每條消息映射為不同的碼字信源發(fā)出的每條消息映射為不同的碼字

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

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

7、異碼、：對(duì)應(yīng)于消息例321x,x,x2第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮11c2x,10c1x, 0c0 x3332211：即時(shí)碼例010111101221000111002分別發(fā)出消息序列分別發(fā)出消息序列0122和和1002所對(duì)應(yīng)的碼字序列及所對(duì)應(yīng)的碼字序列及譯碼過(guò)程譯碼過(guò)程第第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 克拉夫特不等式克拉夫特不等式二元即時(shí)碼的碼長(zhǎng)二元即時(shí)

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

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

10、壓縮4.3 漸進(jìn)最優(yōu)碼定理漸進(jìn)最優(yōu)碼定理信源的熵為信源的熵為H(X)，對(duì)，對(duì)n次擴(kuò)展信源進(jìn)行二元異前置次擴(kuò)展信源進(jìn)行二元異前置碼編碼，對(duì)任意給定的碼編碼，對(duì)任意給定的 0，當(dāng)，當(dāng)n足夠大，碼率滿足夠大，碼率滿足足H(X) R H(X) +第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮限制下的條件極值在平均碼長(zhǎng)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足夠大，當(dāng)任意給定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按概率降序排列按概率降序排列為概率最小的兩條消息各自分配一個(gè)碼元為概率最小的兩條消息各自分配一個(gè)碼元將概率

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

13、息各自分配一個(gè)碼元為概率最小的兩條消息各自分配一個(gè)碼元將概率最小的兩條消息合并成一條新消息，用兩將概率最小的兩條消息合并成一條新消息，用兩者概率之和作為新消息的概率者概率之和作為新消息的概率8/1x8/1x4/1x2/1x)x(Px4321kk104/1x3第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮重復(fù)重復(fù) 步驟，直到合并出新消息的概率為步驟，直到合并出新消息的概率為1時(shí)時(shí)結(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ù)壓縮更緊湊的編碼過(guò)程描述更緊湊的編碼過(guò)程描述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：三元信源例分別對(duì)信

15、源和二次擴(kuò)展信源編赫夫曼碼并計(jì)算編碼分別對(duì)信源和二次擴(kuò)展信源編赫夫曼碼并計(jì)算編碼效率效率第第4章章 數(shù)據(jù)壓縮數(shù)據(jù)壓縮(1)信源編赫夫曼碼并計(jì)算編碼效率信源編赫夫曼碼并計(jì)算編碼效率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)二次擴(kuò)展信源編赫夫曼碼并計(jì)算編碼效率二次擴(kuò)展信源編赫夫曼碼并計(jì)算編碼效率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：五元信源例用兩種排列方式進(jìn)行赫夫曼編碼并計(jì)算平均碼長(zhǎng)用兩種排列方式進(jìn)行赫夫曼編碼并計(jì)算平均碼長(zhǎng)第第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合并后