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

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

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

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

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

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

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

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

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

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

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

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

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