信息論與編碼[第五章無失真信源編碼定理與編碼]山東大學(xué)期末考試知識(shí)點(diǎn)復(fù)習(xí)

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

2、價(jià)唯一可譯碼。512 即時(shí)碼及其樹圖構(gòu)造法 即時(shí)碼(非延長(zhǎng)碼或前綴條件碼)是唯一可譯碼的一類子碼。 即時(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)上碼符號(hào)，從根出發(fā)到終端節(jié)點(diǎn)所走路徑對(duì)應(yīng)的碼符號(hào)序列則為終端節(jié)點(diǎn)的碼字。 即時(shí)碼可用樹圖法來進(jìn)行編碼和譯碼。 從樹圖可知，即時(shí)碼可以即時(shí)進(jìn)行譯碼。 當(dāng)碼字長(zhǎng)度給定，即時(shí)碼不是唯一的。 可以認(rèn)為等長(zhǎng)唯一可譯碼是即時(shí)碼的一類子碼。51

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

4、 上述判斷步驟中Sardinas和Patterson設(shè)計(jì)的判斷方法是能確切地判斷出是否是唯一可譯碼的方法，所以可以跳過前三個(gè)步驟直接采用該判斷法。515 漸近等分割性和典型序列則稱此N長(zhǎng)序列i為非典型序列。 (2)典型序列集516 無失真等長(zhǎng)信源編碼定理 離散信源S，其信息熵為H，用含r個(gè)字母的碼符號(hào)集對(duì)N長(zhǎng)信源符號(hào)序列進(jìn)行等長(zhǎng)編碼，若滿足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 無失真變長(zhǎng)信源編碼定理(香農(nóng)第一

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

6、。 2編碼后信源信息率、碼率和編碼效率 (1)編碼后信源信息率 信源編碼后平均每個(gè)信源符號(hào)能載荷的最大信息量，即519 最佳二元碼 平均碼長(zhǎng)為最短的即時(shí)碼稱為最佳碼(又稱緊致碼)。 對(duì)于某個(gè)給定分布的離散信源，存在一個(gè)二元最佳碼，此碼滿足如下性質(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ì)離散無記憶信源的。對(duì)于離散平穩(wěn)信源只

7、需將。N重概率空間看成無記憶信源進(jìn)行編碼即可。 ·對(duì)于馬爾可夫信源，可考慮不同狀態(tài)下進(jìn)行信源符號(hào)編碼，壓縮效果可得到改善。5110 香農(nóng)(Shannon)碼 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必須滿足q=(r-1)+r(表示縮減次數(shù))。

8、不滿足時(shí)，設(shè)一些概率為零的虛假符號(hào)，使其滿足。當(dāng)r=2時(shí)，任意整數(shù)q一定滿足。 (2)將信源符號(hào)以概率遞減的次序排列。 (3)給r個(gè)概率最小的信源符號(hào)各分配一位碼元，并將它們合并成一個(gè)新符號(hào)，r個(gè)最小的概率之和作為新符號(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)

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

10、)二元信源游程編碼 編碼方法： 將一維二元序列中，分出一段一段的“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”游程起始，所以二元信源序列總是“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”霍夫曼編碼效率。

11、(2)多元信源游程編碼 將多元信源輸出的多元序列映射成一一對(duì)應(yīng)的標(biāo)志序列。 一維多元信源序列需選用表示串的字符、串的長(zhǎng)度的兩個(gè)標(biāo)志參量。 二維多元信源序列需選用表示串的字符、串的長(zhǎng)度及串的位置三個(gè)標(biāo)志參量。 2MH編碼 MH編碼是用于黑白二值文件傳真的數(shù)據(jù)壓縮碼。它是一維編碼方案。它是游程編碼和霍夫曼碼相結(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ī)定每行從白游程開始，每行結(jié)束用結(jié)束碼(EOL)。

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