信息論與編碼無失真信源編碼定理與編碼山東大學(xué)期末考試知識點復(fù)習

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

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

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

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

5、號集對N長信源符號序列進行變長編碼，總能找到一種無失真的唯一可譯碼，使信源符號所需平均碼長滿足：518 無失真信源編碼定理和數(shù)據(jù)壓縮 1無失真數(shù)據(jù)壓縮的極限值 無失真信源編碼定理(無論等長碼還是變長碼)在理論上指出離散信源的信息熵是信源無失真數(shù)據(jù)壓縮的極限值。 在實際應(yīng)用上，變長碼與等長碼相比較，當N不很大時，變長碼能更快地接近這極限值，更快地獲得較好的壓縮效果。 無失真的信源數(shù)據(jù)壓縮是實現(xiàn)減少或消除信源的剩余度，所以在工程實用中又稱為冗余度壓縮編碼。通過無失真數(shù)據(jù)壓縮編碼可使信道的信息傳輸率提高，(提高了信息傳輸系統(tǒng)的有效性)達到信源與信道的匹配，使信道得到充分利用。 2編碼后信源信息率、碼

6、率和編碼效率 (1)編碼后信源信息率 信源編碼后平均每個信源符號能載荷的最大信息量，即519 最佳二元碼 平均碼長為最短的即時碼稱為最佳碼(又稱緊致碼)。 對于某個給定分布的離散信源，存在一個二元最佳碼，此碼滿足如下性質(zhì)： (1)概率大的信源符號所對應(yīng)的碼長不大于概率小的信源符號所對應(yīng)的碼長。 (2)兩個最小概率的信源符號所對應(yīng)的碼字必具有相同碼長。 (3)兩個最小概率的信源符號所對應(yīng)的碼字的差別，必與最后一位碼元不同。 ·對每一種信源編碼需掌握其編碼方法及其平均碼長的極限值范圍。 ·所討論的信源編碼方法都是針對離散無記憶信源的。對于離散平穩(wěn)信源只需將。N重概率空間看成無記

7、憶信源進行編碼即可。 ·對于馬爾可夫信源，可考慮不同狀態(tài)下進行信源符號編碼，壓縮效果可得到改善。5110 香農(nóng)(Shannon)碼 1編碼方法5111 費諾(Fano)碼 1編碼方法(r元費諾碼) (1)將信源符號以概率遞減的次序排列。 (2)將它們劃分成r個組，使每組的概率和接近相同，并各賦予一位碼元。 (3)再將每一組按同樣原則劃分，重復(fù)步驟(2)，直至各組不再可分為止。這樣，所對應(yīng)的碼符號序列則為所編碼字。 2平均碼長的極限5112 霍夫曼(Huffman)碼 1編碼方法(r元霍夫曼碼) (1)信源符號個數(shù)q必須滿足q=(r-1)+r(表示縮減次數(shù))。不滿足時，設(shè)一些概率為零的

8、虛假符號，使其滿足。當r=2時，任意整數(shù)q一定滿足。 (2)將信源符號以概率遞減的次序排列。 (3)給r個概率最小的信源符號各分配一位碼元，并將它們合并成一個新符號，r個最小的概率之和作為新符號的概率，從而得到只包含q-(r-1)個信源符號的新縮減信源S1。 (4)把縮減信源S1重新按概率遞減的次序排列(若此時把所得的新符號盡可能排列在靠前位置上，所得碼的方差最小)，重復(fù)步驟(3)，得只含q-2(r-1)個信源符號的縮減信源S2。 (5)以此繼續(xù)，直至縮減信源只剩r個符號為止。然后，從最后一級縮減信源起，依編碼路徑向前返回，所得碼符號序列就是所對應(yīng)的碼字。 2平均碼長的極限 信源給定情況下，霍

9、夫曼碼是最佳即時碼。其各碼字的碼長是唯一的，但具體碼字不是唯一的。平均碼長的界限為5113 香農(nóng)-費諾-埃利斯碼 1編碼方法 (1)將信源符號X=a1，a2，aq)依次排列(不要求以概率大小排序)。5114 游程編碼和MH編碼 1游程編碼(RLC) 游程編碼是一種針對相關(guān)信源的有效編碼方法，尤其適用于二元相關(guān)信源。有時實際工程技術(shù)中常將游程編碼和其他編碼方法混合使用，能獲得更好的壓縮效果。 信源輸出的字符序列中各種字符連續(xù)地重復(fù)出現(xiàn)而形成一段一段的字符串，稱這種字符串的長度為游程，又稱游長。游程編碼就是將信源字符序列映射成串的字符、串的長度和串的位置的標志序列。 (1)二元信源游程編碼 編碼方

10、法： 將一維二元序列中，分出一段一段的“0”符號串和“1”符號串，對應(yīng)段中的符號個數(shù)標記為“0”游程長度L(0)和“1”游程長度L(1)。 對串的長度即游程長度用自然數(shù)標記，并一般規(guī)定信源序列從“0”游程起始，所以二元信源序列總是“0”游程和“1”游程交替出現(xiàn)。 將二元信源序列映射成交替出現(xiàn)的表示游程長度的自然數(shù)序列(即為對應(yīng)的游程長度的標志序列)。 一般情況，對“0”游程長度和“1”游程長度也可分別編碼，建立各自的碼字和碼表(如霍夫曼編碼)。 編碼效率(游程編碼和霍夫曼編碼)其中p0，p1為“0”和“1”符號的概率。0和1為游程長度為“0”和“1”霍夫曼編碼效率。 (2)多元信源游程編碼 將

11、多元信源輸出的多元序列映射成一一對應(yīng)的標志序列。 一維多元信源序列需選用表示串的字符、串的長度的兩個標志參量。 二維多元信源序列需選用表示串的字符、串的長度及串的位置三個標志參量。 2MH編碼 MH編碼是用于黑白二值文件傳真的數(shù)據(jù)壓縮碼。它是一維編碼方案。它是游程編碼和霍夫曼碼相結(jié)合的一種標準的改進霍夫曼碼。 根據(jù)“黑”、“白”的不同游程長度有兩張結(jié)尾碼(終端碼)表和兩張組合碼(形成碼)表。 (1)編碼方法 游程長度在063時，直接查表用相應(yīng)的結(jié)尾碼為碼字。 游程長度在641728時，用組合碼加上結(jié)尾碼為相應(yīng)碼字。 規(guī)定每行從白游程開始，每行結(jié)束用結(jié)束碼(EOL)。 用于傳輸時，每頁文件開始第

12、一數(shù)據(jù)前加一結(jié)束碼，每頁結(jié)尾連續(xù)用6個結(jié)束碼。為了傳輸還要考慮實現(xiàn)同步的操作。5115 算術(shù)編碼 算術(shù)編碼是非分組碼，它從全信源序列出發(fā)，考慮符號之間的依賴關(guān)系直接對信源符號序列進行的編碼。 算術(shù)編碼的主要概念是將信源符號序列的累積分布函數(shù)和0，1)區(qū)間中的一個數(shù)C聯(lián)系起來，不同的信源符號序列對應(yīng)于不同的無重疊小區(qū)間中的數(shù)。所以，這個碼是即時碼。 1編碼方法 (1)用遞推公式計算信源序列的累積分布函數(shù)F(s)和所對應(yīng)區(qū)間的寬度A(s)：5116 字典碼 字典碼又稱LZ碼，是一種通用編碼方法，無需知道信源的統(tǒng)計特性，而且編碼效率很高。 基本算法是，將長度不同的符號串編成一個個新的短語(符號串)，形成短語詞典的索引表，進行編譯碼。 1LZ-77編碼 編碼算法的主要思想是設(shè)一個滑動窗口，將已輸入的數(shù)據(jù)流存儲起來，作為字典使用。然后用三元標識(K，l，d)即(移位數(shù)，匹配串長度，首字符)，對數(shù)據(jù)流編碼，形成標識符序列。 此編碼字典不用傳送，可以邊譯碼，邊建立譯碼字典。 2LZ-78編碼 LZ-78是一