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

第5章無失真信源編碼定理鄒小林2015.11.

通信的實質(zhì)是信息的傳輸。高效率、高質(zhì)量傳送信息是信息傳輸?shù)幕締栴}！需要解決兩個問題：第一，在不失真或允許一定失真的條件下，如何

用盡可能少的符號來傳送信源信息；第二，在信道受干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大。為了解決這兩個問題，引入信源編碼和信道編碼。了解

抗干擾能力與信息傳輸率二者相互矛盾。編碼定理證明，至少存在某種最佳的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。了解

由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。具體說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。了解

信源編碼常分為無失真信源編碼和限失真信源編碼，前者主要用于文字、數(shù)據(jù)信源的壓縮;

后者主要用于圖像、語音信源的壓縮。了解

無失真編碼

無失真編碼是可逆編碼的基礎(chǔ)。

可逆是指當(dāng)信源符號轉(zhuǎn)換成代碼后，可從代碼無失真地恢復(fù)原信源符號。了解5.1編碼器

編碼實質(zhì)上是對信源的原始符號按一定的數(shù)學(xué)規(guī)則進行的一種變換。

了解

一、編碼器模型由于信源編碼可以不考慮抗干擾問題，所以它的數(shù)學(xué)模型比較簡單。了解輸入是信源符號集:x為編碼器所用的編碼符號集，包含r個元素{}，稱為碼符號(碼元)。由碼符號組成的輸出序列稱為碼字。其長度稱為碼字長度或碼長，全體碼字的集合C稱為碼或碼書。編碼器將信源符號集中的信源符號

(或長為N的信源符號序列)變成由碼符號組成的長為的與信源符號一一對應(yīng)的輸出序列。即:理解

二、碼的分類根據(jù)碼符號集合X中碼元個數(shù)的不同以及碼字長度是否一致，有以下一些常用的編碼形式：

(1)

二元碼和r元碼若碼符號集，編碼所得碼字為一些二元序列，則稱二元碼。二元碼是數(shù)字通信與計算機系統(tǒng)中最常用的一種碼。若碼符號集有r個元素，則稱r元碼。理解

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

(3)

變長碼若一組碼中碼字的碼長各不相同(即碼字長度不等)，則稱為變長碼。如表中“編碼1”為等長碼，“編碼2”為變長碼。信源符號si符號出現(xiàn)概率p(si)編碼1編碼2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)11101理解(4)非奇異碼若一組碼中所有碼字都不相同(即所有信源符號映射到不同的碼符號序列)，則稱為非奇異碼。則稱碼C為非奇異碼。理解

（5）奇異碼若一組碼中有相同的碼字，則為奇異碼。則稱碼C為奇異碼。理解概率信源符號

編碼1編碼2編碼3編碼4編碼51/20000011/4010110011/8101001100011/81110111110001如表中的“編碼2”是奇異碼，其他碼是非奇異碼。理解

（6）同價碼若碼符號集X：{}中每個碼符號所占的傳輸時間都相同，則所得的碼為同價碼。我們一般討論同價碼，對同價碼來說等長碼中每個碼字的傳輸時間相同，而變長碼中每個碼字的傳輸時間就不一定相同。

如：電報中常用的莫爾斯碼是非同價碼，其碼符號點（.）和劃（-）所占的傳輸時間不相同。理解

（7）碼的N次擴展碼假定某碼C，它把信源中的符號一一變換成碼C中的碼字，則碼C的N次擴展碼是所有N個碼字組成的碼字序列的集合。理解

例如：若碼滿足：則碼C的N次擴展碼集合,其中：

即碼C的N次擴展碼中，每個碼字與信源的N次擴展信源中的每個信源符號是一一對應(yīng)的：理解例信源符號ai碼字信源符號ai碼字a100a5010a2001a60101a30001……a40111a16111111信源符號si符號出現(xiàn)概率p(si)編碼1編碼2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)11111求編碼2的2次擴展掌握

（8）惟一可譯碼若任意一串有限長的碼符號序列只能被惟一地譯成所對應(yīng)的信源符號序列，則此碼稱為惟一可譯碼（或稱單義可譯碼）。否則就稱為非惟一可譯碼或非單義可譯碼。若要使某一碼為惟一可譯碼，則對于任意給定的有限長的碼符號序列，只能被惟一地分割成一個個的碼字。理解

例如：對于二元碼，當(dāng)任意給定一串碼字序列，例如“10001101”，只可唯一地劃分為1,00,01,1,01，因此是惟一可譯碼；而對另一個二元碼，當(dāng)碼字序列為“01001”時，可劃分為0,10,01或01,0,01，所以是非惟一可譯的。理解

對惟一可譯碼又分為即時碼和非即時碼：如果在接收端收到一個完整的碼字后，就能立即進行譯碼，這樣的碼叫做即時碼；而在接收端收到一個完整的碼字后，還需等下一個碼字接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。即時碼又稱為非延長碼，對即時碼而言，在碼本中任意一個碼字都不是其它碼字的前綴部分。對非即時碼來說，有的碼是惟一可譯的，有的碼是非惟一可譯的，主要取決于碼的總體結(jié)構(gòu)。信源符號si符號出現(xiàn)概率p(si)編碼1編碼2s1p(s1)11s2p(s2)1001s3p(s3)100001s4p(s4)10000001理解信源符號ai符號出現(xiàn)概率p(ai)碼1碼2碼3碼4a11/20011a21/411101001a31/80000100001a41/8110110000001

碼1是奇異碼，碼2是非奇異碼。碼2不是唯一可譯碼，碼3是。又如，碼字{0，10，11}是一種唯一可譯碼。因為任意一串有限長碼序列，例如100

111

000，只能被分割成10，0，11，10，0，0。任何其他分割法都會產(chǎn)生一些非定義的碼字。理解信源符號ai符號出現(xiàn)概率p(ai)碼1碼2碼3碼4a11/20011a21/411101001a31/80000100001a41/8110110000001

即時碼要求任何一個碼字都不是其他碼字的前綴部分，所以也叫做異前綴碼/非延長碼。如上表中的碼4。如果接收端收到一個完整的碼字后，不能立即譯碼，必須結(jié)合后續(xù)的碼元序列才能進行譯碼，稱為非即時碼。如碼3?？梢姡ㄒ豢勺g碼不一定是即時碼，因為非即時碼(延長碼)也具有唯一可譯性。理解了解5.2等長碼

一般說來，若要實現(xiàn)無失真的編碼，這不但要求信源符號與碼字是一一對應(yīng)的，而且要求所編的碼必須是唯一可譯碼。否則，所編的碼不具有唯一可譯碼性，就會引起譯碼帶來的錯誤與失真。

對于等長碼來說，若等長碼是非奇異碼，則它的任意有限長N次擴展碼一定也是非奇異碼。因此等長非奇異碼一定是唯一可譯碼。理解

此式表明，只有當(dāng)長的碼符號序列數(shù)大于或等于N次擴展信源的符號數(shù)時，才可能存在等長非奇異碼。理解例：

英文電報有32個符號(26個字母加上6個字符),請問對信源符號進行二進制編碼，要想有唯一可譯碼，碼長至少為多少？解：

r=2,q=32,N=1，要想有唯一可譯碼，則理解例：對英文電報得32個符號進行二元編碼，根據(jù)上述關(guān)系：P60頁知道英文的極限熵是1.4bit,遠小于5bit，也就是說，5個二元碼符號只攜帶1.4bit的信息量，實際上，5個二元符號最多可以攜帶5bit信息量?？梢宰龅阶屍骄a長縮短，提高信息傳輸率理解

舉例說明為什么每個信源符號平均所需的碼長可以減少：

設(shè)信源而其依賴關(guān)系為：理解而其依賴關(guān)系為：傳遞矩陣?yán)斫馊舨豢紤]符號間的依賴關(guān)系，可得碼長l＝2若考慮符號間的依賴關(guān)系，則對此信源作二次擴展

可見，由于符號間依賴關(guān)系的存在，擴展后許多符號出現(xiàn)的概率為0，此信源只有4個字符，可得碼長，平均每個信源符號所需碼符號為理解

考慮到英文字母間的相關(guān)性，對信源作N次擴展，在擴展后的信源(也就是句子）中，有些句子是有意義的，而有些句子是沒有意義的，可以只對有意義的句子編碼，而對那些沒有意義的句子不進行編碼，這樣就可以縮短每個信源符號所需的碼長。

等長信源編碼定理給出了進行等長信源編碼所需碼長的極限值。例：英文電報了解5.4等長信源編碼定理信源編碼有等長和變長兩種方法。等長編碼：碼字長度是固定的，相應(yīng)的編碼定理稱為定長信源編碼定理，是尋求最小碼字長度的編碼方法。變長編碼：碼字長度是變值，相應(yīng)的編碼定理稱為變長編碼定理。這里的碼字長度最小意味著數(shù)學(xué)期望最小。理解了解

定理中的公式改寫成不等式左邊表示長為L的碼符號序列能載荷的最大信息量，右邊代表長為N的信源序列平均攜帶的信息量。所以定長編碼定理告訴我們：只要碼字傳輸?shù)男畔⒘看笥谛旁磾y帶的信息量，總可實現(xiàn)幾乎無失真編碼。了解最佳編碼效率為：編碼效率：編碼后信源的信息傳輸率：了解當(dāng)允許錯誤概率小于δ時，信源符號序列的長度N：為自信息的方差如果為最佳編碼，則由式5.32了解例5-1：設(shè)離散無記憶信源求信源序列的長度。對S采取等長二元編碼，要求編碼效率允許錯誤概率了解5.5變長碼5.5.1唯一可譯變長碼與即時碼

優(yōu)點：變長碼往往在N不很大時就可編出效率很高而且無失真的碼。

5.5變長碼5.5.1唯一可譯變長碼與即時碼

變長碼的要求：變長碼必須是唯一可譯碼，才能實現(xiàn)無失真編碼。變長碼不但碼本身必須是非奇異的，而且其任意有限長N次擴展碼也都必須是非奇異的。所以唯一可譯變長碼的任意有限長N次擴展碼都是非奇異的。了解信源符號ai符號出現(xiàn)概率p(ai)碼1碼2碼3碼4a11/20011a21/411101001a31/80000100001a41/8110110000001

觀察表中的各個碼。表5.4掌握碼2二次擴展掌握掌握掌握5.5.2即時碼的樹圖構(gòu)造法即時碼的一種簡單構(gòu)造方法是樹圖法。對于給定碼字的全體集合C，可用碼樹來描述它。所謂樹，既有根、枝，又有節(jié)點。圖中最上端A點為根，從根出發(fā)向下伸出樹枝，樹枝的數(shù)目等于碼符號的總數(shù)r。樹枝的盡頭為節(jié)點，從節(jié)點出發(fā)再伸出樹枝，每次每個節(jié)點伸出r枝，依次下去構(gòu)成一棵樹。了解在下圖中，當(dāng)某一個節(jié)點被安排為碼字后，就不再繼續(xù)伸枝，此節(jié)點稱為終端節(jié)點(用粗黑點表示)。其他節(jié)點稱為中間節(jié)點，不安排為碼字(用空心圈表示)，給每個節(jié)點所伸出的樹枝分別從左向右標(biāo)上碼符號0，1，…，r。了解任一即時碼都可用樹圖法來表示。當(dāng)碼字長度給定時，即時碼不是唯一的。在每個節(jié)點上都有r個分枝的樹稱為整樹（滿樹），否則稱為非整樹（非滿樹）。了解了解5.5.3克拉夫特（Kraft)不等式掌握

例：設(shè)二進制碼樹中X={，，，}，對應(yīng)的，，，，由上述定理，可得因此不存在滿足這種碼長的唯一可譯碼。掌握a1=1

01

01

01a2=01a3=001a4=000{1，01，001，001}惟一可譯碼；

{1，01，010，000}

不是惟一可譯碼；均滿足克勞夫特不等式掌握

注意：不滿足克拉夫特不等式的碼，一定不是唯一可譯碼。碼長滿足克拉夫特不等式的碼，也不一定是唯一可譯碼?？死蛱夭坏仁街皇钦f明唯一可譯碼是否存在，并不能作為一種碼制是否是唯一可譯碼的判斷依據(jù)。了解5.5.4唯一可譯變長碼的判斷法

有限長的碼符號序列能譯成兩種不同的碼字序列，此碼一定不是唯一可譯變長碼。如下圖：

唯一可譯碼的判斷方法將碼C中所有可能的尾隨后綴組成一個集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。

掌握

集合F的構(gòu)成方法：首先，觀察碼C中最短的碼字是否是其它碼字的前綴，若是，將其所有可能的尾隨后綴排列出。這些尾隨后綴又有可能是某些碼字的前綴或者最短碼字是這些尾隨后綴的前綴，再將這些尾隨后綴產(chǎn)生的新的尾隨后綴列出.C={0，10，1100，1110，1011，1101}掌握然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產(chǎn)生的尾隨后綴列出，依此下去，直到?jīng)]有一個尾隨后綴是碼字的前綴為止。

這樣獲得了由最短的碼字引起的所有尾隨后綴，列出上述步驟將所有碼字可能產(chǎn)生的尾隨后綴。由此得到由碼C的所有可能的尾隨后綴的集合F。C={0，10，1100，1110，1011，1101}

例5.2：設(shè)碼C={0，10，1100，1110，1011，1101}，根據(jù)上述測試方法，判斷是否是唯一可譯碼。

解：1.先看最短的碼字：“0”，它不是其他碼字前綴，所以沒有尾隨后綴。

2.再觀察碼字“10”，它是碼字“1011”的前綴，因此有尾隨后綴：掌握

所以，集合F={11，00，10，01}，其中“10”為碼字，故碼C不是唯一可譯碼。C={0，10，1100，1110，1011，1101}掌握掌握練習(xí)：設(shè)消息集合中共有7個消息，分別為被編碼成對應(yīng)的碼字，判斷是否是唯一可譯碼。掌握S0S1S2S3S4S5S6S7S8adebdebaddeb0cbbcdebcdeadabbbaddebbbcde結(jié)論：當(dāng)N>7時，Sn為空集，而在S5中包含S0中的碼字，故而S0不是唯一可譯碼。例5-5：設(shè)消息集合中共有7個消息，分別為被編碼成對應(yīng)的碼字，判斷是否是唯一可譯碼。5.6變長信源編碼定理

對同一信源編成即時碼有許多種。究竟哪一種最好呢？從高效率傳輸信息的觀點來考慮，選擇由短的碼符號組成的碼字，即用碼長作為選擇準(zhǔn)則。如概率大的符號用短碼，概率小的用較長的碼，使得編碼后平均碼長降低，從而提高編碼效率。

因此準(zhǔn)則：碼的平均長度。

理解

設(shè)信源為編碼后的碼字為

對應(yīng)的碼長分布為