信息傳輸基礎(chǔ)07課件

1、4 統(tǒng)計(jì)編碼統(tǒng)計(jì)編碼主要內(nèi)容1基本原理基本原理2霍夫曼編碼3游程編碼4算術(shù)編碼5基于字典的編碼6哥倫布編碼4.2 霍夫曼編碼 1925-1999 戴維霍夫曼，數(shù)學(xué)家，計(jì)算機(jī)科學(xué)領(lǐng)域的先驅(qū)?；舴蚵簧凶鞒龅闹匾暙I(xiàn)有：有限狀態(tài)機(jī)，開關(guān)切換電路，綜合程序，信號設(shè)計(jì)等。 霍夫曼在MIT一直工作到1967年。之后他轉(zhuǎn)入加州大學(xué)的Santa Cruz分校，是該校計(jì)算機(jī)科學(xué)系的創(chuàng)始人，19701973年任系主任。1994年霍夫曼退休。霍夫曼碼的編碼定理 【定理4.3】 在變長編碼中，若各碼字長度嚴(yán)格按照所對應(yīng)符號出現(xiàn)概率的大小逆序排序，則其平均長度為最小。 按上述定理可得霍夫曼碼的編碼步驟： 1）將信源

2、符號出現(xiàn)概率按照減小的順序排列； 2）將兩個(gè)最小的概率進(jìn)行組合相加，并繼續(xù)這一步驟，始終將較高的概率分支放在上部，直到概率達(dá)到1.0為止； 對每對組合中的上邊一個(gè)指定為1，下邊一個(gè)指定為0（霍相反，對上邊一個(gè)指定為0，對下邊一個(gè)指定為1）； 畫出由每個(gè)信源符號概率到1.0處的路徑，記下沿路徑的0和1； 對于每個(gè)信源符號都寫出1、0序列，則從右到左就得到了霍夫曼碼例4-6 對一個(gè)7符號信源 ，其霍夫曼編碼如圖4-6127,Aa aa另例關(guān)鍵在每一步，總是將最低概率的兩個(gè)符號構(gòu)成一對關(guān)鍵在每一步，總是將最低概率的兩個(gè)符號構(gòu)成一對兩種霍夫曼編碼的異同 對一個(gè)5符號信源 ，其霍夫曼編碼如下圖所示 請使

3、用霍夫曼碼進(jìn)行編碼 采用兩種方式進(jìn)行編碼； 求其平均碼長；125,Aa aa12345()0.10.1XaaaaaP X兩種霍夫曼編碼的異同 引入碼字長度偏離平均碼長的方差的概念： 方差小的編碼方法得到的碼字結(jié)構(gòu)更緊湊，碼的變化小， 22521iiiiElLp alL霍夫曼碼的編法并不唯一 每次對縮減信源兩個(gè)概率最小的符號分配“0”和“1”碼元是任意的，所以可以得到不同的碼字。 不同的碼元分配，得到的具體碼字不同，但是平均碼長不變4.2.2 信源編碼基本定理 例4-7：對于二值圖像，如傳真機(jī)，輸出非“黑”即“白”，有 ，其概率與所傳文件有關(guān)，假設(shè)對某頁文件，有12,Xx x

4、白，黑10.9P x20.1P x不考慮信號間的關(guān)聯(lián)時(shí)，其信息熵為：0.9 log0.90.1 log0.10.469H Xbit pel 此時(shí)霍夫曼編碼無壓縮作用1146.9%H Xl編碼效率為基本途徑之四： 如果把X延長后在對K元組（K為延長長度）進(jìn)行編碼，那么只要K足夠大，則代表每消息單元X的平均符號個(gè)數(shù) 可以任意趨向于小界l K【定理4.4（信源編碼的基本定理）】設(shè)如果要求碼字單義可譯，則也叫作無失真編碼的基本定理 121212,;,1,2, ;mKnKnKiiiAa aaXXx xxWWw wwlP wP xP WP win的延長；的延長，其平均長度為 ；，()1loglogH Xl

5、H XmKmK例4-8 把例4-7中的碼元延長到X2，此時(shí)可以獲得圖4.7 2單元延長信號的最佳編碼P(x1, x1) = P(x1)P( x1) =0.81P(x1, x2) = P(x1)P( x2) =0.09P(x2, x1) = P(x2)P( x1) =0.09P(x2, x2) = P(x2)P( x2) =0.00111000W 2 010110111W 2平均長度為:l2 =0.81+0.092+0.093+0.013=1.29 bit/pelW 2的每一個(gè)元素代表兩個(gè)消息單元,因此平均每一個(gè)消息單元的符號個(gè)數(shù)是:l2 /2 = 1.29/2 = 0.

6、645 bit/pel2 =H(X)/ l2=72.7 %編碼效率提高到:圖4.8 3單元延長信號的最佳編碼P(x1, x1, x1) =0.729P(x1, x1, x2) =0.081P(x1, x2, x1) =0.081P(x2, x1, x1) =0.0810.0100.109111000P(x1, x2, x2) =0.009P(x2, x1, x2) =0.009P(x2, x2, x1) =0.009P(x2, x2, x2) =0.0010.0180.0280.1620.2711.0000111001W 3111111111011101110101100011100把把 X

7、延長到延長到 X 3 ，有圖有圖4.8所示所示 X 3 的最佳編碼：的最佳編碼：W 3平均長度為:l3 =0.729+0.08133 +5( 30.09+0.001)=1.598 bit/pelW 3的每一個(gè)元素代表三個(gè)消息單元, 因此平均每一個(gè)消息單元的符號個(gè)數(shù)是:l3 /3 = 1.598/3 = 0.5327 bit/pel3 =H(X)/ l3=88.0 %編碼效率提高到:還能經(jīng)一步壓縮碼？還能經(jīng)一步壓縮碼？H(X, Y )H(X)+H(Y)(3.2-13)H(X | Y )H(X)(3.2-11b)或:要求知道P(X), P(X,Y) 或 P(X|Y) 才能進(jìn)行最佳編碼。信源編碼理論

8、 給定消息單元集合X、符號集合A和X的概率分布P(X)， 可以采用最佳編碼，使代碼W 的平均長度滿足; 如果把X 延長至 X K ,則不必考慮信號前后的關(guān)聯(lián)性, 就可以是代表一個(gè)消息單元的符號個(gè)數(shù) l /K 任意接近 下限 H(X)/logm; 如果利用延長信號X K的前后關(guān)聯(lián),可使下限減小。1log)(,log)(mXHmXHl靜態(tài)統(tǒng)計(jì)模型 在編碼前統(tǒng)計(jì)要編碼的信息中所有字符的出現(xiàn)概率，然后根據(jù)統(tǒng)計(jì)出的信息建立編碼樹，進(jìn)行編碼 。 對數(shù)據(jù)量較大的信息，靜態(tài)統(tǒng)計(jì)要消耗大量的時(shí)間； 必須保存統(tǒng)計(jì)出的結(jié)果以便解碼時(shí)構(gòu)造相同的編碼樹，或者直接保存編碼樹本身，而且，對于每次靜態(tài)統(tǒng)計(jì)，都有不同的結(jié)果，必

9、須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）； 靜態(tài)統(tǒng)計(jì)模型統(tǒng)計(jì)出的頻率是字符在整個(gè)文件中的出現(xiàn)頻率，往往反映不出字符在文件中不同局部出現(xiàn)頻率的變化情況，使用這一頻率進(jìn)行壓縮，大多數(shù)情況下得不到太好壓縮效果，文件有時(shí)甚至在壓縮后反而增大了。缺點(diǎn) If Youth，throughout all history， had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldnt constan

10、tly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 無需為解壓縮預(yù)先保存任何信息，整個(gè)編碼是在壓縮和解壓縮過程中動態(tài)創(chuàng)建的，而且自適應(yīng)編碼由于其符號頻率是根據(jù)信息內(nèi)容的變化動態(tài)得到的，更符合符號的局部分布規(guī)律，因此在壓縮效果上比靜態(tài)模型好許多。自適應(yīng)模型將自適應(yīng)模型與霍夫曼編碼結(jié)合起來的問題是重建霍夫曼樹是一個(gè)非常昂貴的過程。為了讓自適應(yīng)方案高效，有必要在每一個(gè)字符出現(xiàn)之后調(diào)整霍夫曼編碼。直到霍夫曼編碼第一次開發(fā)的 20 年之后，執(zhí)行自適應(yīng)霍夫曼自

11、適應(yīng)霍夫曼編碼編碼的算法都沒有發(fā)布。即使在現(xiàn)在，最好的自適應(yīng)霍自適應(yīng)霍夫曼編碼夫曼編碼算法仍然相當(dāng)耗時(shí)間和金錢。主要內(nèi)容1基本原理基本原理2霍夫曼編碼3游程編碼4算術(shù)編碼5基于字典的編碼6哥倫布編碼4.3 游程編碼游程長度(RL: Run Length,簡稱游程或游長)： 由字符(或信號采樣值)構(gòu)成的數(shù)據(jù)流中各字符重復(fù)出現(xiàn)而形成的字符串的長度。用二進(jìn)制碼字給出形成串的字符、串的長度及串的位置等信息，以此來恢復(fù)出原來的數(shù)據(jù)流。是在控制論中對于二值圖像而言是一種編碼方法，對連續(xù)的黑、白像素?cái)?shù)(游程)以不同的碼字進(jìn)行編碼。 游程長度編碼(RLC)：基本的RLC壓縮方法：最初出現(xiàn)在 IBM 3780

12、BYSYNC (Binary Synchronous Communication)通信協(xié)議中。基本的RLC數(shù)據(jù)結(jié)構(gòu)：XScRL數(shù) 據(jù) 流圖4.9 基本的RLC數(shù)據(jù)結(jié)構(gòu)游程編碼的壓縮效能平均重復(fù)長度重復(fù)出現(xiàn)10次的壓縮比重復(fù)出現(xiàn)20次的壓縮比重復(fù)出現(xiàn)30次的壓縮比重復(fù)出現(xiàn)40次的壓縮比重復(fù)出現(xiàn)50次的壓縮比41.0101.0201.0311.0421.05351.0201.0421.0641.0731.11161.0311.0641.0991.1361.17671.0421.0871.1361.1901.25081.0531.1111.1761.2501.33391.0641.1361.2201.3161.429101.0751.1631.2661.3841.538表4.2 基本的游程編碼壓縮比二值圖像的編碼過程 先對圖像進(jìn)行統(tǒng)計(jì)分別得出白長為 i 的 概率 PiW 和黑長為 i 的概率 PiB， 然后根據(jù)霍夫曼原則按RL出現(xiàn)概率來分 配碼字。二值圖像的RLC實(shí)為霍夫曼碼的具體應(yīng)用修正霍夫曼編碼MH編碼規(guī)則: (見表4.3) RL=063，