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

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

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

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

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

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

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

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

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

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

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

12、最小值的最小值Dmin 在給定的失真測度矩陣中，對每一個在給定的失真測度矩陣中，對每一個xi，找找一個最小的一個最小的 d i j ，然后對所有的然后對所有的i =1, 2, ,I求統求統計平均值，就是計平均值，就是D的最小值，即的最小值，即 (4-14) (4-14) ijiyidxqDjmin)(min 2. R R( (D D) )的定義域的定義域4.2.2 率失真函數的值域、定義域率失真函數的值域、定義域 1.R R( (D D) )的值域（的值域（參見圖參見圖4-1） 率失真函數的值域為率失真函數的值域為 0 R（D） H（X） (4-13) (4-13) D圖41 R（D）的值域D

13、max0DminH（X）R(D)求出計算求出計算Dmax的顯式的顯式: : j =1,2, , J（4-184-18） IiijijdxqD1max)(min（2）D的最大值的最大值Dmax 當當R (D) 達到其最小值達到其最小值Rmin（D）= 0時，對應的失真時，對應的失真最大，這種情況下最大，這種情況下D對應著對應著R (D) 函數定義域的上界值函數定義域的上界值Dmax，如圖如圖4-1所示。所示。=minD: I (X; Y ) = 0 （4-15)4-15) 0:minmaxDRDD 縱上所述，縱上所述，R(D)的定義域為：的定義域為：D min D D max，式中式中D min

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

15、0，x2=1,其概率分布為 ,0.5，信道輸出符號Y = y1=0，y2=1，失真測度為漢明（Hamming）失真測度，求率失真函數R(D)。 1)(21xxXpX (1) 根據式(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 率失真函數的計算率失真函數的計算根據熵的性質 H（XY） H (X) H (XY)，又算出 H (X) = - log

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

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

18、熵： = - (1-D) log (1-D) - D log D= H2 (D)則平均互信息量I (X; Y) = H (X) -H (XY) = H2 () - H2 (D )， 假設的(xy)確實在滿足 的條件下，使 I (X; Y) = H2 () - H2 ( D )。從而有 2121)(log)()(ijjijijyxyxyYXHDD DDDHHDR00)(22DD DD 由上式知 ，滿足失真條件 。 （5）要找出正向信道，可由 ，反解出(yj)， j = 1, 2，再計算出 。=（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】 信源分布 ，失真測度矩陣為: ，計算率失真函數 313131)(321xxxXqX 1211213212

20、1xxxyyd DR(1) 求出R(D)的定義域34431, 431min111131maxminDD（2)計算R (D)根據d的對稱性，可假設信道轉移概率矩陣 , 式中 為待定常數。由假設的信道轉移概率計算信息量 （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）由假設的信道轉移概率計算平均失真，得 （4-36）3121321212)1 (231)()(ijjiiijdxqxypD因為 ，由式(4-36)得 考慮到 ，則DD D321123D34maxD2113423如圖4-3所示：在 的范圍內，H2()是單調遞增函數，有 210123)(22DHHH2()圖 4-3 H2()- 曲線010.5根據式(4-35)，得從而 1232log32;2DHYXI 34103411232log322DDDDHDR，4.3.2 R（D）的參數表示法的參數表示法 (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)()(用參數法求R (D)， 可按下述步驟進行：（1）由式(4-41) 求 ；iJjxqeiisdiij,2, 1)(1用此法求解，有時候會出現(yj)0的情況碰到這種情況，就要令某一(y*j) = 0，重復剛才的求解過程，這種情況下求得的R (D)是一折線，折點對應(y*j) = 0，如圖45所示。圖4-5(y*j) 0的情況D0對應(y*j) = 0R (D)【例4.10】 仍考慮例4.8的輸入概率分布q (x1) = ，q (x2) = 1， R(D)時，時， 只要信源序列長度只要信源序列長度L足夠長，足夠長， 必存在一種編碼方式必存在一種編碼方式C， 使譯碼后的失真使譯碼后的失真 且當且當L時，時， 0反之反之, 若若RR(D) 則必可設計一種編碼方式則必可設計一種編碼方式,滿足滿足 若系統若系統R R(D) 則無法滿足則無法滿足 要求要求2.逆定理逆定理若已規定滿足失真度準則若已規定滿足失真度準則 , 則對所有設計均有則對所有