第5章 無失真信源編碼定理

第五章無失真信源編碼一般來說，抗干擾能與信息傳輸率二者相互矛盾。然而編碼定理已從理論上證明，至少存在某種最佳的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。信源雖然多種多樣，但無論是哪種類型的信源，信源符號之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率。信源編碼的基本途徑有兩個(gè):一是編碼后使序列中的各個(gè)符號之間盡可能地互相獨(dú)立，即解除相關(guān)性----方法包括預(yù)測編碼和變換編碼.二是使編碼后各個(gè)符號出現(xiàn)的概率盡可能相等，即均勻化分布----方法主要是統(tǒng)計(jì)編碼.信源編碼常分為無失真信源編碼和限失真信源編碼，前者主要用于文字、數(shù)據(jù)信源的壓縮，后者主要用于圖像、語音信源的壓縮。本章主要介紹信源編碼的基本思路與主要方法，以無失真、統(tǒng)計(jì)編碼為主，期望通過本章學(xué)習(xí)能建立起信源壓縮編碼的基本概念。5.1編碼器及相關(guān)概念為了分析方便和突出問題的重點(diǎn)，當(dāng)研究信源編碼時(shí)，我們把信道編碼和譯碼看成是信道的一部分，從而突出信源編碼。同樣，在研究信道編碼時(shí)，可以將信源編碼和譯碼看成是信源和信宿的一部分，從而突出信道編碼。5.1.1碼的分類一.編碼器模型

由于信源編碼可以不考慮抗干擾問題，所以它的數(shù)學(xué)模型比較簡單。下圖為一個(gè)編碼器模型:輸入是信源符號集:x為編碼器所用的編碼符號集，包含r個(gè)元素{}，稱為碼符號(碼元).由碼符號組成的輸出序列稱為碼字.

其長度稱為碼字長度或碼長，全體碼字的集合C稱為碼或碼書.編碼器將信源符號集中的信源符號（或長為N的信源符號序列）變成由碼符號組成的長為l的與信源符號一一對應(yīng)的輸出序列。即:二.碼的分類:

對于編碼器而言，根據(jù)碼符號集合X中碼元的個(gè)數(shù)不同以及碼字長度是否一致，有以下一些常用的編碼形式：

(1)二元碼和r元碼

若碼符號集，編碼所得碼字為一些適合在二元信道中傳輸?shù)亩蛄校瑒t稱二元碼。二元碼是數(shù)字通信與計(jì)算機(jī)系統(tǒng)中最常用的一種碼。若碼符號集共有r個(gè)元素，則所得之碼稱為r元碼.(2)等長碼

若一組碼中所有碼字的長度都相同----（即），則稱為等長碼.(3)

變長碼若一組碼中碼字的碼長各不相同（即碼字長度不等），則稱為變長碼

.

如表中“編碼1”為等長碼，“編碼2”為變長碼。信源符號si符號出現(xiàn)概率p(si)編碼1編碼2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)111014、5）非奇異碼和奇異碼若一組碼中所有碼字都不相同(即所有信源符號映射到不同的碼符號序列)，則稱為非奇異碼。反之，則為奇異碼。如表中的“編碼2”是奇異碼，其他碼是非奇異碼。概率信源符號編碼1編碼2編碼3編碼4編碼51/20000011/4010110011/8101001100011/811101111100016）同價(jià)碼若碼符號集X：{}中每個(gè)碼符號所占的傳輸時(shí)間都相同，則所得的碼為同價(jià)碼。我們一般討論同價(jià)碼，對同價(jià)碼來說等長碼中每個(gè)碼字的傳輸時(shí)間相同，而變長碼中每個(gè)碼字的傳輸時(shí)間就不一定相同。7）碼的N次擴(kuò)展碼假定某一碼，它把信源中的符號一一變換成碼C中的碼字，則碼C的N次擴(kuò)展碼是所有N個(gè)碼字組成的碼字序列的集合。例如：若碼滿足：則碼C的N次擴(kuò)展碼集合,其中：即碼C的N次擴(kuò)展碼中，每個(gè)碼字與信源的N次擴(kuò)展信源中的每個(gè)信源符號是一一對應(yīng)的：8）惟一可譯碼若任意一串有限長的碼符號序列只能被惟一地譯成所對應(yīng)的信源符號序列，則此碼稱為惟一可譯碼（或稱單義可譯碼）。否則就稱為非惟一可譯碼或非單義可譯碼。若要使某一碼為惟一可譯碼，則對于任意給定的有限長的碼符號序列，只能被惟一地分割成一個(gè)個(gè)的碼字。例如：對于二元碼，當(dāng)任意給定一串碼字序列，例如“10001101”，只可唯一地劃分為1,00,01,1,01，因此是惟一可譯碼；而對另一個(gè)二元碼，當(dāng)碼字序列為“01001”時(shí)，可劃分為0,10,01或01,0,01，所以是非惟一可譯的。若樹碼的各個(gè)分支都延伸到最后一級端點(diǎn)，此時(shí)將共有個(gè)碼字，這樣的碼樹稱為整樹，如圖(a)所示。否則就稱為非整樹，如圖(b)所示，這時(shí)的碼字就不是等長碼了。因此，碼樹與碼之間具有如下一一對應(yīng)的關(guān)系：樹根

碼字起點(diǎn)；樹枝數(shù)

碼的進(jìn)制數(shù)；節(jié)點(diǎn)

碼字或碼字的一部分；終端節(jié)點(diǎn)

碼字；階數(shù)

碼長；非整樹

變長碼；整樹

等長碼。5.5.3Kraft不等式利用碼樹可以判斷給定的碼是否為惟一可譯碼，但需要畫出碼樹。在實(shí)際中，我們可以利用克拉夫特（Kraft）不等式，直接根據(jù)各碼字的長度來判斷惟一可譯碼是否存在，即各碼字的長度應(yīng)符合克拉夫特不等式：式中，r為進(jìn)制數(shù)也即碼符號的個(gè)數(shù)，q為信源符號數(shù)。Kraft不等式是惟一可譯碼存在的充要條件。其必要性表現(xiàn)在如果碼是惟一可譯碼，則必定滿足Kraft不等式;充分性表現(xiàn)在如果滿足Kraft不等式，則這種碼長的惟一可譯碼一定存在，但并不表示所有滿足Kraft不等式的碼一定是惟一可譯碼。因此，克拉夫特不等式是惟一可譯碼存在的必要條件，而不是惟一