第6章無失真信源編碼

1、第第6 6章章 無失真信源編碼無失真信源編碼 信源編碼與數(shù)據(jù)壓縮信源編碼與數(shù)據(jù)壓縮6.1 編碼的基本概念編碼的基本概念6.2 “無失真無失真”的本質的本質6.3 定長碼定長碼6.4 變長碼變長碼6.5 變長碼的編碼方法變長碼的編碼方法（內容略增內容略增）6.6 算術編碼算術編碼6.7 LZW編碼編碼 本章小結本章小結信源編碼與數(shù)據(jù)壓縮信源編碼與數(shù)據(jù)壓縮l 對于信源來說，有三個重要問題需要解決：對于信源來說，有三個重要問題需要解決：1 1、如何構建描述信源的模型；、如何構建描述信源的模型；2 2、信源輸出信息量的計算，即信源熵的問題；、信源輸出信息量的計算，即信源熵的問題；3 3、如何更有效的表

2、示信源輸出問題，即信源壓、如何更有效的表示信源輸出問題，即信源壓縮編碼問題?？s編碼問題。l信源編碼的主要任務就是：信源編碼的主要任務就是： 減少冗余，提高編碼效率。減少冗余，提高編碼效率。1、信源編碼問題、信源編碼問題l 信源編碼的基本途徑有兩個：信源編碼的基本途徑有兩個：一是使序列中各個符號盡可能地相互獨立，一是使序列中各個符號盡可能地相互獨立，即解除相關性；即解除相關性；二是使編碼中各個符號出現(xiàn)的概率盡可能地二是使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。相等，即概率均勻化。具體來說，就是針對信源輸出符號序列的統(tǒng)計具體來說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的辦法把信源

3、輸出符號序列變特性，尋找一定的辦法把信源輸出符號序列變換為換為最短的碼字序列最短的碼字序列。許多情況下，并不要求在信宿精確重現(xiàn)信源許多情況下，并不要求在信宿精確重現(xiàn)信源的輸出，只要滿足一定的重建質量要求即可，的輸出，只要滿足一定的重建質量要求即可，即允許信息傳輸中出現(xiàn)一定失真，這就是即允許信息傳輸中出現(xiàn)一定失真，這就是限限失真信源編碼失真信源編碼問題。問題。例如，例如，在電話通信中，只要能將通話內容送在電話通信中，只要能將通話內容送達對方就可以了，對音質并無太高要求。達對方就可以了，對音質并無太高要求。實際通信時，信道往往存在干擾，要完全精實際通信時，信道往往存在干擾，要完全精確地重現(xiàn)信源輸出

4、幾乎是做不到的。這就允確地重現(xiàn)信源輸出幾乎是做不到的。這就允許接收信號有一定限度的失真。許接收信號有一定限度的失真。l 限失真信源編碼問題（第限失真信源編碼問題（第7章重點介紹）章重點介紹）2、數(shù)據(jù)壓縮問題、數(shù)據(jù)壓縮問題l 數(shù)據(jù)壓縮數(shù)據(jù)壓縮: :就是用盡可能少的比特數(shù)來表示源信號（采就是用盡可能少的比特數(shù)來表示源信號（采樣和量化后數(shù)字信號），并能將其還原。樣和量化后數(shù)字信號），并能將其還原。 壓縮的任務壓縮的任務就是保持信源信號就是保持信源信號在一個可以接在一個可以接受的狀況前提下受的狀況前提下,把需要的比特數(shù)減到最少程把需要的比特數(shù)減到最少程度，以達到減少存儲、處理和傳輸成本的目度，以達到減

5、少存儲、處理和傳輸成本的目的。的。l 信息理論認為：信息理論認為：若信源編碼的熵大于信源的實際熵，該信若信源編碼的熵大于信源的實際熵，該信源中一定存在冗余度，去掉冗余不會減少源中一定存在冗余度，去掉冗余不會減少信息量，仍可原樣恢復數(shù)據(jù)；但若減少了信息量，仍可原樣恢復數(shù)據(jù)；但若減少了熵，數(shù)據(jù)則不能完全恢復。熵，數(shù)據(jù)則不能完全恢復。但在允許的范圍內損失一定的熵，數(shù)據(jù)可但在允許的范圍內損失一定的熵，數(shù)據(jù)可以近似地恢復。以近似地恢復。 l 常用的壓縮編碼方法可以分為兩大類：常用的壓縮編碼方法可以分為兩大類：1、無損壓縮編碼法，也稱冗余壓縮法或熵、無損壓縮編碼法，也稱冗余壓縮法或熵編碼法及編碼法及無失真

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

7、ngth)(Run-length)編碼，編碼，LZW(Lempel-Ziv-WelchLZW(Lempel-Ziv-Welch) )編碼編碼和算術編碼等。和算術編碼等。無損壓縮優(yōu)點：無損壓縮優(yōu)點：可以做到可以做到100100的保存、沒有任的保存、沒有任 何信號丟失，并且轉換方便。何信號丟失，并且轉換方便。無損壓縮不足：無損壓縮不足：占用空間大、壓縮比不高而且占用空間大、壓縮比不高而且 缺乏硬件支持。缺乏硬件支持。l有損數(shù)據(jù)壓縮：有損數(shù)據(jù)壓縮：經過壓縮、解壓的數(shù)據(jù)與原始數(shù)據(jù)不同經過壓縮、解壓的數(shù)據(jù)與原始數(shù)據(jù)不同, ,但是非但是非常接近的壓縮方法，又稱常接近的壓縮方法，又稱破壞型壓縮破壞型壓縮；即

8、將次要的信息數(shù)據(jù)壓縮掉，犧牲一些質量來減即將次要的信息數(shù)據(jù)壓縮掉，犧牲一些質量來減少數(shù)據(jù)量，使壓縮比提高。少數(shù)據(jù)量，使壓縮比提高。如，利用人類對圖像或聲波中的某些頻率成分不如，利用人類對圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息；敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復原始數(shù)據(jù)，但是所損失的部分雖然不能完全恢復原始數(shù)據(jù)，但是所損失的部分對理解原始圖像的影響縮小，卻換來了大得多的對理解原始圖像的影響縮小，卻換來了大得多的壓縮比。壓縮比。有損壓縮有損壓縮廣泛應用于廣泛應用于語音，圖像和視頻數(shù)據(jù)的壓語音，圖像和視頻數(shù)據(jù)的壓縮。縮。l在多媒體應用中，常見的在

9、多媒體應用中，常見的有損壓縮有損壓縮方法有：方法有：PCM(PCM(脈沖編碼調制脈沖編碼調制) )，預測編碼；，預測編碼；變換編碼，插值和外推法；變換編碼，插值和外推法；統(tǒng)計編碼，矢量量化和子帶編碼等；統(tǒng)計編碼，矢量量化和子帶編碼等；混合編碼是近年來廣泛采用的方法。混合編碼是近年來廣泛采用的方法。l有損壓縮的優(yōu)點：有損壓縮的優(yōu)點： 在有些情況下能夠獲得比任何已知無損方法在有些情況下能夠獲得比任何已知無損方法小得多的文件大小，同時又能滿足系統(tǒng)的需小得多的文件大小，同時又能滿足系統(tǒng)的需要。要。l有損壓縮的不足：有損壓縮的不足： 會影響圖像質量，尤其是在仔細觀察的時候，會影響圖像質量，尤其是在仔細觀

10、察的時候，質量下降更加明顯。質量下降更加明顯。6.1 編碼的基本概念編碼的基本概念6.1.1 編碼器和譯碼器編碼器和譯碼器6.1.2 碼的分類碼的分類6.1.3 N次（階）擴展碼次（階）擴展碼6.1.1 編碼器和譯碼器編碼器和譯碼器l信源編碼器信源編碼器編碼的實質：編碼的實質：是對信源的原始符號按一定的數(shù)是對信源的原始符號按一定的數(shù)學規(guī)則進行的一種變換學規(guī)則進行的一種變換; ;以碼字代替原始信源符號以碼字代替原始信源符號; ;使變換后得到的碼符號接近等概率分布使變換后得到的碼符號接近等概率分布; ;從而提高信息的傳輸有效性。從而提高信息的傳輸有效性。l編碼器編碼器模型模型：輸入序列輸入序列 輸

11、入序列中每一個輸入序列中每一個符號序列符號序列si來自集合來自集合編碼輸出序列編碼輸出序列 其中編碼輸出序列中每一個符號序列其中編碼輸出序列中每一個符號序列ci來自來自碼字集合碼字集合 一般一般m=nW稱為碼字集合，稱為碼字集合，wi （i=1,2,m)稱為碼字稱為碼字l譯碼是編碼的反過程。譯碼是編碼的反過程。),(21LsssS),(21LcccC),(21nuuuU),(21mwwwWN長輸入序列長輸入序列L長碼字序列長碼字序列符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000如：如：若選用碼若選用碼1，如果編碼器輸

12、入序列如果編碼器輸入序列S=u2u4u1，則編碼器輸出序列則編碼器輸出序列C=011100【例例6-2，P84】幾種二進制編碼如表所示幾種二進制編碼如表所示6.1.2 碼的分類碼的分類1、按編碼的目的分、按編碼的目的分信源編碼信源編碼 目的：壓縮消息數(shù)據(jù)量，提高通信有效性；目的：壓縮消息數(shù)據(jù)量，提高通信有效性；保密編碼保密編碼 目的：提高信息傳輸安全性目的：提高信息傳輸安全性信道編碼信道編碼 目的：消除噪聲影響，提高通信可靠性；目的：消除噪聲影響，提高通信可靠性；調制編碼。調制編碼。2、按碼字的長度分、按碼字的長度分等長碼：所有碼字長度相同等長碼：所有碼字長度相同變長碼：碼自的長度不同變長碼：

13、碼自的長度不同（碼（碼1 1）（碼（碼2 2、碼、碼3 3、碼、碼4 4、碼、碼5 5）符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000如碼如碼2例子：例子：3、按碼字的奇異性分、按碼字的奇異性分奇異碼：至少兩個符號的編碼相同奇異碼：至少兩個符號的編碼相同（碼（碼3 3）非奇異碼：所有碼字均不相同（非奇異碼：所有碼字均不相同（正確譯碼的必要條件正確譯碼的必要條件）（碼（碼1 1、碼、碼2 2、碼、碼4 4、碼、碼5 5）符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411

14、0111000110004、按譯碼時是否會產生歧義分、按譯碼時是否會產生歧義分符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000非唯一可譯碼：譯碼時會產生歧義非唯一可譯碼：譯碼時會產生歧義（碼（碼2 2） （碼（碼3 3、奇異碼奇異碼）唯一可譯碼：譯碼時不會產生歧義唯一可譯碼：譯碼時不會產生歧義（碼（碼1 1、碼、碼4 4、碼、碼5 5）奇異碼一定是非惟一可譯碼奇異碼一定是非惟一可譯碼 非奇異碼不一定是惟一可譯碼，如碼非奇異碼不一定是惟一可譯碼，如碼2。碼碼2：如譯碼器接收到序列：如譯碼器接收到序列“01000010”

15、， 可譯為：可譯為： 也可譯為：也可譯為：14321uuuuu2334uuuu5、按譯碼時是否需要知道下一個碼字的符號分、按譯碼時是否需要知道下一個碼字的符號分即時碼：不需要知道下一個碼字的符號就能譯碼即時碼：不需要知道下一個碼字的符號就能譯碼 （碼（碼1 1、碼、碼4 4）非即時碼：需要知道下一個碼字的符號才能譯碼非即時碼：需要知道下一個碼字的符號才能譯碼 （碼（碼5 5） 符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u4110111000110006、按符號、按符號si和和ci之間的映射關系分之間的映射關系分分組碼：已經出現(xiàn)的符號對當前符號的

16、編碼分組碼：已經出現(xiàn)的符號對當前符號的編碼沒有沒有影響；影響；卷積碼：卷積碼：已經出現(xiàn)的符號對當前符號的編碼已經出現(xiàn)的符號對當前符號的編碼有有影響；影響； 符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000001100u411011100011000等長碼：所有碼字長度相同等長碼：所有碼字長度相同變長碼：碼字的長度不同變長碼：碼字的長度不同奇異碼：至少兩個符號的編碼相同奇異碼：至少兩個符號的編碼相同非奇異碼：非奇異碼：所有碼字均不相同所有碼字均不相同非唯一可譯碼：譯碼時會產生歧義非唯一可譯碼：譯碼時會產生歧義唯一可譯碼：唯一可譯碼：譯碼時不會產生歧義譯碼時不會產生

17、歧義即時碼：即時碼：不需要知道下一個碼字的符號就能譯碼不需要知道下一個碼字的符號就能譯碼非即時碼：非即時碼：需要知道下一個碼字的符號才能譯碼需要知道下一個碼字的符號才能譯碼（碼（碼1 1）（碼（碼2 2、碼、碼3 3、碼、碼4 4、碼、碼5 5）（碼（碼3 3）（碼（碼1 1、碼、碼2 2、碼、碼4 4、碼、碼5 5）（碼（碼1 1、碼、碼4 4）（碼（碼5 5）（碼（碼2 2）（碼（碼1 1、碼、碼4 4、碼、碼5 5）7、小結、小結1110110100011101101011001010100125. 0125. 025. 05 . 04321D C B A ssss碼碼碼碼碼碼碼碼概概率

18、率消消息息【例，增例，增】考慮以下碼字特性。考慮以下碼字特性。奇異碼奇異碼 非奇異碼非奇異碼 非奇異碼非奇異碼 非奇異碼非奇異碼 非唯一可譯非唯一可譯 唯一可譯唯一可譯 唯一可譯唯一可譯 非即時碼非即時碼 即時碼即時碼 碼的分類例子碼的分類例子即時碼的構造-樹圖l通常情況下可以用碼樹來表示碼字的構成通常情況下可以用碼樹來表示碼字的構成：如果碼字序列符號為如果碼字序列符號為r進制的，可以用進制的，可以用r個符號的碼樹個符號的碼樹來構造碼字；來構造碼字；每個碼樹有一個每個碼樹有一個樹根樹根A；樹根有樹根有r個個樹枝樹枝；樹枝的盡頭稱為樹枝的盡頭稱為節(jié)點節(jié)點；每個節(jié)點生出是樹枝的數(shù)量等于碼符號的數(shù)量

19、每個節(jié)點生出是樹枝的數(shù)量等于碼符號的數(shù)量r；從而形成從而形成r進制的碼樹。進制的碼樹。A021012120021120A10100101101001幾點說明：幾點說明：碼樹中自樹根經過一個分枝到達一階節(jié)點，一階節(jié)點最碼樹中自樹根經過一個分枝到達一階節(jié)點，一階節(jié)點最多為多為r個，二階節(jié)點的可能個數(shù)為個，二階節(jié)點的可能個數(shù)為r2個，個，n階節(jié)點最多有階節(jié)點最多有rn個；個；若將從每個節(jié)點發(fā)出的若將從每個節(jié)點發(fā)出的r個分枝分別標以個分枝分別標以0，1，r-1，則每個則每個n階節(jié)點需要用階節(jié)點需要用n個個r元數(shù)字表示；元數(shù)字表示；用樹圖方法構造的碼滿足即時碼的條件，因為從樹根到用樹圖方法構造的碼滿足即

20、時碼的條件，因為從樹根到每一個終端節(jié)點所走的路徑均不相同，所以一定滿足對每一個終端節(jié)點所走的路徑均不相同，所以一定滿足對即時碼前綴的限制。即時碼前綴的限制。如果有個如果有個q信源符號，那么在碼樹上就要選擇信源符號，那么在碼樹上就要選擇q個終端節(jié)個終端節(jié)點，用相應點，用相應r元基本符號表示這些碼字。元基本符號表示這些碼字。A021012120021120A10100101101001若樹碼的各個分支都延伸到最后一級端點，此時將共有若樹碼的各個分支都延伸到最后一級端點，此時將共有rn個個碼字，這樣的碼樹稱為整樹，如圖碼字，這樣的碼樹稱為整樹，如圖(a)所示。否則就稱為非整所示。否則就稱為非整樹，如

21、圖樹，如圖(b)所示，這時的碼字就不是等長碼了。所示，這時的碼字就不是等長碼了。 因此，碼樹與碼之間具有如下一一對應的關系：因此，碼樹與碼之間具有如下一一對應的關系：樹根樹根碼字起點；碼字起點； 樹枝數(shù)樹枝數(shù)碼的進制數(shù)；碼的進制數(shù)；節(jié)點節(jié)點碼字的一部分；碼字的一部分； 終端節(jié)點終端節(jié)點碼字；碼字；階數(shù)階數(shù)碼長；碼長； 非整樹非整樹變長碼；變長碼；整樹整樹等長碼。等長碼。6.1.3 N次（階）擴展碼次（階）擴展碼l將將N次擴展信源的概念加以延伸，可以得到次擴展信源的概念加以延伸，可以得到N次擴展碼次擴展碼集合集合 的的N次擴展次擴展相應碼字集合的相應碼字集合的N次擴展次擴展其中其中 是一一對應的

22、。是一一對應的。),(21nuuuU),(21NiiiNuuuU),(21NiiiNwwwWjjiiwu 和解：解：ABC000110AAABACBABBBCCACBCC000000010010010001010110100010011010【例例6-3，P86】符號集符號集U=A，B，C分別編碼為分別編碼為00，01，10，試寫出它的，試寫出它的2次擴展碼。次擴展碼。NN次擴展碼例子次擴展碼例子1 1例如下面的兩個例子，例如下面的兩個例子，ACD編碼成為編碼成為001011/0001111的形的形式，均為式，均為3階擴展碼。階擴展碼。而而3次擴展符號共有次擴展符號共有43=64個個 如：如：

23、ABCD00011011ABCD0010011113次 擴展符號3次 擴展碼字3次 擴展符號3次 擴展碼字AAA000AAB0001DDB11111101AAC00001DDC111111001DDD111111111NN次擴展碼例子次擴展碼例子2 2【例，增例，增】6.2 “無失真無失真”的本質的本質無失真信源編碼：編碼時沒有信息丟失，譯碼器可以精確無失真信源編碼：編碼時沒有信息丟失，譯碼器可以精確恢復編碼之前的消息?；謴途幋a之前的消息。無失真信源編碼又叫無失真信源編碼又叫“無損壓縮無損壓縮”無失真信源編碼的基本問題是研究如何用無失真信源編碼的基本問題是研究如何用最少的比特數(shù)最少的比特數(shù)去去

24、表示離散表示離散信源的熵值信源的熵值，也就是如何找出，也就是如何找出最佳編碼方案最佳編碼方案若要實現(xiàn)無失真信源編碼，信源符號集合若要實現(xiàn)無失真信源編碼，信源符號集合U和碼字集合和碼字集合W中的元素要相等，即中的元素要相等，即n=m； nm失真；失真； n1）的構造）的構造：若有碼字：若有碼字 ，且，且 是是 的的前綴，即前綴，即 則將后綴則將后綴A列為列為Sn中的元素；同樣，若中的元素；同樣，若有碼字有碼字 是是 的前綴，即的前綴，即 ，則將后，則將后綴綴A也列為也列為Sn中的元素。中的元素。一直到更新的集合為空集為止。一直到更新的集合為空集為止。 iAjij0S1nSuAu1nSu0SAul

25、碼字集合構造的舉例說明碼字集合構造的舉例說明S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde 【命題命題6-1】 一種碼是唯一可譯碼的充要條件是一種碼是唯一可譯碼的充要條件是S1, S2,中中沒有一個含有沒有一個含有S0中的碼字。中的碼字。l唯一可譯碼的判別方法唯一可譯碼的判別方法唯一可譯碼判別例子唯一可譯碼判別例子【例例6-9，P94】接例接例6-2，分析例，分析例6-2給出的給出的5種編碼方法是否為種編碼方法是否為唯一可譯碼。唯一可譯碼。解：解：分別構造各自的集合分別構造各自的集合符號碼1碼2碼3碼4碼5u1000011u201101101

26、10u3100000001100u411011100011000碼碼1 1S0S100011011碼碼2 2S0S101000010碼碼3 3S00110011碼碼4 4S0S11010010001碼碼5S0S1S21101001000000000碼碼1：S0中不存在一個碼字是另一個碼字前綴的情況，中不存在一個碼字是另一個碼字前綴的情況， S1為空集，因此碼為空集，因此碼1是唯一可譯碼。是唯一可譯碼。碼碼2：S0中的中的0是是00的前綴，將后綴的前綴，將后綴0放入集合放入集合S1中，此時中，此時S1中已經包含了中已經包含了S0中的碼字，中的碼字，無需向下再構造集合無需向下再構造集合就能判定就能

27、判定碼碼2不是唯一可譯碼。不是唯一可譯碼。碼碼3：S0中本身就出現(xiàn)了中本身就出現(xiàn)了S0中的碼字，因此碼中的碼字，因此碼3不是唯一可不是唯一可譯碼。譯碼。碼碼4：S0中不存在一個碼字是另一個碼字前綴的情況，中不存在一個碼字是另一個碼字前綴的情況， S1為空集，因此碼為空集，因此碼4是唯一可譯碼。是唯一可譯碼。碼碼5：S0中有一個碼字是另一個碼字前綴的情況，將所有中有一個碼字是另一個碼字前綴的情況，將所有后綴放入后綴放入S1中，中， 從從S0和和S1中各取一個碼字，不存在一個碼中各取一個碼字，不存在一個碼字是另一個碼字前綴的情況，字是另一個碼字前綴的情況， S2為空集，且為空集，且S1中不包含中不

28、包含S0中碼字，因此碼中碼字，因此碼5是唯一可譯碼。是唯一可譯碼。唯一可譯碼判別例子唯一可譯碼判別例子即時碼的判別方法即時碼的判別方法l即時碼的判別方法即時碼的判別方法 【命題命題6-2】 一個唯一可譯碼成為即時碼的充要條件是其一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。中任何一個碼字都不是其他碼字的前綴?！纠?-10，P94】接例接例6-9，在例，在例6-9中已經知道，碼中已經知道，碼1、碼、碼4和碼和碼5是唯一可譯碼，試判別哪些是即時碼。是唯一可譯碼，試判別哪些是即時碼。解：解：符號碼1碼2碼3碼4碼5u1000011u20110110110u3100000

29、001100u411011100011000碼碼1：其中任何一個碼字都不是其他碼字的前綴，：其中任何一個碼字都不是其他碼字的前綴， 因此碼因此碼1是即時碼。是即時碼。碼碼4：其中任何一個碼字都不是其他碼字的前綴，：其中任何一個碼字都不是其他碼字的前綴， 因此碼因此碼4是即時碼。是即時碼。碼碼5：存在多個一個碼字是其他碼字前綴的情況，：存在多個一個碼字是其他碼字前綴的情況， 因此碼因此碼5不是即時碼。不是即時碼。6.4.4 無失真信源編碼定理（香農第一定理）無失真信源編碼定理（香農第一定理）l問題的引出：問題的引出：緊致碼緊致碼（或（或最佳碼最佳碼）：某種編碼方式的平均碼長小于）：某種編碼方式的

30、平均碼長小于所有其他編碼方式；所有其他編碼方式；無失真信源編碼基本問題：無失真信源編碼基本問題：確定最佳碼確定最佳碼；平均碼長有極限值嗎？如果有，值是多少？平均碼長有極限值嗎？如果有，值是多少？變長編碼定理解決這個問題。變長編碼定理解決這個問題。 說明：說明： 熵除以熵除以logr只是為了將熵的單位轉換到只是為了將熵的單位轉換到r進制，以保持進制，以保持與平均碼長與平均碼長 的單位統(tǒng)一；的單位統(tǒng)一；【定理定理6-3】對于熵為對于熵為H(U)的離散無記憶信源，若對其進的離散無記憶信源，若對其進行行r元信源編碼，則一定存在一種編碼方式構成唯一可譯元信源編碼，則一定存在一種編碼方式構成唯一可譯碼，其

31、平均碼長滿足碼，其平均碼長滿足1log)(log)(rUHLrUHL1)()(UHLUHrr1)()(UHLUH 上式記為：上式記為： 如果是二元編碼，可表示為：如果是二元編碼，可表示為：該定理說明，要構成唯一可譯碼，平均碼長要處在該定理說明，要構成唯一可譯碼，平均碼長要處在信源熵和信源熵加信源熵和信源熵加1之間。之間。證明證明【定理定理6-4】無失真變長信源編碼定理（香農第一定理）。無失真變長信源編碼定理（香農第一定理）。離散無記憶信源離散無記憶信源U的的N次擴展信源次擴展信源UN，其熵為，其熵為H(UN)，對該擴展，對該擴展信源信源UN進行進行r元編碼，總可以找到一種編碼方法，構成唯一可譯

32、元編碼，總可以找到一種編碼方法，構成唯一可譯碼，使信源碼，使信源UN中每個信源符號（即長度為中每個信源符號（即長度為N的信源序列）所需的的信源序列）所需的平均碼長滿足：平均碼長滿足：NrUHNLrUHN1log)(log)(NUHNLUHrNr1)()()(limUHNLrNN或者或者N當當 時時NL其中其中 是無記憶是無記憶N次擴展信源次擴展信源UN中每個信源符號（即長度為中每個信源符號（即長度為N的信源序列）所對應的平均碼長；的信源序列）所對應的平均碼長；NLN表示原始信源表示原始信源U中每個信源符號所對應的平均碼長。中每個信源符號所對應的平均碼長。證明證明N次擴展信源次擴展信源l表達式表

33、達式1 說明：說明：LNLN和定理和定理6-4中的中的 都是是原始信源都是是原始信源U中每中每個信源符號所對應的平均碼長，個信源符號所對應的平均碼長， 定理定理6-3中的中的NLN ，為了得到這個平均值，不是直，為了得到這個平均值，不是直接對單個信源符號編碼，而是對接對單個信源符號編碼，而是對N次擴展信源編碼得到的。次擴展信源編碼得到的。 但不同的是，對于但不同的是，對于NrUHNLrUHN1log)(log)(以以r=2為例，則為例，則這說明，總可以找到一種惟一可譯碼，它的平均碼長處在這說明，總可以找到一種惟一可譯碼，它的平均碼長處在信源熵和信源熵加信源熵和信源熵加1之間。之間。而且當平均碼

34、長小于信源熵的時候，這種編碼肯定不是唯而且當平均碼長小于信源熵的時候，這種編碼肯定不是唯一可譯碼。一可譯碼。還說明編碼效率還說明編碼效率 最大是最大是100%該定理并未給出這種惟一可譯碼的構造方法。該定理并未給出這種惟一可譯碼的構造方法。( )( )1NNH ULNH UNLN)(UHrNLN)(UHr 這表明，當這表明，當N充分大時，每個信源符號所對應的平均碼長充分大時，每個信源符號所對應的平均碼長等于等于r進制的信源熵進制的信源熵 若編碼的平均碼長若編碼的平均碼長小于該信源熵小于該信源熵 ，則唯一可譯碼不存在。則唯一可譯碼不存在。 l表達式表達式2 說明：說明：)(limUHNLrNN 將

35、定理將定理6-4的結論推廣到平穩(wěn)遍歷的有記憶信源，有的結論推廣到平穩(wěn)遍歷的有記憶信源，有rHNLNNloglimH其中，其中， 為有記憶信源的極限熵。為有記憶信源的極限熵。 無失真信源編碼定理是香農信息論的三大定理之一。無失真信源編碼定理是香農信息論的三大定理之一。l編碼速率編碼速率類似于定長碼中的編碼速率，可以定義變長碼的編碼類似于定長碼中的編碼速率，可以定義變長碼的編碼速率：速率： 它表示它表示r元編碼后平均每個信源符號用多少個二進制符元編碼后平均每個信源符號用多少個二進制符號表示。號表示。 于是定理于是定理6-46-4又可以表述為，若又可以表述為，若 ： 就存在唯一可譯的變長編碼。就存在

36、唯一可譯的變長編碼。 若：若： 則不存在唯一可譯的變長編碼。不能實現(xiàn)無失真信源則不存在唯一可譯的變長編碼。不能實現(xiàn)無失真信源編碼。編碼。編碼速率編碼速率rNLRNlog)()(UHRUH)(UHR 編碼效率編碼效率LUHRUHr)()(NLLN【定理定理6-5 】編碼效率編碼效率一定小于等于一定小于等于1，其中，其中LL)(UHr 平均碼長平均碼長越短，即越短，即越接近于它的極限值越接近于它的極限值 ，那么編碼效率越趨近于那么編碼效率越趨近于1，效率就越高；，效率就越高；l 說明：說明： 因此，可用編碼效率因此，可用編碼效率來衡量各種編碼的優(yōu)劣。來衡量各種編碼的優(yōu)劣。證明證明6.5 變長碼的編

37、碼方法變長碼的編碼方法6.5.1 香農編碼香農編碼 6.5.2 費諾編碼費諾編碼 6.5.3 霍夫曼碼霍夫曼碼6.5.4 游程編碼游程編碼6.5.1 香農編碼香農編碼)(.)()(.2121nnupupupuuuPU設有離散無記憶信源設有離散無記憶信源)(log1)(log:22iiiiuplupl確定3的碼字位作為點后的用二進制表示，用小數(shù)把iijuulup)(4香農編碼方法的步驟：香農編碼方法的步驟：1按信源符號的概率從大到小的順序排隊，不妨設不妨設)(.)()(21nupupup2個碼字的累加概率表示第，用令iijupupju1),(0)(010)()(jiijuupup香農編碼例子香農

38、編碼例子05.01 .015.02 .025.025.0654321uuuuuuPU設有一單符號離散無記憶信源設有一單符號離散無記憶信源試對該信源編二進制香農碼試對該信源編二進制香農碼，并求平均碼長和編碼效率并求平均碼長和編碼效率?！纠?，增例，增】編碼過程：編碼過程：10)()(jiijuupup（1 1）計算累加概率）計算累加概率262524232221)1110. 0(11110595. 005. 0)1101. 0(1101485. 01 . 0)101. 0(10137 . 015. 0)100. 0(10035 . 02 . 0)010. 0(01225. 025. 0)000. 0

39、(002025. 0)()(654321uuuuuulupupuiijuii碼字信源符號）（碼符號 /7 .2)(61iiilupL碼符號）（比特 /42. 2)(UH%63.897 .242.2)(LUH信源熵：信源熵：平均碼長：平均碼長：編碼效率：編碼效率：（2）編碼效率計算編碼效率計算6.5.2 費諾編碼費諾編碼)(.)()(.2121nnupupupuuuPU設有離散無記憶信源設有離散無記憶信源費諾編碼方法的步驟：費諾編碼方法的步驟：按編碼進制數(shù)按編碼進制數(shù)r將概率分組，使每組概率盡可能接近或相等。將概率分組，使每組概率盡可能接近或相等。2給每個分組分配一個碼元。給每個分組分配一個碼元

40、。3對每個分組重復對每個分組重復2、3步，直到不可分為止。步，直到不可分為止。4信源符號所對應的碼字即為費諾碼。信源符號所對應的碼字即為費諾碼。51按信源符號的概率從大到小的順序排隊，不妨設不妨設)(.)()(21nupupup費諾編碼例子費諾編碼例子04. 008. 016. 018. 022. 032. 0654321uuuuuuPU設有一單符號離散無記憶信源設有一單符號離散無記憶信源試對該信源編二進制費諾碼試對該信源編二進制費諾碼，并求平均碼長和編碼效率并求平均碼長和編碼效率?！纠?，增例，增】（1）編碼過程）編碼過程1u2u3u4u5u6u32.022.018.016.008.004.0

41、001010011000110110111011111)/(35. 2)(信源符號比特UH%92.97)(LUH說明：說明：可以看出本例中費諾碼有較高的編碼效率?？梢钥闯霰纠匈M諾碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。費諾碼比較適合于每次分組概率都很接近的信源。61)/(40.2)(iiilupL信源符號碼符號信源熵：信源熵：平均碼長：平均碼長：編碼效率：編碼效率：（2）編碼效率計算編碼效率計算l費諾碼具有如下的性質：費諾碼具有如下的性質：費諾碼的編碼方法實際上是一種構造碼樹的方法，所費諾碼的編碼方法實際上是一種構造碼樹的方法，所以費諾碼是即時碼。以費諾碼是即時碼。費

42、諾碼考慮了信源的統(tǒng)計特性，使概率大的信源符號費諾碼考慮了信源的統(tǒng)計特性，使概率大的信源符號能對應碼長較短的碼字，從而有效地提高了編碼效率。能對應碼長較短的碼字，從而有效地提高了編碼效率。費諾碼不一定是最佳碼。因為費諾碼編碼方法不一定費諾碼不一定是最佳碼。因為費諾碼編碼方法不一定能使短碼得到充分利用能使短碼得到充分利用:當信源符號較多時，若有一當信源符號較多時，若有一些符號概率分布很接近時，分兩大組的組合方法就會些符號概率分布很接近時，分兩大組的組合方法就會很多?？赡苣撤N分大組的結果，會使后面小組的很多?？赡苣撤N分大組的結果，會使后面小組的“概概率和率和”相差較遠，從而使平均碼長增加。相差較遠，

43、從而使平均碼長增加。lr 元費諾碼元費諾碼前面討論的費諾碼是二元費諾碼；前面討論的費諾碼是二元費諾碼；對對r元費諾碼，與二元費諾碼編碼方法相同，只是每元費諾碼，與二元費諾碼編碼方法相同，只是每次分組時應將符號分成概率分布接近的次分組時應將符號分成概率分布接近的r個組。個組。6.5.3 霍夫曼碼霍夫曼碼1、 二元霍夫曼碼二元霍夫曼碼l1952年，霍夫曼（年，霍夫曼（Huffman）提出了一種構造最佳碼的）提出了一種構造最佳碼的方法，這是一種最佳的逐個符號的編碼方法，一般就稱方法，這是一種最佳的逐個符號的編碼方法，一般就稱作霍夫曼碼作霍夫曼碼)(.)()(.2121nnupupupuuuPU設有離

44、散無記憶信源設有離散無記憶信源二元霍夫曼編碼方法的步驟：二元霍夫曼編碼方法的步驟：將將兩個概率最小的符號兩個概率最小的符號合并成一個新符號，新符號的概率合并成一個新符號，新符號的概率為兩個符號概率之和，得到只包含為兩個符號概率之和，得到只包含n1個符號的個符號的縮減信源縮減信源U12將信源符號按概率由大到小順序排隊將信源符號按概率由大到小順序排隊1依次繼續(xù)，直至信源最后依次繼續(xù)，直至信源最后只剩下個符號只剩下個符號為止。為止。4把把縮減信源縮減信源U1的符號仍按概率從大到小排列，將其中兩的符號仍按概率從大到小排列，將其中兩個概率最小的符號合并成一個符號，形成個概率最小的符號合并成一個符號，形成

45、n2個符號的個符號的縮減信源縮減信源U23將每次合并的將每次合并的兩個信源符號兩個信源符號分別用分別用0和和1碼符號表示。碼符號表示。5從從最后一級縮減信源最后一級縮減信源開始，向前返回，就得出各信源符號開始，向前返回，就得出各信源符號所對應的所對應的碼符號序列碼符號序列，即得各信源符號對應的碼字，即得各信源符號對應的碼字 。6符 號概 率縮減后符號概率碼 字u1u2u3u250.1250.50.25010.25010.50.5011.0010110111碼 長1233霍夫曼編碼過程二元霍夫曼編碼例子二元霍夫曼編碼例子1 1123250.125Uuu

46、uuP【例例6-11，P99】對離散無記憶信源對離散無記憶信源進行二元霍夫曼編碼，并求平均碼長和編碼效率進行二元霍夫曼編碼，并求平均碼長和編碼效率（1）編碼過程）編碼過程信源熵：信源熵： （比特（比特/信源符號）信源符號）平均碼長：平均碼長： （碼符號（碼符號/信源符號）信源符號）編碼效率：編碼效率：( )( )log( )1.75iiiH Up up u ( )1.75iiiLp u l( )100%H UL（2）編碼效率計算編碼效率計算二元霍夫曼編碼例子二元霍夫曼編碼例子2 2【例例6-12，P99】對信源對信源的二次擴展信源進行二元霍夫曼編碼。的二次擴展信源進行二元霍夫曼編碼。0.30.

47、710PU解：解：信源信源U的二次擴展信源為：的二次擴展信源為：09. 021. 021. 049. 0111001002PU按例按例1方法，對其進行二元霍夫曼編碼，為：方法，對其進行二元霍夫曼編碼，為：符號符號00011011碼字碼字010110111設有一個長度為設有一個長度為60的信源序列：的信源序列：01000111100011110010011000000000000100001100000000000100011編碼后，變成長度為編碼后，變成長度為53的序列的序列10010111110010111110100111000000110010110000001100111做到無失真壓縮

48、做到無失真壓縮12345 0.1 0.1UuuuuuP【例例6-13，P99】對離散無記憶信源對離散無記憶信源進行二元霍夫曼編碼，并求平均碼長和編碼效率。進行二元霍夫曼編碼，并求平均碼長和編碼效率。二元霍夫曼編碼例子二元霍夫曼編碼例子3 3（1）編碼過程）編碼過程可以有如下兩種方法：可以有如下兩種方法：符 號概 率碼 字u1u2u3u0.1u50.10.210100.60.4101.0001011010011碼 長22233(a)縮減后符號概率概 率碼 字u1u2u3u0.1u50.1100.40

49、.0.40.210100.60.4101.010100000100011碼 長12344(b)符 號信源熵：信源熵： （比特（比特/信源符號）信源符號）平均碼長：平均碼長： （碼符號（碼符號/信源符號）信源符號）編碼效率：編碼效率：( )( )log( )2.12iiiH Up up u ( )2.2iiiLp u l( )96.3%H UL（2）編碼效率計算編碼效率計算對于兩種編碼方法，有對于兩種編碼方法，有碼長方差碼長方差這兩種編碼方式的平均碼長和編碼效率均相同，如何這兩種編碼方式的平均碼長和編碼效率均相同，如何衡量這兩種編碼方式的好壞呢？衡量這兩種編碼方式的好壞呢？碼

50、長方差碼長方差522( )1522( )1( )()0.16( )()1.36aiiibiiip ulLp ulL方差小意味著更接近等長碼, 更易于傳輸，所以方法(a)要優(yōu)于方法(b)結論：結論：進行赫夫曼編碼時，為得到進行赫夫曼編碼時，為得到碼方差碼方差最小的碼，應使合最小的碼，應使合并的信源符號位于縮減信源序列并的信源符號位于縮減信源序列盡可能高的位置盡可能高的位置上，上，以減少再次合并的次數(shù)，充分利用短碼。以減少再次合并的次數(shù)，充分利用短碼。 2 2 多元霍夫曼碼多元霍夫曼碼每次把概率最小的每次把概率最小的r個符號合并成一個新的符號，并分別個符號合并成一個新的符號，并分別用用0,1,(r

51、-1)等碼元表示等碼元表示為了使短碼得到充分利用，使平均碼長最短，必須使最后為了使短碼得到充分利用，使平均碼長最短，必須使最后一步的縮減信源有一步的縮減信源有r個信源符號個信源符號因此對于因此對于r元編碼，信源元編碼，信源U符號個數(shù)符號個數(shù)n必須滿足：必須滿足：n=(r-1)Q+r 即要求方程即要求方程n=(r-1)Q+r有解，其中有解，其中Q為未知數(shù)。為未知數(shù)。當此方程沒有解時，可以通過人為增加一些概率為當此方程沒有解時，可以通過人為增加一些概率為0的符的符號來解決。號來解決。r元霍夫曼編碼方法的步驟：元霍夫曼編碼方法的步驟：r r元霍夫曼編碼例子元霍夫曼編碼例子1 112345 0.40.

52、30.20.05 0.05UuuuuuP【例例6-14，P101】對例對例6-13離散無記憶信源離散無記憶信源分別進行三元霍夫曼和四元霍夫曼編碼。分別進行三元霍夫曼和四元霍夫曼編碼。l三元霍夫曼編碼三元霍夫曼編碼此時：此時：n=5, m=3，因此，因此n=(m-1)Q+m是有解的，解為是有解的，解為Q=1平均碼長：平均碼長：編碼效率：編碼效率：符 號概 率碼 字u1u2u3u0.0501012021u50.0501222碼 長112223( )(0.40.3) 12 (0.20.050.05)1.3iiiLp u l 332( )1.9594.7%log

53、 31.3 1.58H ULl四元霍夫曼編碼四元霍夫曼編碼此時：此時：n=5, m=4，因，因此此n=(m-1)Q+m是無是無解的，需要增加解的，需要增加2個個概率為概率為0的符號的符號平均碼長：平均碼長：編碼效率：編碼效率：4( )() 12 (0.20.050.05)1.1iiiLp u l 符 號概 率碼 字u1u2u3u40.400.300.200.050101230u50.0520.400.300.2001231碼 長11122u6u70.000.0030.103323322442( )1.9588.6%log 41.1 2H UL霍夫曼碼的最佳性霍夫曼碼的最佳性霍

54、夫曼碼是最佳碼（緊致碼）霍夫曼碼是最佳碼（緊致碼）霍夫曼碼是即時碼：任一碼字都不是其他碼字的霍夫曼碼是即時碼：任一碼字都不是其他碼字的前綴。前綴。6.5.4 游程編碼游程編碼前面的幾種編碼方法主要時針對無記憶信源，對有記憶信前面的幾種編碼方法主要時針對無記憶信源，對有記憶信源，這些編碼方法的效率并不高，特別是對二元相關信源，源，這些編碼方法的效率并不高，特別是對二元相關信源，需要一些其它的方法。游程編碼就是這樣的方法，對相關需要一些其它的方法。游程編碼就是這樣的方法，對相關信源的編碼更有效。信源的編碼更有效。 游程游程（Run-Length，簡記，簡記RL） ：指數(shù)字序列中連續(xù)出現(xiàn)相指數(shù)字序列

55、中連續(xù)出現(xiàn)相同符號的一段。在二元信源中，連續(xù)的一段同符號的一段。在二元信源中，連續(xù)的一段0稱為一個稱為一個0游程，游程，0的個數(shù)稱為此游程的長度，同樣，也有的個數(shù)稱為此游程的長度，同樣，也有1游程。游程。因為游程長度是隨機的，其取值可以是因為游程長度是隨機的，其取值可以是1，2，3， 游程編碼游程編碼（Run-Length Coding，簡記，簡記RLC） ：用交替出現(xiàn)用交替出現(xiàn)的的0游程、游程、1游程的長度，來表示任意二元序列而產生的游程的長度，來表示任意二元序列而產生的一個新序列。它和二元序列是一個一一對應的變換。一個新序列。它和二元序列是一個一一對應的變換。例如：例如：000101110

56、01000131132131二元序列二元序列游程編碼特別適用于對相關信源的編碼。對二元相關信源，游程編碼特別適用于對相關信源的編碼。對二元相關信源，其輸出序列往往會出現(xiàn)多個連續(xù)的其輸出序列往往會出現(xiàn)多個連續(xù)的“0”或連續(xù)的或連續(xù)的“1”。對二元序列，對二元序列，“0”游程和游程和“1游程游程”總是交替出現(xiàn)的，如總是交替出現(xiàn)的，如果規(guī)定二元序列是以果規(guī)定二元序列是以“0”開始的，那么第一個游程是開始的，那么第一個游程是“0”游程，第二個游程必為游程，第二個游程必為“1”游程，第三個游程又是游程，第三個游程又是“0”游游程等等。將任何二元序列變換成游程長度序列，這種變換程等等。將任何二元序列變換成

57、游程長度序列，這種變換是一一對應的，因此是可逆的、無失真的。是一一對應的，因此是可逆的、無失真的。因為游程長度是隨機的、多值的，所以游程序列本身是多因為游程長度是隨機的、多值的，所以游程序列本身是多元序列，對游程序列可以按霍夫曼編碼或其他編碼方法進元序列，對游程序列可以按霍夫曼編碼或其他編碼方法進行處理以達到壓縮碼率的目的。行處理以達到壓縮碼率的目的。說明說明：游程編碼仍是變長碼，有著變長碼固有的缺點，即需要大游程編碼仍是變長碼，有著變長碼固有的缺點，即需要大量的緩沖和優(yōu)質的通信信道。此外，由于游程長度可從量的緩沖和優(yōu)質的通信信道。此外，由于游程長度可從“1”直到無窮大，這在碼字的選擇和碼表的

58、建立方面都有直到無窮大，這在碼字的選擇和碼表的建立方面都有困難，實際應用時尚需采取某些措施來改進。例如，通常困難，實際應用時尚需采取某些措施來改進。例如，通常長游程出現(xiàn)的概率較小，所以對于這類長游程所對應的小長游程出現(xiàn)的概率較小，所以對于這類長游程所對應的小概率碼字，在實際應用時采用截斷處理的方法。概率碼字，在實際應用時采用截斷處理的方法。游程編碼已在圖文傳真、圖像傳輸?shù)韧ㄐ殴こ碳夹g中得到游程編碼已在圖文傳真、圖像傳輸?shù)韧ㄐ殴こ碳夹g中得到應用。在實際中還常常將游程編碼與其他編碼方法綜合起應用。在實際中還常常將游程編碼與其他編碼方法綜合起來使用，以期得到更好的壓縮效果。來使用，以期得到更好的壓縮

59、效果。下面以三類傳真機中使用的壓縮編碼的國際標準下面以三類傳真機中使用的壓縮編碼的國際標準MH編碼編碼為例說明游程編碼的實際應用。為例說明游程編碼的實際應用。lMH編碼編碼:文件傳真是指一般文件、圖紙、手寫稿、表格、報紙文件傳真是指一般文件、圖紙、手寫稿、表格、報紙等文件的傳真，這種信源是黑白二值的，也即信源為等文件的傳真，這種信源是黑白二值的，也即信源為二元信源（二元信源（q=2）。）。MH編碼是一維編碼方案，它是一行一行的對文件傳真編碼是一維編碼方案，它是一行一行的對文件傳真數(shù)據(jù)進行編碼。編碼將游程編碼和霍夫曼碼相結合，數(shù)據(jù)進行編碼。編碼將游程編碼和霍夫曼碼相結合，是一種改進的霍夫曼碼。是

60、一種改進的霍夫曼碼。對黑白二值文件傳真，每一行由連續(xù)出現(xiàn)的對黑白二值文件傳真，每一行由連續(xù)出現(xiàn)的“白（用碼符白（用碼符號號0表示）像素表示）像素”或連續(xù)出現(xiàn)或連續(xù)出現(xiàn)“黑（用碼符號黑（用碼符號1表示）像素表示）像素”組成。組成。MH碼分別對碼分別對“黑黑”、“白白”像素的不同游程長度像素的不同游程長度進行霍夫曼編碼，形成黑、白兩張霍夫曼碼表。進行霍夫曼編碼，形成黑、白兩張霍夫曼碼表。MH碼的碼的編、譯碼都通過查表進行。編、譯碼都通過查表進行。MH碼以國際電話電報咨詢委員會（碼以國際電話電報咨詢委員會（CCITT）確定的）確定的8幅幅標準文件樣張為樣本信源，對這標準文件樣張為樣本信源，對這8幅樣