信息論與編碼[第五章無失真信源編碼定理與編碼]山東大學(xué)期末考

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

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

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

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

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

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

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

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

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

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

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

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