無失真的信源編碼

1、幻燈片1第8章 無失真的信源編碼幻燈片2l 信源編碼主要可分為無失真信源編碼和限失真信源編碼。l 無失真信源編碼主要適用于離散信源或數(shù)字信號，要求進(jìn)行無失真地數(shù)據(jù)壓縮，要求完全能夠無失真地可逆恢復(fù)。l 限失真信源編碼主要適用于波形信源或波形信號（即模擬信號），不要求完全可逆地恢復(fù)，而是允許在一定限度內(nèi)可以有失真的壓縮。l 兩種信源編碼都是為了用較少的碼率來傳送同樣多的信息，增加單位時間內(nèi)傳送的信息量，從而提高通信系統(tǒng)的有效性?；脽羝?l 香農(nóng)信息理論香農(nóng)第一定理和香農(nóng)第三定理是信源壓縮編碼的理論基礎(chǔ)，從理論上給出了進(jìn)行無失真信源壓縮和限失真信源壓縮的理論極限，還論證與指出了理想最佳信源編碼是存

2、在的，但沒有給出信源編碼實際構(gòu)造方法和實用碼的結(jié)構(gòu)?；脽羝?l 本章主要研究無失真信源編碼的技術(shù)和方法。從第5章香農(nóng)第一定理已知，信源的信息熵是信源進(jìn)行無失真編碼的理論極限值?？偰苷业侥撤N合適的編碼方法使編碼后信源的信息傳輸率R任意地逼近信源的信息熵而不存在任何失真。在數(shù)據(jù)壓縮技術(shù)中無失真信源編碼又常被稱為熵編碼?；脽羝?l 從第二章的討論可知，正是由于信源概率分布的不均勻性，或者信源是有記憶的、具有相關(guān)性，使信源中或多或少含有一定的剩余度。只要尋找到去除相關(guān)性或者改變概率分布不均勻的方法和手段，就能找到熵編碼的具體方法和實用碼的結(jié)構(gòu)。幻燈片6l 本章首先討論了典型的霍夫曼編碼、游程編碼及算術(shù)

3、編碼的原理和方法。這都是當(dāng)信源的統(tǒng)計特性已確知時，能達(dá)到或接近壓縮極限界限的編碼方法。前者主要適用于多元獨立的信源，后兩者主要適用于二元信源及具有一定相關(guān)性的有記憶信源。最后討論了通用編碼（又稱字典碼）的原理和方法。是針對信源的統(tǒng)計特性未確知或不知時所采用的壓縮編碼方法。l 本章主要介紹霍夫曼編碼?；脽羝?香農(nóng)Shannon編碼非最佳碼l 香農(nóng)碼的編碼流程：l 1、將信源符號以概率遞減次序排列起來。l 2、確定滿足下列不等式的整數(shù)碼長l 3、為編成唯一可譯碼，計算第i個消息的累加概率：l 4、將累加概率Pi變換成二進(jìn)制數(shù)。l 5、取二進(jìn)制數(shù)的小數(shù)點后li位即為該消息符號的二進(jìn)制碼字，即為香農(nóng)碼

4、?；脽羝?8.1 霍夫曼（Huffman）碼l 香農(nóng)第一定理的證明過程告訴我們一種編碼方法，這就是香農(nóng)編碼。但是一般情況下，香農(nóng)編碼的平均碼長不是最短，即編出來的不是緊致碼（最佳碼）。幻燈片98.1.1 二元霍夫曼碼l 霍夫曼編碼適用于多元獨立信源，對于多元獨立信源來說它是最佳碼。充分利用了信源概率分布的特性進(jìn)行編碼，是一種最佳的逐個符號的編碼方法?；脽羝?0二元霍夫曼碼的編碼步驟l 將q個信源符號按概率分布P(si)的大小，以遞減次序排列起來，設(shè)p1>p2>p3>>pql 用0和1碼符號分別分配給概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個新符號，并

5、用這兩個最小概率之和作為新符號的概率，從而得到只包含q-1個符號的新信源，稱為S信源的縮減信源S1。幻燈片11續(xù)l 把縮減信源S1的符號仍按概率大小以遞減次序排列，再將其最后兩個概率最小的符號合并成一個新符號，并分別用0和1碼符號表示，這樣又形成了q-2個符號的縮減信源S2。l 依次繼續(xù)下去，直至縮減信源最后只剩下兩個符號為止。將這兩個符號分別用0和1碼符號表示。最后這兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑由后向前返回，就得出個信源符號所對應(yīng)得碼符號序列，即得對應(yīng)得碼字了?；脽羝?2霍夫曼編碼的選擇l 霍夫曼編碼方法得到的碼并非是唯一的。l 對于平均碼長相等的霍夫曼碼

6、可以通過引進(jìn)碼字長度偏離平均長度的方差選擇判斷。l 在霍夫曼編碼過程中，當(dāng)縮減信源的概率分布重新排列時，應(yīng)使合并得來的概率和盡量處于最高的位置，這樣可以使得合并的元素重復(fù)編碼次數(shù)減少，使短碼得到充分利用?；脽羝?3二元霍夫曼碼的特點l 霍夫曼碼的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，即pj>pk，lj>lk，而且短碼得到充分利用。l 每次縮減信源的最后兩個碼字總是最后一位碼元不同，前面各位碼元相同（二元編碼情況）如表8.1和8.2所示。l 每次縮減信源的最長兩個碼字有相同的碼長l 這三個特點保證了所得到的霍夫曼碼一定是最佳碼?；脽羝?4霍夫曼碼的推廣和最佳性

7、l 二元霍夫曼碼的編碼方法同樣可以推廣到r元編碼中去。不同的只是每次把r個符號（概率最小的）合并成一個新的信源符號，并分別用0,1,(r-1)等碼元表示。l 霍夫曼碼是最佳碼（緊致碼）。所謂最佳性，就是指對于某個給定信源，在所有可能的唯一可譯碼中，此碼的平均碼長為最短。并稱此碼為最佳碼或緊致碼?；脽羝?58.2費(fèi)諾（Fano）碼l 費(fèi)諾編碼方法屬于概率匹配編碼，這種編碼方法稍不同于前述的霍夫曼編碼法，它不是最佳的編碼方法，但有時也可得到最佳碼的性能?；脽羝?6二元費(fèi)諾碼的編碼步驟l 首先，將信源符號以概率遞減的次序排列起來，將排列好的信源符號劃分成兩大組，使每組的概率和近于相同，并各賦予一個二

8、元碼符號“0”和“1”。l 然后，將每一大組的信源符號再分成兩組，使同一組的兩個小組的概率和近于相同，并又分別賦予一個二元碼符號。l 依次下去，直至每個小組只剩下一個信源符號為止。l 最后，由前向后（從左向右）讀取碼符號序列（注意：讀取碼字與霍夫曼編碼不同）。l 這樣，信源符號所對應(yīng)的碼符號序列則為編得的碼字。幻燈片17續(xù)l 費(fèi)諾碼的編碼方法實際上是構(gòu)造碼樹的一種方法，所以費(fèi)諾碼是即時碼。l 費(fèi)諾碼也考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號能對應(yīng)碼長短的碼字。l 費(fèi)諾碼仍然是一種相當(dāng)好的編碼方法。l 費(fèi)諾編碼方法同樣適合于r元編碼，只需每次分成r組即可?；脽羝?8三種編碼方式的比較l 只有霍

9、夫曼碼必定是最佳碼，霍夫曼碼的平均碼長最小，信息傳輸率最大，編碼效率最高，但在實際使用時其設(shè)備較為復(fù)雜。l 費(fèi)諾碼有時也能達(dá)到最佳碼的性質(zhì)。l 香農(nóng)碼的編碼效率較以上兩者要差一些。l 對于以上三種編碼有：幻燈片198.3 香農(nóng)費(fèi)諾埃利斯碼l 香農(nóng)費(fèi)諾埃利斯碼是采用信源符號的累積分布函數(shù)來分配碼字l 雖然香農(nóng)費(fèi)諾埃利斯碼不是最佳碼，但由它拓寬可得到一種算數(shù)碼。該算數(shù)碼是一種非分組碼，其編碼和譯碼都是計算效率高的碼。幻燈片20本章小結(jié)l 討論了基于熵概念的無損壓縮編碼及其各種壓縮編碼。這些方法在實際工程技術(shù)中得到廣泛的應(yīng)用，如現(xiàn)在所用的各種圖像格式，除BMP文件外，都用到這些無損壓縮編碼算法。又如廣為人知的MP3、MP4