第8章限失真信源編碼

8.1失真函數(shù)與平均失真

8.2信息率失真函數(shù)及其性質(zhì)8.3信息率失真函數(shù)的計(jì)算8.4保真度準(zhǔn)則下的信源編碼定理8.5限失真信源編碼的基本原理習(xí)題8由第3章的討論我們知道，在圖8-1給出的簡單信息傳輸系統(tǒng)中，系統(tǒng)的信息傳輸率為R=I(X;Y)由于平均互信息I(X;Y)是信源概率分布P(x)和信道轉(zhuǎn)移概率分布P(y|x)的函數(shù)，并且I（X;Y）=I［P(x);P(y|x)］是信源概率分布P(x)的上凸函數(shù)，是信道轉(zhuǎn)移概率分布P(y|x)的下凸函數(shù)，因此如果信息傳輸系統(tǒng)中的信源不同（P(x)不同）或者信道不同（P(y|x)不同），則該信息傳輸系統(tǒng)的信息傳輸率R不同。圖8-1簡單信息傳輸系統(tǒng)第5章中我們討論了使用固定信道傳輸不同信源信息的情況。由于此時信道轉(zhuǎn)移概率分布P(y|x)固定不變，平均互信息I(X;Y)僅隨著信源概率分布P(x)的改變而改變，且是信源概率分布P(x)的上凸函數(shù),因此，對于給定的信道（P(y|x)固定），僅改變信源（P(x)可變）時可以求出I(X;Y)的極大值，此極大值反映出了給定信道信息傳輸?shù)哪芰?，并被定義為給定信道的信道容量：與此類似，如果使用不同的信道傳輸同一信源（P(x)固定）輸出的信息，則系統(tǒng)的信息傳輸率將隨著信道轉(zhuǎn)移概率P(y|x)的變化而改變。由于平均互信息I(X;Y)是信道轉(zhuǎn)移概率分布P(y|x)的下凸函數(shù)，因此一定可以找到一個信道，當(dāng)使用該信道傳輸給定信源輸出的信息時，系統(tǒng)的信息傳輸率最小。此最小的平均互信息反映出了傳輸該給定信源信息時必須有的最小信息傳輸率。顯然，與是一個成對偶關(guān)系的理論問題。對于一個給定的信源，可以使用不同的信源編碼方法表示其輸出的信息。從信息傳輸系統(tǒng)的有效性考慮，我們希望找出一種信源編碼方法（可以看做某種信道），采用該方法表示給定信源輸出的符號時，信息傳輸率R最小，以構(gòu)成一種最有效的信息傳輸系統(tǒng)。由平均互信息I（X;Y）的非負(fù)性可知：minI(X;Y)=0但是當(dāng)I(X;Y)=0即H(Y)－H(Y|X)=0H(Y|X)=H(Y)時，信道的轉(zhuǎn)移概率:P(y|x)=P(y)

表明該信道的輸出Y與其輸入X相互獨(dú)立，由Y根本得不到關(guān)于信源X的任何信息。由此可見，若使用R=I(X;Y)=0的信道傳輸給定信源輸出信息，則信道的輸出Y與信源的輸出X相比面目全非，信息傳輸系統(tǒng)中產(chǎn)生了嚴(yán)重的失真，以至于完全喪失了傳輸信息的能力。因此，關(guān)于信息傳輸系統(tǒng)有效性的分析，應(yīng)當(dāng)將信息傳輸率R與系統(tǒng)產(chǎn)生的失真聯(lián)系起來，對于給定的信源（P(x)固定），度量Y與X之間的失真，并在一定的失真限度內(nèi)尋求信息傳輸率R,即平均互信息的最小值。第7章我們討論的無失真信源編碼是一類在完全不允許失真（即失真度為零）的條件下的信源編碼問題。根據(jù)無失真信源編碼定理，信源的信息熵是進(jìn)行無失真編碼時編碼器信息傳輸率的理論下界。本章討論的信息率失真函數(shù)表示在某一失真限度下，傳輸給定信源信息時需要的最小信息傳輸率。本課程主要針對離散無記憶信源，介紹信息率失真理論的基本概念，給出失真的度量、信息率失真函數(shù)R(D)的定義和性質(zhì)。下面我們將在允許一定限度內(nèi)的信息損失的條件下，分析平均互信息I（X；Y）的最小值問題，在最簡單的條件下介紹信息率失真函數(shù)的計(jì)算，給出保真度準(zhǔn)則下的限失真信源編碼定理，初步討論限失真信源編碼的基本原理和主要方法。8.1失真函數(shù)與平均失真

由于人類生理、心理特性的影響，在實(shí)際的信息傳遞過程中，人們往往并不要求完全無失真地表示信源輸出的信息，而是要求在一定保真度（失真限度）條件下，近似地還原信源輸出的消息。為了討論一定失真限度條件下的最小信息傳輸率，首先需要對信源、信道的輸出給出一個定量的失真測度?？紤]圖8-2所示的信息傳輸系統(tǒng)。圖8-2簡單信息傳輸系統(tǒng)設(shè)離散無記憶信源:

經(jīng)信道P(vj|ui)傳輸后，接收符號集為V=［v1,v2,…,vs］

1.單個符號的失真函數(shù)對于信道的每一對輸入ui和輸出取值vj，指定一個非負(fù)數(shù)：d(ui,vj)≥0

i=1,2,…,r;j=1,2,…,s

(8.1)表示ui與vj之間的誤差或失真，被稱為單個符號的失真函數(shù)。顯然，若vj=ui，則用vj表示ui時便沒有產(chǎn)生失真，于是，d(ui,vj)=0；若vj≠ui，則d(ui,vj)>0。失真函數(shù)定量地描述了用vj表示ui時引起的失真、損失、風(fēng)險和主觀感覺上的差異大小，其具體的度量方式應(yīng)視應(yīng)用場合而定。常用的失真函數(shù)有以下幾種。（1）均方失真：d(ui,vj)=(ui－vj)2（2）絕對失真：d(ui,vj)=|ui－vj|(3)相對失真：

(4)漢明失真：

2.失真函數(shù)的表示由于信源U有r種可能取值，而接收符號集V有s種可能取值，因此，對于不同的i、

j取值，U、V之間共有r×s個失真函數(shù)d(ui,vj)。它們可以排列成一個r×s的矩陣，即此矩陣稱為失真函數(shù)矩陣。

3.K維隨機(jī)矢量的失真函數(shù)若信道的輸入與輸出是K維隨機(jī)矢量，則可以將單個符號的失真函數(shù)的定義加以推廣。設(shè)信源輸出的符號序列U=（U1，U2，…，UK），其中每一隨機(jī)變量Ui(i=1,2,…,K)取自同一符號集［u1,u2,…,ur］，所以信源輸出的符號序列U共有rK種可能的取值。接收端的符號序列為V=(V1,V2,…,VK)，其中每一個隨機(jī)變量Vj(j=1,2,…,K)取自同一符號集［v1,v2,…,vs］，因此，V共有sK種可能的取值。又設(shè)，分別是U、V的樣矢量，則ul與vm之間的失真函數(shù)為(8.2)對于不同的輸入、輸出符號序列，共有rK×sK個失真函數(shù)，可寫成矩陣形式DK，稱之為信道輸入、輸出為K維隨機(jī)矢量時的失真函數(shù)矩陣，它是一個rK×sK階矩陣。

【例8.1】已知U、V∈{0,1}，失真函數(shù)定義為。若作二次擴(kuò)展，即U，V∈{00，01，10，11}，則二維隨機(jī)矢量u、v之間的失真函數(shù)為依次可寫出u、v之間的失真函數(shù)矩陣:

4.平均失真由失真函數(shù)d(ui,vj)的定義可以看出，對于不同的ui、vj，d(ui,vj)的值可能不同。因此，失真函數(shù)d(ui,vj)是一個伴隨著隨機(jī)變量ui和vj的發(fā)生而發(fā)生的隨機(jī)變量，發(fā)生的概率為P(ui,vj)。于是，在信息傳輸系統(tǒng)中產(chǎn)生的失真可以使用失真函數(shù)的統(tǒng)計(jì)平均值來表示。平均失真定義為(8.3)若已知信道轉(zhuǎn)移概率P(vj|ui)，則平均失真可進(jìn)一步表示為

(8.4)

可見，單個符號的失真函數(shù)d(ui,vj)描述了某個信源符號經(jīng)過信道傳輸后的失真大小，對于不同的信源符號和不同的接收符號，其值是不同的，而平均失真則是從總體上描述整個系統(tǒng)失真情況的一個量。若信道的輸入、輸出為K維隨機(jī)矢量U、V，則系統(tǒng)的平均失真定義為(8.5)也可寫成：(8.6)當(dāng)信源與信道都是無記憶時，可進(jìn)一步簡化為

(8.7)

其中，是K維隨機(jī)矢量的第i個分量的平均失真。如果離散信源是平穩(wěn)的，則有和

，即通過離散無記憶信道傳輸離散無記憶平穩(wěn)信源輸出的符號序列時，系統(tǒng)的平均失真等于信源輸出單個符號的平均失真。8.2信息率失真函數(shù)及其性質(zhì)8.2.1D失真許可準(zhǔn)則與D失真許可信道在實(shí)際的通信過程中，人們對于通信質(zhì)量的要求一般是從統(tǒng)計(jì)平均的意義上進(jìn)行考查和度量的。為了滿足一定的通信質(zhì)量要求，需要對系統(tǒng)中產(chǎn)生的失真加以限制，要求信息傳輸系統(tǒng)所產(chǎn)生的平均失真不能夠大于某一給定的常數(shù)D，即滿足：≤D

(8.8)由于常數(shù)D為信息傳輸系統(tǒng)中所允許的失真限度，因此式(8.8)稱為信息傳輸系統(tǒng)的D失真許可準(zhǔn)則?？紤]一個使用不同信道P(vj|ui)傳輸給定的信源U輸出符號的信息傳輸過程，信道的輸出符號為隨機(jī)變量V。顯然，使用不同信道傳輸該給定信源信息時，系統(tǒng)的信息傳輸率R=I(U;V)不同，產(chǎn)生的失真也不同。在定義了失真函數(shù)d(ui,vj)之后，我們總是希望在允許一定失真限度D的條件下，使得傳輸信源信息的信息傳輸率R=I(U;V)盡可能地小。也就是說,在D失真許可準(zhǔn)則(≤D)下，尋找傳輸該給定信源信息的信息傳輸率R=I(U;V)的最小值。由平均失真的定義式(8.4)可以看出，系統(tǒng)的平均失真不僅與失真函數(shù)d(ui,vj)有關(guān)，而且與信源的統(tǒng)計(jì)特性P(ui)和信道的轉(zhuǎn)移概率P(vj|ui)有關(guān)。應(yīng)當(dāng)注意，在給定信源U，并且定義了U、V之間的失真函數(shù)d(ui,vj)之后，系統(tǒng)的平均失真僅由信道轉(zhuǎn)移概率P(vj|ui)決定，即=［P(vj|ui)］。如果要求信息傳輸系統(tǒng)所產(chǎn)生的平均失真不能夠大于某一給定的常數(shù)D，則可以使用的信道受到了限制。于是，傳輸該給定信源信息的信道可以劃分為兩類:一類信道能夠滿足D失真許可準(zhǔn)則的要求，即滿足≤D;另一類信道中所產(chǎn)生的平均失真>D。因此，我們將信道P(vj|ui)劃分為兩個集合：

(8.9)(8.10)顯然，如果信道P(vj|ui)∈PD，則使用該信道傳輸給定信源輸出信息時，傳輸系統(tǒng)的平均失真將滿足D失真許可準(zhǔn)則。因此，集合PD中的信道稱為D失真許可信道。說明：為了求出信道可變條件下信息傳輸率R=I(U;V)的最小值，此處引用的信道P(vj|ui)為一種假想的可變信道，稱為試驗(yàn)信道。在實(shí)際問題的分析中，這些不同的試驗(yàn)信道可以看做不同的信源編碼方法。8.2.2信息率失真函數(shù)平均互信息的凸性表明，對于給定的信源，信息傳輸系統(tǒng)的信息傳輸率：R=I(U;V)=I［P(vj|ui)］是信道轉(zhuǎn)移概率P(vj|ui)的下凸函數(shù)。因此，若改變信道參數(shù)，則一定存在一個平均互信息的最小值，使得傳輸給定信源信息時系統(tǒng)的信息傳輸率最小。但是，此時討論的問題是在滿足D失真許可要求下尋找重建給定信源信息時所必須有的最小平均信息量。雖然由平均互信息的下凸性知道此時R=I（U；V）的最小值一定存在，但是由于規(guī)定了失真限度D，因此傳輸給定信源信息所能夠使用的信道受到了限制，即P(vj|ui)∈PD。于是，我們可以在D失真許可信道集合PD中選出一組信道轉(zhuǎn)移概率P(vj|ui)，使得信息傳輸率R=I(U;V)達(dá)到最小值。此平均互信息的最小值表示在滿足D失真許可要求（≤D）時傳輸給定信源信息的信息傳輸率R的最小值。定義滿足D失真許可要求的平均互信息的最小值為信息率失真函數(shù),即

(8.11)簡稱率失真函數(shù)，單位是比特/符號或奈特/符號。信息率失真函數(shù)R(D)的定義表明，R(D)為給定信源和定義失真函數(shù)的前提下，在失真限度為D（試驗(yàn)信道滿足一定約束條件）時平均互信息I(U;V)的最小值。因此信息率失真函數(shù)R(D)具有明確的物理含義和實(shí)際指導(dǎo)意義。信息率失真函數(shù)R(D)與信道容量C具有對偶性。R(D)是在給定信源P(u)和失真限度D時平均互信息I(U;V)的最小值。這個最小值R(D)是在給定信源的情況下，接收端以滿足失真限度D的要求而重建信源信息時所必須獲得的最小平均信息量。因此，R（D）反映了在滿足一定失真限度D的要求下，給定信源輸出的信息率可以壓縮的程度，即最有效地表達(dá)信源輸出信息時可以壓縮到的最低信息率。顯然，

R（D）所表示的最低信息率是反映信源特性的參量，與試驗(yàn)信道無關(guān)。對于不同的信源，其R（D）不同。信道容量C則是在給定信道P(v|u)時平均互信息I(U;V)的最大值。信道容量C反映了信道傳輸信息的能力，是在信道中實(shí)現(xiàn)可靠傳輸時該給定信道的最大信息傳輸率。信道容量C與信源無關(guān)，是反映信道特性的參量。對于不同的信道，其信道容量不同。信息率失真函數(shù)R(D)與信道容量C這兩個概念在實(shí)際應(yīng)用中有明顯區(qū)別。信道容量C的研究目的是掌握給定信道傳輸信息的能力，即該信道能夠可靠傳送的最大信息量。在充分利用給定信道傳輸能力的條件下，使信息傳輸系統(tǒng)的信息傳輸率最大而錯誤概率任意小，這就是一般的信道編碼問題。信息率失真函數(shù)R（D）的研究目的是掌握給定信源輸出信息的特性。在滿足D失真許可要求的條件下，人們希望使用盡可能少的碼符號表達(dá)（傳送）給定信源輸出的信息。由于R(D)恰為失真限度D之內(nèi)傳輸給定信源輸出信息時所必需的最小信息傳輸率，因此信息率失真函數(shù)R(D)反映了信息傳輸系統(tǒng)的有效性研究，即信源編碼和數(shù)據(jù)壓縮應(yīng)用中所面臨的一個基本問題。8.2.3R(D)的基本函數(shù)關(guān)系由上面的討論可以看出，傳輸給定信源輸出的符號時，如果信息傳輸系統(tǒng)中允許產(chǎn)生的平均失真限度為D，則由D失真許可信道集合PD中找出的平均互信息的最小值便為信息率失真函數(shù)R（D）。顯然，如果要求的平均失真限度D不同，則D失真許可信道集合PD不同，所得到的最小信息傳輸率也不同。因此，信息率失真函數(shù)R(D)是失真限度D的函數(shù)。設(shè)已給定離散無記憶信源:

對于試驗(yàn)信道:

已定義U、V之間的r×s個失真函數(shù)d(ui,vj)≥0。失真函數(shù)矩陣為(8.12)(8.13)(8.14)下面首先討論信息率失真函數(shù)：

所具有的基本函數(shù)關(guān)系,即考察R(D)的值域和使得R(D)有定義的失真限度D的取值范圍。

1．R(D)的值域信息率失真函數(shù)R(D)的定義式(8.11)表明，R(D)本質(zhì)上反映的是信息傳輸系統(tǒng)中信源U與信道輸出V之間的平均互信息I(U;V)。依據(jù)平均互信息I(U;V)的基本性質(zhì)，可以確定信息率失真函數(shù)R(D)取值大小滿足的關(guān)系。由于平均互信息I(U;V)具有非負(fù)性,即I(U;V)≥0因此信息率失真函數(shù)的取值不會小于0，即R（D）≥0由平均互信息I(U;V)的極值性，即I(U;V)≤H(U)

可以看出，信息率失真函數(shù)R(D)的取值有界:R(D)≤H(U)即信息率失真函數(shù)R(D)的數(shù)值不會超過信源U的輸出的平均信息量H(U)。于是，信息率失真函數(shù)R(D)的取值范圍為0≤R(D)≤H(U)

2．R(D)的定義域的下界Dmin

對于給定的信源（P(u)固定）和定義的失真函數(shù)d(ui,vj)，使得信息率失真函數(shù)R(D)有定義的失真限度D中的最小值Dmin便為R(D)的定義域的下界。由前面關(guān)于失真函數(shù)的討論可知，失真函數(shù)大于或等于零，即d(ui,vj)≥0i=1,2,…,r;j=1,2,…,s作為失真函數(shù)d(ui,vj)的統(tǒng)計(jì)平均值，平均失真也是一個非負(fù)的實(shí)數(shù)，即≥0。因此，使得信息率失真函數(shù)R(D)有意義的失真限度D的取值不可能小于零。由此可知，信息率失真函數(shù)R(D)的定義域的下界滿足Dmin≥0。在實(shí)際應(yīng)用中，由于不同信源具有不同的統(tǒng)計(jì)關(guān)系，在不同的應(yīng)用場合用vj表示ui時所產(chǎn)生的差異、損失與風(fēng)險的大小也各不相同，因此，信息率失真函數(shù)R（D）的定義域需要根據(jù)具體問題和應(yīng)用要求加以確定。對于以給定的信源U（見式(8.12)）和失真函數(shù)矩陣D（見式(8.14)），可以求出U與V之間的平均失真：(8.15)由于信源概率分布P(ui)和失真函數(shù)d(ui,vj)已確定，因此此時的平均失真是信道參數(shù)P(vj|ui)的函數(shù)。于是，改變試驗(yàn)信道參數(shù)時所取得的平均失真的最小值即為R(D)定義域的下界,即(8.16)對于信源輸出符號集合中的某一符號ui（i=1,2,…,r，且為固定的參變量），不同試驗(yàn)信道P(vj|ui)的輸出vj（j=1,2,…,s）不同，則該試驗(yàn)信道傳輸某一信源符號ui所產(chǎn)生的平均失真為

(8.17)顯然，使用的試驗(yàn)信道P(vj|ui)不同，則平均失真的大小不同，并且一定存在一種試驗(yàn)信道P(vj|ui)，使得式(8.17)所表示的平均失真達(dá)到其可能的最小值。進(jìn)一步分析可知，對于給定的信源和已定義的失真函數(shù)，如果可以找到一種試驗(yàn)信道，對于ui（i=1,2,…,r）都能夠使式(8.16)達(dá)到其可能的最小值，則U、V之間的平均失真一定達(dá)到其最小值，且為信息率失真函數(shù)R(D)的定義域的下界Dmin。于是，式(8.16)可以表示為

(8.18)由此可以看出，我們可以通過選擇一種試驗(yàn)信道，使每一種信源符號所產(chǎn)生的平均失真最?。词?8.18)中的內(nèi)和式達(dá)到其最小值），從而得到R(D)的定義域的下界Dmin。使用不同的vj(j=1,2,…,s)表示固定的ui時，由于失真函數(shù)矩陣D中第i行的元素d(ui,vj)互不相同，因此在失真函數(shù)矩陣D的第i行元素中一定可以找出一個最小值（也可能有若干個相同的最小值）。不妨設(shè)失真函數(shù)矩陣D的第i行中第J列失真函數(shù)的取值（此處記做Ji）最小，便有：可以選擇一種試驗(yàn)信道，使其滿足：

(8.19)那么，第i行的平均失真達(dá)到其最小值：由于失真函數(shù)矩陣D中每一行的平均失真都是最小的，因此系統(tǒng)總體的平均失真一定為其可能取值的最小值。于是，對于給定的信源和定義的失真函數(shù)，信息率失真函數(shù)R（D）的定義域的下界為

(8.20)若失真函數(shù)矩陣D的每一行中至少有一個失真函數(shù)為零，則有Dmin=0，否則，Dmin≠0。若給定失真限度為D=Dmin=0則表示該信息傳輸系統(tǒng)必須無失真?zhèn)鬏斀o定信源輸出的符號。于是，信息傳輸率至少應(yīng)等于信源的信息熵，即R(0)=H(U)如果失真函數(shù)矩陣D中某些列中包含了至少兩個取值為零的元素，則表明給定信源符號集中的某些符號可以壓縮、合并。此時，一般滿足:R(0)<H(U)

若失真函數(shù)矩陣D中至少有一行全部為非零元素，則有Dmin≠0。此時R(Dmin)≤H(U)

【例8.2】設(shè)信源(0≤p≤1)，V∈［v1,v2,v3］，定義失真函數(shù)矩陣為

由式(8.20)可以求出信息率失真函數(shù)R(D)的定義域的下界為由前面的分析和式(8.19)所示的關(guān)系可以看出，達(dá)到此最小允許失真限度的試驗(yàn)信道為

由于此試驗(yàn)信道是一個無噪無損信道，在信道的輸出端觀測到輸出V之后，便可以消除關(guān)于信源U的不確定性，因此信道疑義度H(U|V)=0,則有：I(U;V)=H(U)－H(U|V)=H(U)于是

【例8.3】設(shè)信源

，V∈［v1,v2］，定義失真函數(shù)矩陣為

由式(8.20)計(jì)算得：所以，對于此信源U和定義的失真函數(shù)，R(D)的定義域的下界為。根據(jù)式(8.19)，達(dá)到此最小允許失真限度的試驗(yàn)信道必須滿足：由于滿足約束條件P(v1|u2)+P(v2|u2)=1的P(v1|u2)和P(v2|u2)可以有無窮多種組合，因此可以使得系統(tǒng)平均失真的試驗(yàn)信道有無數(shù)多個。這些試驗(yàn)信道的信道矩陣中每一列都有不止一個非零元素，所以H(U|V)≠0,于是若將失真函數(shù)矩陣改成：

則

同理，達(dá)到此最小允許失真限度的試驗(yàn)信道必須滿足：滿足上述條件的試驗(yàn)信道的共同特點(diǎn)就是信道矩陣中每列有不止一個非零元素，所以，H(U|V)≠0，因此，。從失真函數(shù)矩陣d′也可以看出，信源符號u1傳遞到符號v1無失真，而信源符號u2傳遞到v1也無失真，因此，完全可以將信源的符號u1和u2合并成一個符號，使信源符號集由三個符號壓縮成兩個符號，并不引起任何失真。顯然，壓縮后信息傳輸率必然減小，所以得R(0)<H(U)。

3．R(D)的定義域的上界Dmax

由信息率失真函數(shù)的值域可知，R(D)在其定義域內(nèi)的取值非負(fù)，只要失真限度D≥0，則R（D）≥0。為了能夠更加明確地反映出信息率失真函數(shù)的函數(shù)變化關(guān)系和工程意義，此處需要進(jìn)一步分析R(D)隨著失真限度D改變時其函數(shù)關(guān)系的特點(diǎn)。當(dāng)使用可變試驗(yàn)信道傳輸給定信源U時，如果信道不同，則不僅信息傳輸率R=I(U;V)不同，V、U之間的平均失真也不同。由前面的討論可以看出，隨著系統(tǒng)平均失真的增大，信息傳輸率R=I(U;V)將單調(diào)減小，其極限情況為R=I(U;V)=0。由于I(U;V)=0意味著信道的輸出V與信源的輸出U相互獨(dú)立，因此接收者不能夠由該信息傳輸系統(tǒng)得到信源輸出的信息。然而對于一個實(shí)際的信息傳輸系統(tǒng)來說，在平均失真增大而R=I(U;V)單調(diào)遞減的過程中，存在著某一個特定的平均失真取值。當(dāng)時，R=I(U;V)>0；當(dāng)時，R=I(U;V)≡0。于是，作為在D失真許可條件下傳輸給定信源信息時的平均互信息的最小值(即使得I(U;V)由非零變?yōu)榱闼鶎?yīng)的平均失真取值)，對于考察信息率失真函數(shù)R(D)的基本函數(shù)關(guān)系有重要意義。因此，設(shè)給定信源的信息率失真函數(shù)為R(D)，對于失真限度D≥0，一定存在一個自變量的取值D=Dmax,使得D<Dmax時，有0<R(D)≤H(U)當(dāng)D≥Dmax時，有R（D）≡0則Dmax表示R(D)定義域的上界值。下面我們討論和給出R(D)定義域的上界Dmax的確定方法。由前面關(guān)于系統(tǒng)平均失真與系統(tǒng)信息傳輸率R=I(U;V)的討論可以看出，當(dāng)≥時，R=I(U;V)≡0。由于與此對應(yīng)的試驗(yàn)信道的輸入U與輸出V相互獨(dú)立，因此為了得到，構(gòu)造試驗(yàn)信道轉(zhuǎn)移概率：P(vj|ui)=P(vj)i=1,2,…,r;j=1,2,…,s

(8.21)于是可以求出信道輸入U與輸出V之間的平均失真：

顯然，在滿足U與V相互獨(dú)立（見式(8.21)）的條件下，不同的試驗(yàn)信道中產(chǎn)生的平均失真不同，而恰為此類信道中平均失真的下界(最小值),于是其中，內(nèi)和式表示了U、V統(tǒng)計(jì)獨(dú)立時，失真函數(shù)矩陣D的每一列元素d(ui,vj)對P(ui)的均值。為使上式總和最小，我們可以按下述方法來選擇試驗(yàn)信道。首先計(jì)算失真函數(shù)矩陣D中每一列元素d(ui,vj)的統(tǒng)計(jì)平均值:

而后在各列均值中找出最小者。此處不妨設(shè)第k列最小，即

相應(yīng)地，取試驗(yàn)信道的轉(zhuǎn)移概率為

于是，得到了U、V統(tǒng)計(jì)獨(dú)立條件下的最小平均失真，即顯然，由這樣的U、V相互獨(dú)立的試驗(yàn)信道所得到的平均失真的最小值即為信息率失真函數(shù)R(D)定義域的上界值Dmax，即

(8.22)并且當(dāng)D≥Dmax時，有R（D）≡0

【例8.4】設(shè)輸入隨機(jī)變量的概率空間為，輸出符號集，定義失真函數(shù)矩陣為

則由式(8.22)可知：可以看出，達(dá)到最大失真限度Dmax所對應(yīng)的試驗(yàn)信道矩陣為

并且當(dāng)時，有

R（D）≡08.2.4信息率失真函數(shù)的性質(zhì)

性質(zhì)1

在定義域［Dmin,Dmax

］內(nèi)，R(D)是D的下凸函數(shù)，即已知D1，D2∈［Dmin,Dmax］,對于任意給定的0≤θ≤1，有：R(θD1+(1－θ)D2)≤θR(D1)+(1－θ)R(D2)

(8.23)

證明：在R（D）的定義域內(nèi)任取兩點(diǎn)，并有：

其中，P1(vj|ui)是恰使I(U;V1)達(dá)到最小值的試驗(yàn)信道。同理有：

其中，P2(vj|ui)是恰使I(U;V2)達(dá)到最小值的試驗(yàn)信道。令0≤θ≤1，并令D′=θD1+(1－θ)D2且P(vj|ui)=θP1(vj|ui)+(1－θ)P2(vj|ui)首先證明P(vj|ui)是D′失真許可信道集合PD′內(nèi)的信道,即使用信道P(vj|ui)∈PD′傳輸信源信息時，系統(tǒng)中產(chǎn)生的平均失真≤D′。因?yàn)榭捎洺?/p>

因?yàn)?/p>

所以

于是

因此P(vj|ui)∈PD′

即P(vj|ui)是D失真許可信道集合PD內(nèi)的一個信道。因此有：R(D′)=R(θD1+(1－θ)D2)≤I(U;V,P(vj|ui))(8.24)另外，由于平均互信息I(U;V,P(vj|ui))是信道轉(zhuǎn)移概率的下凸函數(shù)，因此有：

由式(8.24)和式(8.25)可得：R（θD1+(1－θ)D2）≤R(D1)+(1－θ)R(D2)因此信息率失真函數(shù)R(D)在定義域內(nèi)是下凸的。(8.25)

性質(zhì)2

R(D)在定義域［Dmin,Dmax］內(nèi)是單調(diào)遞減函數(shù)。由上面的討論可以看出，當(dāng)傳輸給定信源輸出的信息時，允許的失真限度D愈大，則傳輸該信源必須有的最小信息傳輸率將愈小。因此，依信息率失真函數(shù)的定義可知，在定義域［Dmin,Dmax］內(nèi)，R(D)是單調(diào)遞減函數(shù)。R(D)在定義域內(nèi)的單調(diào)遞減性可以由R(D)的下凸性加以證明。

證明：設(shè)D1為定義域內(nèi)的任意一點(diǎn)。在(D1,Dmax)中任取一點(diǎn)Dθ，使Dθ=(1－θ)D1+θDmax

其中,θ是任意小的正數(shù)。由于R(D)在定義域內(nèi)是下凸的，因此有：R(Dθ)=R((1－θ)D1+θDmax)≤(1－θ)R(D1)+θR(Dmax)已知R(Dmax)=0，則R(Dθ)≤(1－θ)R(D1)由于0<1－θ<1，于是R(Dθ)<R(D1)即對于定義域［Dmin,Dmax］內(nèi)的任意兩點(diǎn)D1和Dθ，無論Dθ多么接近D1，只要Dθ>D1，則一定滿足R(Dθ)<R(D1)。所以,信息率失真函數(shù)R(D)在定義域［Dmin,Dmax］內(nèi)是單調(diào)遞減函數(shù)。

性質(zhì)3

R(D)在定義域［Dmin,Dmax］內(nèi)是失真限度D的連續(xù)函數(shù)。對于給定的信源U，信息傳輸率R=I(U;V)是信道轉(zhuǎn)移概率P(vj|ui)的函數(shù)，即在滿足概率分布關(guān)系的條件下，如果使信道轉(zhuǎn)移概率P(vj|ui)有一個微小的變化，即使信道參數(shù)為P(vj|ui)±ε

ε>0則系統(tǒng)的信息傳輸率改變?yōu)榱瞀拧?，則P(vj)≠0因此，平均互信息I(U;V)是信道轉(zhuǎn)移概率P(vj|ui)的連續(xù)函數(shù)。對于給定信源U，如果失真限度為D，則D失真許可信道集合為PD={P(vj|ui);≤D}

由信息率失真函數(shù)R(D)的定義可知，一定存在一組信道參數(shù)P1(vj|ui)∈PD，使得：

若將失真限度調(diào)整為D′=D+Δ

Δ≥0則滿足D′失真許可的信道集合為PD′={P(vj|ui);≤D+Δ}同理,一定可以找到一組信道參數(shù):P2(vj|ui)∈PD′

使得:

顯然，當(dāng)Δ→0時，PD′→PD，且有：P2(vj|ui)=P1(vj|ui)±ε

ε→0由于平均互信息I(U;V)是信道轉(zhuǎn)移概率P(vj|ui)的連續(xù)函數(shù)，因此有：

此式等價于：于是

因此，信息率失真函數(shù)R(D)在其定義域［Dmin,Dmax］內(nèi)是失真限度D的連續(xù)函數(shù)。根據(jù)R(D)的上述性質(zhì)，可以做出R(D)的大致函數(shù)曲線。設(shè)給定信源U，其信息熵為H（U），并且已定義信道輸入U與輸出V之間的失真函數(shù)矩陣D。如果失真函數(shù)矩陣D的每一行元素中的最小值為0，且只有一個元素為0，則由前面關(guān)于信息率失真函數(shù)R(D)的基本函數(shù)關(guān)系的討論可知，系統(tǒng)中允許的失真限度D的下限值為Dmin=0，且有：R(Dmin)=R(0)=H(U)并且一定存在一個失真限度Dmax，當(dāng)D≥Dmax時，R(Dmax)≡0。于是，在失真限度D和信息率失真函數(shù)R(D)分別為橫、縱坐標(biāo)構(gòu)成的坐標(biāo)系中，可以標(biāo)出信息失真函數(shù)的定義域［0,Dmax］與函數(shù)中的兩個點(diǎn)：(0,H(U))和(Dmax,0)。由于信息失真函數(shù)R(D)在其定義域［0,Dmax］內(nèi)是下凸、單調(diào)遞減的連續(xù)函數(shù)，因此可以做出R(D)在其定義域內(nèi)的函數(shù)曲線，并且當(dāng)D≥Dmax時，有R(Dmax）≡0，如圖8-3(a)所示。如果對于給定的失真函數(shù)矩陣D，系統(tǒng)中允許的失真限度D≠0，則可計(jì)算得到信息失真函數(shù)R(D)的定義域的下界Dmin和上界Dmax，求出相應(yīng)的信息率失真函數(shù)取值R(Dmin)和R(Dmax)≡0，依據(jù)信息失真函數(shù)R(D)在其定義域［Dmin,Dmax］內(nèi)的下凸性、單調(diào)遞減性和連續(xù)性，做出R(D)的函數(shù)曲線，如圖8-3(b)所示。（注意：當(dāng)D≥Dmax

時，R(Dmax)≡0。）圖8-3R(D)函數(shù)的曲線8.3信息率失真函數(shù)的計(jì)算8.3.1信息率失真函數(shù)的一般計(jì)算方法由前面關(guān)于信息率失真函數(shù)的定義知道，R(D)是在滿足失真限度D的條件下系統(tǒng)平均互信息I(X;Y)的最小值。于是，對于給定的信源U和定義的失真函數(shù)矩陣D，首先需要找出滿足失真限度D要求的信道,構(gòu)成D失真許可信道集合PD，依據(jù)平均互信息I(X;Y)的下凸性，從D失真許可信道集合PD內(nèi)選出一組信道參數(shù)函數(shù)P(v|u)，使得平均互信息I(X;Y)達(dá)到其最小值，得到信息率失真函數(shù):

顯然，這種在使用信道受限的條件下求出平均互信息最小值的問題(即信息率失真函數(shù)R(D)的計(jì)算)是一個比較復(fù)雜和困難的問題。設(shè)給定離散無記憶信源:

已知信道的輸出符號集合為V=［v1,v2,…,vs］，定義U、V之間的失真函數(shù)矩陣：

由上面關(guān)于信息率失真函數(shù)R(D)的基本函數(shù)關(guān)系和性質(zhì)可以知道，給定信源的信息率失真函數(shù)R(D)的一般計(jì)算內(nèi)容主要包括：（1）確定Dmin及R(Dmin);（2）確定Dmax及R(Dmax);（3）確定Dmin<D<Dmax內(nèi)R(D)的解析式。此處，我們以一個特定類型的信源U和失真函數(shù)矩陣D為例，介紹信息率失真函數(shù)R(D)的一般計(jì)算思路和方法，以進(jìn)一步理解和掌握R(D)的基本函數(shù)關(guān)系和性質(zhì)。

【例8.5】設(shè)二元對稱信源，其中，接收符號集V={0,1}，定義失真函數(shù)矩陣，試求R(D)在其定義域內(nèi)的解析式。

解：首先求出信源U的信息熵:H(U)=H(p,1－p)=H2(p)

（1）確定Dmin及R(Dmin)。由前面關(guān)于R(D)的定義域下界的討論可以得到：可見，此系統(tǒng)中允許的最小失真限度Dmin=0。可以找出使得Dmin=0的試驗(yàn)信道為

顯然，此試驗(yàn)信道是一個無噪無損信道，可以求出：R(Dmin)=R(0)=I(U;V)=H(p,1－p)=H2(p)（2）確定Dmax及R(Dmax)。因?yàn)?/p>

于是，使得R(D)=0時，失真限度D的最小值，即R（D)定義域的上界為Dmax=p可以找出，使得系統(tǒng)平均失真恰為Dmax的試驗(yàn)信道為

顯然，這個試驗(yàn)信道的輸出V與輸入U相互獨(dú)立，即無論信源U輸出符號為u1或u2，信道的輸出符號都是v2。因此，當(dāng)信源U輸出符號u1時一定發(fā)生傳輸錯誤，而當(dāng)信源U輸出符號u2時，信道的輸出與輸入之間的失真為0。由于P(u1)=p，因此此時系統(tǒng)的平均失真＝Dmax=p。同時，由信息率失真函數(shù)的基本關(guān)系知:R(Dmax)=0

（3）確定0<D<p內(nèi)R(D)的解析式。由R(D)的定義式：

可知，R(D)實(shí)際上是在滿足保真度準(zhǔn)則≤D條件下平均互信息I(U;V)的最小值。由于R(D)在定義域內(nèi)是單調(diào)遞減函數(shù)，因此R(D)即為在=D的條件下I(U;V)的最小值，即其中:

顯然，此時的平均失真為錯誤概率:

若使系統(tǒng)的平均失真等于錯誤概率:

則有:

而根據(jù)范諾不等式(r=2)有:H(U|V)≤H(pe)+pelog(2－1)=H(pe)即H(U|V)≤H(D)因此有:所以，一定存在一個試驗(yàn)信道［P(v|u)］，使得平均互信息I(U;V)可以達(dá)到上述不等式的下界，于是，在0≤D≤p內(nèi)滿足≤D條件下信源的信息率失真函數(shù)R(D)為R(D)=H2(p)－H(D)上面我們只是假定一定存在一個試驗(yàn)信道［P(v|u)］，使得用該信道傳輸信源信息時系統(tǒng)的平均失真≤D，而接收端獲得的平均信息量I(U;V)=H2(p)－H(D)。關(guān)于這一假設(shè)是否真的成立，還需要進(jìn)一步證實(shí)。為證實(shí)這一點(diǎn)，就必須找到一個這樣的試驗(yàn)信道，使得其平均失真=D，接收端獲得的平均信息量度:I(U;V)=H2(p)－H(D)為此，我們構(gòu)造一個反向的試驗(yàn)信道，即將原信道的傳遞關(guān)系反向，使原信道的輸入端為輸出端，而輸出端為輸入端。按照失真限度D的要求，所構(gòu)造的反向試驗(yàn)如圖8-4所示。其轉(zhuǎn)移概率為P(u=0|v=0)=1－D

P(u=1|v=0)=D

P(u=0|v=1)=D

P(u=1|v=1)=1－D

圖8-4反向信道轉(zhuǎn)移概率現(xiàn)在，我們來計(jì)算用該信道傳輸信源時系統(tǒng)的平均失真及接收端獲得的平均互信息。對于此反向試驗(yàn)信道，可以求出系統(tǒng)的平均失真和平均互信息。系統(tǒng)的平均失真：

系統(tǒng)的平均互信息I(U;V)為I(U;V)=H(U)－H(U|V)而因此I(U;V)=H(U)－H(U|V)=H2(p)－H(D)由此可見，所選擇的反向試驗(yàn)信道滿足失真許可準(zhǔn)則≤D，且接收端獲得的平均信息量達(dá)到平均互信息的下界，即I(U;V)=H2(p)－H(D)但是上述結(jié)論是對一個構(gòu)造的反向試驗(yàn)信道進(jìn)行計(jì)算得到的，而此反向試驗(yàn)信道的構(gòu)造是否合理，即此反向試驗(yàn)信道是否存在，還需要依據(jù)已知的信源概率分布P(u)和反向試驗(yàn)信道的轉(zhuǎn)移概率P(u|v)，檢驗(yàn)隨機(jī)變量V是否滿足概率分布關(guān)系的要求。由于在上面的分析中已經(jīng)應(yīng)用了P(v1)+P(v2)=1的條件，因此只需驗(yàn)證隨機(jī)變量V的概率分布是否滿足：0≤P(v1)≤1設(shè)P(v1)=α,P(v2)=1－α0<α<1則由已知條件可得：解得：

由于已知而0≤D≤p所以

因此，上面定義的反向試驗(yàn)信道參數(shù)合理，所構(gòu)成的反向試驗(yàn)信道是存在的。又因?yàn)?/p>

所以我們得到了在滿足≤D的條件下，使得平均互信息I(U;V)達(dá)到最小值時所對應(yīng)的試驗(yàn)信道。于是，通過對信息率失真函數(shù)的定義域、值域和解析式的分析與計(jì)算，對于此例所給定的信源U和定義的失真函數(shù)，信息率失真函數(shù)R(D)為圖8-5給出了R(D)的函數(shù)曲線。圖8-6描述了在p取不同值時的R(D)曲線。由此可見，對于同一個D，信源分布越均勻，R(D)就越大，信源壓縮的可能性就越小。反之，若信源分布越不均勻，即信源信息冗余度越大，則R(D)就越小，壓縮的可能性就越大。比特符號

圖8-5二元對稱信源的R(D)圖8-6p取不同值時的R(D)函數(shù)8.3.2r元等概信源和漢明失真函數(shù)的R(D)

設(shè)信源、信宿的符號集相同，即U,V∈{0,1,2,…,r－1}，已知信源符號等概分布，定義失真函數(shù)為漢明失真，即則信源的信息率失真函數(shù)為

稱為r元等概信源和漢明失真函數(shù)的R(D)，也可稱做r元信源在錯誤概率準(zhǔn)則下的信息率失真函數(shù)。證明：對于給定的信源和漢明失真函數(shù)可以求出：以及R(Dmin)=R(0)=H(U)=logr

比特/符號R（Dmax）=0當(dāng)Dmin<D<Dmax,時，由于R(D)為失真限度的單調(diào)遞減函數(shù)，因此

R(D)=min{I(U;V);≤D}

=min{I(U;V);

=D}（因?yàn)镽（D）單調(diào)遞減）首先計(jì)算系統(tǒng)的平均失真：其中，pe為信道的平均錯誤概率。因?yàn)榱?ape=D，得pe=D/a，于是根據(jù)范諾不等式有:

所以因此，根據(jù)范諾不等式，一定存在一個試驗(yàn)信道［P(v|u)］，使得在該信道中平均失真=D，且接收端獲得的平均信息量I(U;V)可以達(dá)到上述不等式的下界，即

于是可得r元等概信源在漢明失真函數(shù)下的信息率失真函數(shù)R(D)為由于上述討論中我們假定存在一個反向試驗(yàn)信道，因此對于反向試驗(yàn)信道的合理性還需要作進(jìn)一步的論證，即設(shè)法找到一個試驗(yàn)信道，在該信道中平均失真＝D，且接收端獲得的平均信息量:

為此，我們構(gòu)造一個反向信道,如圖8-7所示，并用該反向信道作為試驗(yàn)信道。首先，我們需要驗(yàn)證一下該反向信道是否存在，或者說是否合理，即驗(yàn)證下列條件是否成立：且圖8-7反向試驗(yàn)信道根據(jù)已知條件P(ui)=1/r及反向信道的信道轉(zhuǎn)移概率：

可由公式:

求得r元方程組的解：

顯然:

所以該反向信道是一個合理的信道?，F(xiàn)在，我們用該反向信道作為試驗(yàn)信道，并計(jì)算在該試驗(yàn)信道中的平均失真及接收端獲得的平均信息量I(U;V)：因此：

可見，在所選擇的反向試驗(yàn)信道中平均失真=D，且接收端獲得平均互信息達(dá)到最小值。因此，在漢明失真函數(shù)定義下，r元等概信源的信息率失真函數(shù)R(D)為根據(jù)r的不同取值，可做出R(D)的曲線,如圖8-8所示。由曲線圖可以看出，對于同一失真限度D，r越大，R(D)越大，信源壓縮的可能性就越?。环粗?/p>

r越小，R(D)越小，信源壓縮的可能性就越大。這一規(guī)律對于實(shí)際信源的量化分層及數(shù)據(jù)壓縮有深刻的理論指導(dǎo)意義。圖8-8r取不同值時的R（D）函數(shù)8.3.3信息率失真函數(shù)的參量表示根據(jù)R(D)的定義式，對于給定的信源（P(u)固定），在定義了具體的失真函數(shù)后，就可求得信源的R(D)函數(shù)，方法上與求信道的信道容量一樣，是一個在有約束的條件下計(jì)算平均互信息I(U;V)的極小值問題，即選擇適當(dāng)?shù)脑囼?yàn)信道P(v|u)使平均互信息：(8.26)最小化，并使得P(vj|ui)滿足以下約束條件：P(vj|ui)≥0i=1,2,…,r;j=1,2,…,s

(8.27)(8.28)和

(8.29)因此，可采用拉格朗日乘子法進(jìn)行求解。但是如果要求得到明顯的解析式，那么也是比較困難的，通常只能用參量形式來表達(dá)。即便如此，除簡單情況外，實(shí)際計(jì)算仍然是相當(dāng)困難的，尤其約束條件式(8.27)是求解R（D）函數(shù)的主要障礙。因?yàn)閼?yīng)用拉格朗日乘子法解得的一個或幾個P(vj|ui)很可能是負(fù)的，所以在這種情況下，必須假設(shè)某些P(vj|ui)=0，然后重新計(jì)算，這就使得計(jì)算復(fù)雜化了。目前，可采用收斂的迭代算法在計(jì)算機(jī)上求解R(D)函數(shù)。下面介紹拉格朗日乘子法求解R(D)函數(shù)，并用S作為參量來表述信息率失真函數(shù)R（D）和平均失真函數(shù)D（S）。值得說明的是，為了討論和書寫方便，平均互信息表達(dá)式（式(8.26)）中采用了自然對數(shù)的形式。首先，構(gòu)造一輔助函數(shù)Φ，在該輔助函數(shù)中暫且不考慮約束條件式(8.27)，僅考慮約束條件式(8.28)和式(8.29)。其中，約束條件式(8.28)包含r個等式，取拉格朗日乘子μi(i=1,2,…,r)分別與之對應(yīng),并取拉格朗日乘子S與式(8.29)對應(yīng)。

(8.30)求平均互信息I(U;V)的極小值，實(shí)質(zhì)上就是求輔助函數(shù)Φ的一階導(dǎo)數(shù)等于零的方程組的解。因?yàn)镮(U;V)是信道轉(zhuǎn)移概率P(v|u)的下凸函數(shù)，所以若極值存在，則它一定是極小值，即求：

(8.31)因?yàn)橛忠驗(yàn)橛谑堑?

當(dāng)i=1,2,…,r和j=1,2,…,s分別取值時，式(8.32)共有r×s個方程，加上式(8.28)的r個方程，共有r+1+r×s個方程。而其中未知數(shù)ui(i=1,2,…,r)、S和P(vj|ui)(i=1,2,…,r;j=1,2,…,s)的個數(shù)也正好為r+1+r×s個，所以原則上求極小值的問題已解決。只需求解式(8.28)、式(8.29)和式(8.32)組成的方程組，即可求出I(U;V)在約束條件下的極小值。(8.32)為了求解方便，令μi=P(ui)lnλi，并整理式(8.32)得：

(8.33)求解式(8.33)可得r×s個信道轉(zhuǎn)移概率：

(8.34)將式(8.34)對j求和得：

即

(8.35)再將式(8.34)兩端同乘以P(ui)并對i求和得：

若P(vj)≠0，則可得：

(8.36)將式(8.35)代入式(8.36)得：

(8.37)由式(8.37)中的S個方程就可以解出S個輸出符號的概率P(vj)，然后將所求的P(vj)代入式(8.35)即可求出λi。若將式(8.35)代入式(8.34)，則得：

(8.38)將由式(8.37)求得的P(vj)代入式(8.38)，即可求得I(U;V)取極小值時的試驗(yàn)信道的轉(zhuǎn)移概率P(vj|ui)。應(yīng)該強(qiáng)調(diào)的是，這里所得的結(jié)果是以S為參量的表達(dá)式，而不是顯式表達(dá)式。因而所得到的R(D)的表達(dá)式也將是以S為參量的表達(dá)式。參量S對應(yīng)的約束條件為式(8.29)，它與允許的失真限度D有關(guān)，所以以S為參量就相當(dāng)于以D為參量。將式(8.34)分別代入式(8.29)和式(8.26)，可得到以S為參量的信息率失真函數(shù)R(S)和平均失真函數(shù)D(S)。(8.40)(8.41)可見，當(dāng)參數(shù)S給定某一數(shù)值時，可由式(8.37)求出P(vj)(j=1,2,…,s),再由式(8.35)計(jì)算出λi(i=1,2,…,r)，將所求的結(jié)果代入式(8.39)和式(8.40)即可確定R(D)的值。由于P(vj)(j=1,2,…,s)不能是負(fù)值，所以參量S的取值有一定的限制。現(xiàn)在我們來分析一下參量S的物理意義及其可能取值的范圍。由于D是參量S的函數(shù)，λi也是S的函數(shù)，因此，也可以把S看成是D的函數(shù)，則λi也是D的函數(shù)。首先求R(S)對D的導(dǎo)數(shù)，得：(8.41)將式(8.36)對S求導(dǎo)，則得：

將上式兩端同乘以P(vj)，并對j求和，得：即

考慮式(8.35)，上式可簡化為將上式代入式(8.41)可得：

(8.42)式(8.42)表明，參量S是信息率失真函數(shù)R(D)的斜率。由于信息率失真函數(shù)R(D)是D的單調(diào)遞減的下凸函數(shù)，所以斜率S必為非正且遞增(即dS/dD>0)。當(dāng)D由Dmin增大至Dmax時，

S的數(shù)值也隨之由Smin增至Smax。當(dāng)Dmin=0時，由式(8.38)可知，等式可變諸因子P(ui)、P(vj)、λi都是非負(fù)值，而各d(ui,vj)也不都等于零。因此，使?jié)M足Dmin=0的條件必使指數(shù)的冪為負(fù)無窮大，即Smin應(yīng)該趨于負(fù)無窮，也就是Dmin=0處R(D)的斜率應(yīng)該趨于負(fù)無窮。當(dāng)D>0時，S隨D而增加。當(dāng)D達(dá)到Dmax時，

S也達(dá)到Smax，但它仍是負(fù)值，當(dāng)然，最大值等于零。一般情況下，在（Dmin，Dmax)區(qū)域內(nèi)S是D的連續(xù)函數(shù)。當(dāng)D>Dmax時，R(D)≡0，當(dāng)然。所以在D=Dmax處，除某些特例外，S在這一點(diǎn)上將不是連續(xù)的，它將從某一負(fù)值跳到零。從上面的分析過程中可以看出，對于一般的離散信源來說，采用上述方法計(jì)算R（D）是相當(dāng)復(fù)雜的。8.4保真度準(zhǔn)則下的信源編碼定理本節(jié)將闡述和證明信息率失真理論的基本定理。這些定理嚴(yán)格地證實(shí)了R（D）函數(shù)確實(shí)是在允許失真為D的條件下，每個信源符號能夠被壓縮的最低值。雖然本節(jié)的討論局限于離散無記憶信源，但所述定理可以推廣到連續(xù)信源、有記憶信源等更一般的情況。8.4.1信源編碼定理及其逆定理

定理8.1

（保真度準(zhǔn)則下的信源編碼定理）設(shè)R(D)為一離散無記憶信源的信息率失真函數(shù)，并且有有限的失真測度。對于任意D≥0,ε>0，以及任意足夠長的碼長k，一定存在一種信源編碼C，其碼字個數(shù)為M=e{k［R(D)+ε］}

(8.43)而編碼后的平均失真度:d(C)≤D+ε如果用二元編碼，R(D)取比特為單位，則上式M可寫成:M=2{k［R(D)+ε］}該定理又稱為香農(nóng)第三定理。該定理告訴我們：對于任意失真度D≥0，只要碼長k足夠長，總可以找到一種編碼C，使編碼后每個符號的信息傳輸率:

(8.44)即R′≥R(D)而碼的平均失真度:d(C)≤D

證明：令離散無記憶信源的符號集及其概率分布為

接收再現(xiàn)的符號V=［v1,v2,…,vs］。對于給定的有限失真函數(shù)d(ui,vj)，存在R(D)函數(shù)?？偪梢哉业侥骋辉囼?yàn)信道［P(v|u)］，使達(dá)到：I（U;V）=R(D)

(8.45)并且E［d(ui,vj)］≤D

(8.46)現(xiàn)考慮信源U輸出的是長度為k的信源符號序列U=(U1U2…Uk)，其中每個變量Ul∈U。因而其中:

同理，接收再現(xiàn)的符號序列：

其中:于是，根據(jù)失真函數(shù)的定義有：

若假設(shè)滿足式(8.45)、式(8.46)的試驗(yàn)信道是無記憶的，則根據(jù)信源和信道都是無記憶的可得：(8.47)(8.50)(8.48)(8.49)并有:Rk(D)=kR(D)

(8.51)現(xiàn)在定義一種信源編碼C={β1,β2,…,βM}，它包含M個碼字，并屬于Vk空間的某一子集。每個碼字是長度為k的接收序列。當(dāng)用碼C對信源［U,P］的輸出進(jìn)行編碼時，就是將信源序列集Uk中的每個序列αi一一映射到碼C中。映射的原則是將每一個信源序列αi變換成失真最小的那個碼字βj，即f(αi)=βj

αi∈Uk使?jié)M足:

(8.52)因?yàn)樾旁淳幋a是一一對應(yīng)的，所以可以把這種編碼方法看成是一個特殊的假設(shè)信道P0(βj|αi)，它滿足:因此，根據(jù)平均失真的定義式可知，該碼中每個信源符號的平均失真為

(8.53)現(xiàn)在考慮碼C是由隨機(jī)選擇的碼字所組成的，即每個碼字都是按照式(8.50)的概率分布P(βj)從Vk集中任意選取的，并且每個碼字的選取是彼此獨(dú)立的，因此碼C的發(fā)生概率為

(8.54)在隨機(jī)選擇信源編碼的情況下，可以得到skM種不同的碼。在這skM種隨機(jī)編碼的信源碼集中，總的平均失真度為式中,d(C)是隨機(jī)選擇的每種信源編碼的平均失真度，與式(8.53)相同。所以將式(8.53)代入得：

(8.55)將信源序列集Uk分成兩個子集S和T，即

其中,δ是大于零的任意整數(shù)。所以得：(8.56)根據(jù)子集S的定義，顯然有:

令Dmax是d(ui,vj)的最大失真度，所以顯然，子集T中的序列αi滿足:

代入式(8.56)得

(8.57)根據(jù)式(8.52)可知，只有當(dāng)碼字βj∈C，d(αi，βj)>k(D+δ)時，d(αi,f(αi))才大于k(D+δ)。因此，設(shè)一示性函數(shù):這樣使式(8.57)中有限制的求和號變?yōu)闊o限制的求和號，即于是，式(8.57)變換成:

若某函數(shù)f(x)是定義在集合A上的，則有關(guān)系式:

根據(jù)上式可得:(8.58)現(xiàn)在需要估計(jì)式(8.58)中括號內(nèi)求和號的上限值。因此，進(jìn)一步定義示性函數(shù):

其中：

而P(βj|αi)和P(βj)分別滿足式(8.48)和式(8.50)。比較所定義的兩種示性函數(shù)得：Δ0(αi,βj)≤Δ(αi,βj)因此當(dāng)Δ0(αi,βj)=1時，αi與βj滿足:于是，式(8.58)中括號項(xiàng)為(8.59)利用以下不等式:(1－xy)M≤1－x+e－yM0≤x,y≤1;M>0現(xiàn)令代入式(8.59)得:

將上式代入式(8.58)，得:(8.60)首先，若取M=ek［R(D)+4δ］，則當(dāng)k→∞時，式(8.60)右邊大括號內(nèi)最后一項(xiàng)趨于零。只要k選取足夠大，就可使該項(xiàng)小于δ/Dmax，因此，式(8.60)成為

(8.61)其次，考慮上式的最后一項(xiàng)。根據(jù)Δ0(αi,βj)的定義可知，式(8.61)最后一項(xiàng)求和號是有限制的。它只對或者滿足條件d(αi,βj)>k(D+δ)，或者滿足條件I(αi,βj)>k［R(D)+δ］的αi和βj求和。根據(jù)概率關(guān)系得：(8.62)因?yàn)?/p>

它是服從同一概率分布的k個彼此統(tǒng)計(jì)獨(dú)立的隨機(jī)變量之和，且每個隨機(jī)變量d(ui,vj)的均值E［d(ui,vj)］≤D，所以，根據(jù)弱大數(shù)定理有：同理，因?yàn)?/p>

所以根據(jù)大數(shù)定理又可得：對于足夠長的k，可使：

(8.63)聯(lián)合式(8.61)~式(8.63)，當(dāng)k足夠大時，得：

令ε=4δ得：而此時碼字個數(shù)為M=ek［R(D)+ε］

所以證得在隨機(jī)選擇的信源編碼集中，每一碼集含有M=ek［R(D)+ε］個碼字，并且總的平均失真度(C)≤D+ε。那么，在該隨機(jī)信源編碼集中至少必有一個碼C，它的平均失真度d(C)≤d(C)≤D+ε。因此，只要證得碼長k足夠長，就一定存在一種信源編碼，其含有M個碼字，而碼的平均失真度(C)≤D+ε。

定理8.2（信源編碼逆定理）不存在平均失真度為D，而平均信息傳輸率R′<R(D)的任何信源編碼，亦即對任意碼長為k的信源編碼C，若碼字個數(shù)M<ek［R(D)］，則一定有d(D)>D。逆定理告訴我們：如果編碼后平均每個信源符號的信息傳輸率R′小于信息率失真函數(shù)R(D)，則不能在保真度準(zhǔn)則下再現(xiàn)信源的消息。下面用反證法來證明此逆定理。

證明：設(shè)存在一種信源編碼C={β1,β2,…,βM}，M<ek［R(D)］，它使得d(C)≤D。信源碼與信源序列αi的變換關(guān)系仍采用式(8.52)的方法。這種編碼方法可看成是一種特殊的試驗(yàn)信道P0(βj|αi)，它滿足:根據(jù)假設(shè)在這個試驗(yàn)信道中，可得d(C)≤D。又因?yàn)樵谶@個信道中，H(V|U)=0，所以，平均互信息：I（U;V）=H(V)≤logM因?yàn)樾旁碪是離散無記憶信源，所以有：

將上式兩端分別除以k得：設(shè)Ul以平均失真Dl≤D再現(xiàn)，則必有:R(Dl)≤I(Ul;Vl)又根據(jù)信息率失真函數(shù)的下凸性和單調(diào)遞減性得：因此得：即M≥ek［R(D)］這個結(jié)果與前面的假設(shè)相矛盾，所以逆定理成立。8.4.2編碼定理的意義保真度準(zhǔn)則下的信源編碼定理及其逆定理在實(shí)際的通信理論中有著重要的意義。這兩個定理證實(shí)了允許失真限度D確定后，總存在一種信源編碼方法，使編碼的信息傳輸率R′大于R(D)且可任意接近于R(D)，而平均失真度小于允許的失真限度D。反之，若R′<R(D)，則編碼的平均失真度將大于D。如果用二元碼符號來進(jìn)行編碼，則在允許一定失真限度D的情況下，平均每個信源符號所需二元碼符號個數(shù)的下限值就是R（D）。由香農(nóng)第三定理可知，R（D）確實(shí)是允許失真限度D的情況下信源壓縮的下限值。比較香農(nóng)第一定理和香農(nóng)第三定理可知，當(dāng)信源給定后，無失真信源壓縮的極限值是信源的信息熵H(U)；有失真壓縮的極限值是信息率失真函數(shù)R(D)。在給定某D后，一般R(D)<H(U)。因此，香農(nóng)第三定理是有失真（限失真）信源壓縮的理論基礎(chǔ)。另外，把香農(nóng)第二定理和香農(nóng)第三定理結(jié)合起來，可得信息傳輸?shù)牧硪粋€重要結(jié)論,即通過某信道來傳輸信源輸出的消息，若信道的信道容量C>R(D)，則在信源和信道處用足夠復(fù)雜的處理后，總能以保真度D+ε再現(xiàn)信源的消息；反之，若C<R(D)，則不管如何處理，在信道的接收端總不能以保真度D的要求再現(xiàn)信源的消息。在給定信源U和允許的失真限