第6章 無失真信源編碼

第6章無失真信源編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（碼1、碼4）非即時(shí)碼：需要知道下一個(gè)碼字的符號(hào)才能譯碼

（碼5）

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

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

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

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

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

【命題6-2】

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

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

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

游程（Run-Length，簡(jiǎn)記RL）

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

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

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

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

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

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

該行經(jīng)編碼后只需用54位二元碼元，而原來一行共有1728個(gè)像素，如用“0”表示白，用“l(fā)”表示黑，則共需1728位二元碼元?？梢?，這一行數(shù)據(jù)的壓縮比為1728:54＝32，因此壓縮效率很高。【例，增】游程編碼例子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ù)編碼的思想：用信源符號(hào)對(duì)應(yīng)的概率區(qū)間中的一個(gè)點(diǎn)來表示該信源符號(hào)。算術(shù)編碼不是對(duì)信源符號(hào)編碼，而是對(duì)N次擴(kuò)展信源（信源符號(hào)序列）編碼。算術(shù)編碼適合于小消息信源，即n較小的信源。算術(shù)編碼基本思想6.6.1算術(shù)編碼基本原理一次擴(kuò)展二次擴(kuò)展三次擴(kuò)展符號(hào)abaaabbabbaaaaabababaaabbbabbbabbb概率0.70.30.490.210.210.090.3430.1470.1470.1470.0630.0630.0630.027碼字1010100000100110100111000100110101011編碼長(zhǎng)度11123322334444平均碼長(zhǎng)10.910.90867編碼效率88.1%96.2%96.9%為什么對(duì)信源序列編碼【例6-15，P102】試分別對(duì)信源的一次、二次、三次擴(kuò)展信源進(jìn)行霍夫曼編碼，并比較平均碼長(zhǎng)和編碼效率?；窘Y(jié)論對(duì)信源序列編碼比對(duì)信源符號(hào)編碼能獲得更好的壓縮效果；序列越長(zhǎng)，單個(gè)符號(hào)所需的平均碼長(zhǎng)越短，編碼效率越高；算術(shù)編碼的基本思想算術(shù)編碼是對(duì)信源序列進(jìn)行無失真信源編碼的一種方法；算術(shù)編碼適合于小消息信源，即n較小的信源。算術(shù)編碼的思想：用信源符號(hào)對(duì)應(yīng)的概率區(qū)間中的一個(gè)點(diǎn)來表示該信源序列。算術(shù)編碼不是對(duì)信源符號(hào)編碼，而是對(duì)N次擴(kuò)展信源（信源符號(hào)序列）編碼。什么是概率區(qū)間說明以例6-15信源為例；對(duì)于一次擴(kuò)展信源，序列a的概率區(qū)間是[0,0.7]，序列b的概率區(qū)間是[0.7,1]；對(duì)于二次擴(kuò)展信源，序列aa的概率區(qū)間是[0,0.49]，序列ab的概率區(qū)間是[0.49,0.7]

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

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

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

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

5.將F(S)寫成二進(jìn)制數(shù)的形式，取其小數(shù)點(diǎn)后前L位作為序列S的碼字，若后面有尾數(shù)就在第L位進(jìn)位信源符號(hào)的積累概率：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）求出各個(gè)信源符號(hào)的概率區(qū)間和積累概率，并將碼字轉(zhuǎn)換成十進(jìn)制小數(shù)形式；（2）判斷十進(jìn)制小數(shù)所在符號(hào)區(qū)間，翻譯出1個(gè)符號(hào)u；（3）按照公式（6-13）計(jì)算出一個(gè)新的十進(jìn)制小數(shù)；

（6-13）（4）重復(fù)2、3直至全部信源序列被翻譯完為止?！纠?-17，P105】對(duì)例6-16中得到的碼字01010譯碼值所在區(qū)間譯得的符號(hào)計(jì)算過程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)計(jì)特性未知時(shí)的無失真信源編碼LZW編碼歷史1977年，以色列學(xué)者蘭佩爾(A.lempel)和奇費(fèi)(J.ziv)提出一種語法解析碼，簡(jiǎn)稱LZ編碼1978年提出了改進(jìn)算法，LZ77和LZ781984年，韋爾奇(T.A.Welch)將LZ78算法修改成一種實(shí)用的算法，后定名為L(zhǎng)ZW算法LZW編碼歷史6.7.1LZW基本原理LZW編碼算法的基本思想是建立一個(gè)編碼表(轉(zhuǎn)換表)，韋爾奇稱其為串表，該表將輸入字符串映射成定長(zhǎng)碼字輸出，通常碼長(zhǎng)設(shè)為12bitLZW編碼算法從一個(gè)空符號(hào)串表開始工作，在產(chǎn)生輸出串的同時(shí)動(dòng)態(tài)更新串表，這樣串表就對(duì)應(yīng)產(chǎn)生壓縮信源的特殊性質(zhì)簡(jiǎn)單說，LZW算法就是將待編碼信源序列進(jìn)行分割，每一部分編碼為一個(gè)長(zhǎng)度為12bit的0-1串。字符串碼字6.7.2LZW編碼方法將待編碼非空字符串中的所有單個(gè)字符存入串表中，并給每個(gè)符號(hào)賦一個(gè)碼字值讀入第一個(gè)輸入字符，賦給前綴串變量P讀下一個(gè)輸入字符，賦給擴(kuò)展串變量S如果S為空，輸出P，停止；否則執(zhí)行步驟5如果PS不在串表中，則將P

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

；否則將PS賦給P

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

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

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

；否則將PS賦給P

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