第5章-無(wú)失真信源編碼定理 - 2005-9

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

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

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

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

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

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

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

無(wú)失真編碼

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

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

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

了解

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

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

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

(1)

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

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

(3)

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

（5）奇異碼若一組碼中有相同的碼字，則為奇異碼。則稱(chēng)碼C為奇異碼。理解概率信源符號(hào)

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

（6）同價(jià)碼若碼符號(hào)集X：{}中每個(gè)碼符號(hào)所占的傳輸時(shí)間都相同，則所得的碼為同價(jià)碼。我們一般討論同價(jià)碼，對(duì)同價(jià)碼來(lái)說(shuō)等長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間相同，而變長(zhǎng)碼中每個(gè)碼字的傳輸時(shí)間就不一定相同。

如：電報(bào)中常用的莫爾斯碼是非同價(jià)碼，其碼符號(hào)點(diǎn)（.）和劃（-）所占的傳輸時(shí)間不相同。理解

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

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

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

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

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

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

碼1是奇異碼，碼2是非奇異碼。碼2不是唯一可譯碼，碼3是。又如，碼字{0，10，11}是一種唯一可譯碼。因?yàn)槿我庖淮邢揲L(zhǎng)碼序列，例如100

111

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

即時(shí)碼要求任何一個(gè)碼字都不是其他碼字的前綴部分，所以也叫做異前綴碼/非延長(zhǎng)碼。如上表中的碼4。如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，必須結(jié)合后續(xù)的碼元序列才能進(jìn)行譯碼，稱(chēng)為非即時(shí)碼。如碼3?？梢?jiàn)，唯一可譯碼不一定是即時(shí)碼，因?yàn)榉羌磿r(shí)碼(延長(zhǎng)碼)也具有唯一可譯性。理解了解5.2等長(zhǎng)碼

一般說(shuō)來(lái)，若要實(shí)現(xiàn)無(wú)失真的編碼，這不但要求信源符號(hào)與碼字是一一對(duì)應(yīng)的，而且要求所編的碼必須是唯一可譯碼。否則，所編的碼不具有唯一可譯碼性，就會(huì)引起譯碼帶來(lái)的錯(cuò)誤與失真。

對(duì)于等長(zhǎng)碼來(lái)說(shuō)，若等長(zhǎng)碼是非奇異碼，則它的任意有限長(zhǎng)N次擴(kuò)展碼一定也是非奇異碼。因此等長(zhǎng)非奇異碼一定是唯一可譯碼。理解

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

英文電報(bào)有32個(gè)符號(hào)(26個(gè)字母加上6個(gè)字符),請(qǐng)問(wèn)對(duì)信源符號(hào)進(jìn)行二進(jìn)制編碼，要想有唯一可譯碼，碼長(zhǎng)至少為多少？解：

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

舉例說(shuō)明為什么每個(gè)信源符號(hào)平均所需的碼長(zhǎng)可以減少：

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

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

考慮到英文字母間的相關(guān)性，對(duì)信源作N次擴(kuò)展，在擴(kuò)展后的信源(也就是句子）中，有些句子是有意義的，而有些句子是沒(méi)有意義的，可以只對(duì)有意義的句子編碼，而對(duì)那些沒(méi)有意義的句子不進(jìn)行編碼，這樣就可以縮短每個(gè)信源符號(hào)所需的碼長(zhǎng)。

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

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

優(yōu)點(diǎn)：變長(zhǎng)碼往往在N不很大時(shí)就可編出效率很高而且無(wú)失真的碼。

5.5變長(zhǎng)碼5.5.1唯一可譯變長(zhǎng)碼與即時(shí)碼

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

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

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

01

01

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

{1，01，010，000}

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

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

有限長(zhǎng)的碼符號(hào)序列能譯成兩種不同的碼字序列，此碼一定不是唯一可譯變長(zhǎng)碼。如下圖：

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

掌握

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

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

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

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

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

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

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

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

理解

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

對(duì)應(yīng)的碼長(zhǎng)分布為