第4章 離散信源編碼理論

第4章離散信源編碼理論主講鄧家先目錄4.1信源編碼的基本概念4.2漸近等同分割性4.3信源無(wú)失真編碼

4.3.1等長(zhǎng)碼

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

4.4.1失真測(cè)度

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

4.4.3信息率失真函數(shù)的性質(zhì)結(jié)束

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

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

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

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

輸出序列也稱為碼字，是由碼表產(chǎn)生的。碼字取值于一個(gè)碼字集合，稱為碼集，記作碼表中的每個(gè)碼字是由若干個(gè)來(lái)自于同一個(gè)碼

符號(hào)集合的符號(hào)構(gòu)成，如果碼符號(hào)集合為則稱這樣構(gòu)成的碼為d元碼。碼字Ci的符號(hào)數(shù)量稱為碼字長(zhǎng)度，記作Li例4.1

表4.1為信源編碼所使用的碼表，信源輸出序列的長(zhǎng)度為N=1，信源共有4個(gè)符號(hào)，對(duì)應(yīng)的概率空間為對(duì)于碼1

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

4.即時(shí)碼一個(gè)碼稱為即時(shí)碼，如果不需要考慮后續(xù)的碼符號(hào)，可以直接根據(jù)當(dāng)前的碼符號(hào)序列正確譯出相應(yīng)的碼字。即時(shí)碼的充要條件是沒(méi)有一個(gè)碼字是其它碼字的前綴，所以即時(shí)碼是唯一可譯碼；反之，唯一可譯碼不一定是即時(shí)碼，有時(shí)可以通過(guò)搜遍整個(gè)碼符號(hào)序列自后至前進(jìn)行譯碼。5.樹碼通常情況下可用碼樹來(lái)表示各個(gè)碼字的構(gòu)成，如果碼序列符號(hào)為進(jìn)制的，可以使用個(gè)符號(hào)的碼樹來(lái)構(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)過(guò)的路徑所對(duì)應(yīng)的碼符號(hào)按順序排列而成。樹碼一定是即時(shí)碼，反過(guò)來(lái)，任何即時(shí)碼都可以用樹碼來(lái)表示。利用樹碼可以推導(dǎo)出唯一可譯碼的充分必要條件。定理4.1采用d進(jìn)制符號(hào)集進(jìn)行信源編碼，產(chǎn)生的碼字Ci所對(duì)應(yīng)的長(zhǎng)度為L(zhǎng)i，則即時(shí)碼存在的充分必要條件為該不等式就是克勞夫特不等式(KraftInequality)4.2漸近等同分割性漸近等同分割性中的概念——典型序列是在研究信源編碼時(shí)提出的，為信源編碼奠定了理論基礎(chǔ)。在信息論中，漸近等同分割性與大數(shù)定律類似，是由大數(shù)定律直接得到的。大數(shù)定律的內(nèi)容是：對(duì)于獨(dú)立同一分布(i.i.d,independentidenticallydistributed)的隨機(jī)變量X，和充分大的N逼近其數(shù)學(xué)期望EX。

漸近等同分割性的內(nèi)容是：當(dāng)X1,X2,…,XN是服從獨(dú)立同一分布的隨機(jī)變量時(shí)，逼近熵H，其中表示觀察序列的概率，所觀察序列的概率逼近這樣就可以將所有序列分為兩個(gè)集合：一種是典型集合，其樣點(diǎn)值熵逼近真正熵；另一種是非典型集合，它包含了剩余序列。我們主要關(guān)心典型序列，典型序列的任何特性都是以大概率成立的，而且決定了樣點(diǎn)值的主要特性。例4.2隨機(jī)變量X的概率空間為1．漸近等同分割性

定理4.2

如果X1,X2,…,XN服從獨(dú)立同一分布p(x)，那么以概率逼近H(X)。證明：X服從獨(dú)立同一分布p(x),那么服從獨(dú)立同一分布。根據(jù)弱大數(shù)定律以概率定理4.3

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

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

2漸近等同分割性與編碼令X1,X2,…,XN是服從獨(dú)立同一分布的隨機(jī)變量，概率密度函數(shù)為p(x)，對(duì)于這樣的隨機(jī)變量序列XN，希望以更短長(zhǎng)度加以描述，實(shí)現(xiàn)數(shù)據(jù)壓縮。首先將的序列分為兩個(gè)集合，典型集合及其補(bǔ)集。每個(gè)集合都按照某種順序?qū)?shù)據(jù)進(jìn)行排序，這樣就可以使用序列排序的序號(hào)來(lái)描述每個(gè)序列。根據(jù)典型序列的性質(zhì)可知，典型序列中所有序列的數(shù)量不大于2N(H(X)+ε)，所以使用不多于比特就可以對(duì)序列進(jìn)行編號(hào)，對(duì)于典型序列可以在前面加上前綴0，這樣就可以使用長(zhǎng)度為比特的序號(hào)描述所有的序列。同理，可以對(duì)非典型序列（典型序列的補(bǔ)集）中的每個(gè)序列進(jìn)行變換，序號(hào)長(zhǎng)度不超過(guò)比特，其中表示信源符號(hào)個(gè)數(shù)，為了與典型序列加以區(qū)別，在非典型序列的序號(hào)前面加上前綴1。這樣序列集合中所有的序列都有唯一的序號(hào)與之對(duì)應(yīng)。上述的編碼方案具有下列性質(zhì)：碼與序列之間是一一對(duì)應(yīng)的，第一位是前綴碼，表示碼的長(zhǎng)度或者類型。非典型序列采用的是枚舉法，盡管沒(méi)有考慮非典型序列的長(zhǎng)度一定小于信源符號(hào)的個(gè)數(shù)，但是這種描述方法也是十分有效的，因?yàn)榉堑湫托蛄袑?duì)應(yīng)的概率較小，對(duì)平均長(zhǎng)度的貢獻(xiàn)較小。典型序列的最小描述長(zhǎng)度約為NH。4.3信源無(wú)失真編碼

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

證明：根據(jù)漸近等分割定理可知，在離散無(wú)記憶信源輸出中，典型序列對(duì)應(yīng)的概率應(yīng)當(dāng)滿足條件設(shè)典型序列集合G中序列數(shù)量為NG，于是有當(dāng)N足夠大時(shí)，典型序列的數(shù)量所占比例很小，這樣就可以只對(duì)典型序列進(jìn)行一一對(duì)應(yīng)的等長(zhǎng)編碼，那么碼字的總數(shù)應(yīng)當(dāng)不小于NG，即典型序列集合中所有的序列都有不同的碼字與之相對(duì)應(yīng)，而非典型序列沒(méi)有相應(yīng)的碼字。盡管非典型序列出現(xiàn)的概率很小，但是仍然有可能出現(xiàn)，一旦非典型序列出現(xiàn)，就會(huì)造成譯碼錯(cuò)誤，相應(yīng)的錯(cuò)誤概率就是非典型序列集合的概率，即如果滿足當(dāng)N趨向無(wú)窮大時(shí)，譯碼錯(cuò)誤的概率PE趨向于0反之，如果等長(zhǎng)碼的碼長(zhǎng)滿足該定理可以擴(kuò)展到平穩(wěn)離散有記憶信源，但是要求有記憶信源的極限熵存在，并將上述定理中的替換為極限熵。上述定理的意義在于：(1)對(duì)于給定的離散無(wú)記憶信源X和碼符號(hào)集合D，如果對(duì)的次擴(kuò)展信源進(jìn)行無(wú)失真等長(zhǎng)編碼，那么當(dāng)碼長(zhǎng)滿足下列條件時(shí)，一定存在一種編碼方案，使得正確譯碼的錯(cuò)誤概率趨向0，即能夠?qū)崿F(xiàn)無(wú)失真編碼；反之，如果上述不等式不成立，不可能存在一種編碼方案，能使得正確譯碼的概率趨向0，也就是說(shuō)，不可能進(jìn)行無(wú)失真編碼。(2)對(duì)于給定的信源離散無(wú)記憶X，信源的熵是一定的，當(dāng)碼符號(hào)數(shù)量選定時(shí)，可以增加信源序列的長(zhǎng)度N，使得無(wú)失真編碼產(chǎn)生的每個(gè)符號(hào)平均長(zhǎng)度盡可能小，但是無(wú)論怎樣增加序列長(zhǎng)度N，信源每個(gè)符號(hào)的平均碼長(zhǎng)不可能小于H(X)/logd，即平均碼長(zhǎng)的極限為H(X)/logd。(3)當(dāng)序列長(zhǎng)度N一定，譯碼錯(cuò)誤概率為其中2.變長(zhǎng)碼

等長(zhǎng)碼編碼定理表明：增加序列長(zhǎng)度可以提高信源編碼效率。但序列長(zhǎng)度的增加，會(huì)增加系統(tǒng)編碼的復(fù)雜度。等長(zhǎng)編碼之所以編碼效率難以提高，是因?yàn)榈乳L(zhǎng)碼沒(méi)有充分利用信源及擴(kuò)展信源的統(tǒng)計(jì)特性進(jìn)行編碼，而是無(wú)論概率大小，給每個(gè)信源符號(hào)分配等長(zhǎng)碼字，從而無(wú)法降低平均碼長(zhǎng)。變長(zhǎng)碼的基本思想是：對(duì)于給定的信源，當(dāng)信源符號(hào)對(duì)應(yīng)的先驗(yàn)概率不是等概率分布時(shí)，為了提高編碼效率，給概率大的符號(hào)分配較短碼字，概率小的符號(hào)分配長(zhǎng)碼字，從而使得平均碼長(zhǎng)盡可能短。所以，往往在序列長(zhǎng)度不是很大時(shí)，變長(zhǎng)碼即可實(shí)現(xiàn)很高效率的無(wú)失真信源編碼。麥克米倫不等式與格拉夫特不等式具有相同的形式，該不等式首先由格拉夫特在研究即使碼存在的條件時(shí)提出，后來(lái)麥克米倫證明唯一可解碼的條件也滿足該不等式。當(dāng)信源給定時(shí)，使用相同的碼符號(hào)對(duì)信源進(jìn)行變長(zhǎng)編碼，得到的即時(shí)碼或者唯一可解碼也可以有許多種。現(xiàn)在的問(wèn)題是那種碼最好？從提高有效性角度考慮，應(yīng)當(dāng)選擇碼長(zhǎng)作為衡量編碼方法好壞的準(zhǔn)則。定理4.7設(shè)離散無(wú)記憶信源的熵為H(X)，編碼使用的符號(hào)個(gè)數(shù)為d，一定存在一種無(wú)失真編碼方法，構(gòu)成唯一可譯碼，使得平均碼長(zhǎng)滿足首先證明下界，根據(jù)熵和平均碼長(zhǎng)的定義

根據(jù)詹森不等式唯一可譯碼存在的條件就是滿足即克拉夫特不等式，即令，可得下面證明上界對(duì)于給定的概率分布p(ai)，一定存在一個(gè)正整數(shù)mi，使得下列不等式成立選擇該信源符號(hào)對(duì)應(yīng)碼字的長(zhǎng)度li＝mi。兩邊同乘以p(ai)，并且對(duì)求i和得根據(jù)熵、平均碼長(zhǎng)的定義該定理的意義：無(wú)失真不等長(zhǎng)編碼的平均碼長(zhǎng)不能小于極限Hd(X)，否則唯一可解碼不存在；同時(shí)給出上界1+Hd(X)，說(shuō)明小于上界的唯一可解碼是存在的；最佳碼的平均碼長(zhǎng)應(yīng)當(dāng)滿足上述不等式;當(dāng)然，平均碼長(zhǎng)超出上界的唯一可解碼是存在的。定理4.8（香農(nóng)第一定理）設(shè)離散無(wú)記憶信源的概率空間為信源的熵為H(X)，其N次擴(kuò)展信源為擴(kuò)展信源的熵為H(XN)。使用d元碼對(duì)次N擴(kuò)展信源進(jìn)行編碼，可以找到一種編碼方法，構(gòu)成唯一可譯碼，使得信源編碼得到的每個(gè)信源符號(hào)的平均碼長(zhǎng)滿足證明：由于信源X為無(wú)記憶信源，其次擴(kuò)展信源XN也是無(wú)記憶的，而且有直接應(yīng)用定理4.7的結(jié)論將擴(kuò)展信源的熵代入上式得可以將該結(jié)論加以推廣，對(duì)于平穩(wěn)、遍歷的有記憶信源香農(nóng)第一定理的意義：使用d元碼對(duì)信源進(jìn)行無(wú)失真編碼，信源編碼每個(gè)符號(hào)平均碼長(zhǎng)的極限就是信源的熵；如果編碼產(chǎn)生的平均碼長(zhǎng)大于信源的熵，唯一可解碼是存在的;反之，唯一可解碼是不存在的，即在譯碼時(shí)一定會(huì)引入失真或者差錯(cuò)。如果要取得好的編碼效果，序列的長(zhǎng)度應(yīng)當(dāng)更長(zhǎng)，從而增加系統(tǒng)編碼復(fù)雜度。當(dāng)然實(shí)際編碼時(shí)，往往是通過(guò)變換方法進(jìn)行編碼，降低編碼系統(tǒng)復(fù)雜度。而等長(zhǎng)編碼是將符號(hào)序列分為兩大類：典型序列和非典型序列。典型序列分配相同長(zhǎng)度的碼字，而非典型序列被丟棄或者通過(guò)附加前綴的方法與典型序列的碼字區(qū)分開。而典型序列的概率分布并不完全相同，分配相同的碼字顯然沒(méi)有利用統(tǒng)計(jì)特性，所以等長(zhǎng)碼不僅編碼效率難以提高，而且可能出現(xiàn)譯碼錯(cuò)誤。在香農(nóng)的等長(zhǎng)編碼理論中，非典型序列是不編碼的，一旦非典型序列出現(xiàn)，不可能再現(xiàn)或者重建該序列，所以會(huì)存在譯碼錯(cuò)誤。4.4信息率失真函數(shù)及性質(zhì)

無(wú)論是等長(zhǎng)編碼還是變長(zhǎng)編碼，都可以通過(guò)增加序列的長(zhǎng)度提高編碼效率。信源無(wú)失真編碼平均碼長(zhǎng)是受信源熵的限制，無(wú)論采用何種編碼方案，平均碼長(zhǎng)不可能小于信源的熵。由于編碼產(chǎn)生的信息率受到熵的限制，當(dāng)其大于信道容量時(shí)，不能夠在信道中有效傳輸信息。而在實(shí)際中，為了傳輸信息，允許出現(xiàn)一定的失真，從而降低信息傳輸率。那么在允許一定失真條件下，信源編碼輸出的信息率是否存在極限；或者說(shuō)，當(dāng)信息率一定時(shí)，是否會(huì)存在最小失真，使得在有效傳輸信源的信息同時(shí)，盡可能減小編碼引入的失真。這就是將要討論的問(wèn)題。4.4.1失真測(cè)度

從直觀上來(lái)看，如果允許失真越大，信息傳輸率應(yīng)當(dāng)越?。环催^(guò)來(lái)，如果允許失真越小，信息傳輸率越大，所以信息傳輸速率與信源編碼引入的失真是相關(guān)的，在允許失真一定的情況下，應(yīng)當(dāng)存在一種信源編碼方法使得信息傳輸率最小。失真的測(cè)度常用的失真函數(shù)有·平方誤差失真

·絕對(duì)失真：

·漢明失真：

無(wú)論是單個(gè)符號(hào)的失真還是序列的失真，實(shí)際都是反映了具體符號(hào)或者具體符號(hào)序列的失真，為了衡量每傳輸一個(gè)符號(hào)引入的失真大小，需要引入平均失真。定義4.11設(shè)信源的概率空間為如果將信源序列中的每個(gè)序列看作是擴(kuò)展信源的一個(gè)符號(hào)，類似地可以定義符號(hào)序列的平均失真。

定義4.12

定義信源X的N維符號(hào)序列的平均失真度為平均每個(gè)信源符號(hào)的失真為如果信源與試驗(yàn)信道都是無(wú)記憶的，利用序列概率與構(gòu)成序列的各符號(hào)概率之間的關(guān)系，可以得出如果信源還是平穩(wěn)的，就可以得出，結(jié)論：對(duì)于離散無(wú)記憶平穩(wěn)信源，如果試驗(yàn)信道也是無(wú)記憶的，那么信源序列的平均失真度等于單個(gè)符號(hào)的平均失真度的倍。4.4.2信息率失真函數(shù)的定義信源編碼的目的是為了減小信息傳輸率，而與編碼引入的失真存在一定的關(guān)系。對(duì)于給定的信源和選擇的失真測(cè)度，在編碼輸出的平均碼長(zhǎng)，即信息傳輸率一定的條件下，總是希望編碼引入的平均失真越小越好；或者說(shuō)，對(duì)于給定的平均失真，希望編碼產(chǎn)生的平均碼長(zhǎng)越小越好。信源編碼可以看作是存在一個(gè)試驗(yàn)信道，信道的輸入就是信源X，而信道的輸出就是譯碼后再現(xiàn)符號(hào)Y.對(duì)于給定的信源和選擇的失真測(cè)度，信源編碼就是尋找一種試驗(yàn)信道，在平均失真一定條件下，輸出碼率R最小。試驗(yàn)信道是不存在的，是為了分析限失真編碼理論而引入的，便于分析信息率失真函數(shù)。根據(jù)熵的性質(zhì)可知：在已知H(X)條件下，平均互信息I(X;Y)是信道轉(zhuǎn)移概率的U型凸函數(shù)，所以最小值是存在的。對(duì)于離散無(wú)記憶信源信息量失真函數(shù)不僅與信源符號(hào)取值、信源概率分布、失真的測(cè)度有關(guān)，而且與接收端再現(xiàn)符號(hào)也是密切相關(guān)的。經(jīng)過(guò)信源編碼后，信源所需要傳輸?shù)男畔⒘坑稍瓉?lái)的2比特/符號(hào)壓縮為1比特/符號(hào)。按照給定失真測(cè)度，引入的平均失真為，改變?cè)佻F(xiàn)或者重建符號(hào)并且采用相同的測(cè)度，則平均失真為采用不同的重建符號(hào)取值，則得到的平均失真也不同對(duì)于這種給定的簡(jiǎn)單試驗(yàn)信道，平均失真可以根據(jù)失真測(cè)度計(jì)算出來(lái)；當(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)概率一定從失真矩陣來(lái)看，平均失真最小值就是矩陣每行元素的最小值乘以對(duì)應(yīng)符號(hào)概率，然后求累加和。允許失真最小值是否為0取決于失真函數(shù)，如果失真矩陣中每行都有一個(gè)0元素，則最小失真為0；否則，只要有一行沒(méi)有0元素，則最小失真不為0。所以0是失真函數(shù)的下界。例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è)無(wú)噪有損信道，滿足(2)Dmax和R(Dmax)根據(jù)信息率失真函數(shù)的定義，R(D)是在給定平均失真D情況下，平均互信息量的最小值;由于I(X;Y)是非負(fù)的，其下限為0。當(dāng)R(D)=0時(shí)，對(duì)應(yīng)的平均失真取得最大值。的條件是什么？將概率分布和失真代入上式，得到2．R(D)是D的下凸函數(shù)

3.在區(qū)間上是嚴(yán)格遞減的連續(xù)函數(shù)

4.5信息率失真函數(shù)的計(jì)算1.約束條件設(shè)信源的概率空間為由于對(duì)所有的對(duì)所有的2．極值求解構(gòu)造函數(shù)考慮到以及于是得到下列方程得到個(gè)r×s方程，加上r個(gè)約束條件和約束條件為了討論問(wèn)題方便起見，令3．中間參數(shù)的表示根據(jù)關(guān)系式

兩邊同時(shí)乘4．信息率失真函數(shù)的參數(shù)表示信息率失真函數(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ù)將等式兩邊同時(shí)乘以p(bj)，并且對(duì)i求和，可以得出上述方程左邊第二項(xiàng)就是平均失真D將代入例4.12設(shè)信源的概率空間為信宿接收符號(hào)取值于{b1,b2},失真矩陣為求信息率失真函數(shù)解：（1）解下列方程（2）解下列方程，得到p(bj)即（3）將上述參數(shù)代入，求解信道轉(zhuǎn)移概率（4）用參量表示平均失真整理后可以得出將S，λi等參數(shù)代入對(duì)于某些特殊分布，信息率失真函數(shù)如下：（1）如果離散無(wú)記憶信源服從均值為0的高斯分布，即失真測(cè)度為則有（2）如果4.6信息率失真函數(shù)的迭代算法

信息率失真函數(shù)的計(jì)算顯得過(guò)于繁瑣;當(dāng)信符號(hào)數(shù)量較多時(shí)，人工計(jì)算信息率失真是相當(dāng)困難的;信息率失真函數(shù)存在迭代算法，這里只給出結(jié)論和具體迭代算法，推導(dǎo)過(guò)程不加以討論。試驗(yàn)信道的條件轉(zhuǎn)移概率可以表示為試驗(yàn)信道輸出符號(hào)的概率為從上述兩個(gè)公式來(lái)看，條件概率p*(bj|ai)與再現(xiàn)符號(hào)概率p*(bj)之間相互表示。在S一定的條件下，可以假設(shè)試驗(yàn)信道的轉(zhuǎn)移概率取值p*(bj|ai)，根據(jù)概