第6章 無失真信源編碼

第6章無失真信源編碼

信源編碼與數(shù)據(jù)壓縮6.1編碼的基本概念6.2“無失真”的本質(zhì)6.3定長碼6.4變長碼6.5變長碼的編碼方法（內(nèi)容略增）6.6算術(shù)編碼6.7LZW編碼

本章小結(jié)信源編碼與數(shù)據(jù)壓縮

對于信源來說，有三個重要問題需要解決：1、如何構(gòu)建描述信源的模型；2、信源輸出信息量的計算，即信源熵的問題；3、如何更有效的表示信源輸出問題，即信源壓縮編碼問題。信源編碼的主要任務(wù)就是：

減少冗余，提高編碼效率。1、信源編碼問題

信源編碼的基本途徑有兩個：一是使序列中各個符號盡可能地相互獨立，即解除相關(guān)性；二是使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。具體來說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的辦法把信源輸出符號序列變換為最短的碼字序列。許多情況下，并不要求在信宿精確重現(xiàn)信源的輸出，只要滿足一定的重建質(zhì)量要求即可，即允許信息傳輸中出現(xiàn)一定失真，這就是限失真信源編碼問題。例如，在電話通信中，只要能將通話內(nèi)容送達對方就可以了，對音質(zhì)并無太高要求。實際通信時，信道往往存在干擾，要完全精確地重現(xiàn)信源輸出幾乎是做不到的。這就允許接收信號有一定限度的失真。

限失真信源編碼問題（第7章重點介紹）2、數(shù)據(jù)壓縮問題

數(shù)據(jù)壓縮:就是用盡可能少的比特數(shù)來表示源信號（采樣和量化后數(shù)字信號），并能將其還原。

壓縮的任務(wù)就是保持信源信號在一個可以接受的狀況前提下,把需要的比特數(shù)減到最少程度，以達到減少存儲、處理和傳輸成本的目的。

信息理論認(rèn)為：若信源編碼的熵大于信源的實際熵，該信源中一定存在冗余度，去掉冗余不會減少信息量，仍可原樣恢復(fù)數(shù)據(jù)；但若減少了熵，數(shù)據(jù)則不能完全恢復(fù)。但在允許的范圍內(nèi)損失一定的熵，數(shù)據(jù)可以近似地恢復(fù)。

常用的壓縮編碼方法可以分為兩大類：1、無損壓縮編碼法，也稱冗余壓縮法或熵編碼法及無失真編碼；2、有損壓縮編碼法，也稱為熵壓縮法或限失真編碼。無損壓縮：是利用數(shù)據(jù)的統(tǒng)計冗余進行壓縮，可完全回復(fù)原始數(shù)據(jù)而不引起任何失真。但壓縮率是受到數(shù)據(jù)統(tǒng)計冗余度的理論限制，一般為2:1到5:1。特殊應(yīng)用場合的圖像數(shù)據(jù)(如指紋圖像，醫(yī)學(xué)圖像等)的壓縮通常采用這種壓縮。由于壓縮比的限制，僅使用無損壓縮方法是不可能解決圖像和數(shù)字視頻的存儲和傳輸?shù)乃袉栴}。經(jīng)常使用的無損壓縮方法有：

香農(nóng)Shannon編碼，哈夫曼Huffman編碼，游程(Run-length)編碼，LZW(Lempel-Ziv-Welch)編碼和算術(shù)編碼等。無損壓縮優(yōu)點：可以做到100％的保存、沒有任何信號丟失，并且轉(zhuǎn)換方便。無損壓縮不足：占用空間大、壓縮比不高而且缺乏硬件支持。有損數(shù)據(jù)壓縮：經(jīng)過壓縮、解壓的數(shù)據(jù)與原始數(shù)據(jù)不同,但是非常接近的壓縮方法，又稱破壞型壓縮；即將次要的信息數(shù)據(jù)壓縮掉，犧牲一些質(zhì)量來減少數(shù)據(jù)量，使壓縮比提高。如，利用人類對圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對理解原始圖像的影響縮小，卻換來了大得多的壓縮比。有損壓縮廣泛應(yīng)用于語音，圖像和視頻數(shù)據(jù)的壓縮。在多媒體應(yīng)用中，常見的有損壓縮方法有：PCM(脈沖編碼調(diào)制)，預(yù)測編碼；變換編碼，插值和外推法；統(tǒng)計編碼，矢量量化和子帶編碼等；混合編碼是近年來廣泛采用的方法。有損壓縮的優(yōu)點：在有些情況下能夠獲得比任何已知無損方法小得多的文件大小，同時又能滿足系統(tǒng)的需要。有損壓縮的不足：會影響圖像質(zhì)量，尤其是在仔細觀察的時候，質(zhì)量下降更加明顯。6.1編碼的基本概念6.1.1編碼器和譯碼器6.1.2碼的分類6.1.3N次（階）擴展碼6.1.1編碼器和譯碼器信源編碼器編碼的實質(zhì)：是對信源的原始符號按一定的數(shù)學(xué)規(guī)則進行的一種變換;以碼字代替原始信源符號;使變換后得到的碼符號接近等概率分布;從而提高信息的傳輸有效性。編碼器模型：輸入序列輸入序列中每一個符號序列si來自集合編碼輸出序列其中編碼輸出序列中每一個符號序列ci來自碼字集合

一般m=nW稱為碼字集合，wi

（i=1,2,…,m)稱為碼字譯碼是編碼的反過程。N長輸入序列L長碼字序列符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000如：若選用碼1，如果編碼器輸入序列S=u2u4u1，則編碼器輸出序列C=011100【例6-2，P84】幾種二進制編碼如表所示6.1.2碼的分類1、按編碼的目的分信源編碼目的：壓縮消息數(shù)據(jù)量，提高通信有效性；保密編碼目的：提高信息傳輸安全性信道編碼目的：消除噪聲影響，提高通信可靠性；調(diào)制編碼。2、按碼字的長度分等長碼：所有碼字長度相同變長碼：碼自的長度不同（碼1）（碼2、碼3、碼4、碼5）符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000如碼2例子：3、按碼字的奇異性分奇異碼：至少兩個符號的編碼相同（碼3）非奇異碼：所有碼字均不相同（正確譯碼的必要條件）（碼1、碼2、碼4、碼5）符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u4110111000110004、按譯碼時是否會產(chǎn)生歧義分符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000非唯一可譯碼：譯碼時會產(chǎn)生歧義（碼2）

（碼3、奇異碼）唯一可譯碼：譯碼時不會產(chǎn)生歧義（碼1、碼4、碼5）奇異碼一定是非惟一可譯碼非奇異碼不一定是惟一可譯碼，如碼2。碼2：如譯碼器接收到序列“01000010”，可譯為：也可譯為：5、按譯碼時是否需要知道下一個碼字的符號分即時碼：不需要知道下一個碼字的符號就能譯碼

（碼1、碼4）非即時碼：需要知道下一個碼字的符號才能譯碼

（碼5）

符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u4110111000110006、按符號si和ci之間的映射關(guān)系分分組碼：已經(jīng)出現(xiàn)的符號對當(dāng)前符號的編碼沒有影響；卷積碼：已經(jīng)出現(xiàn)的符號對當(dāng)前符號的編碼有影響；

符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000等長碼：所有碼字長度相同變長碼：碼字的長度不同奇異碼：至少兩個符號的編碼相同非奇異碼：所有碼字均不相同非唯一可譯碼：譯碼時會產(chǎn)生歧義唯一可譯碼：譯碼時不會產(chǎn)生歧義即時碼：不需要知道下一個碼字的符號就能譯碼非即時碼：需要知道下一個碼字的符號才能譯碼（碼1）（碼2、碼3、碼4、碼5）（碼3）（碼1、碼2、碼4、碼5）（碼1、碼4）（碼5）（碼2）（碼1、碼4、碼5）7、小結(jié)【例，增】考慮以下碼字特性。奇異碼非奇異碼非奇異碼非奇異碼非唯一可譯唯一可譯唯一可譯非即時碼即時碼碼的分類例子即時碼的構(gòu)造-樹圖通常情況下可以用碼樹來表示碼字的構(gòu)成：如果碼字序列符號為r進制的，可以用r個符號的碼樹來構(gòu)造碼字；每個碼樹有一個樹根A；樹根有r個樹枝；樹枝的盡頭稱為節(jié)點；每個節(jié)點生出是樹枝的數(shù)量等于碼符號的數(shù)量r；從而形成r進制的碼樹。幾點說明：碼樹中自樹根經(jīng)過一個分枝到達一階節(jié)點，一階節(jié)點最多為r個，二階節(jié)點的可能個數(shù)為r2個，n階節(jié)點最多有rn個；若將從每個節(jié)點發(fā)出的r個分枝分別標(biāo)以0，1，…，r-1，則每個n階節(jié)點需要用n個r元數(shù)字表示；用樹圖方法構(gòu)造的碼滿足即時碼的條件，因為從樹根到每一個終端節(jié)點所走的路徑均不相同，所以一定滿足對即時碼前綴的限制。如果有個q信源符號，那么在碼樹上就要選擇q個終端節(jié)點，用相應(yīng)r元基本符號表示這些碼字。若樹碼的各個分支都延伸到最后一級端點，此時將共有rn個碼字，這樣的碼樹稱為整樹，如圖(a)所示。否則就稱為非整樹，如圖(b)所示，這時的碼字就不是等長碼了。因此，碼樹與碼之間具有如下一一對應(yīng)的關(guān)系：樹根碼字起點；樹枝數(shù)碼的進制數(shù)；節(jié)點碼字的一部分；終端節(jié)點碼字；階數(shù)碼長；非整樹變長碼；整樹等長碼。6.1.3N次（階）擴展碼將N次擴展信源的概念加以延伸，可以得到N次擴展碼集合的N次擴展相應(yīng)碼字集合的N次擴展其中是一一對應(yīng)的。解：ABC000110AAABACBABBBCCACBCC000000010010010001010110100010011010【例6-3，P86】符號集U={A，B，C}分別編碼為00，01，10，試寫出它的2次擴展碼。N次擴展碼例子1例如下面的兩個例子，ACD編碼成為001011/0001111的形式，均為3階擴展碼。而3次擴展符號共有43=64個如：ABCD00011011ABCD0010011113次擴展符號3次擴展碼字3次擴展符號3次擴展碼字AAA000……AAB0001DDB11111101AAC00001DDC111111001……DDD111111111N次擴展碼例子2【例，增】6.2“無失真”的本質(zhì)無失真信源編碼：編碼時沒有信息丟失，譯碼器可以精確恢復(fù)編碼之前的消息。無失真信源編碼又叫“無損壓縮”無失真信源編碼的基本問題是研究如何用最少的比特數(shù)去表示離散信源的熵值，也就是如何找出最佳編碼方案若要實現(xiàn)無失真信源編碼，信源符號集合U和碼字集合W中的元素要相等，即n=m；

n>m失真；n<m浪費編碼之前的信息量=編碼之后的信息量6.3定長碼定長碼碼長l的確定假設(shè)對信源進行r元定長編碼，則存在唯一可譯碼的條件是：n≤rl即碼長其中，符號表示上取整運算。對信源N次擴展碼進行定長編碼，定長碼是惟一可譯碼的條件是nN≤rl即碼長對定長碼來說，碼長確定，編碼方案也就確定了。定長碼例子1【例6-4，P87】兩個信源，分別有4個和5個符號，如果分別對這兩個信源進行二進制定長編碼，試給出編碼方案。對于4個符號的信源，則n=4，r=2，因此碼長編碼方案可以是：符號碼字u100u201u310u411對于5個符號的信源，則n=5，r=2，因此碼長編碼方案可以是：符號碼字u1000u2001u3010u4011u5100解：編碼信息率和編碼效率設(shè)熵為H(U)的離散無記憶信源，若對信源的長為N的符號序列（即N次擴展）進行定長編碼，設(shè)碼字是從r個符號集中選取l個碼元構(gòu)成（即碼長為l），定義：

為編碼信息率又叫編碼速率。單位：bit/符號l/N表示平均一個信源符號用多少個r進制碼符號表示；編碼信息率的含義：平均每個信源符號用多少個二進制碼符號表示；定義編碼效率：=H(U)/R’，其中H(U)是信源的熵。編碼效率的含義：每個信源符號帶有的信息量（即理論上平均每個信源符號用多少個二進制碼表示）除以實際上用的二進制碼符號的個數(shù)，即效率。定長碼例子2【例6-5，P88】假設(shè)信源都是等概分布，試分別求例6-3的二次擴展碼，以及例6-4的兩種編碼的編碼信息率和編碼效率。解：(1)例6-3的二次擴展碼：在該碼中，N=2，r=2，l=4，n=3，則編碼信息率：編碼效率：說明：每個信源符號用兩個二進制符號表示，編碼效率只有79.25%；原因是：長度為2的二元序列有4個：00，01，10，11，但是該編碼中只用到3個，浪費了1個。(2)例6-4中有4個符號的信源：在該碼中，N=1，r=2，l=2，n=4，則編碼信息率：編碼效率：說明：每個信源符號用兩個二進制符號表示，編碼效率是100%；(3)例6-4中有5個符號的信源：在該碼中，N=1，r=2，l=3，n=5，則編碼信息率：編碼效率：說明：每個信源符號用三個二進制符號表示，但編碼效率只有77.4%；原因是：長度為3的二元序列有8個：000，001，010，011，100，101，110，111，但是該編碼中只用到5個，浪費了3個。編碼效率與擴展次數(shù)N的關(guān)系（增加內(nèi)容）定長編碼定理中，只有N足夠大的時候，編碼效率才能趨近于1；可以證明，只要：譯碼差錯率一定小于任意正數(shù)【例，增】設(shè)某單符號信源模型為若要求編碼效率為90%，經(jīng)過計算可知，N必須滿足如下條件原因是信源概率分布差異很大6.4變長碼

變長碼的引入6.4.1變長碼的衡量指標(biāo)6.4.2變長碼的特點6.4.3唯一可譯碼和即時碼的判別6.4.4無失真信源編碼定理（香農(nóng)第一定理）變長碼的引入定長編碼在理論上，可以達到很高的編碼效率，但從前面例子可以看到，在編碼效率、錯誤概率要求較高的情況下，擴展次數(shù)N要求非常大，這在實際工程中是無法實現(xiàn)的；當(dāng)N有限時，高傳輸效率的等長碼往往要引入一定的失真和錯誤，它不像變長碼那樣可以實現(xiàn)無失真編碼；在實際過程中，通常采用變長編碼。概率大的符號編碼為較短的碼字；概率小的符號編碼為較長的碼字。變長碼的引入變長碼的幾個衡量指標(biāo)平均碼長：每個信源符號平均需用的碼元數(shù)信息傳輸率：平均每個碼元攜帶的信息量編碼效率：6.4.1變長碼的衡量指標(biāo)說明平均碼長越小，壓縮效果越好；信息傳輸率R表示平均每個碼符號攜帶的信息量。而前面給出的編碼信息率R’表示平均每個信源符號用多少個二進制數(shù)表示；編碼效率（同前）表示理論上平均每個信源符號用多少個二進制碼符號的個數(shù)除以實際上用的二進制碼符號的個數(shù)。符號u1u2u3u4碼字010110111碼元數(shù)r=2（二元碼）碼長1233概率0.50.250.1250.125信源熵平均碼長編碼效率信息傳輸率變長碼幾個衡量指標(biāo)例子【例，增】比特/符號比特/碼符號6.4.2變長碼的特點1、能夠提高壓縮效果【例6-6，P90】對離散無記憶信源分別用定長碼和變長碼對其編碼，編碼結(jié)果如表。求平均碼長。符號定長碼變長碼u1000u20110u310110u411111解：計算得：定長碼平均碼長為2變長碼平均碼長為1.75。2、使信道復(fù)雜化【例6-7，P90】接例6-6，假設(shè)信源每秒鐘輸出一個信源符號，信源輸出一個信源序列為u1u3u2，則經(jīng)過變長編碼后：信道第1秒；傳輸1個符號“0”；信道第2秒；傳輸3個符號“110”；信道第3秒；傳輸2個符號“10”；增加了信道的復(fù)雜化。6.4.3唯一可譯碼和即時碼的判別對信源進行編碼的兩個定理（兩個不等式）【定理6-1】克拉夫特（Kraft）不等式：對于碼長分別為l1,l2,…,ln的r元碼，存在即時碼的充要條件是【定理6-2】麥克米倫（McMillan）不等式：對于碼長分別為l1,l2,…,ln的r元碼，存在唯一可譯碼的充要條件是說明：在碼長選擇的條件上，即時碼與惟一可譯碼是一致的；惟一可譯碼并不比即時碼有什么更寬松的條件。證明證明碼1：因此，必存在至少一種碼長為2222的二元碼是即時碼（或唯一可譯碼）。碼1既是即時碼，又是唯一可譯碼。【例6-8，P93】接例6-2，分析例6-2給出的5種編碼方法的碼長是否能構(gòu)成即時碼（或唯一可譯碼）。唯一可譯碼、即時碼判斷例子解：符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000奇異碼：至少兩個符號的編碼相同非奇異碼：所有碼字均不相同非唯一可譯碼：譯碼時會產(chǎn)生歧義唯一可譯碼：譯碼時不會產(chǎn)生歧義即時碼：不需要知道下一個碼字的符號就能譯碼非即時碼：需要知道下一個碼字的符號才能譯碼（碼3）（碼1、碼2、碼4、碼5）（碼1、碼4）（碼5）（碼2）（碼1、碼4、碼5）碼2、3：因此，碼長為1222的二元碼必不可能是即時碼（或唯一可譯碼。符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000奇異碼：至少兩個符號的編碼相同非奇異碼：所有碼字均不相同非唯一可譯碼：譯碼時會產(chǎn)生歧義唯一可譯碼：譯碼時不會產(chǎn)生歧義即時碼：不需要知道下一個碼字的符號就能譯碼非即時碼：需要知道下一個碼字的符號才能譯碼（碼3）（碼1、碼2、碼4、碼5）（碼1、碼4）（碼5）（碼2）（碼1、碼4、碼5）碼4、5：因此，必存在至少一種碼長為1234的二元碼是即時碼（或唯一可譯碼），碼4既是即時碼，又是唯一可譯碼。碼5是唯一可譯碼，但不是即時碼。符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000奇異碼：至少兩個符號的編碼相同非奇異碼：所有碼字均不相同非唯一可譯碼：譯碼時會產(chǎn)生歧義唯一可譯碼：譯碼時不會產(chǎn)生歧義即時碼：不需要知道下一個碼字的符號就能譯碼非即時碼：需要知道下一個碼字的符號才能譯碼（碼3）（碼1、碼2、碼4、碼5）（碼1、碼4）（碼5）（碼2）（碼1、碼4、碼5）唯一可譯碼判別方法碼字集合的構(gòu)造設(shè)S0為原始碼字的集合，再構(gòu)造一系列集合S1

,S2

,…；集合S1的構(gòu)造：考察S0中所有碼字，若碼字是碼字的前綴，即，則將后綴A列為S1中的元素；Sn（n>1）的構(gòu)造：若有碼字，且是的前綴，即則將后綴A列為Sn中的元素；同樣，若有碼字是的前綴，即，則將后綴A’也列為Sn中的元素。一直到更新的集合為空集為止。碼字集合構(gòu)造的舉例說明S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde

【命題6-1】

一種碼是唯一可譯碼的充要條件是S1,S2,…中沒有一個含有S0中的碼字。唯一可譯碼的判別方法唯一可譯碼判別例子【例6-9，P94】接例6-2，分析例6-2給出的5種編碼方法是否為唯一可譯碼。解：分別構(gòu)造各自的集合符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000碼1S0S100011011?碼2S0S101000010碼3S00110011碼4S0S11010010001?碼5S0S1S21101001000000000?碼1：S0中不存在一個碼字是另一個碼字前綴的情況，S1為空集，因此碼1是唯一可譯碼。碼2：S0中的0是00的前綴，將后綴0放入集合S1中，此時S1中已經(jīng)包含了S0中的碼字，無需向下再構(gòu)造集合就能判定碼2不是唯一可譯碼。碼3：S0中本身就出現(xiàn)了S0中的碼字，因此碼3不是唯一可譯碼。碼4：S0中不存在一個碼字是另一個碼字前綴的情況，S1為空集，因此碼4是唯一可譯碼。碼5：S0中有一個碼字是另一個碼字前綴的情況，將所有后綴放入S1中，從S0和S1中各取一個碼字，不存在一個碼字是另一個碼字前綴的情況，S2為空集，且S1中不包含S0中碼字，因此碼5是唯一可譯碼。唯一可譯碼判別例子即時碼的判別方法即時碼的判別方法

【命題6-2】

一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。【例6-10，P94】接例6-9，在例6-9中已經(jīng)知道，碼1、碼4和碼5是唯一可譯碼，試判別哪些是即時碼。解：符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000碼1：其中任何一個碼字都不是其他碼字的前綴，因此碼1是即時碼。碼4：其中任何一個碼字都不是其他碼字的前綴，因此碼4是即時碼。碼5：存在多個一個碼字是其他碼字前綴的情況，因此碼5不是即時碼。6.4.4無失真信源編碼定理（香農(nóng)第一定理）問題的引出：緊致碼（或最佳碼）：某種編碼方式的平均碼長小于所有其他編碼方式；無失真信源編碼基本問題：確定最佳碼；平均碼長有極限值嗎？如果有，值是多少？變長編碼定理解決這個問題。說明：熵除以logr只是為了將熵的單位轉(zhuǎn)換到r進制，以保持與平均碼長的單位統(tǒng)一；【定理6-3】對于熵為H(U)的離散無記憶信源，若對其進行r元信源編碼，則一定存在一種編碼方式構(gòu)成唯一可譯碼，其平均碼長滿足上式記為：如果是二元編碼，可表示為：該定理說明，要構(gòu)成唯一可譯碼，平均碼長要處在信源熵和信源熵加1之間。證明【定理6-4】無失真變長信源編碼定理（香農(nóng)第一定理）。離散無記憶信源U的N次擴展信源UN，其熵為H(UN)，對該擴展信源UN進行r元編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源UN中每個信源符號（即長度為N的信源序列）所需的平均碼長滿足：或者當(dāng)時其中是無記憶N次擴展信源UN中每個信源符號（即長度為N的信源序列）所對應(yīng)的平均碼長；表示原始信源U中每個信源符號所對應(yīng)的平均碼長。證明N次擴展信源表達式1說明：和定理6-4中的都是是原始信源U中每個信源符號所對應(yīng)的平均碼長，定理6-3中的，為了得到這個平均值，不是直接對單個信源符號編碼，而是對N次擴展信源編碼得到的。但不同的是，對于以r=2為例，則這說明，總可以找到一種惟一可譯碼，它的平均碼長處在信源熵和信源熵加1之間。而且當(dāng)平均碼長小于信源熵的時候，這種編碼肯定不是唯一可譯碼。還說明編碼效率最大是100%該定理并未給出這種惟一可譯碼的構(gòu)造方法。這表明，當(dāng)N充分大時，每個信源符號所對應(yīng)的平均碼長等于r進制的信源熵若編碼的平均碼長小于該信源熵，則唯一可譯碼不存在。表達式2說明：將定理6-4的結(jié)論推廣到平穩(wěn)遍歷的有記憶信源，有其中，為有記憶信源的極限熵。無失真信源編碼定理是香農(nóng)信息論的三大定理之一。編碼速率類似于定長碼中的編碼速率，可以定義變長碼的編碼速率：它表示r元編碼后平均每個信源符號用多少個二進制符號表示。于是定理6-4又可以表述為，若：就存在唯一可譯的變長編碼。若：則不存在唯一可譯的變長編碼。不能實現(xiàn)無失真信源編碼。編碼速率編碼效率【定理6-5】編碼效率一定小于等于1，其中平均碼長越短，即越接近于它的極限值，那么編碼效率越趨近于1，效率就越高；說明：因此，可用編碼效率η來衡量各種編碼的優(yōu)劣。證明6.5變長碼的編碼方法6.5.1香農(nóng)編碼6.5.2費諾編碼6.5.3霍夫曼碼6.5.4游程編碼6.5.1香農(nóng)編碼設(shè)有離散無記憶信源34香農(nóng)編碼方法的步驟：1按信源符號的概率從大到小的順序排隊，不妨設(shè)2香農(nóng)編碼例子設(shè)有一單符號離散無記憶信源試對該信源編二進制香農(nóng)碼，并求平均碼長和編碼效率?！纠?，增】編碼過程：（1）計算累加概率信源熵：平均碼長：編碼效率：（2）編碼效率計算6.5.2費諾編碼設(shè)有離散無記憶信源費諾編碼方法的步驟：按編碼進制數(shù)r將概率分組，使每組概率盡可能接近或相等。2給每個分組分配一個碼元。3對每個分組重復(fù)2、3步，直到不可分為止。4信源符號所對應(yīng)的碼字即為費諾碼。51按信源符號的概率從大到小的順序排隊，不妨設(shè)費諾編碼例子設(shè)有一單符號離散無記憶信源試對該信源編二進制費諾碼，并求平均碼長和編碼效率。【例，增】（1）編碼過程說明：可以看出本例中費諾碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。信源熵：平均碼長：編碼效率：（2）編碼效率計算費諾碼具有如下的性質(zhì)：費諾碼的編碼方法實際上是一種構(gòu)造碼樹的方法，所以費諾碼是即時碼。費諾碼考慮了信源的統(tǒng)計特性，使概率大的信源符號能對應(yīng)碼長較短的碼字，從而有效地提高了編碼效率。費諾碼不一定是最佳碼。因為費諾碼編碼方法不一定能使短碼得到充分利用:當(dāng)信源符號較多時，若有一些符號概率分布很接近時，分兩大組的組合方法就會很多。可能某種分大組的結(jié)果，會使后面小組的“概率和”相差較遠，從而使平均碼長增加。r元費諾碼前面討論的費諾碼是二元費諾碼；對r元費諾碼，與二元費諾碼編碼方法相同，只是每次分組時應(yīng)將符號分成概率分布接近的r個組。6.5.3霍夫曼碼1、二元霍夫曼碼1952年，霍夫曼（Huffman）提出了一種構(gòu)造最佳碼的方法，這是一種最佳的逐個符號的編碼方法，一般就稱作霍夫曼碼設(shè)有離散無記憶信源二元霍夫曼編碼方法的步驟：將兩個概率最小的符號合并成一個新符號，新符號的概率為兩個符號概率之和，得到只包含n－1個符號的縮減信源U12將信源符號按概率由大到小順序排隊1依次繼續(xù)，直至信源最后只剩下１個符號為止。4把縮減信源U1的符號仍按概率從大到小排列，將其中兩個概率最小的符號合并成一個符號，形成n－2個符號的縮減信源U23將每次合并的兩個信源符號分別用0和1碼符號表示。5從最后一級縮減信源開始，向前返回，就得出各信源符號所對應(yīng)的碼符號序列，即得各信源符號對應(yīng)的碼字。6霍夫曼編碼過程二元霍夫曼編碼例子1【例6-11，P99】對離散無記憶信源進行二元霍夫曼編碼，并求平均碼長和編碼效率（1）編碼過程信源熵：（比特/信源符號）平均碼長：（碼符號/信源符號）編碼效率：（2）編碼效率計算二元霍夫曼編碼例子2【例6-12，P99】對信源的二次擴展信源進行二元霍夫曼編碼。解：信源U的二次擴展信源為：按例1方法，對其進行二元霍夫曼編碼，為：符號00011011碼字010110111設(shè)有一個長度為60的信源序列：01000111100011110010011000000000000100001100000000000100011編碼后，變成長度為53的序列10010111110010111110100111000000110010110000001100111做到無失真壓縮【例6-13，P99】對離散無記憶信源進行二元霍夫曼編碼，并求平均碼長和編碼效率。二元霍夫曼編碼例子3（1）編碼過程可以有如下兩種方法：信源熵：（比特/信源符號）平均碼長：（碼符號/信源符號）編碼效率：（2）編碼效率計算對于兩種編碼方法，有碼長方差這兩種編碼方式的平均碼長和編碼效率均相同，如何衡量這兩種編碼方式的好壞呢？碼長方差方差小意味著更接近等長碼,更易于傳輸，所以方法(a)要優(yōu)于方法(b)結(jié)論：進行赫夫曼編碼時，為得到碼方差最小的碼，應(yīng)使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。

2多元霍夫曼碼每次把概率最小的r個符號合并成一個新的符號，并分別用0,1,…,(r-1)等碼元表示為了使短碼得到充分利用，使平均碼長最短，必須使最后一步的縮減信源有r個信源符號因此對于r元編碼，信源U符號個數(shù)n必須滿足：n=(r-1)Q+r

即要求方程n=(r-1)Q+r有解，其中Q為未知數(shù)。當(dāng)此方程沒有解時，可以通過人為增加一些概率為0的符號來解決。r元霍夫曼編碼方法的步驟：r元霍夫曼編碼例子1【例6-14，P101】對例6-13離散無記憶信源分別進行三元霍夫曼和四元霍夫曼編碼。三元霍夫曼編碼此時：n=5,m=3，因此n=(m-1)Q+m是有解的，解為Q=1平均碼長：編碼效率：四元霍夫曼編碼此時：n=5,m=4，因此n=(m-1)Q+m是無解的，需要增加2個概率為0的符號平均碼長：編碼效率：霍夫曼碼的最佳性霍夫曼碼是最佳碼（緊致碼）霍夫曼碼是即時碼：任一碼字都不是其他碼字的前綴。6.5.4游程編碼前面的幾種編碼方法主要時針對無記憶信源，對有記憶信源，這些編碼方法的效率并不高，特別是對二元相關(guān)信源，需要一些其它的方法。游程編碼就是這樣的方法，對相關(guān)信源的編碼更有效。

游程（Run-Length，簡記RL）

：指數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。在二元信源中，連續(xù)的一段‘0’稱為一個‘0’游程，‘0’的個數(shù)稱為此游程的長度，同樣，也有‘1’游程。因為游程長度是隨機的，其取值可以是1，2，3，…

游程編碼（Run-LengthCoding，簡記RLC）：用交替出現(xiàn)的‘0’游程、‘1’游程的長度，來表示任意二元序列而產(chǎn)生的一個新序列。它和二元序列是一個一一對應(yīng)的變換。例如：000101110010001……31132131……若已知二元序列以0起始，從游程序列很容易恢復(fù)成原來的二元序列游程編碼特別適用于對相關(guān)信源的編碼。對二元相關(guān)信源，其輸出序列往往會出現(xiàn)多個連續(xù)的“0”或連續(xù)的“1”。對二元序列，“0”游程和“1游程”總是交替出現(xiàn)的，如果規(guī)定二元序列是以“0”開始的，那么第一個游程是“0”游程，第二個游程必為“1”游程，第三個游程又是“0”游程等等。將任何二元序列變換成游程長度序列，這種變換是一一對應(yīng)的，因此是可逆的、無失真的。因為游程長度是隨機的、多值的，所以游程序列本身是多元序列，對游程序列可以按霍夫曼編碼或其他編碼方法進行處理以達到壓縮碼率的目的。說明：游程編碼仍是變長碼，有著變長碼固有的缺點，即需要大量的緩沖和優(yōu)質(zhì)的通信信道。此外，由于游程長度可從“1”直到無窮大，這在碼字的選擇和碼表的建立方面都有困難，實際應(yīng)用時尚需采取某些措施來改進。例如，通常長游程出現(xiàn)的概率較小，所以對于這類長游程所對應(yīng)的小概率碼字，在實際應(yīng)用時采用截斷處理的方法。游程編碼已在圖文傳真、圖像傳輸?shù)韧ㄐ殴こ碳夹g(shù)中得到應(yīng)用。在實際中還常常將游程編碼與其他編碼方法綜合起來使用，以期得到更好的壓縮效果。下面以三類傳真機中使用的壓縮編碼的國際標(biāo)準(zhǔn)MH編碼為例說明游程編碼的實際應(yīng)用。MH編碼:文件傳真是指一般文件、圖紙、手寫稿、表格、報紙等文件的傳真，這種信源是黑白二值的，也即信源為二元信源（q=2）。MH編碼是一維編碼方案，它是一行一行的對文件傳真數(shù)據(jù)進行編碼。編碼將游程編碼和霍夫曼碼相結(jié)合，是一種改進的霍夫曼碼。對黑白二值文件傳真，每一行由連續(xù)出現(xiàn)的“白（用碼符號0表示）像素”或連續(xù)出現(xiàn)“黑（用碼符號1表示）像素”組成。MH碼分別對“黑”、“白”像素的不同游程長度進行霍夫曼編碼，形成黑、白兩張霍夫曼碼表。MH碼的編、譯碼都通過查表進行。MH碼以國際電話電報咨詢委員會（CCITT）確定的8幅標(biāo)準(zhǔn)文件樣張為樣本信源，對這8幅樣張作統(tǒng)計，計算出“黑”、“白”各種游程長度的出現(xiàn)概率，然后根據(jù)這些概率分布，分別得出“黑”、“白”游程長度的霍夫曼碼表。碼編碼規(guī)則如下：游程長度在063時，碼字直接用相應(yīng)的終端碼表示。游程長度在641728，用一個形成碼加上一個終端碼作為相應(yīng)碼字。規(guī)定每行都從白游程開始。若實際出現(xiàn)黑游程開始的話，則在行首加上長度為零的白游程碼字，每行結(jié)束時用一個結(jié)束碼(EOL)作標(biāo)記。每頁文件開始第一個數(shù)據(jù)前加一個結(jié)束碼，每頁結(jié)尾連續(xù)使用6個結(jié)束碼表示結(jié)尾。譯碼時，每一行的碼都應(yīng)恢復(fù)出1728個像素，否則有錯。為了在傳輸時可實現(xiàn)同步操作，規(guī)定T為每個編碼行的最小傳輸時間，一般規(guī)定T最小為20，最大為5。若編碼行傳輸時間小于T，則在結(jié)束碼之前填上足夠的“0”碼元(稱填充碼)。

如果采用編碼僅僅是用于存儲，則可省去步驟中的4)至6)步。

設(shè)某頁傳真文件中某一掃描行的像素點為：

17白5黑55白10黑l641白解:通過查表可得該掃描行的碼為：

17白5黑55白10黑1600白（+）41白EOL101011001101011000000010001001101000101010000000000001

該行經(jīng)編碼后只需用54位二元碼元，而原來一行共有1728個像素，如用“0”表示白，用“l(fā)”表示黑，則共需1728位二元碼元。可見，這一行數(shù)據(jù)的壓縮比為1728:54＝32，因此壓縮效率很高?！纠觥坑纬叹幋a例子6.6算術(shù)編碼

算術(shù)編碼的基本思想6.6.1算術(shù)編碼基本原理6.6.2算術(shù)編碼方法6.6.3算術(shù)譯碼方法20世紀(jì)70年代末、80年代初由Rissanen、Pasco和Landon等人發(fā)展起來的編碼方法算術(shù)編碼的思想：用信源符號對應(yīng)的概率區(qū)間中的一個點來表示該信源符號。算術(shù)編碼不是對信源符號編碼，而是對N次擴展信源（信源符號序列）編碼。算術(shù)編碼適合于小消息信源，即n較小的信源。算術(shù)編碼基本思想6.6.1算術(shù)編碼基本原理一次擴展二次擴展三次擴展符號abaaabbabbaaaaabababaaabbbabbbabbb概率0.70.30.490.210.210.090.3430.1470.1470.1470.0630.0630.0630.027碼字1010100000100110100111000100110101011編碼長度11123322334444平均碼長10.910.90867編碼效率88.1%96.2%96.9%為什么對信源序列編碼【例6-15，P102】試分別對信源的一次、二次、三次擴展信源進行霍夫曼編碼，并比較平均碼長和編碼效率?；窘Y(jié)論對信源序列編碼比對信源符號編碼能獲得更好的壓縮效果；序列越長，單個符號所需的平均碼長越短，編碼效率越高；算術(shù)編碼的基本思想算術(shù)編碼是對信源序列進行無失真信源編碼的一種方法；算術(shù)編碼適合于小消息信源，即n較小的信源。算術(shù)編碼的思想：用信源符號對應(yīng)的概率區(qū)間中的一個點來表示該信源序列。算術(shù)編碼不是對信源符號編碼，而是對N次擴展信源（信源符號序列）編碼。什么是概率區(qū)間說明以例6-15信源為例；對于一次擴展信源，序列a的概率區(qū)間是[0,0.7]，序列b的概率區(qū)間是[0.7,1]；對于二次擴展信源，序列aa的概率區(qū)間是[0,0.49]，序列ab的概率區(qū)間是[0.49,0.7]

,序列ba的概率區(qū)間是[0.7,0.91]，序列bb的概率區(qū)間是[0.91,1]；對于三次擴展信源，序列aaa的概率區(qū)間是[0,0.3439]，.…6.6.2算術(shù)編碼方法信源符號積累概率定義為信源序列S的積累概率的遞推公式為：F(Sur)=F(S)+p(S)F(ur)p(Sur)=p(S)p(ur)其中F(Sur)——信源序列S添加一個新的信源符號ur后所得到的新序列Sur的積累概率p(S)——信源序列S的概率F(ur)——信源符號ur的積累概率p(Sur)——信源序列S添加一個新的信源符號ur后所得到的新序列Sur的概率p(ur)——信源符號ur的概率1、積累概率的遞推公式2、算術(shù)編碼的碼長把信源序列S的編碼取前L位二進制小數(shù)，若后面有尾數(shù)就在第L位進位如：計算出的數(shù)值為

0.011011，且L=3，則序列S的二進制編碼是1003、算術(shù)編碼方法二進制算術(shù)編碼的計算步驟計算信源符號的積累概率

設(shè)S＝（空集），F(xiàn)()＝0，p()＝1計算序列的積累概率F(Sui)和概率p(Sui)計算碼長L

將F(S)寫成二進制數(shù)的形式，取其小數(shù)點后前L位作為序列S的碼字，若后面有尾數(shù)就在第L位進位1.計算信源符號的積累概率2.設(shè)S＝（空集），F(xiàn)()＝0，p()＝13.計算序列的積累概率F(Sui)和概率p(Sui)4.計算碼長L

5.將F(S)寫成二進制數(shù)的形式，取其小數(shù)點后前L位作為序列S的碼字，若后面有尾數(shù)就在第L位進位信源符號的積累概率：F(0)＝0，F(xiàn)(1)＝0.25序列F(S)p(S)L序列的碼字

01F(1)＝F()＋p()F(1)＝0＋1×0.25＝0.25=(0.01)2p(1)＝p()p(1)＝1×0.75＝0.75=(0.11)20.250.751(0.01)2(0.11)2F(10)＝F(1)＋p(1)F(0)＝0.25＋0.75×0＝0.25=(0.01)2p(10)＝p(1)p(0)＝0.75×0.25＝0.1875=(0.0011)20.250.187510(0.01)2(0.0011)2F(101)＝F(10)＋p(10)F(1)＝0.296875＝(0.010011)2p(101)＝p(10)p(1)＝0.140625＝(0.001001)20.2968750.140625101(0.010011)2(0.001001)2F(1010)＝F(101)＋p(101)F(0)＝0.296875＝(0.010011)2p(1010)＝p(101)p(0)＝0.03515625=(0.00001001)20.2968751010

(0.010011)2(0.00001001)2501010【例6-16，P104】求信源序列S=1010的算術(shù)編碼【例6-16，續(xù)】

求S=11111100的算術(shù)編碼6.6.3算術(shù)譯碼方法（1）求出各個信源符號的概率區(qū)間和積累概率，并將碼字轉(zhuǎn)換成十進制小數(shù)形式；（2）判斷十進制小數(shù)所在符號區(qū)間，翻譯出1個符號u；（3）按照公式（6-13）計算出一個新的十進制小數(shù)；

（6-13）（4）重復(fù)2、3直至全部信源序列被翻譯完為止?！纠?-17，P105】對例6-16中得到的碼字01010譯碼值所在區(qū)間譯得的符號計算過程0.3125[0.25,1]10.08333[0,0.25)00.3333[0.25,1]10.1111[0,0.25)06.7LZW編碼

LZW編碼歷史6.7.1LZW基本原理6.7.2LZW編碼方法信源統(tǒng)計特性未知時的無失真信源編碼LZW編碼歷史1977年，以色列學(xué)者蘭佩爾(A.lempel)和奇費(J.ziv)提出一種語法解析碼，簡稱LZ編碼1978年提出了改進算法，LZ77和LZ781984年，韋爾奇(T.A.Welch)將LZ78算法修改成一種實用的算法，后定名為LZW算法LZW編碼歷史6.7.1LZW基本原理LZW編碼算法的基本思想是建立一個編碼表(轉(zhuǎn)換表)，韋爾奇稱其為串表，該表將輸入字符串映射成定長碼字輸出，通常碼長設(shè)為12bitLZW編碼算法從一個空符號串表開始工作，在產(chǎn)生輸出串的同時動態(tài)更新串表，這樣串表就對應(yīng)產(chǎn)生壓縮信源的特殊性質(zhì)簡單說，LZW算法就是將待編碼信源序列進行分割，每一部分編碼為一個長度為12bit的0-1串。字符串碼字6.7.2LZW編碼方法將待編碼非空字符串中的所有單個字符存入串表中，并給每個符號賦一個碼字值讀入第一個輸入字符，賦給前綴串變量P讀下一個輸入字符，賦給擴展串變量S如果S為空，輸出P，停止；否則執(zhí)行步驟5如果PS不在串表中，則將P

對應(yīng)的碼字值輸出，將PS存入串表，并分配一個碼字值，同時將擴展字符S賦給P

；否則將PS賦給P

；重復(fù)步驟3【例6-18，P107】

對信源序列XYXYZYXYXYXXXXXXX進行LZW編碼字符串XYZ碼字1231.將待編碼非空字符串中的所有單個字符存入串表中，并給每個符號賦一個碼字值2.讀入第一個輸入字符，賦給前綴串變量P3.讀下一個輸入字符，賦給擴展串變量S4.如果S為空，輸出P，停止；否則執(zhí)行步驟55.如果PS不在串表中，則將P

對應(yīng)的碼字值輸出，將PS存入串表，并分配一個碼字值，同時將擴展字符S賦給P

；否則將PS賦給P

；6.重復(fù)步驟3P=XS=Y1字符串XYZXY碼字1234P=YS=X2字符串XYZXYYX碼字12345P=XS=Y字符串XYZ