信息論與編碼(第三版)-第4章-離散信源編碼理論-0525

第4章離散信源編碼理論目錄4.1信源編碼的基本概念4.2漸近等同分割性4.3信源無失真編碼

4.3.1等長碼

4.3.2變長碼4.4信息率失真函數(shù)及性質(zhì)

4.4.1失真測(cè)度

4.4.2信息率失真函數(shù)的定義

4.4.3信息率失真函數(shù)的性質(zhì)4.5信息率失真函數(shù)的計(jì)算

4.6信息率失真函數(shù)的迭代算法

4.7香農(nóng)第三定理通信本質(zhì)信源信宿信息信源輸出的符號(hào)經(jīng)過信道傳送到信宿，在信宿精確或者近似重現(xiàn)信源發(fā)送的信息解決兩個(gè)問題：(1)信源的輸出如何描述，即如何計(jì)算信源產(chǎn)生的信息量(2)如何表示信源的輸出，即信源編碼問題信源輸出的符號(hào)經(jīng)過信道傳送到信宿，在信宿精確或者近似重現(xiàn)信源發(fā)送的信息要求精確地重現(xiàn)信源的輸出，信源產(chǎn)生的信息全部無損傳送到信宿，對(duì)信源進(jìn)行無失真編碼不要求在信宿精確重現(xiàn)信源的輸出，允許信息傳輸過程中出現(xiàn)一定失真，這就是限失真編碼問題。回顧通信系統(tǒng)的信道容量是有限的，根據(jù)第3章中信源與信道匹配理論，為了有效傳輸信息，信道的輸入分布應(yīng)當(dāng)盡可能接近信道要求的最佳分布。實(shí)際信道很多都是對(duì)稱信道，最佳分布為等概率分布，這就要求對(duì)信源進(jìn)行編碼，除去信源輸出符號(hào)之間的相關(guān)性，從而實(shí)現(xiàn)信道輸入與信道的匹配。4.1信源編碼的基本概念

是對(duì)信源輸出符號(hào)進(jìn)行描述，將原始符號(hào)按照一定的規(guī)則進(jìn)行變換，以滿足信息傳輸?shù)囊?。信源編碼將信道編譯碼看作信道的一部分，從而突出信源編碼，此時(shí)的信道稱為編碼信道。編碼信道是一種廣義信道。不考慮信道編碼、譯碼過程中是否會(huì)引入失真或者錯(cuò)誤。按照一定的變換在研究信源編碼時(shí)，一般認(rèn)為信道是理想的，即不考慮編碼信道的干擾或者噪聲對(duì)信源符號(hào)重建的影響，認(rèn)為信道編碼具有足夠好的檢錯(cuò)和糾錯(cuò)能力，信道譯碼器能夠準(zhǔn)確重建信源編碼器輸出的消息在有些情況下，信源編碼也需要考慮編碼方法的抗誤碼能力，并且將抗誤碼作為衡量信源編碼的一項(xiàng)指標(biāo)假設(shè)信源序列符號(hào)長度為N，等待編碼的符號(hào)序列為這樣產(chǎn)生的碼稱為分組碼或者塊碼

例4.1

表4.1為信源編碼所使用的碼表，信源輸出序列的長度為N=1，信源共有4個(gè)符號(hào)，對(duì)應(yīng)的概率空間為輸出序列稱為碼字碼字由碼表產(chǎn)生。碼字取值于一個(gè)碼字集合，稱為碼集碼集碼字由若干個(gè)符號(hào)構(gòu)成，這些符號(hào)構(gòu)成集合，稱為碼符號(hào)集合碼符號(hào)集合碼符號(hào)集合元素?cái)?shù)量為d，則稱為d元碼碼字Ci的符號(hào)數(shù)量稱為碼字長度，記作Li對(duì)于碼1

信源編碼器輸出共有4個(gè)碼字，分別為00、01、10和11，碼字的長度都為2。二元碼碼2的碼字同樣是由二進(jìn)制碼符號(hào)組成，與碼1不同的是，并非所有的碼字都具有相同的碼字長度，所以稱這種碼為變長碼。1.非奇異碼一個(gè)碼是非奇異的，如果信源編碼器輸入的每個(gè)元素映射為不同的碼字，即非奇異是輸入序列的每個(gè)取值都得以明確描述的充分條件。例如，采用表4.1中碼2進(jìn)行編碼，由于編碼器輸入的每個(gè)元素映射為不同的碼字，所以為非奇異碼。2.奇異碼一個(gè)碼是奇異的，如果存在信源編碼器的不同輸入序列的元素映射為相同的碼字，即3.唯一可譯碼任意有限長的碼符號(hào)序列，只能被唯一地譯碼為所對(duì)應(yīng)的信源符號(hào)序列，這樣的碼稱為唯一可譯碼，即編碼的碼字只有一種可能信源序列與之相對(duì)應(yīng)，這就要求碼是非奇異的。例如,對(duì)表4.1給定的四個(gè)信源符號(hào)進(jìn)行不等長編碼這樣的碼就是非唯一可譯碼的，比如給定碼序列001，就存在兩種解釋：0，01和001，相應(yīng)的譯碼就有兩種：a1a2或者a3，因此這種編碼不是唯一可譯碼的。，，

4.即時(shí)碼一個(gè)碼稱為即時(shí)碼，如果不需要考慮后續(xù)的碼符號(hào)，可以直接根據(jù)當(dāng)前的碼符號(hào)序列正確譯出相應(yīng)的碼字。即時(shí)碼的充要條件是沒有一個(gè)碼字是其它碼字的前綴，所以即時(shí)碼是唯一可譯碼；反之，唯一可譯碼不一定是即時(shí)碼，有時(shí)可以通過搜遍整個(gè)碼符號(hào)序列自后至前進(jìn)行譯碼。例如，使用表4.1中的碼2對(duì)信源進(jìn)行編碼，編碼產(chǎn)生的比特串0110111100110，譯碼器譯碼時(shí)不需要考慮后續(xù)碼符號(hào)，直接解碼為，所以碼2為即時(shí)碼

5.樹碼通常情況下可用碼樹來表示各個(gè)碼字的構(gòu)成，如果碼序列符號(hào)為進(jìn)制的，可以使用個(gè)符號(hào)的碼樹來構(gòu)造碼字。每個(gè)碼樹有一個(gè)樹根，樹根有d個(gè)樹枝，樹枝的盡頭稱為節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)生出的樹枝的數(shù)量等于碼符號(hào)數(shù)量d，形成d進(jìn)制的碼樹。當(dāng)某個(gè)節(jié)點(diǎn)被安排為一個(gè)碼字后，不再繼續(xù)生出樹枝，該節(jié)點(diǎn)稱為終端節(jié)點(diǎn)。每個(gè)樹枝分別標(biāo)上碼符號(hào)，終端節(jié)點(diǎn)對(duì)應(yīng)的碼字就是從根節(jié)點(diǎn)出發(fā)到終端節(jié)點(diǎn)經(jīng)過的路徑所對(duì)應(yīng)的碼符號(hào)按順序排列而成。樹碼一定是即時(shí)碼，反過來，任何即時(shí)碼都可以用樹碼來表示。利用樹碼可以推導(dǎo)出唯一可譯碼的充分必要條件。定理4.1

采用d進(jìn)制符號(hào)集進(jìn)行信源編碼，產(chǎn)生的碼字Ci所對(duì)應(yīng)的長度為Li，則即時(shí)碼存在的充分必要條件為該不等式就是克勞夫特不等式(KraftInequality)4.2漸近等同分割性。

典型序列漸近等同分割性中的概念等長編碼的基礎(chǔ)對(duì)于獨(dú)立同一分布(i.i.d)的隨機(jī)變量X，和充分大的N大數(shù)定律的內(nèi)容

通俗說法算術(shù)平均以概率逼近統(tǒng)計(jì)平均independentidenticallydistributed逼近其數(shù)學(xué)期望EX漸近等同分割性X1,X2,…,XN服從獨(dú)立同一分布逼近熵H觀察序列的概率逼近自信息量的算術(shù)平均逼近熵公式表示例4.2

隨機(jī)變量X的概率空間為獨(dú)立序列分類將所有序列分為兩個(gè)集合典型集合：樣點(diǎn)值自信息量平均逼近熵非典型集合：包含剩余序列。主要關(guān)心典型序列，典型序列的任何特性都是以大概率成立的，而且決定了樣點(diǎn)值的主要特性如果隨機(jī)變量都服從獨(dú)立同一分布那么序列的概率為如序列(1,0,1,1,0,1)的概率為N足夠大時(shí)，序列中“0”的數(shù)量以大概率逼近于Np

1．漸近等同分割性

定理4.2

如果X1,X2,…,XN服從獨(dú)立同一分布p(x)，那么以概率逼近H(X)。證明：X服從獨(dú)立同一分布p(x),那么服從獨(dú)立同一分布。根據(jù)弱大數(shù)定律以概率定義4.1關(guān)于p(x)的典型集合是序列的集合，具有下列性質(zhì)含義對(duì)于給定的基本信源和參數(shù)ε，對(duì)于一個(gè)具體排列(樣本)，滿足上述關(guān)系，則屬于典型序列的一個(gè)元素；所有這類元素構(gòu)成典型集合例如一個(gè)二元信源，p(0)=0.75,p(1)=0.25,則H(x)=0.811，取ε=0.111，N=100100個(gè)元素都是0的序列，對(duì)應(yīng)的聯(lián)合概率為0.75100=3.21×10-13,那么該序列就不是典型序列80個(gè)元素都是0的序列，對(duì)應(yīng)的聯(lián)合概率為0.7580×0.2520=9.2×10-23,那么該序列就是典型序列定理4.3

(1)如果，那么(2)當(dāng)N充分大時(shí)，(3)其中|A|表示集合A的元素個(gè)數(shù)(4)當(dāng)N充分大時(shí)，

所以典型序列的概率幾乎為1，典型序列的所有元素幾乎是等概率的，元素個(gè)數(shù)幾乎是

性質(zhì)(1)可以根據(jù)定義直接證明證明兩邊同時(shí)取對(duì)數(shù)性質(zhì)(2)可以由定理4.2加以證明令典型序列集合以概率逼近1，根據(jù)大數(shù)定理得到性質(zhì)2性質(zhì)(3)

漸近等同分割含義典型序列定義相同數(shù)據(jù)相加性質(zhì)(4)

對(duì)于充分大的N

得到定理4.4設(shè)離散無記憶信源X的特定序列對(duì)于任意給定的存在一個(gè)整數(shù)N0時(shí)典型序列的平均自信息量以概率逼近熵2漸近等同分割性與編碼數(shù)據(jù)壓縮服從獨(dú)立同一分布的隨機(jī)變量X1,X2,…,XN構(gòu)成隨機(jī)變量序列XN為了實(shí)現(xiàn)數(shù)據(jù)壓縮將序列所有可能取值分類兩類典型集合及其補(bǔ)集每個(gè)集合都按照某種順序?qū)π蛄羞M(jìn)行排序序列排序的序號(hào)來描述每個(gè)序列；實(shí)現(xiàn)數(shù)據(jù)壓縮方法1典型序列數(shù)量不大于2N(H(X)+ε)編碼：0+序列編號(hào)碼長非典型序列編碼：1+序列編號(hào)碼長：

前綴碼這是一種無失真編碼方法上述的編碼方案具有下列性質(zhì)：碼與序列之間是一一對(duì)應(yīng)的，第一位是前綴碼，表示碼的長度或者類型。非典型序列采用的是枚舉法，盡管沒有考慮非典型序列的長度一定小于信源符號(hào)的個(gè)數(shù)，但是這種描述方法也是十分有效的，因?yàn)榉堑湫托蛄袑?duì)應(yīng)的概率較小，對(duì)平均長度的貢獻(xiàn)較小。典型序列的最小描述長度約為NH。方法2非典型序列不參與編碼典型序列排序的序號(hào)來描述每個(gè)序列碼長一旦非典型序列出現(xiàn)，出現(xiàn)譯碼錯(cuò)誤由于非典型序列對(duì)應(yīng)概率小，幾乎無失真編碼方法3非典型序列使用典型序列代替一旦非典型序列出現(xiàn)，同樣出現(xiàn)譯碼錯(cuò)誤其他與方法2一樣等長編碼理論是建立在后兩種編碼方法基礎(chǔ)上4.3信源無失真編碼

無失真信源編碼就是要求信源符號(hào)與碼字之間形成一一映射關(guān)系，并且要求編碼輸出的碼字序列對(duì)應(yīng)的反變換是唯一的，即是唯一可解碼的，否則會(huì)造成譯碼錯(cuò)誤或者失真。根據(jù)信源編碼輸出碼長的特點(diǎn)，可以將信源編碼分為等長編碼和變長編碼。如果對(duì)于信源不同的輸出符號(hào)，碼字的長度總是相同的，這樣的編碼稱為等長編碼，即反之，如果編碼產(chǎn)生的碼長不完全相同，稱這樣的碼為變長碼。定理4.5設(shè)離散無記憶信源X的符號(hào)數(shù)量為r，信源熵為H(X)，對(duì)應(yīng)N次擴(kuò)展信源XN為現(xiàn)在使用碼符號(hào)個(gè)數(shù)為d的碼符號(hào)集合，對(duì)次擴(kuò)展信源進(jìn)行等長編碼，碼長為l，對(duì)于任意ε>0，只要滿足則當(dāng)N足夠大時(shí)，錯(cuò)誤譯碼的概率為任意小，即可實(shí)現(xiàn)幾乎無失真編碼。反之，如果則當(dāng)充分大時(shí)，譯碼錯(cuò)誤的概率趨向1，不可能實(shí)現(xiàn)無失真編碼。

證明：根據(jù)漸近等分割定理可知，在離散無記憶信源輸出中，典型序列對(duì)應(yīng)的概率應(yīng)當(dāng)滿足條件設(shè)典型序列集合G中序列數(shù)量為NG，于是有當(dāng)N足夠大時(shí)，典型序列的數(shù)量所占比例很小，這樣就可以只對(duì)典型序列進(jìn)行一一對(duì)應(yīng)的等長編碼，那么碼字的總數(shù)應(yīng)當(dāng)不小于NG，即典型序列集合中所有的序列都有不同的碼字與之相對(duì)應(yīng)，而非典型序列沒有相應(yīng)的碼字。盡管非典型序列出現(xiàn)的概率很小，但是仍然有可能出現(xiàn)，一旦非典型序列出現(xiàn)，就會(huì)造成譯碼錯(cuò)誤，相應(yīng)的錯(cuò)誤概率就是非典型序列集合的概率，即如果滿足當(dāng)N趨向無窮大時(shí)，譯碼錯(cuò)誤的概率PE趨向于0反之，如果等長碼的碼長滿足該定理可以擴(kuò)展到平穩(wěn)離散有記憶信源，但是要求有記憶信源的極限熵存在，并將上述定理中的替換為極限熵。上述定理的意義在于：(1)對(duì)于給定的離散無記憶信源X和碼符號(hào)集合D，如果對(duì)的次擴(kuò)展信源進(jìn)行無失真等長編碼，那么當(dāng)碼長滿足下列條件時(shí)，一定存在一種編碼方案，使得正確譯碼的錯(cuò)誤概率趨向0，即能夠?qū)崿F(xiàn)無失真編碼；反之，如果上述不等式不成立，不可能存在一種編碼方案，能使得正確譯碼的概率趨向0，也就是說，不可能進(jìn)行無失真編碼。(2)對(duì)于給定的信源離散無記憶X，信源的熵是一定的，當(dāng)碼符號(hào)數(shù)量選定時(shí)，可以增加信源序列的長度N，使得無失真編碼產(chǎn)生的每個(gè)符號(hào)平均長度盡可能小，但是無論怎樣增加序列長度N，信源每個(gè)符號(hào)的平均碼長不可能小于H(X)/logd，即平均碼長的極限為H(X)/logd。(3)當(dāng)序列長度N一定，譯碼錯(cuò)誤概率為其中定義4.2設(shè)離散無記憶信源X的熵為H(x)，對(duì)N次擴(kuò)展信源的符號(hào)序列XN進(jìn)行等長無失真編碼，碼長為L，定義自信息量方差為編碼信息率。每個(gè)符號(hào)的平均碼長從定理4.5可知，如果編碼信息率R’<H(x),總是存在一種編碼方法，能夠?qū)崿F(xiàn)無失真編碼；反之，則不能夠?qū)崿F(xiàn)無失真編碼。定義4.3定義編碼信息率與信源熵之比為編碼效率η已知自信息量方差和編碼效率情況下，信源序列長度N與最佳編碼效率η和允許錯(cuò)誤概率σ之間的關(guān)系允許錯(cuò)誤概率越小，編碼效率越高，信源序列的長度就越大例4.3設(shè)某離散無記憶信源的熵為H(x)=0.6比特/符號(hào)，采用二元碼編碼，分別使用長度為10和100的序列進(jìn)行等長無失真編碼，分別計(jì)算最短平均碼長和編碼效率。解：當(dāng)N=10時(shí)比特/10符號(hào)考慮到碼長必須為整數(shù)，所以最短碼長為最短平均碼長為比特/符號(hào)編碼效率為當(dāng)N=100時(shí)比特/100符號(hào)平均碼長為比特/符號(hào)編碼效率為結(jié)論：隨著N的增加，平均碼長減小，編碼效率增加不過序列長度的增加，意味著編碼復(fù)雜度相應(yīng)增加，編碼付出的代價(jià)會(huì)越大，可見通過無限制增加碼長提高編碼效率并不總是一種有效方法。例4.4設(shè)離散無記憶信源為如果要求編碼效率為92%，允許錯(cuò)誤概率為求編碼序列的長度

解：信源的熵為比特/符號(hào)自信息量方差為如果采用二進(jìn)制碼，則序列長度應(yīng)當(dāng)滿足從指標(biāo)來看，編碼效率和允許錯(cuò)誤概率的要求并不高，但是序列的長度卻很大。這是因?yàn)榈乳L碼的編碼沒有充分利用信源統(tǒng)計(jì)特性的結(jié)果。等長編碼使用概率方式：根據(jù)概率大小，將序列劃分為典型序列和非典型序列；所有典型序列的碼長相等，沒有充分利用每個(gè)序列的概率指導(dǎo)編碼，所以編碼效率難以提高等長編碼的平均碼長受到熵的約束；增加序列長度有利于提高編碼效率。歸納序列長度增加會(huì)提高編碼復(fù)雜度。2.變長碼

等長碼編碼定理表明：增加序列長度可以提高信源編碼效率。但序列長度的增加，會(huì)增加系統(tǒng)編碼的復(fù)雜度。等長編碼之所以編碼效率難以提高，是因?yàn)榈乳L碼沒有充分利用信源及擴(kuò)展信源的統(tǒng)計(jì)特性進(jìn)行編碼，而是無論概率大小，給每個(gè)信源符號(hào)分配等長碼字，從而無法降低平均碼長。變長碼的基本思想是：對(duì)于給定的信源，當(dāng)信源符號(hào)對(duì)應(yīng)的先驗(yàn)概率不是等概率分布時(shí)，為了提高編碼效率，給概率大的符號(hào)分配較短碼字，概率小的符號(hào)分配長碼字，從而使得平均碼長盡可能短。

往往在序列長度不是很大時(shí)，變長碼即可實(shí)現(xiàn)很高效率的無失真信源編碼。麥克米倫不等式與格拉夫特不等式具有相同的形式，該不等式首先由格拉夫特在研究即使碼存在的條件時(shí)提出，后來麥克米倫證明唯一可解碼的條件也滿足該不等式。當(dāng)信源給定時(shí)，使用相同的碼符號(hào)對(duì)信源進(jìn)行變長編碼，得到的即時(shí)碼或者唯一可解碼也可以有許多種?，F(xiàn)在的問題是那種碼最好？從提高有效性角度考慮，應(yīng)當(dāng)選擇碼長作為衡量編碼方法好壞的準(zhǔn)則。定理4.6設(shè)信源符號(hào)數(shù)為r，對(duì)信源進(jìn)行無失真編碼，碼符號(hào)的個(gè)數(shù)為d，碼字的長度分別為則唯一可譯碼存在的充分必要條件是該不等式就是麥克米倫不等式(McmilanInequality)定義4.4設(shè)信源的概率空間為碼符號(hào)個(gè)數(shù)為d，編碼產(chǎn)生的碼字對(duì)應(yīng)的長度分別為則平均長度為含義：信源符號(hào)編碼所需要的平均碼符號(hào)個(gè)數(shù)定義4.5給定信源X的熵為H(X),編碼得到的每個(gè)信源符號(hào)平均長度為,那么定義平均每個(gè)碼元攜帶的信息量為編碼后信道的信息傳輸率物理含義：平均每個(gè)碼元所載荷信息量定理4.7設(shè)離散無記憶信源的熵為H(X)，編碼使用的符號(hào)個(gè)數(shù)為d，一定存在一種無失真編碼方法，構(gòu)成唯一可譯碼，使得平均碼長滿足首先證明下界，根據(jù)熵和平均碼長的定義

根據(jù)詹森不等式香農(nóng)第一定理的基本形式先求數(shù)學(xué)期望，后求函數(shù)先求函數(shù)，后求數(shù)學(xué)期望唯一可譯碼存在的條件就是滿足即克拉夫特不等式，即令，可得下面證明上界對(duì)于給定的概率分布p(ai)，一定存在一個(gè)正整數(shù)mi，使得下列不等式成立選擇該信源符號(hào)對(duì)應(yīng)碼字的長度li＝mi。兩邊同乘以p(ai)，并且對(duì)求i和得根據(jù)熵、平均碼長的定義消息符號(hào)自信洗量上取整該定理的意義：無失真不等長編碼的平均碼長不能小于極限Hd(X)，否則唯一可解碼不存在；同時(shí)給出上界1+Hd(X)，說明小于上界的唯一可解碼是存在的；最佳碼的平均碼長應(yīng)當(dāng)滿足上述不等式;當(dāng)然，平均碼長超出上界的唯一可解碼是存在的。定理4.8（香農(nóng)第一定理）設(shè)離散無記憶信源的概率空間為信源的熵為H(X)，其N次擴(kuò)展信源為擴(kuò)展信源的熵為H(XN)。使用d元碼對(duì)次N擴(kuò)展信源進(jìn)行編碼，可以找到一種編碼方法，構(gòu)成唯一可譯碼，使得信源編碼得到的每個(gè)信源符號(hào)的平均碼長滿足證明：由于信源X為無記憶信源，其次擴(kuò)展信源XN也是無記憶的，而且有直接應(yīng)用定理4.7的結(jié)論將擴(kuò)展信源的熵代入上式得可以將該結(jié)論加以推廣，對(duì)于平穩(wěn)、遍歷的有記憶信源香農(nóng)第一定理的意義：使用d元碼對(duì)信源進(jìn)行無失真編碼，信源編碼每個(gè)符號(hào)平均碼長的極限就是信源的熵；如果編碼產(chǎn)生的平均碼長大于信源的熵，唯一可解碼是存在的;反之，唯一可解碼是不存在的，即在譯碼時(shí)一定會(huì)引入失真或者差錯(cuò)。如果要取得好的編碼效果，序列的長度應(yīng)當(dāng)更長，從而增加系統(tǒng)編碼復(fù)雜度。當(dāng)然實(shí)際編碼時(shí)，往往是通過變換方法進(jìn)行編碼，降低編碼系統(tǒng)復(fù)雜度。定義4.7設(shè)信源X進(jìn)行變長編碼得到的平均碼長為定義編碼效率為衡量各種編碼方法的優(yōu)劣指標(biāo)之一定義4.8定義變長碼的碼剩余度為例4.5設(shè)離散無記憶信源的概率空間為（1）如果采用二元碼對(duì)其進(jìn)行等長編碼，映射關(guān)系為編碼效率為該編碼方案可以使用信道形式表示，對(duì)應(yīng)條件轉(zhuǎn)移概率矩陣為其中信道的輸入為，輸出則為0,1。顯然這是一個(gè)無噪無損信道（2）現(xiàn)在對(duì)信源進(jìn)行二次擴(kuò)展，并且采用下列編碼方法進(jìn)行變長編碼擴(kuò)展信源的概率分布為，，序列的平均碼長比特/序列每個(gè)符號(hào)平均碼長為比特/符號(hào)編碼效率為編碼方案對(duì)應(yīng)條件轉(zhuǎn)移概率矩陣為（3）如果采用序列等長編碼，要求編碼效率為η=96%，而允許譯碼錯(cuò)誤概率為，根據(jù)信源統(tǒng)計(jì)特性，可以計(jì)算自信息方差編碼序列的長度應(yīng)當(dāng)滿足要取得相當(dāng)?shù)木幋a效率，在允許譯碼錯(cuò)誤概率并不是很小的情況下，定長編碼所需要的序列長度很長，這就意味著需要產(chǎn)生巨大的碼表；而采用變長編碼，只采用二次擴(kuò)展信源就可以得到相同的編碼效率，隨著序列的長度增加，變長編碼的效率越接近1。而等長編碼是將符號(hào)序列分為兩大類：典型序列和非典型序列。典型序列分配相同長度的碼字，而非典型序列被丟棄或者通過附加前綴的方法與典型序列的碼字區(qū)分開。而典型序列的概率分布并不完全相同，分配相同的碼字顯然沒有利用統(tǒng)計(jì)特性，所以等長碼不僅編碼效率難以提高，而且可能出現(xiàn)譯碼錯(cuò)誤。在香農(nóng)的等長編碼理論中，非典型序列是不編碼的，一旦非典型序列出現(xiàn)，不可能再現(xiàn)或者重建該序列，所以會(huì)存在譯碼錯(cuò)誤。4.4信息率失真函數(shù)及性質(zhì)

無論是等長編碼還是變長編碼，都可以通過增加序列的長度提高編碼效率。信源無失真編碼平均碼長是受信源熵的限制，無論采用何種編碼方案，平均碼長不可能小于信源的熵。由于編碼產(chǎn)生的信息率受到熵的限制，當(dāng)其大于信道容量時(shí)，不能夠在信道中有效傳輸信息。而在實(shí)際中，為了傳輸信息，允許出現(xiàn)一定的失真，從而降低信息傳輸率。那么在允許一定失真條件下，信源編碼輸出的信息率是否存在極限；或者說，當(dāng)信息率一定時(shí)，是否會(huì)存在最小失真，使得在有效傳輸信源的信息同時(shí)，盡可能減小編碼引入的失真。這就是將要討論的問題。4.4.1失真測(cè)度從直觀上來看，如果允許失真越大，信息傳輸率應(yīng)當(dāng)越小；反過來，如果允許失真越小，信息傳輸率越大，所以信息傳輸速率與信源編碼引入的失真是相關(guān)的，在允許失真一定的情況下，應(yīng)當(dāng)存在一種信源編碼方法使得信息傳輸率最小。失真實(shí)際是距離的一種，其定義應(yīng)當(dāng)滿足一定的條件，對(duì)于任意i，j滿足1）非負(fù)性，即，當(dāng)且僅當(dāng)?shù)忍?hào)成立2）可交換性3）三角不等式失真的測(cè)度常用的失真函數(shù)有平方誤差失真

r=s且ai=bi絕對(duì)失真：

漢明失真：

r=s且ai=bir=s且ai=bi例4.6對(duì)于離散對(duì)稱信源，信源發(fā)送符號(hào)變量為再現(xiàn)符號(hào)變量為，定義單個(gè)符號(hào)失真為它表示：當(dāng)再現(xiàn)符號(hào)與信源發(fā)送符號(hào)相同時(shí)，就不存在失真和錯(cuò)誤，所以失真度，當(dāng)再現(xiàn)符號(hào)與信源發(fā)送符號(hào)不同時(shí)，就有失真存在例4.7對(duì)于刪除信源，假設(shè)信源發(fā)送變量而再現(xiàn)符號(hào)變量為，且s=r+1定義它的單個(gè)符號(hào)失真度為無論是單個(gè)符號(hào)的失真還是序列的失真，實(shí)際都是反映了具體符號(hào)或者具體符號(hào)序列的失真，為了衡量每傳輸一個(gè)符號(hào)引入的失真大小，需要引入平均失真。定義4.11設(shè)信源的概率空間為再現(xiàn)符號(hào)集合為，單個(gè)符號(hào)的失真度為定義的數(shù)學(xué)期望為平均失真，即或者兩個(gè)矩陣對(duì)應(yīng)位置上的元素相乘平均失真是信源分布和信道轉(zhuǎn)移概率的函數(shù)，描述了信源在某試驗(yàn)信道下，平均失真的大小，描述了整體失真情況如果將信源序列中的每個(gè)序列看作是擴(kuò)展信源的一個(gè)符號(hào)，類似地可以定義符號(hào)序列的平均失真。

定義4.12

定義信源X的N維符號(hào)序列的平均失真度為平均每個(gè)信源符號(hào)的失真為如果信源與試驗(yàn)信道都是無記憶的，利用序列概率與構(gòu)成序列的各符號(hào)概率之間的關(guān)系，可以得出如果信源還是平穩(wěn)的，就可以得出，結(jié)論：對(duì)于離散無記憶平穩(wěn)信源，如果試驗(yàn)信道也是無記憶的，那么信源序列的平均失真度等于單個(gè)符號(hào)的平均失真度的倍。4.4.2信息率失真函數(shù)的定義信源編碼的目的是為了減小信息傳輸率，而與編碼引入的失真存在一定的關(guān)系。對(duì)于給定的信源和選擇的失真測(cè)度，在編碼輸出的平均碼長，即信息傳輸率一定的條件下，總是希望編碼引入的平均失真越小越好；或者說，對(duì)于給定的平均失真，希望編碼產(chǎn)生的平均碼長越小越好。信源編碼可以看作是存在一個(gè)試驗(yàn)信道，信道的輸入就是信源X，而信道的輸出就是譯碼后再現(xiàn)符號(hào)Y.對(duì)于給定的信源和選擇的失真測(cè)度，信源編碼就是尋找一種試驗(yàn)信道，在平均失真一定條件下，輸出碼率R最小。根據(jù)熵的性質(zhì)可知：在已知H(X)條件下，平均互信息I(X;Y)是信道轉(zhuǎn)移概率的U型凸函數(shù)，所以最小值是存在的。對(duì)于離散無記憶信源定義4.13對(duì)于給定信源X和失真測(cè)度，信息率失真函數(shù)定義為編碼引入平均失真給定平均失真，或者是允許失真已知條件信源先驗(yàn)分布p(x),給定失真D變化參數(shù)平均互信息量極大值極值問題試驗(yàn)信道條件轉(zhuǎn)移概率p(bj|ai)試驗(yàn)信道是不存在的，是為了分析限失真編碼理論而引入的，便于分析信息率失真函數(shù)。信息率失真函數(shù)不僅與信源符號(hào)取值、信源概率分布、失真的測(cè)度有關(guān)，而且與接收端再現(xiàn)符號(hào)也是密切相關(guān)的。

例4.8設(shè)信源概率空間為，

選擇試驗(yàn)信道的輸出為{b1=0,b2=0}，失真測(cè)度為編碼方案如下：經(jīng)過信源編碼后，信源所需要傳輸?shù)男畔⒘坑稍瓉淼?比特/符號(hào)壓縮為1比特/符號(hào)。按照給定失真測(cè)度，引入的平均失真為，改變?cè)佻F(xiàn)或者重建符號(hào)并且采用相同的測(cè)度，則平均失真為采用不同的重建符號(hào)取值，則得到的平均失真也不同對(duì)于這種給定的簡(jiǎn)單試驗(yàn)信道，平均失真可以根據(jù)失真測(cè)度計(jì)算出來；當(dāng)改變?cè)囼?yàn)信道的轉(zhuǎn)移矩陣，平均失真會(huì)發(fā)生變化，所以平均失真是信道轉(zhuǎn)移概率的函數(shù)；同樣平均互信息量也是試驗(yàn)信道轉(zhuǎn)移概率的函數(shù)。信息率失真函數(shù)就是在信源和再現(xiàn)符號(hào)取值一定情況下，對(duì)于給定平均失真測(cè)度，改變?cè)囼?yàn)信道的轉(zhuǎn)移概率，使得平均互信息量最小。在信源編碼中，平均互信息量就是信源進(jìn)行限失真壓縮后的輸出碼率，所以信息率失真函數(shù)就是在給定信源的情況下，在允許的失真內(nèi)再現(xiàn)或者重建信源消息的最小平均信息量，即信源壓縮后的最小輸出碼率。4.4.3信息率失真函數(shù)的性質(zhì)

1.R(D)的定義域

(1)Dmin和R(Dmin)D是非負(fù)的；此時(shí)一般表示形式先驗(yàn)概率一定由于d(ai,bj)是已知的,現(xiàn)在任務(wù)就是選擇試驗(yàn)信道的轉(zhuǎn)移概率p(bj|ai),對(duì)每個(gè)信源符號(hào)ai,使得下列表示式最小從失真矩陣來看，平均失真最小值就是矩陣每行元素的最小值乘以對(duì)應(yīng)符號(hào)概率，然后求累加和。允許失真最小值是否為0取決于失真函數(shù)，如果失真矩陣中每行都有一個(gè)0元素，則最小失真為0；否則，只要有一行沒有0元素，則最小失真不為0。所以0是失真函數(shù)的下界。上述的最小值問題，就是對(duì)給定ai找到一個(gè)最小的失真d(ai,bj)使得對(duì)應(yīng)的條件轉(zhuǎn)移概率為1，而對(duì)于其它失真，p(bj|ai)=0,從而使得平均失真最小對(duì)于所有d(ai,bj)最小的bj對(duì)于所有d(ai,bj)不為最小的bj例4.9

信源X的概率空間為而Y取值于{b1,b2,b3}，失真矩陣為求Dmin

解：由于失真矩陣中每行都存在0元素，所以取得最小允許失真所對(duì)應(yīng)試驗(yàn)信道概率矩陣為從信道概率矩陣可以看出，允許失真取得最小值的條件是：信源符號(hào)與再現(xiàn)符號(hào)之間滿足一一對(duì)應(yīng)的關(guān)系，顯然這是一個(gè)無噪有損信道，滿足(2)Dmax和R(Dmax)根據(jù)信息率失真函數(shù)的定義，R(D)是在給定平均失真D情況下，平均互信息量的最小值;由于I(X;Y)是非負(fù)的，其下限為0。當(dāng)R(D)=0時(shí)，對(duì)應(yīng)的平均失真取得最大值。的條件是什么？取的最小值得到由于概率p(ai)和d(ai,bj)是已知的，上述的極值問題就是找到一種概率分布p(bj),使得表示式取得最小值R(D)的定義域?yàn)?0,Dmax),而值域?yàn)?0,H(X)),且滿足如果最小失真為0，則對(duì)應(yīng)的率一定為H(X);否則，對(duì)應(yīng)率小于H(X)失真大于最大失真，則率一定為0例4.10

給定信源X的率空間為失真矩陣為求最小失真，并且給出取得最小失真的條件解：確定條件轉(zhuǎn)移概率最小失真為找每行元素最小值例4.11求例4.10給定條件的最大失真解：根據(jù)最大失真計(jì)算公式給定列，先驗(yàn)概率p(ai)乘以失真矩陣對(duì)應(yīng)列元素，然后相加將概率分布和失真代入上式，得到2．R(D)是D的下凸函數(shù)

假設(shè)有一個(gè)函數(shù)f(x),在定義域內(nèi)任意兩點(diǎn)x1<x2,可以連成一條直線，該直線的函數(shù)表達(dá)式為下凸函數(shù)直線上的任一點(diǎn)x，滿足x1<x<x2,可以表示為滿足即則該函數(shù)是下凸函數(shù)將下凸函數(shù)用于信息率失真其中為兩個(gè)任意失真證明：設(shè)有兩個(gè)試驗(yàn)信道p1(bj|ai),p2(bj|ai)對(duì)應(yīng)的信息率失真函數(shù)分別為R(D’),R(D”),有試驗(yàn)信道中的平均失真再定義一個(gè)新的試驗(yàn)信道，設(shè)其信道轉(zhuǎn)移概率為對(duì)應(yīng)的平均失真為根據(jù)信息率失真函數(shù)的定義可得由于平均互信息是信道轉(zhuǎn)移概率的下凸函數(shù)在平均失真度E[d]≤θD’+(1-θ)D”的信道集合中，這個(gè)信道并不一定是使I(X;Y)最小于是有3.在區(qū)間上是嚴(yán)格遞減的連續(xù)函數(shù)

在區(qū)間上是嚴(yán)格遞減的連續(xù)函數(shù)4.5信息率失真函數(shù)的計(jì)算1.約束條件設(shè)信源的概率空間為由于對(duì)所有的對(duì)所有的2．極值求解構(gòu)造函數(shù)考慮到以及于是得到下列方程得到個(gè)r×s方程，加上r個(gè)約束條件和約束條件為了討論問題方便起見，令共有(r*s+r+1)個(gè)方程。而未知數(shù)有r個(gè)ui,一個(gè)S和(r*s)個(gè)p(bj|ai),共有(r*s+r+1)未知參數(shù)，理論上，方程的解是可以求出來的。如果能夠解出方程的解，代入互信息量公式即可求出極小值，從而得到信息率失真函數(shù)。3．中間參數(shù)的表示根據(jù)關(guān)系式

兩邊同時(shí)乘將λi的表示式代入，得到由參量S表示的p(bj)為根據(jù)上式可以求出由參量S表示的p(bj)。如果p(bj)不等于0，則vi=1；否則，如果p(bj)=0，則vi小于等于1。

將p(bj)代入λi表示式，可以求出λi，再將λi代入即可求出4．信息率失真函數(shù)的參數(shù)表示即根據(jù)參數(shù)S計(jì)算出的p(bj|ai)必需滿足上述條件的約束,從這種意義上講,p(bj|ai)以參數(shù)S為變量，實(shí)際上就是以參數(shù)D為變量。將p(bj|ai)表示式代入上述約束條件得到平均失真D(S)為將參數(shù)S表示的p(bj|ai),p(bj)代入I(X;Y)和平均失真D中,即可得到以參數(shù)S為變量的信息率失真R(S)和平均失真D(S)。顯然這不是顯式表達(dá)式，參數(shù)S對(duì)應(yīng)的限制條件為信息率失真函數(shù)的計(jì)算：根據(jù)給定參數(shù)S取值，計(jì)算出p(bj)、λi;將其代入平均失真公式D(S)，最后求出R(S)，從而得到信息率失真函數(shù)R(D)。5．參量S的物理意義由于概率p(bj)在[0,1]之間取值，而所以參數(shù)S的取值范圍應(yīng)當(dāng)有一定的限制。且λi也是S的函數(shù)為了得到，對(duì)方程兩邊同時(shí)對(duì)S求導(dǎo)數(shù)，得到下列方程將等式兩邊同時(shí)乘以p(bj)，并且對(duì)i求和，可以得出上述方程左邊第二項(xiàng)就是平均失真D將代入該式表明：參量S就是信息率失真函數(shù)R(D)的斜率。由于R(D)在(0,Dmax)之間是嚴(yán)格單調(diào)遞減的下凸函數(shù)，所以斜率S是非正的，并且是D的單調(diào)遞增函數(shù)。根據(jù)R(D)的性質(zhì)可知，

D=0時(shí)，R(D)的斜率可能為負(fù)無窮；而當(dāng)D>Dmax時(shí)，斜率為0，所以S的取值范圍為負(fù)實(shí)數(shù)，而且信息率失真函數(shù)R(D)是參數(shù)S的連續(xù)函數(shù)。例4.12設(shè)信源的概率空間為信宿接收符號(hào)取值于{b1,b2},失真矩陣為求信息率失真函數(shù)解：（1）解下列方程（2）解下列方程，得到p(bj)即（3）將上述參數(shù)代入，求解信道轉(zhuǎn)移概率（4）用參量表示平均失真整理后可以得出將S，λi等參數(shù)代入對(duì)于某些特殊分布，信息率失真函數(shù)如下：（1）如果離散無記憶信源服從均值為0的高斯分布，即失真測(cè)度為則有（2）如果4.6信息率失真函數(shù)的迭代算法

信息率失真函數(shù)的計(jì)算顯得過于繁瑣;當(dāng)信符號(hào)數(shù)量較多時(shí)，人工計(jì)算信息率失真是相當(dāng)困難的;信息率失真函數(shù)存在迭代算法，這里只給出結(jié)論和具體迭代算法，推導(dǎo)過程不加以討論。試驗(yàn)信道的條件轉(zhuǎn)移概率可以表示為試驗(yàn)信道輸出符號(hào)的概率為從上述兩個(gè)公式來看，條件概率p*(bj|ai)與再現(xiàn)符號(hào)概率p*(bj)之間相互表示。在S一定的條件下，可以假設(shè)試驗(yàn)信道的轉(zhuǎn)移概率取值p*(bj|ai)，根據(jù)概率知識(shí)計(jì)算出概率p*(bj)；然后將得到的代入公式計(jì)算出一個(gè)新值p*(bj|ai)，這樣就構(gòu)成了一種迭代算法迭代算法具體如下：(1)首先假設(shè)絕對(duì)值足夠大的負(fù)數(shù)作為斜率S的取值，并且選擇試驗(yàn)信道的轉(zhuǎn)移概率pi(bj|ak)為等分布的，且令n=1。(2)根據(jù)公式計(jì)算出pn(bj)(3)將pn(bj)代入公式計(jì)算出pn+1(bj|ai)。對(duì)于每個(gè)斜率都得到相應(yīng)的失真和信息率，從而得到信息率失真函數(shù)R(D)曲線(4)計(jì)算平均失真和信息率(5)如果，則跳轉(zhuǎn)到(6);否則，令n=n+1，跳轉(zhuǎn)到(2)。其中ε為事先確定的精度。(6)令D(S)=Dn，R(S)=Rn；改變斜率值S，選擇初始條件概率為等概率分布，令n=1，然后跳轉(zhuǎn)到(2)，直至斜率足夠接近0為止。，

4.7香農(nóng)第三定理香農(nóng)第三定理也稱為限失真編碼定理，與無失真編碼的香農(nóng)第一定理一樣，討論碼的存在性問題，具有重要的理論意義。其中e為碼元數(shù)。定理4.9(香農(nóng)第三定理)設(shè)R(D)為離散無記憶平穩(wěn)信源的信息率失真函數(shù)，對(duì)于任意給定的