統(tǒng)計編碼(2015)

1、1 1壓縮編碼技術(shù)壓縮編碼技術(shù) 2數(shù)據(jù)壓縮的類型可逆的無失真編碼可逆的無失真編碼不可逆的有失真編碼不可逆的有失真編碼不允許在壓縮過程中丟失信息。利用消息或消息序列出現(xiàn)概不允許在壓縮過程中丟失信息。利用消息或消息序列出現(xiàn)概率的分布特性，注重尋找概率與碼字長度間的最優(yōu)匹配。率的分布特性，注重尋找概率與碼字長度間的最優(yōu)匹配。語音、圖像或其他物理過程的量化采樣。語音、圖像或其他物理過程的量化采樣。本章討論的內(nèi)容3對于計算機文件對于計算機文件邏輯壓縮邏輯壓縮(Logical Compression)物理壓縮物理壓縮(Physical Compression)由數(shù)據(jù)自身特點及設(shè)計者技巧來決定的由數(shù)據(jù)自身特

2、點及設(shè)計者技巧來決定的 “壓縮表示壓縮表示法法”，這種技巧在數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)設(shè)計中特別有效。，這種技巧在數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)設(shè)計中特別有效。減少計算機文件內(nèi)部冗余度的統(tǒng)計編碼方法。減少計算機文件內(nèi)部冗余度的統(tǒng)計編碼方法。本章討論的內(nèi)容44.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計編碼方法統(tǒng)計編碼方法54.1 4.1 統(tǒng)計編碼方法的基本原理統(tǒng)計編碼方法的基本原理文件的冗余度類型文件的冗余度類型編碼器的數(shù)學(xué)描述編碼器的數(shù)學(xué)描述變長碼的基本分析變長碼的基本分析唯一可譯碼的存在唯一可譯碼的存在6計算機文件字

3、符集合(如文本);二進制符號集合(如數(shù)據(jù));壓縮必須壓縮必須“透明透明”，恢復(fù)后的文件不允許有任何失真。，恢復(fù)后的文件不允許有任何失真。7 文件的冗余度類型文件的冗余度類型冗余度，專指對數(shù)據(jù)解釋一無所知時由數(shù)據(jù)流中即可觀察到的，與具體應(yīng)用背景無關(guān)。了解文件的冗余度，意在考慮有針對性的編碼方法。了解文件的冗余度，意在考慮有針對性的編碼方法。8冗余類型冗余類型 字符分布字符分布(Character Distribution) 字符重復(fù)字符重復(fù)(Character Repetition)在典型的字符串中，某些符號要比其他符號出現(xiàn)的更頻繁，在一份具體的文件中字符不會以等概率出現(xiàn)，字符的分布明顯地因文件

4、而異，影響到字符的統(tǒng)計特性。對于字符重復(fù)所形成的符號串常常有更緊湊的編碼方式，例如：格式化文件中的空白、報表中的空格串和零串、業(yè)務(wù)圖表中的線圖包含成片的空白等。 字符分布字符分布(Character Distribution) 字符重復(fù)字符重復(fù)(Character Repetition)9 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy)這四類冗余度之間有重疊這四類冗余度之間有重疊某些符號序列會以較高的頻率反復(fù)出現(xiàn)，可用較少的位數(shù)表示，從而得到時間和空間的凈節(jié)約。若某些字符總是在各數(shù)據(jù)塊中可預(yù)見的位置上出現(xiàn)，那么

5、這些字符至少是部分冗余的 ，例如：光柵掃描圖像中含有的豎線、報表文件中的某些字段的記錄幾乎總是相同的等等。 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Positional Redundancy) 高使用率模式高使用率模式(High-usage Patterns) 位置冗余位置冗余(Posit

6、ional Redundancy) 高使用率模式高使用率模式(High-usage Patterns)10一份零件報表中的冗余度的類型零件名: HEX NUT 1/4 20說 明: STEEL, STANDARD THREAD顏色碼:倉 庫: 45th STREET貨 位: 4R9存貨量: 0020再進貨量:0010文字長度可變,字母分布不同;空字段同樣的名字在文件中多次出現(xiàn);數(shù)值字段, 有限的字符變化;11u 編碼器的數(shù)學(xué)描述編碼器的數(shù)學(xué)描述 4.1 4.1 統(tǒng)計編碼方法的基本原理統(tǒng)計編碼方法的基本原理 消息集X：元素 x 叫做信號單元或消息； 輸出集W (代碼、碼組或碼書)：元素 w叫做碼

7、字； 碼字的符號集A：元素 a 叫做碼元或者符號； 以符號 A 構(gòu)建代碼 W ; 建立 XW 對應(yīng)關(guān)系;12例例4-1X =x1, x2 , x3, A =0, 1, W =w1, w2, w3A2 =00, 01, 10, 11假設(shè)用構(gòu)成代碼構(gòu)成代碼W , W 到到 A2 的映射關(guān)系為的映射關(guān)系為 (完成步驟完成步驟):R1 = (w1,01), (w2,10), (w3,11)R2 =(x1 ,w1), (x2 ,w2), (x3 ,w3)建立建立X 與與 W 的映射關(guān)系為的映射關(guān)系為 (完成步驟完成步驟):若若xi(dk,dk+1, 1in, 0kJ-1, 為一模擬信號為一模擬信號, ,

8、 該該編碼器實際就是一個量化器。編碼器實際就是一個量化器。編碼就是信息集編碼就是信息集X 到到 碼字集碼字集W 的一個映射的一個映射建立建立X 與與 W 的映射關(guān)系為的映射關(guān)系為 (完成步驟完成步驟):13編碼，就是將不同的消息用 不同的碼字來代替，或稱為從消息集到碼字集的一種映射(分組編碼或塊碼的概念)。 碼長: 組成碼字的符號個數(shù), Li=2, 1i3, 等長(或定長)編碼: 采用相同長度的不同碼字去 代表一個消息集合中的不同消息; M元編碼(或M進制):取M個不同字符來組成碼字, 最常用的有二元編碼(或二進制)。 14 變長碼的基本分析變長碼的基本分析對一個消息集合中的不同消息，采用不同

9、長度的碼字表示。不等長(或變長)編碼：采用變長碼可以提高編碼效率，即對相同的信息量所需的平均編碼長度可以短一些。151()njjjlP aL平均碼長：對對P(aj)大的大的aj 用短碼用短碼;對對P(aj)小的小的aj 用長碼用長碼; 當(dāng)這些信息符號互不相關(guān)時當(dāng)這些信息符號互不相關(guān)時,平均碼長比等長編碼的碼長短平均碼長比等長編碼的碼長短161843年，莫爾斯電報碼年，莫爾斯電報碼字母莫爾斯碼鉛字?jǐn)?shù)E12000T9000A 8000I 8000N 8000O 8000S 8000H 6400R 6200D 4400L 4000U 3400C 3000字母莫爾斯碼鉛字?jǐn)?shù)M 3000F 2500W

10、2000Y 2000G 1700P 1700B 1600V 1200K 800Q 500J 400X 400Z 200表4.1莫爾斯碼17莫爾斯碼的形成莫爾斯碼的形成: 首先找到各消息符號的統(tǒng)計特性: 再根據(jù)各符號出現(xiàn)的概率分布分 配不同長度的碼字:變長碼在編碼時要預(yù)先知道各種信息符號出現(xiàn)的概率,解碼也遠比等長碼復(fù)雜:正確識別碼字起點不容易;存在唯一可譯性問題;譯碼實時性問題;勻速輸入輸出匹配的緩存問題; 18定義定義 4-1若W 中任一有限長的碼字序列(即有限長的一串W) ,可唯一地分割成一個一個碼字,稱為單義可譯或唯一可譯的,W 也叫做單義代碼。單義可譯碼（唯一可譯碼）單義可譯碼（唯一可譯

11、碼）19例例4-2考慮以下幾種變長碼：信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111 碼A不是一一對應(yīng) ; 碼B是一一對應(yīng)，但構(gòu)成的序列不能被唯一分割;01110(0,1,1,1,0) (0,1,11,0) (0,11,1,0) (0,111,0)20100111011010(10, 0, 111, 0, 110, 10) 碼C是唯一可譯的;信源字母碼B碼C碼Da1a2a3a401111110101101110010110111 碼D是在碼B各碼字(除了w1)之前加一

12、個碼元“0”, 成為唯一可譯的, 但平均碼長增加0.5bit;21 碼F 即使從尾開始判斷, 也不是唯一可譯的;信源字母碼E碼Fa1a2a3a4001011111010101111101111010(10, 111, 10, 10)(101, 111, 0, 10)問題: 什么樣的碼才是唯一可譯的? 碼E的譯碼要求等到收到全部序列, 才能從尾開始進行判決, 產(chǎn)生了時間上延時和存儲容量的增加;0111111 111(a1 1111) (a2111) ( a311)22 唯一可譯碼的存在唯一可譯碼的存在定理 4.1(Kraft不等式)長度為L1, L2, Ln 的 m 進制唯一可譯碼存在的充分必要

13、條件是:含義：要求 Li 比較大(碼長不能過短)，意味著碼字可能的組合數(shù)多,不為別的碼字的字首。11niLim(4.1-1)目前還沒有一個明確的判斷唯一可譯碼的準(zhǔn)則, 只有一個判斷不是唯一可譯碼的準(zhǔn)則。含義：要求 Li 比較大(碼長不能過短)，意味著碼字可能的組合數(shù)多,不為別的碼字的字首。23Kraft不等式：只涉及唯一可譯碼的存在問題而并不涉及具體的碼。可用來判定某一組碼不是唯一可譯的，但不能判定是唯一可譯的。不滿足Kraft不等式的碼肯定不是唯一可譯碼，而滿足的也不一定就是唯一可譯的，但可以肯定若按這樣的Li 分配碼組，則必存在有一個唯一可譯碼(也可能不止一個)對應(yīng)于信源符號。24碼A碼B

14、碼C碼D碼E碼F 的值7/411/4115/1611是否滿足Kraft不等式是否唯一可譯例例4-3對于例4-2,有:412iLi25問題: 如何來確定碼字長度?如何在確定了碼字長度后找出唯一可譯碼?定理 4.2(按符號)變長編碼定理)對于符號熵為H(X)的離散無記憶信源進行m 進制不等長編碼, 一定存在一種無失真編碼方法, 其碼字平均長度 l 滿足:mXHlmXHlog)(1log)(4.1-2)小于上限的唯一可譯碼總是存在的。26當(dāng)m=2，有(二進制編碼定理):此時l 叫編碼速率, 有時又叫比特率。對于m進制的不等長編碼的編碼速率定義為：mlRlog(4.1-4)(bit) )(1)(XHl

15、XH(4.1-3)定理4.2改述為：若H(X)R H(X)+, 就存在唯一可譯的變長碼;若R 1.75 碼長的一種設(shè)計為: L1 = 1, L2 = 2, L3 = L4 = 3信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111滿足上述碼長設(shè)計的碼如：例4.2中的碼C、E、F（滿足Kraft不等式）。如何做出具體的變長碼是變長碼的構(gòu)造問題。28 唯一可譯碼的構(gòu)造唯一可譯碼的構(gòu)造唯一可譯碼的基本要求:碼字非續(xù)長對碼字序列能做出唯一正確的分割。充分條件碼字非續(xù)長對碼字序列能做

16、出唯一正確的分割。29若W 中任一碼字都不是另一個碼字的字頭；或換句話說,任一碼字都不是由另一個碼字加上若干個碼元所構(gòu)成，則W 就叫作非續(xù)長碼字或異字頭碼(Prefix Condition Code)。定義 4-2碼字非續(xù)長30例4.2中:信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111碼A、碼B、碼D、碼E和碼F都含有續(xù)長碼，或同字頭碼；碼C是異字頭碼。31u 唯一可譯碼唯一可譯碼4.1 4.1 統(tǒng)計編碼方法的基本原理統(tǒng)計編碼方法的基本原理32不過非異字頭碼也并非一定

17、不是唯一可譯，碼D和碼E就唯一可譯；碼D：各碼組靠“逗號”（碼元0）分開；碼E：為碼C的“鏡像”，具有“異后尾”，從 后向前即具有唯一可譯性。異字頭條件保證譯出的碼字是唯一的且具有“即時性”，減少了譯碼延時。33異字頭性質(zhì)只是碼字可分離的充分條件，非續(xù)長碼也只是唯一可譯代碼集合的一個子集。唯一可譯碼非續(xù)長碼圖4.3 唯一可譯碼與非續(xù)長碼34二進制編碼二進制編碼通?？捎枚M碼樹(二叉樹)來表示各碼字的構(gòu)成(根)(節(jié)點)圖4.4 二進碼樹C(節(jié)點)D(節(jié)點)串接的最大枝數(shù)為書的節(jié)數(shù)， 圖4.4的節(jié)數(shù)為3。35用碼樹表述任何一個代碼W, 異字頭條件就成為: W中所有的碼字中所有的碼字 wi 均只對應(yīng)

18、地配置在終端節(jié)點上。均只對應(yīng)地配置在終端節(jié)點上。圖4.5 碼C的樹結(jié)構(gòu)(異字頭碼)根001110010110111根011100(011)(111)11(0)(01)碼E的樹結(jié)構(gòu)(非異字頭碼)3611niLim此時碼C為用盡的異字頭碼, 有:倘若有一碼字為(0,10,110), 則該碼為非用盡的異字頭碼, 有:11niLim37按照Kraft 不等式的要求，對n個消息x1, x2, ,xn分配了編碼長度L1,L2, ,Ln, 即可用二進碼樹來生成異字頭碼, 生成規(guī)律是: 從根出發(fā)開始生出2枝 ; 每一枝用一個碼元aj A=0,1來表示; 枝盡節(jié)來,節(jié)外生枝; 在第Li級端節(jié)點(Li級節(jié)點共有2

19、Li個)上,配置信 號單元 xi , i=1,2, , n ; 從根開始直奔對應(yīng)的端節(jié)點,沿途(聯(lián)枝)所遇到 的碼元 aj 所構(gòu)成的符號,即為對應(yīng)于該信號單元 xi 的碼字 wi 。異字頭碼無譯碼延時，構(gòu)造簡單。38結(jié)論：任一唯一可譯碼，總可以用與各相應(yīng)碼字長度一樣的異字頭碼代替。異字頭碼雖然只是唯一可譯碼的一種，但它具有代表性和普遍意義，在信息保持編碼中廣泛應(yīng)用。長度為L1,L2, ,Ln的M進制異字頭碼存在的充要條件，也使Kraft不等式成立。394.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計

20、編碼方法統(tǒng)計編碼方法40Shannon-Fano 編碼編碼 貝爾實驗室的 Claude Shannon 和 MIT 的 R.M.Fano 幾乎同時提出了最早的對符號進行有效編碼從而實現(xiàn)數(shù)據(jù)壓縮的 Shannon-Fano 編碼方法。信源字母概率a1a2a3a41/2=0.51/4=0.251/8=0.1251/8=0.125對于例4.2中的信源:Shannon-Fano 編碼的核心是構(gòu)造二進碼樹，構(gòu)造的方式非常簡單： 411) 將給定符號按照其概率從大到小排序 2) 將序列分成上下兩部分，使得上部概率總和盡可能接近下部概率總和,有：a1 0.5a2 0.25a3 0.125a4 0.125a1

21、 0.5 -a2 0.25a3 0.125a4 0.125Shannon-Fano 編碼步驟編碼步驟424) 分別對左右子樹重復(fù)2 、3兩步，直到所有的符號都成為二進碼樹的終端節(jié)點為止?，F(xiàn)在如下的二進碼樹：3) 把第2步中劃分出的上部作為二進碼樹的左子樹，記 0，下部作為二進碼樹的右子樹，記 1。 a1 0.5 0-a2 0.25 1a3 0.125a4 0.125a1 0.5 0-a2 0.25 1 0 -a3 0.125 1 0-a4 0.125 143a1 - 0 a2 10 a3 - 110 a4 - 111 根001110a1a2a3a4于是得到了此信息的編碼表：得到的碼表就是碼C4

22、4習(xí)題：二進制費諾編碼 信信源源符符號號 概概率率 編編碼碼 碼碼字字 碼碼長長 x1 0.32 0 00 2 x2 0.22 0 1 01 2 x3 0.18 0 10 2 x4 0.16 0 110 3 x5 0.08 0 1110 4 x6 0.04 1 1 1 1 1111 4 123456,()0.320.220.180.160.080.04XxxxxxxP X解：編碼過程如下表。對該信源編二進制費諾碼。平均碼長平均碼長 碼元碼元/符號符號 編碼效率編碼效率61( )2.4iiiLp x L()2.350.982.4H XL設(shè)有一單符號離散信源454.2 霍夫曼編碼霍夫曼編碼1952

23、年 ，霍夫曼(D.A.Huffman) 提出霍夫曼編碼, 又稱最佳編碼根據(jù)字符出現(xiàn)概率來構(gòu)造平均長度根據(jù)字符出現(xiàn)概率來構(gòu)造平均長度最短的異字頭碼字。最短的異字頭碼字。 46 霍夫曼碼的構(gòu)造霍夫曼碼的構(gòu)造理論基礎(chǔ)定理定理4.3在變長編碼中,若碼字長度嚴(yán)格按照所對應(yīng)符號出現(xiàn)概率的大小逆序排列,則其平均長度最短。47編碼步驟：編碼步驟： 將信源符號概率按遞減順序排列將信源符號概率按遞減順序排列; ; 將兩個最小的概率進行相加，并繼續(xù)這一步驟，直到概率將兩個最小的概率進行相加，并繼續(xù)這一步驟，直到概率 達到達到1.0為止為止; ; 在每對組合中的上部指定為在每對組合中的上部指定為1(或或0), ,下部

24、指定為下部指定為0(或或1); ; 畫出每個信源符號概率到畫出每個信源符號概率到1.0處的路徑處的路徑, ,記下沿路徑的記下沿路徑的1和和0 ; 對于每個信源符號都寫出對于每個信源符號都寫出1 1、0 0序列，則序列，則從右到左從右到左就得到霍就得到霍 夫曼編碼。夫曼編碼。48例例4-6對一個7符號信源A=a1,a2, ,a7, 求其霍夫曼編碼信源符號 出現(xiàn)概率 a1 0.20 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 碼長 碼 字 2 11 2 10 3 011 3 010 3 001 4 0001 4 00000.26010.11010

25、.35010.390110.61101.00049011a3根例4-6的Huffman二進碼樹11a110a2010a4001a50001a60000a750例4-6的信源熵為:霍夫曼編碼的平均字長為:(bit) 61. 2)(log)()(71iiiapapAH(bit) 72.2)(71iiiLapl編碼效率:( )2.6196 %2.72H Al51另例另例1對一個對一個7符號信源符號信源A=a1,a2, ,a7, 求其霍夫曼編碼求其霍夫曼編碼:信源符號 出現(xiàn)概率 a1 0.35 a2 0.20 a3 0.15 a4 0.12 a5 0.10 a6 0.05 a7 0.03 碼長 碼 字

26、 2 00 2 10 3 010 3 011 3 110 4 1110 4 11110.080.180.270.620.381.00111111000000關(guān)鍵：在每一步，總是最低概率的兩個符號構(gòu)成一對。關(guān)鍵：在每一步，總是最低概率的兩個符號構(gòu)成一對。52注意注意：哈夫曼的編法并不唯一哈夫曼的編法并不唯一每次對縮減信源兩個概率最小的符號分配每次對縮減信源兩個概率最小的符號分配“0”0”和和“1”1”碼碼元是任意的，所以可得到不同的碼字。只要元是任意的，所以可得到不同的碼字。只要在各次縮減信在各次縮減信源中保持碼元分配的一致性源中保持碼元分配的一致性，即能得到可分離碼字。即能得到可分離碼字。不同

27、的碼元分配，得到的具體碼字不同，但碼長不同的碼元分配，得到的具體碼字不同，但碼長k ki i不變，不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別；平均碼長也不變，所以沒有本質(zhì)區(qū)別；縮減信源時，若合并后的新符號概率與其他符號概率相等，縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，從編碼方法上來說，這幾個符號的次序可任意排列，編出這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的的碼都是正確的，但得到的碼字不相同碼字不相同。不同的編法得到不同的編法得到的的碼字長度碼字長度k ki i也不盡相同也不盡相同。53 單符號離散無記憶信源單符號離散無記憶信源對其編二進制哈夫曼碼。對其

28、編二進制哈夫曼碼。解：解：方法一方法一 合并后的新符號排在其它相同概率符號之后合并后的新符號排在其它相同概率符號之后12345,()0.40.20.20.10.1XxxxxxP X另例另例254 這兩種編碼哪一種更好呢？這兩種編碼哪一種更好呢？我們來計算一下二者的碼長。我們來計算一下二者的碼長。方法二：方法二：合并后的新符號排在其它相同概率符號的前面。合并后的新符號排在其它相同概率符號的前面。552221() ( )()qiiiiE lLP slL引入碼字長度偏離平均碼長的方差的概念：36. 1 2)2 . 24(1 . 0)2 . 23(2 . 0 )2 . 22(2 . 0)2 . 21

29、(4 . 0 22222方法一：16. 0 2)2 . 23(1 . 0 2)2 . 22(2 . 0)2 . 22(4 . 02222方法二：兩種編碼的平均碼長是一樣的，都是兩種編碼的平均碼長是一樣的，都是2.2，那一種更好呢，我，那一種更好呢，我們可以計算一下平均碼長的方差。們可以計算一下平均碼長的方差。56n可見：第二種編碼方法的碼長方差要小許多。意味著第二種可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。編碼方法的碼長變化較小，比較接近于平均碼長。第一種方法編出的第一種方法編出的5 5個碼字有個碼字有4 4種不同的碼長；種不同的碼長；第二

30、種方法編出的碼長只有第二種方法編出的碼長只有2 2種不同的碼長；種不同的碼長；顯然，顯然，第二種編碼方法更簡單、更容易實現(xiàn)，所以更好。第二種編碼方法更簡單、更容易實現(xiàn)，所以更好。57結(jié)論：在哈夫曼編碼過程中，對縮減信源符號按概率由結(jié)論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)使大到小的順序重新排列時，應(yīng)使合并后的新符號盡可能合并后的新符號盡可能排在靠前的位置排在靠前的位置，這樣可使合并后的新符號重復(fù)編碼次，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。數(shù)減少，使短碼得到充分利用。58Huffman編碼和譯碼過程編碼和譯碼過程編碼編碼輸出輸出Huffma

31、nHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號序列信源符號序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號序列信源符號序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號序列信源符號序列解碼解碼解碼后的解碼后的字符序列字符序列Huff

32、man碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號序列信源符號序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表編碼編碼輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表傳傳輸輸接收的接收的Huffman碼碼流緩沖器流緩沖器信源符號序列信源符號序列解碼解碼解碼后的解碼后的字符序列字符序列Huffman碼表碼表Huffman碼表碼表信源符號序列信源符號序列解碼后的解碼后的字符序列字符序列Huffman碼表碼表信源符號序列信源符號序列解碼后的解碼后的字符序列字符序列H

33、uffman碼表碼表信源符號序列信源符號序列Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器Huffman碼表碼表輸出輸出HuffmanHuffman碼流碼流接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流解碼后的解碼后的字符序列字符序列Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流信源符號序列信源符號序列解碼后的解碼后的字符序列字符序列Huffman碼表碼

34、表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流Huffman碼表碼表信源符號序列信源符號序列解碼后的解碼后的字符序列字符序列Huffman碼表碼表接收的接收的Huffman碼碼流緩沖器流緩沖器輸出輸出HuffmanHuffman碼流碼流59 信源編碼基本定理信源編碼基本定理霍夫曼編碼霍夫曼編碼定長的數(shù)據(jù)段定長的數(shù)據(jù)段當(dāng)信源符號的概率當(dāng)信源符號的概率 pj=2-k編碼效率等于編碼效率等于100%定長的數(shù)據(jù)段定長的數(shù)據(jù)段定長的數(shù)據(jù)段定長的數(shù)據(jù)段編碼效率等于編碼效率等于100%定長的數(shù)據(jù)段定長的數(shù)據(jù)段編碼效率等于編碼效率等于100%定長的數(shù)據(jù)段定長的數(shù)據(jù)

35、段編碼效率等于編碼效率等于100%定長的數(shù)據(jù)段定長的數(shù)據(jù)段編碼效率等于編碼效率等于100%定長的數(shù)據(jù)段定長的數(shù)據(jù)段變長的代碼變長的代碼( (只能分配接只能分配接近近log2pj的整數(shù)長碼字的整數(shù)長碼字) )60例4-7:對于二值圖像，如傳真機文件，輸出非“黑”即“白”，有：X=x1，x2=白，黑，其概率與所傳文件有關(guān)，假設(shè)對某頁文件，有P(x1)=0.9, P(x2)=0.1 。不考慮信號間的關(guān)聯(lián)時，其信息熵為：不考慮信號間的關(guān)聯(lián)時，其信息熵為：()0.9log0.90.1 log0.10.469 (bit/pel)H X 此時此時W=0,1，無論用定長碼還是最佳編碼，無論用定長碼還是最佳編碼

36、, 平均碼長至平均碼長至少為少為l1=1 (bit) ；此時霍夫曼編碼無壓縮作用此時霍夫曼編碼無壓縮作用編碼效率為編碼效率為1 =H(X)/ l1=46.9 %61解決辦法:A =a1, , am ;X K - X =x1, , xn 的延長的延長;W K - W =w1, , wn 的延長的延長, , 其平均長度為其平均長度為lK ;P(wi)=P( xi), P(W)= P(wi), i=1,2, ,n ;如果要求如果要求W K 為單義代碼為單義代碼, , 則則: :(4.2-1)式式(4.2-1)也叫做無失真編碼的基本定理。也叫做無失真編碼的基本定理。定理定理4.4(信源編碼定理信源編碼

37、定理):( )( )1loglogH XlH XmKmK62含義：含義：如果我們把如果我們把 X 延長后再對延長后再對 K 元組元組( K 為為延長長度延長長度)進行編碼，那么不必利用數(shù)據(jù)前后的關(guān)聯(lián)，只要進行編碼，那么不必利用數(shù)據(jù)前后的關(guān)聯(lián)，只要K 足夠大，則代表每消息單元足夠大，則代表每消息單元 X 的平均符號個數(shù)的平均符號個數(shù)l/K 可以任意趨向于下限?？梢匀我廒呄蛴谙孪蕖?3例例4-8: 利用最佳編碼利用最佳編碼, 以例以例4-7來說明來說明l/K趨向于下限的情況。趨向于下限的情況。把把 X 延長到延長到 X 2 ，假定信源是離散無記憶信源，有圖假定信源是離散無記憶信源，有圖4.7所所示

38、示 X 2 的最佳編碼：的最佳編碼：圖圖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.010.100.191.00111000W 2 01011011164W 2平均長度為平均長度為:l2 =0.81+0.092+0.093+0.013=1.29 bit/pelW 2的每一個元素代表兩個消息單元的每一個元素代表兩個消息單元,因此平均每一個消因此平均每一個消息單元

39、的符號個數(shù)是息單元的符號個數(shù)是:l2 /2 = 1.29/2 = 0.645 bit/pel2 =H(X)/ l2=72.7 %編碼效率提高到編碼效率提高到: :65把 X 延長到 X 3 ，有圖4.8所示 X 3 的最佳編碼：圖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)

40、 =0.0010.0180.0280.1620.2711.0000111001W 311111111101110111010110001110066W 3平均長度為:l3 =0.729+0.08133 +5( 30.09+0.001)=1.598 bit/pelW 3的每一個元素代表三個消息單元, 因此平均每一個消息單元的符號個數(shù)是:l3 /3 = 1.598/3 = 0.5327 bit/pel3 =H(X)/ l3=88.0 %編碼效率提高到:繼續(xù)下去,就可使 lK /K 0.469, 或=100% 67進一步減小 l/K , 利用信號的前后關(guān)聯(lián)減小下限, 即利用:H(X, Y )H(X)

41、+H(Y)(3.2-13)H(X | Y )H(X)(3.2-11b)或:可以減小下限,從而減小l/K要求知道P(X), P(X,Y) 或 P(X|Y) 才能進行最佳編碼。如果信號繼續(xù)有關(guān)聯(lián)可供利用，繼續(xù)延長，會使下限變得很小。68信源編碼理論信源編碼理論 給定消息單元集合X、符號集合A和X的概率分布P(X)， 可以采用最佳編碼，使代碼W 的平均長度滿足; 如果把X 延長至 X K ,則不必考慮信號前后的關(guān)聯(lián)性, 就可以是代表一個消息單元的符號個數(shù) l /K 任意接近 下限 H(X)/logm; 如果利用延長信號X K的前后關(guān)聯(lián),可使下限減小。具體實現(xiàn)時，如果將信號延長得過長，會使實際設(shè)備復(fù)雜

42、到不合理的程度。1log)(,log)(mXHmXHl69霍夫曼編碼選擇模型霍夫曼編碼選擇模型靜態(tài)統(tǒng)計模型 在編碼前統(tǒng)計要編碼的信息中所有字符的出現(xiàn)概率，然后根據(jù)統(tǒng)計出的信息建立編碼樹，進行編碼 。70缺點缺點 對數(shù)據(jù)量較大的信息，靜態(tài)統(tǒng)計要消耗大量的時間； 必須保存統(tǒng)計出的結(jié)果以便解碼時構(gòu)造相同的編碼樹，或者直接保存編碼樹本身，而且，對于每次靜態(tài)統(tǒng)計，都有不同的結(jié)果，必須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）； 靜態(tài)統(tǒng)計模型統(tǒng)計出的頻率是字符在整個文件中的出現(xiàn)頻率，往往反映不出字符在文件中不同局部出現(xiàn)頻率的變化情況，使用這一頻率進行壓縮，大多數(shù)情況下得不到太好壓縮效果，文

43、件有時甚至在壓縮后反而增大了。71一種有效的“靜態(tài)統(tǒng)計模型”的替代方案 如果要壓縮的所有信息在分布上存在著共同的特征，使用語言學(xué)家事先已經(jīng)建立好的字母頻率表來進行壓縮和解壓縮，不但不用保存多份統(tǒng)計信息，而且一般說來對該類文件有著較好的壓縮效果。比如我們要壓縮的是普通的英文文本，那么，字母 a 或者字母 e 的出現(xiàn)頻率應(yīng)當(dāng)是大致穩(wěn)定的。一種有效的“靜態(tài)統(tǒng)計模型”的替代方案 比如我們要壓縮的是普通的英文文本，那么，字母 a 或者字母 e 的出現(xiàn)頻率應(yīng)當(dāng)是大致穩(wěn)定的。72這種方案除了適應(yīng)性不太強以外，偶爾還會有一些尷尬的時候。缺點缺點 If Youth，throughout all history，

44、 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 constantly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 發(fā)現(xiàn)什么問題了嗎？整段話中竟沒有出現(xiàn)一次英文中出現(xiàn)頻率最高的字母 e 。這種方案除了適應(yīng)性不太強以外，偶爾還會有一些尷尬的時候

45、。發(fā)現(xiàn)什么問題了嗎？整段話中竟沒有出現(xiàn)一次英文中出現(xiàn)頻率最高的字母 e 。73對英文或中文文本，有一種比較實用的靜態(tài)模型：不是把字符而是把英文單詞或中文詞語作為統(tǒng)計頻率和編碼的單位進行壓縮。這種壓縮方式可以達到相當(dāng)不錯的壓縮效果，并被廣泛地用于全文檢索系統(tǒng)。74自適應(yīng)模型自適應(yīng)模型無需為解壓縮預(yù)先保存任何信息，整個編碼是在壓縮和解壓縮過程中動態(tài)創(chuàng)建的，而且自適應(yīng)編碼由于其符號頻率是根據(jù)信息內(nèi)容的變化動態(tài)得到的，更符合符號的局部分布規(guī)律，因此在壓縮效果上比靜態(tài)模型好許多。根據(jù)已經(jīng)編碼的符號頻率決定下一個符號的編碼。根據(jù)已經(jīng)編碼的符號頻率決定下一個符號的編碼。75算術(shù)編碼、字典編碼等更為適合采用自

46、適應(yīng)模型 但是，采用自適應(yīng)模型必須考慮編碼表的動態(tài)特性，即編碼表必須可以隨時更新以適應(yīng)符號頻率的變化。對于 Huffman 編碼來說，我們很難建立能夠隨時更新的二叉樹，76 霍夫曼碼的局限性霍夫曼碼的局限性霍夫曼編碼霍夫曼編碼文本文件壓縮文本文件壓縮二進制文件壓縮二進制文件壓縮適用于適用于經(jīng)過符號合并經(jīng)過符號合并77局限性局限性: : 輸入符號數(shù)受限于可實現(xiàn)的霍夫曼碼表尺寸輸入符號數(shù)受限于可實現(xiàn)的霍夫曼碼表尺寸 ; ; 譯碼復(fù)雜度譯碼復(fù)雜度; ; 需要知道輸入符號集的概率分布；需要知道輸入符號集的概率分布； 由于碼長不等，還存在一個輸入與輸出的速率由于碼長不等，還存在一個輸入與輸出的速率 匹配

47、問題。匹配問題。784.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計編碼方法統(tǒng)計編碼方法794.3 游程編碼游程編碼游程長度游程長度(RL: Run Length,簡稱游程或游長簡稱游程或游長) )： 由字符由字符( (或信號采樣值或信號采樣值) )構(gòu)成的數(shù)據(jù)流中各字符構(gòu)成的數(shù)據(jù)流中各字符重復(fù)出現(xiàn)而形成的字符串的長度。重復(fù)出現(xiàn)而形成的字符串的長度。用二進制碼字給出形成串的字符、串的長度用二進制碼字給出形成串的字符、串的長度及串的位置等信息，以此來恢復(fù)出原來的數(shù)及串的位置等信息，以此來恢復(fù)出原來的數(shù)據(jù)

48、流。據(jù)流。 游程長度編碼游程長度編碼(RLC) )：80游程編碼類型：游程編碼類型：變長游程編碼變長游程編碼使用位數(shù)是固定的，即使用位數(shù)是固定的，即RLRL位數(shù)是固定的，如果灰度位數(shù)是固定的，如果灰度連續(xù)相同的個數(shù)超過了固定位數(shù)所能表示的最大值，連續(xù)相同的個數(shù)超過了固定位數(shù)所能表示的最大值，則進入下一輪游程編碼；則進入下一輪游程編碼；定長游程編碼定長游程編碼對不同范圍的游程采用不同位數(shù)的編碼，即表示對不同范圍的游程采用不同位數(shù)的編碼，即表示RLRL位數(shù)不固定。位數(shù)不固定。81 基本的游程編碼基本的游程編碼基本的基本的RLC壓縮方法：壓縮方法：最初出現(xiàn)在最初出現(xiàn)在 IBM 3780 BYSYNC

49、 (Binary Synchronous Communication)通信協(xié)議中。通信協(xié)議中?；镜幕镜腞LC數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：XScRL數(shù)數(shù) 據(jù)據(jù) 流流圖圖4.9 基本的基本的RLC數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)82其中其中X ： 代表數(shù)據(jù)字符；代表數(shù)據(jù)字符； Sc： Sc X，表示有一個字符在此位置；，表示有一個字符在此位置； RL： 代表串（游程）的長度，字符重復(fù)出現(xiàn)的次數(shù)；代表串（游程）的長度，字符重復(fù)出現(xiàn)的次數(shù)；只有當(dāng)只有當(dāng)RL 3時時, 才有數(shù)據(jù)壓縮效益。才有數(shù)據(jù)壓縮效益。編碼時：先判斷編碼時：先判斷RL值，再決定是否值，再決定是否RLC； 解碼時：根據(jù)每一解碼時：根據(jù)每一X后的碼字是否為后

50、的碼字是否為Sc，再，再 決定下一個字的含義。決定下一個字的含義。83RLC壓縮效能:取決于數(shù)據(jù)流中重復(fù)字符出現(xiàn)次數(shù)、平均游程長度及所采用的編碼結(jié)構(gòu)。平均重復(fù)平均重復(fù)長度長度重復(fù)出現(xiàn)重復(fù)出現(xiàn)1010次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)2020次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)3030次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)4040次的壓縮比次的壓縮比重復(fù)出現(xiàn)重復(fù)出現(xiàn)5050次的壓縮比次的壓縮比41.0101.0201.0311.0421.05351.0201.0421.0641.0731.11161.0311.0641.0991.1361.17671.0421.0871.1361.1901.25

51、081.0531.1111.1761.2501.33391.0641.1361.2201.3161.429101.0751.1631.2661.3841.538表4.2 基本的游程編碼壓縮比84 二值圖像的游程編碼二值圖像的游程編碼僅有黑(“1”代表)、白(“0”代表)兩個亮度值的圖像。 經(jīng)掃描儀得到的氣象圖、工程圖、地圖、線 路圖等； 文字組成的文件圖像； 灰度圖像經(jīng)過位平面分解或抖動處理后 的圖像。最常用的傳輸方式：傳真二值圖像二值圖像編碼也往往指數(shù)字傳真編碼。85二值圖像的游程編碼二值圖像的游程編碼數(shù)據(jù)字符 X=白，黑對二值圖像每一掃描行： 白像素游程（白長） 黑像素游程（黑長）對不同長

52、度的白長和黑長，按其出現(xiàn)概率的不同分別配以不同長度的碼字。RLC利用多個像素之間的相關(guān)性，可得到較低的碼率下限。86二值圖像的二值圖像的RLC的兩種方式的兩種方式 不分白長和黑長，只根據(jù)長度進行編碼由于在實際圖像中, 白長和黑長的概率分布各異, 此方法不是很有效; 其最低比特率 滿足:WBnWBWBWBWBWBPPhnhll(4.3-1)其中：PW和PB分別是白像素和黑像素出現(xiàn)的概率; lW和lB分別是白長和黑長的平均像素數(shù)(平均長度 ); hWB為每個像素的熵值。 不分白長和黑長，只根據(jù)長度進行編碼 對白長和黑長分別編碼(前CCITT建議)87編碼過程：編碼過程： 先對圖像進行統(tǒng)計分別得出白

53、長為先對圖像進行統(tǒng)計分別得出白長為 i 的的 概率概率 PiW 和黑長為和黑長為 i 的概率的概率 PiB， 然后根據(jù)霍夫曼原則按然后根據(jù)霍夫曼原則按RL出現(xiàn)概率來分出現(xiàn)概率來分 配碼字。配碼字。二值圖像的二值圖像的RLC實為霍夫曼碼的具體應(yīng)用實為霍夫曼碼的具體應(yīng)用88由于各種由于各種 RL 的出現(xiàn)概率在行間、頁的出現(xiàn)概率在行間、頁間都不相同，且為求得概率，需要存間都不相同，且為求得概率，需要存儲數(shù)據(jù)并做統(tǒng)計計算，難以實時編碼儲數(shù)據(jù)并做統(tǒng)計計算，難以實時編碼CCITT的的T.4建議建議: 推薦推薦8幅標(biāo)準(zhǔn)傳真樣張為幅標(biāo)準(zhǔn)傳真樣張為統(tǒng)計依據(jù)統(tǒng)計依據(jù),根據(jù)各種根據(jù)各種RL的出現(xiàn)概率編出霍夫的出現(xiàn)概

54、率編出霍夫曼碼表，稱為改進型霍夫曼編碼曼碼表，稱為改進型霍夫曼編碼(MHC) 。89MH編碼規(guī)則: (見表4.7) RL=063， 用一個相應(yīng)的結(jié)尾碼表示用一個相應(yīng)的結(jié)尾碼表示 ; ; RL=641728，用一個組合基干碼加一個補充結(jié)尾碼；，用一個組合基干碼加一個補充結(jié)尾碼； RL(白白)=128, 補充結(jié)尾碼為補充結(jié)尾碼為0(白白)=00110101, 其編碼為其編碼為: 10010 | 00110101 RL(白白)=129, 補充結(jié)尾碼為補充結(jié)尾碼為1(白白)=000111, 其編碼為其編碼為: 10010 | 000111 規(guī)定每行都從白游程開始，若實際掃描由黑開始，則規(guī)定每行都從白游

55、程開始，若實際掃描由黑開始，則 需在行首加零長度白游程；每行結(jié)束要加同步碼需在行首加零長度白游程；每行結(jié)束要加同步碼EOL。90 游程編碼的局限性游程編碼的局限性 對二值圖像最為有效，但對數(shù)據(jù)文件就不那對二值圖像最為有效，但對數(shù)據(jù)文件就不那 么顯著，而對于課文實質(zhì)已無使用價值么顯著，而對于課文實質(zhì)已無使用價值; 壓縮字符與數(shù)值混合序列比較麻煩，要求區(qū)分壓縮字符與數(shù)值混合序列比較麻煩，要求區(qū)分 計數(shù)字段和常規(guī)字符；計數(shù)字段和常規(guī)字符； 需要較大容量的緩沖和較低誤碼的優(yōu)質(zhì)信道。需要較大容量的緩沖和較低誤碼的優(yōu)質(zhì)信道。914.1 基本原理基本原理 4.2 Huffman編碼編碼4.3 游程編碼游程編

56、碼4.4 算術(shù)編碼算術(shù)編碼4.5 LZW編碼編碼第四章第四章 統(tǒng)計編碼方法統(tǒng)計編碼方法92u 問題的引入問題的引入 Huffman碼等在實際應(yīng)用過程中，只有在信源符號概率分碼等在實際應(yīng)用過程中，只有在信源符號概率分布等于布等于2的負(fù)整次冪時，它們才能產(chǎn)生最佳效果，即產(chǎn)生最佳的負(fù)整次冪時，它們才能產(chǎn)生最佳效果，即產(chǎn)生最佳變長碼。變長碼。 假設(shè)某個字符的出現(xiàn)概率為假設(shè)某個字符的出現(xiàn)概率為 80%，那么該字符事實上只需，那么該字符事實上只需要要 -log2(0.8) = 0.322 位編碼，但位編碼，但Huffman 編碼一定會為其分編碼一定會為其分配一位配一位 0 或或1 的編碼。的編碼。 真的能

57、只輸出真的能只輸出 0.322 個個 0 或或 0.322 位信息嗎位信息嗎？4.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）934.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）u 算術(shù)編碼基本思路算術(shù)編碼基本思路 算術(shù)編碼一種非分組編碼算法。它是從全序列出發(fā)，算術(shù)編碼一種非分組編碼算法。它是從全序列出發(fā)，采用遞推形式的連續(xù)編碼。它不是將單個的信源符號映射采用遞推形式的連續(xù)編碼。它不是將單個的信源符號映射成一個碼字，而是將整個輸入序列的符號依據(jù)它們的概率成一個碼字，而是將整個輸入序列的符號依據(jù)它們的概率映射為實數(shù)軸上區(qū)間映射為實數(shù)軸上區(qū)間0 1)0 1)內(nèi)的一個

58、小區(qū)間，再在該小區(qū)間內(nèi)的一個小區(qū)間，再在該小區(qū)間內(nèi)選擇一個代表性的二進制小數(shù)，作為實際的編碼輸出。內(nèi)選擇一個代表性的二進制小數(shù)，作為實際的編碼輸出。 例如算術(shù)編碼對某條信息的輸出為例如算術(shù)編碼對某條信息的輸出為 10100011111010001111，那么它，那么它表示小數(shù)表示小數(shù) 0.10100011110.1010001111，也即十進制數(shù)，也即十進制數(shù) 0.640.64。941) 碼字刷新：碼字刷新：C(sai)=C(s)+P(ai)A(s)2) 區(qū)間刷新：區(qū)間刷新：A(sai)=p(ai)A(s) 設(shè)輸入符號串設(shè)輸入符號串s取自符號集取自符號集S=a1,a2,a3,am, p(ai)

59、=p1,p2,p3,pm, s后跟符號后跟符號ai擴展成符號串?dāng)U展成符號串sai，算術(shù)編碼的迭代關(guān)系為，算術(shù)編碼的迭代關(guān)系為: 符號累積概率：符號累積概率：初始條件：初始條件： 11)()(ikkiapaP1)(, 0)(, 1)(, 0)(pPACu 算術(shù)編碼方法具體過程算術(shù)編碼方法具體過程4.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）95當(dāng)處理當(dāng)處理ai時，區(qū)間時，區(qū)間A(s)寬度根據(jù)寬度根據(jù)ai出現(xiàn)概率出現(xiàn)概率p(ai)而變窄，符號而變窄，符號序列越長，相應(yīng)的子區(qū)間越窄，編碼的位數(shù)越多。符號串每序列越長，相應(yīng)的子區(qū)間越窄，編碼的位數(shù)越多。符號串每一步新擴展的碼字一步新擴

60、展的碼字C(sai)都是由原符號串的碼字都是由原符號串的碼字C(s)與新區(qū)間與新區(qū)間寬度寬度A(sai)的算術(shù)相加，的算術(shù)相加，“算術(shù)碼算術(shù)碼”由此得名。由此得名。算術(shù)編碼在傳輸任何信號算術(shù)編碼在傳輸任何信號ai之前，信號的完整范圍是之前，信號的完整范圍是) 1 , 0)()(),(ACC4.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）u 算術(shù)編碼方法具體過程算術(shù)編碼方法具體過程964.4 算術(shù)編碼（算術(shù)編碼（Arithmetic Coding）u 例：算術(shù)編碼方法具體編碼過程例：算術(shù)編碼方法具體編碼過程 設(shè)某信源取自符號集設(shè)某信源取自符號集S=a,b,c,e,r,!，!表示編