1、第五章 無失真信源編碼定理與編碼511 信源編碼和碼的類型1信源編碼2碼的類型若碼符號集中符號數r=2稱為二元碼，r=3稱為三元碼，r元碼。若分組碼中所有碼字的碼長都相同則稱為等長碼，否則稱為變長碼。若分組碼中所有碼字都不相同則稱為非奇異碼，否則稱為奇異碼。若每個碼符號xiX的傳輸時間都相同則稱為同價碼，否則稱為非同價碼。若分組碼的任意一串有限長的碼符號只能被唯一地譯成所對應的信源符號序列則稱為唯一可譯碼，否則稱為非唯一可譯碼。若分組碼中，沒有任何完整的碼字是其他碼字的前綴，則稱為即時碼(又稱非延長碼或前綴條件碼，否則稱為延長碼。本章主要研究的是同價唯一可譯碼。512 即時碼及其樹圖構造法即時

2、碼(非延長碼或前綴條件碼是唯一可譯碼的一類子碼。即時碼可用樹圖法來構造。構造的要點是：(1最上端為樹根A，從根出發向下伸出樹枝，樹枝總數等于r，樹枝的盡頭為節點。(2從每個節點再伸出r枝樹枝，當某節點被安排為碼字后，就不再伸枝，這節點為終端節點。一直繼續進行，直至都不能伸枝為止。(3每個節點所伸出的樹枝標上碼符號，從根出發到終端節點所走路徑對應的碼符號序列則為終端節點的碼字。即時碼可用樹圖法來進行編碼和譯碼。從樹圖可知，即時碼可以即時進行譯碼。當碼字長度給定，即時碼不是唯一的。可以認為等長唯一可譯碼是即時碼的一類子碼。513 唯一可譯碼存在的充要條件(1對含有q個信源符號的信源用含r個符號的碼

3、符號集進行編碼，各碼字的碼長為l1，l2，lq的唯一可譯碼存在的充要條件是，滿足Kraft不等式514 唯一可譯碼的判斷法唯一可譯碼的判斷步驟：首先，觀察是否是非奇異碼。若是奇異碼則一定不是唯一可譯碼。其次，計算是否滿足Kraft不等式。若不滿足一定不是唯一可譯碼。再次，將碼畫成一棵樹圖，觀察是否滿足即時碼的樹圖的構造，若滿足則是唯一可譯碼。或用Sardinas和Patterson設計的判斷方法：計算出分組碼中所有可能的尾隨后綴集合F，觀察F中有沒有包含任一碼字，若無則為唯一可譯碼；若有則一定不是唯一可譯碼。上述判斷步驟中Sardinas和Patterson設計的判斷方法是能確切地判斷出是否是

4、唯一可譯碼的方法，所以可以跳過前三個步驟直接采用該判斷法。515 漸近等分割性和典型序列則稱此N長序列i為非典型序列。(2典型序列集516 無失真等長信源編碼定理離散信源S，其信息熵為H，用含r個字母的碼符號集對N長信源符號序列進行等長編碼，若滿足l/NH/logr+(>0的任意小數，則當N足夠大時，可實現幾乎無失真編碼。其中，當S為離散無記憶信源時，H=H(S；當S為離散平穩信源，H為信源的極限熵；當S為馬爾可夫信源，H為馬爾可夫信源的極限熵。517 無失真變長信源編碼定理(香農第一定理用含r個字母的碼符號集對N長信源符號序列進行變長編碼，總能找到一種無失真的唯一可譯碼，使信源符號所需

5、平均碼長滿足：518 無失真信源編碼定理和數據壓縮1無失真數據壓縮的極限值無失真信源編碼定理(無論等長碼還是變長碼在理論上指出離散信源的信息熵是信源無失真數據壓縮的極限值。在實際應用上，變長碼與等長碼相比較，當N不很大時，變長碼能更快地接近這極限值，更快地獲得較好的壓縮效果。無失真的信源數據壓縮是實現減少或消除信源的剩余度，所以在工程實用中又稱為冗余度壓縮編碼。通過無失真數據壓縮編碼可使信道的信息傳輸率提高，(提高了信息傳輸系統的有效性達到信源與信道的匹配，使信道得到充分利用。2編碼后信源信息率、碼率和編碼效率(1編碼后信源信息率信源編碼后平均每個信源符號能載荷的最大信息量，即519 最佳二元

6、碼平均碼長為最短的即時碼稱為最佳碼(又稱緊致碼。對于某個給定分布的離散信源，存在一個二元最佳碼，此碼滿足如下性質：(1概率大的信源符號所對應的碼長不大于概率小的信源符號所對應的碼長。(2兩個最小概率的信源符號所對應的碼字必具有相同碼長。(3兩個最小概率的信源符號所對應的碼字的差別，必與最后一位碼元不同。·對每一種信源編碼需掌握其編碼方法及其平均碼長的極限值范圍。·所討論的信源編碼方法都是針對離散無記憶信源的。對于離散平穩信源只需將。N重概率空間看成無記憶信源進行編碼即可。·對于馬爾可夫信源，可考慮不同狀態下進行信源符號編碼，壓縮效果可得到改善。5110 香農(Sh

7、annon碼1編碼方法5111 費諾(Fano碼1編碼方法(r元費諾碼(1將信源符號以概率遞減的次序排列。(2將它們劃分成r個組，使每組的概率和接近相同，并各賦予一位碼元。(3再將每一組按同樣原則劃分，重復步驟(2，直至各組不再可分為止。這樣，所對應的碼符號序列則為所編碼字。2平均碼長的極限5112 霍夫曼(Huffman碼1編碼方法(r元霍夫曼碼(1信源符號個數q必須滿足q=(r-1+r(表示縮減次數。不滿足時，設一些概率為零的虛假符號，使其滿足。當r=2時，任意整數q一定滿足。(2將信源符號以概率遞減的次序排列。(3給r個概率最小的信源符號各分配一位碼元，并將它們合并成一個新符號，r個最小

8、的概率之和作為新符號的概率，從而得到只包含q-(r-1個信源符號的新縮減信源S1。(4把縮減信源S1重新按概率遞減的次序排列(若此時把所得的新符號盡可能排列在靠前位置上，所得碼的方差最小，重復步驟(3，得只含q-2(r-1個信源符號的縮減信源S2。(5以此繼續，直至縮減信源只剩r個符號為止。然后，從最后一級縮減信源起，依編碼路徑向前返回，所得碼符號序列就是所對應的碼字。2平均碼長的極限信源給定情況下，霍夫曼碼是最佳即時碼。其各碼字的碼長是唯一的，但具體碼字不是唯一的。平均碼長的界限為5113 香農-費諾-埃利斯碼1編碼方法(1將信源符號X=a1，a2，aq依次排列(不要求以概率大小排序。511

9、4 游程編碼和MH編碼1游程編碼(RLC游程編碼是一種針對相關信源的有效編碼方法，尤其適用于二元相關信源。有時實際工程技術中常將游程編碼和其他編碼方法混合使用，能獲得更好的壓縮效果。信源輸出的字符序列中各種字符連續地重復出現而形成一段一段的字符串，稱這種字符串的長度為游程，又稱游長。游程編碼就是將信源字符序列映射成串的字符、串的長度和串的位置的標志序列。(1二元信源游程編碼編碼方法：將一維二元序列中，分出一段一段的“0”符號串和“1”符號串，對應段中的符號個數標記為“0”游程長度L(0和“1”游程長度L(1。對串的長度即游程長度用自然數標記，并一般規定信源序列從“0”游程起始，所以二元信源序列

10、總是“0”游程和“1”游程交替出現。將二元信源序列映射成交替出現的表示游程長度的自然數序列(即為對應的游程長度的標志序列。一般情況，對“0”游程長度和“1”游程長度也可分別編碼，建立各自的碼字和碼表(如霍夫曼編碼。 編碼效率(游程編碼和霍夫曼編碼其中p0，p1為“0”和“1”符號的概率。0和1為游程長度為“0”和“1”霍夫曼編碼效率。(2多元信源游程編碼將多元信源輸出的多元序列映射成一一對應的標志序列。一維多元信源序列需選用表示串的字符、串的長度的兩個標志參量。二維多元信源序列需選用表示串的字符、串的長度及串的位置三個標志參量。2MH編碼MH編碼是用于黑白二值文件傳真的數據壓縮碼。它是一維編碼

11、方案。它是游程編碼和霍夫曼碼相結合的一種標準的改進霍夫曼碼。根據“黑”、“白”的不同游程長度有兩張結尾碼(終端碼表和兩張組合碼(形成碼表。(1編碼方法游程長度在063時，直接查表用相應的結尾碼為碼字。游程長度在641728時，用組合碼加上結尾碼為相應碼字。規定每行從白游程開始，每行結束用結束碼(EOL。用于傳輸時，每頁文件開始第一數據前加一結束碼，每頁結尾連續用6個結束碼。為了傳輸還要考慮實現同步的操作。5115 算術編碼算術編碼是非分組碼，它從全信源序列出發，考慮符號之間的依賴關系直接對信源符號序列進行的編碼。算術編碼的主要概念是將信源符號序列的累積分布函數和0，1區間中的一個數C聯系起來，

12、不同的信源符號序列對應于不同的無重疊小區間中的數。所以，這個碼是即時碼。1編碼方法(1用遞推公式計算信源序列的累積分布函數F(s和所對應區間的寬度A(s：5116 字典碼字典碼又稱LZ碼，是一種通用編碼方法，無需知道信源的統計特性，而且編碼效率很高。基本算法是，將長度不同的符號串編成一個個新的短語(符號串，形成短語詞典的索引表，進行編譯碼。1LZ-77編碼編碼算法的主要思想是設一個滑動窗口，將已輸入的數據流存儲起來，作為字典使用。然后用三元標識(K，l，d即(移位數，匹配串長度，首字符，對數據流編碼，形成標識符序列。此編碼字典不用傳送，可以邊譯碼，邊建立譯碼字典。2LZ-78編碼LZ-78是一種分段編