信息論第四章失真率函數(shù)

1、第第4章章率失真編碼率失真編碼 內(nèi)容提要數(shù)據(jù)壓縮是信息傳輸和處理的重要研究?jī)?nèi)容，率失真理論研究的就是在允許一定失真的前提下，對(duì)信源的壓縮編碼。率失真信源編碼定理（香農(nóng)第三定理）指出：率失真函數(shù)R (D) 就是在給定失真測(cè)度條件下，對(duì)信源熵可壓縮的最低程度。本章只限于研究率失真理論最基本的內(nèi)容，失真測(cè)度，率失真函數(shù)，率失真函數(shù)的定義域，值域，性質(zhì)及定量計(jì)算。R (D) 的計(jì)算很煩瑣，文中通過二個(gè)例子介紹了幾種特殊情況下R (D )的求法，一般情況只能用參數(shù)法求解。第第4章章 率失真編碼率失真編碼信息率失真函數(shù)信息率失真函數(shù)R(D)香農(nóng)香農(nóng)1959年提出年提出 在允許一定在允許一定失真度失真度D的

2、情況下，的情況下， 信源輸出的信源輸出的信息率可壓縮為信息率可壓縮為R(D)值值 數(shù)據(jù)壓縮的理論基礎(chǔ)數(shù)據(jù)壓縮的理論基礎(chǔ)I(X;Y)H(X)、H(Y/X)的二元函數(shù)的二元函數(shù)固定固定H(Y/X) ，改變改變H(X)得得I(X;Y)最大值最大值 信道容量信道容量固定固定H(X)，改變改變H(Y/X) 得得I(X;Y)最小值最小值 率失真函數(shù)率失真函數(shù)第第4章章 率失真編碼率失真編碼1失真測(cè)度失真測(cè)度d( x, y ) 給定離散信源給定離散信源 ，信道信道 輸出符號(hào)輸出符號(hào)yj引起的失真用引起的失真用 d (xi ,y j)（i =1, ,I j = 1, , J）表示，簡(jiǎn)記為表示，簡(jiǎn)記為d i j

3、，將所有的將所有的d i j列出來(lái)，可以得到下面的失真列出來(lái)，可以得到下面的失真測(cè)度矩陣測(cè)度矩陣)()()()(2121IIxqxqxqxxxXqX JIIIJJdddddddddd212221211211(4-1)(4-1) 在允許一定失真的前提下，從提高傳輸效率的角度出發(fā)，在允許一定失真的前提下，從提高傳輸效率的角度出發(fā)，可以對(duì)信源信息量事先進(jìn)行壓縮再予傳輸，這章要討論的可以對(duì)信源信息量事先進(jìn)行壓縮再予傳輸，這章要討論的問題就是給定一個(gè)失真度，求出在平均失真小于給定值的問題就是給定一個(gè)失真度，求出在平均失真小于給定值的條件下，信源所能壓縮的最低程度，即率失真函數(shù)條件下，信源所能壓縮的最低程

4、度，即率失真函數(shù)R( (D) )。4.1 4.1 失真測(cè)度與平均失真失真測(cè)度與平均失真【例例4.1】 漢明漢明（Hamming）失真測(cè)度失真測(cè)度信源輸出符號(hào)X = x1, x2, , xK，信道輸出符號(hào)Y = y1, y2, , yK，約定失真測(cè)度上述約定可以用矩陣表示為 式中di j 0 i, j = 1, 2, , K為信源方發(fā)送符號(hào)為信源方發(fā)送符號(hào)xi而信宿方判為而信宿方判為yj引起的失真度。引起的失真度。Kjidjixydxyijijiiii, 2 , 1,1)(0誤碼無(wú)誤碼 011101110d對(duì)于矢量傳輸情況，若信道的輸入、輸出均為對(duì)于矢量傳輸情況，若信道的輸入、輸出均為N 長(zhǎng)序列

5、長(zhǎng)序列X = X1 X2 XN ，Y = Y1 Y2 YN ，定義失真測(cè)度為定義失真測(cè)度為 NkkkNYXdNd1)(),(1),(Y YX X（4-2）【例例4.2】 平方誤差失真測(cè)度平方誤差失真測(cè)度信源輸出符號(hào)X = 0, 1, 2， 信道輸出符號(hào)Y = 0, 1, 2 ， 給出失真測(cè)度d i j = (xi - yj )2 i, j = 0, 1, 2則失真測(cè)度矩陣為 014101410d【例例4.3】 絕對(duì)值誤差失真測(cè)度絕對(duì)值誤差失真測(cè)度信源輸出符號(hào)X = 0, 1, 2，信道輸出符號(hào)Y = 0, 1, 2 ，給出失真測(cè)度d i j = xi - yj i, j = 0, 1, 2則失

6、真測(cè)度矩陣為 012101210d2.平均失真平均失真離散信源離散信源 ，經(jīng)有擾信，經(jīng)有擾信道傳輸，信道輸出符號(hào)為道傳輸，信道輸出符號(hào)為Y = y1, y2, , yJ，平均失真即對(duì)平均失真即對(duì)d i j（i =1, 2, ,I; j = 1, 2, , J）求統(tǒng)計(jì)平均值，記為求統(tǒng)計(jì)平均值，記為 （4-4）)()()()(2121IIxqxqxqxxxXqXjiIiJjjidyxpD11)(jiIiJjijidxypxq11)()(平均失真平均失真 是對(duì)在給定信源分布是對(duì)在給定信源分布q(x)條件下，通過條件下，通過有擾信道傳輸而引起失真的統(tǒng)計(jì)平均度量。有擾信道傳輸而引起失真的統(tǒng)計(jì)平均度量。

7、D平均失真說(shuō)明：平均失真說(shuō)明：是在是在平均意義平均意義上，對(duì)系統(tǒng)失真的總體描述上，對(duì)系統(tǒng)失真的總體描述是信源統(tǒng)計(jì)特性是信源統(tǒng)計(jì)特性p(xi)的函數(shù)的函數(shù) 是信道統(tǒng)計(jì)特性是信道統(tǒng)計(jì)特性p(yj / xi)的函數(shù)的函數(shù) 是規(guī)定失真度是規(guī)定失真度 d(xi, yj)的函數(shù)的函數(shù) 若保持若保持p(xi)、d(xi, yj) 不變，則平均失真不變，則平均失真度就是信道特性度就是信道特性p(yj / xi)的函數(shù)的函數(shù)N次擴(kuò)展信道次擴(kuò)展信道 對(duì)于矢量傳輸情況，若信道的輸入、輸出符號(hào)均為對(duì)于矢量傳輸情況，若信道的輸入、輸出符號(hào)均為N長(zhǎng)序列長(zhǎng)序列X=X1，,Xk,XN, , Y=Y1，,Yk,YN, ，平均失

8、真定義為平均失真定義為 （4-5） NkkjkiIiJjkjkiNkkNyxdyxpNDND1111)(),(),(11（4-54-5）式表明了離散無(wú)記憶）式表明了離散無(wú)記憶N N次擴(kuò)展信道的輸入輸出符號(hào)之次擴(kuò)展信道的輸入輸出符號(hào)之間平均失真等于單個(gè)符號(hào)間平均失真等于單個(gè)符號(hào)x xkiki,y,ykjkj之間失真統(tǒng)計(jì)值的總和。之間失真統(tǒng)計(jì)值的總和。,.,21IkxxxX,.,21JkyyyY 若矢量信源是原離散無(wú)記憶信道的若矢量信源是原離散無(wú)記憶信道的N次擴(kuò)展，且矢次擴(kuò)展，且矢量信道也是原離散無(wú)記憶信道的量信道也是原離散無(wú)記憶信道的N次擴(kuò)展，則每個(gè)次擴(kuò)展，則每個(gè) 對(duì)一位信源信道所取的均值相等，

9、即對(duì)一位信源信道所取的均值相等，即從而，從而， kDDDN)(DDDDNk.1Nk,.,2 , 14.2.1 率失真函數(shù)的定義率失真函數(shù)的定義給定信源，即信源概率分布給定信源，即信源概率分布q (x) 一定，給定失真測(cè)度矩陣一定，給定失真測(cè)度矩陣 d=dij ，尋找信道，記它的轉(zhuǎn)移概率矩陣為尋找信道，記它的轉(zhuǎn)移概率矩陣為 ，要求滿足，要求滿足 （4-114-11）式中式中D是預(yù)先給定的失真度，上式稱為是預(yù)先給定的失真度，上式稱為保真度準(zhǔn)則保真度準(zhǔn)則。ijiijjiDdxypxqD)()()(ijxypP P4.2 4.2 信息率失真函數(shù)信息率失真函數(shù)R(D)根據(jù)根據(jù)定理定理2.2，當(dāng)信源，當(dāng)信

10、源q (x)一定時(shí)，平均互信息量一定時(shí)，平均互信息量I (X ; Y)是信道轉(zhuǎn)移概率函數(shù)是信道轉(zhuǎn)移概率函數(shù)p(y x)的的型凸函數(shù)，這意味著可以型凸函數(shù)，這意味著可以關(guān)于關(guān)于p(y x)對(duì)平均互信息量對(duì)平均互信息量I (X ; Y)求得極小值，定義這個(gè)求得極小值，定義這個(gè)極小值為極小值為率失真函數(shù)率失真函數(shù)R(D)，即：即： (4-12)(4-12) DDYXIDRxyp:;min)(式式(4-12)的意義在于，選擇的意義在于，選擇p(y x)即選擇某種編碼方法在滿足即選擇某種編碼方法在滿足 的的 前提下，使前提下，使I (X ; Y) 達(dá)到最小值達(dá)到最小值R(D) ，這就是滿足平這就是滿足平

11、均失真均失真 條件下的信源信息量可壓縮的最低程度。條件下的信源信息量可壓縮的最低程度。DD DD 補(bǔ)充：試驗(yàn)信道補(bǔ)充：試驗(yàn)信道(D允許信道允許信道)PD1.定義：定義：固定信源固定信源(H(X)時(shí)，時(shí)，滿足失真度滿足失真度準(zhǔn)則準(zhǔn)則 的所有轉(zhuǎn)移概率的所有轉(zhuǎn)移概率p(y/x)的集合的集合2.單單符號(hào)信源、單符號(hào)信道的試驗(yàn)信道符號(hào)信源、單符號(hào)信道的試驗(yàn)信道3.N次擴(kuò)展信源、次擴(kuò)展信源、N次擴(kuò)展信道的次擴(kuò)展信道的PD(N)()DD (/):1,1DjiPp yxDDin jm() (/):()1,1NND NjiPp baD NNDinjm4.2 4.2 信息率失真函數(shù)信息率失真函數(shù)R(D)（1）D的

12、最小值的最小值Dmin 在給定的失真測(cè)度矩陣中，對(duì)每一個(gè)在給定的失真測(cè)度矩陣中，對(duì)每一個(gè)xi，找找一個(gè)最小的一個(gè)最小的 d i j ，然后對(duì)所有的然后對(duì)所有的i =1, 2, ,I求統(tǒng)求統(tǒng)計(jì)平均值，就是計(jì)平均值，就是D的最小值，即的最小值，即 (4-14) (4-14) ijiyidxqDjmin)(min 2. R R( (D D) )的定義域的定義域4.2.2 率失真函數(shù)的值域、定義域率失真函數(shù)的值域、定義域 1.R R( (D D) )的值域（的值域（參見圖參見圖4-1） 率失真函數(shù)的值域?yàn)槁适д婧瘮?shù)的值域?yàn)?0 R（D） H（X） (4-13) (4-13) D圖41 R（D）的值域D

13、max0DminH（X）R(D)求出計(jì)算求出計(jì)算Dmax的顯式的顯式: : j =1,2, , J（4-184-18） IiijijdxqD1max)(min（2）D的最大值的最大值Dmax 當(dāng)當(dāng)R (D) 達(dá)到其最小值達(dá)到其最小值Rmin（D）= 0時(shí)，對(duì)應(yīng)的失真時(shí)，對(duì)應(yīng)的失真最大，這種情況下最大，這種情況下D對(duì)應(yīng)著對(duì)應(yīng)著R (D) 函數(shù)定義域的上界值函數(shù)定義域的上界值Dmax，如圖如圖4-1所示。所示。=minD: I (X; Y ) = 0 （4-15)4-15) 0:minmaxDRDD 縱上所述，縱上所述，R(D)的定義域?yàn)椋旱亩x域?yàn)椋篋 min D D max，式中式中D min

14、和和D max可分可分別由式（別由式（4-14）和式（）和式（4-18）求出。）求出。 4.2.3 率失真函數(shù)率失真函數(shù)的性質(zhì)的性質(zhì) 率失真函數(shù)有如下幾條性質(zhì):： 3.對(duì)于離散無(wú)記憶信源（對(duì)于離散無(wú)記憶信源（DMS） R (N ) (D) = N R (D) 2. R(D)是是D的連續(xù)、單調(diào)、減函數(shù)的連續(xù)、單調(diào)、減函數(shù) 1.R(D)是是D的的型凸函數(shù)型凸函數(shù)分別給定兩個(gè)失真度D1和D2（Dmin D1, D2 Dmax），則下式成立： R (1D1+2D2) 1R (D1)+2 R (D2) （4-19） 4.3.1二種特殊情況下的求解二種特殊情況下的求解 【例例4.8】 信源含兩個(gè)消息x1=

15、0，x2=1,其概率分布為 ,0.5，信道輸出符號(hào)Y = y1=0，y2=1，失真測(cè)度為漢明（Hamming）失真測(cè)度，求率失真函數(shù)R(D)。 1)(21xxXpX (1) 根據(jù)式(4-14)和(4-18)可求出R(D)的定義域 Dmin = 0+0(1-) = 0 D max = min 1-, = (2) 求R(D)的值域R (Dmin=0) = H(U ) = -log- (1-) log (1-) = H2 () R (Dmax) = R () = 0 4.3 4.3 率失真函數(shù)的計(jì)算率失真函數(shù)的計(jì)算根據(jù)熵的性質(zhì) H（XY） H (X) H (XY)，又算出 H (X) = - log

16、 -(1-) log (1-) = H2 ( )將這兩個(gè)結(jié)果代入平均互信息量的表達(dá)式 I (X; Y) = H (X) -H (XY)，得到 I (X; Y ) H2 () -H (XY) （4-32） （3）在0 D 的范圍內(nèi)，計(jì)算R(D ）對(duì)于漢明失真測(cè)度，失真測(cè)度矩陣為平均失真 在R(D)的定義中，要求滿足 ，取等號(hào) ，則 H（XY）= H2（XY）= H2 p (XY ) = H2 (D)將這一結(jié)果代入式（4-32），得I（X；Y） H2 ()- H2 (D) 根據(jù)定義 = H2 ()- H2 (D ) 0110d2121)()(ijjijiYXpdyxpDDD DD DDYXIDRx

17、yp:;min)(根據(jù)d的對(duì)稱性，假設(shè)一個(gè)反向信道(YX ) DDDDxxyyyx11)(2121反向信道的轉(zhuǎn)移概率矩陣為，假設(shè)的反向信道應(yīng)滿足： (xiyj) 0 i, j = 1,2211)(ijiyx211)(jijxyp（4）上面是按照定義求出了R(D)，下面的問題是要真正找到這么一個(gè)信道轉(zhuǎn)移概率矩陣為P的信道，使H（YX）= H2（D），從而R(D)= H2 () - H2 (D)，且P中的每一個(gè)元素p (yjxi) 都滿足p (yjxi) 0 i, j = 1,2由假設(shè)的反向信道計(jì)算平均失真，得 = (y1) +(y2) D = D 2121)()(ijjijjidyyxD計(jì)算條件

18、熵： = - (1-D) log (1-D) - D log D= H2 (D)則平均互信息量I (X; Y) = H (X) -H (XY) = H2 () - H2 (D )， 假設(shè)的(xy)確實(shí)在滿足 的條件下，使 I (X; Y) = H2 () - H2 ( D )。從而有 2121)(log)()(ijjijijyxyxyYXHDD DDDHHDR00)(22DD DD 由上式知 ，滿足失真條件 。 （5）要找出正向信道，可由 ，反解出(yj)， j = 1, 2，再計(jì)算出 。=（1-D）（y1）+ D (y2)1- = D （y1）+（1-D） (y2)由上面方程組解出， 再算出

19、212, 1)()()(jjjiiivvuuq)()()()(ijjiijxqyyxxypDDy21)(1DDy211)(2)21 ()(1 ()1 ()()()()(21111111DDDDxqyyxxypDD)21 ()1 ()()()()(211122112DDDDxqyyxxypDD)21)(1 ()(1)()()()(21211221DDDDxqyyxxypDD)21)(1 ()1)(1 (1)1 ()()()()(211222222DDDDxqyyxxypDD【例例4. .9】 信源分布 ，失真測(cè)度矩陣為: ，計(jì)算率失真函數(shù) 313131)(321xxxXqX 1211213212

20、1xxxyyd DR(1) 求出R(D)的定義域34431, 431min111131maxminDD（2)計(jì)算R (D)根據(jù)d的對(duì)稱性，可假設(shè)信道轉(zhuǎn)移概率矩陣 , 式中 為待定常數(shù)。由假設(shè)的信道轉(zhuǎn)移概率計(jì)算信息量 （4-33）121211P P XYHYHYXI;312121)(1log)()()(1log)(ijijiijjjjxypxqxypyy3121)(log)(312log;ijijijxypxypYXI)(2log322H21)(1)(2121131)()()(123111yyxqxypyiii先算出 (4-34)將式(4-34)代入式(4-33)得 )(2log32;2HYXI

21、即 （4-35）由假設(shè)的信道轉(zhuǎn)移概率計(jì)算平均失真，得 （4-36）3121321212)1 (231)()(ijjiiijdxqxypD因?yàn)?，由式(4-36)得 考慮到 ，則DD D321123D34maxD2113423如圖4-3所示：在 的范圍內(nèi)，H2()是單調(diào)遞增函數(shù)，有 210123)(22DHHH2()圖 4-3 H2()- 曲線010.5根據(jù)式(4-35)，得從而 1232log32;2DHYXI 34103411232log322DDDDHDR，4.3.2 R（D）的參數(shù)表示法的參數(shù)表示法 (2) 由式(4-40) 求 ；iJjsdjijey1)(1)(jv(3) 由式(4-3

22、9) 求p(yjxi)；ijsdijijeyxyp)()(4) 由式(4-42) 求D；IiJjsdijiijijedxqyD11)()(5) 由式(4-43) 求R (D)。IiiixqsDDR1log)()(用參數(shù)法求R (D)， 可按下述步驟進(jìn)行：（1）由式(4-41) 求 ；iJjxqeiisdiij,2, 1)(1用此法求解，有時(shí)候會(huì)出現(xiàn)(yj)0的情況碰到這種情況，就要令某一(y*j) = 0，重復(fù)剛才的求解過程，這種情況下求得的R (D)是一折線，折點(diǎn)對(duì)應(yīng)(y*j) = 0，如圖45所示。圖4-5(y*j) 0的情況D0對(duì)應(yīng)(y*j) = 0R (D)【例4.10】 仍考慮例4.8的輸入概率分布q (x1) = ，q (x2) = 1， R(D)時(shí)，時(shí)， 只要信源序列長(zhǎng)度只要信源序列長(zhǎng)度L足夠長(zhǎng)，足夠長(zhǎng)， 必存在一種編碼方式必存在一種編碼方式C， 使譯碼后的失真使譯碼后的失真 且當(dāng)且當(dāng)L時(shí)，時(shí)， 0反之反之, 若若RR(D) 則必可設(shè)計(jì)一種編碼方式則必可設(shè)計(jì)一種編碼方式,滿足滿足 若系統(tǒng)若系統(tǒng)R R(D) 則無(wú)法滿足則無(wú)法滿足 要求要求2.逆定理逆定理若已規(guī)定滿足失真度準(zhǔn)則若已規(guī)定滿足失真度準(zhǔn)則 , 則對(duì)所有設(shè)計(jì)均有則對(duì)所有