本_信息論及編碼A_第5章有失真信源編碼

1、1第第5章章 有失真信源編碼有失真信源編碼信息論與編碼 Information and Coding Theory 2第第5 5章章 有失真信源編碼有失真信源編碼5.1 5.1 信息率失真函數(shù)信息率失真函數(shù)5.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質5.3 5.3 限失真信源編碼定理限失真信源編碼定理35.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 編碼器輸入編碼器輸入X：xi a1, a2,an.l 編碼器輸出編碼器輸出Y：yj b1, b2,bm.u無失真無失真: xi=yju有失真有失真: xiyjl 失真函數(shù)失真函數(shù)d(xi,yj)0,( ,)0,ijijijxyd x y

2、xy45.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 失真矩陣失真矩陣111212122212(,)(,)(,)(,)(,)(,)(,)(,)(,)mmnnnmd abd abd abd abd abd abdd abd abd ab55.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 例例5.1.1. 設信源符號X0,1, 編碼器輸出符號Y0,1,2, 規(guī)定失真函數(shù)為 d(0,0 )= d(1,1)=0 d(0,1 )= d(1,0)=1 d(0,2 )= d(1,2)=0.5則失真矩陣為0 1 0.5.1 0 0.5d65.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 均方失真：均方失真：l 絕

3、對失真：絕對失真： l 相對失真：相對失真： l 誤碼失真誤碼失真（適用于離散信源）：2,)()ijijd x yxy（適用于連續(xù)信源適用于連續(xù)信源,) |ijijd x yxy（,)| |ijijid x yxyx（0,(,)(,)1,ijijijijxyd x yx yxy75.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 平均失真：平均失真：l 平均失真平均失真 是對給定信源分布是對給定信源分布p(xi) 經(jīng)過某一轉移概率分布經(jīng)過某一轉移概率分布為為p(yj |xi) 的有失真信源編碼器后產(chǎn)生失真的總體量度。的有失真信源編碼器后產(chǎn)生失真的總體量度。1111( ( ,)( ,) ( ,)(

4、) (|) ( ,)nmijijijijnmijiijijDE d x yp x y d x yp x p yx d x y85.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 序列編碼的失真序列編碼的失真u輸入：輸入：X=(X1, X2,XL)，樣值為，樣值為: x=(x1, x2, xL)u輸出：輸出：Y=(Y1, Y2,YL)，樣值為，樣值為: y=(y1, y2, yL)u失真函數(shù)定義為：失真函數(shù)定義為：11( , )( ,).LLllldx yd x yLu序列編碼的平均失真：序列編碼的平均失真：11 = (,).LLlllDE d x yL95.1 5.1 信息率失真函數(shù)信息率失真函數(shù)

5、l 有失真信源編碼器模型有失真信源編碼器模型u信源編碼目的信源編碼目的 尋找一種編碼方案，使編碼后所需的信息傳輸率R盡量小。u問題問題 R越小，引起的平均失真就越大。u解決方法解決方法 給出一個失真限制值失真限制值D,在滿足平均失真小于D的條件下，尋找一種編碼案使得信息率R最小.DD105.1 5.1 信息率失真函數(shù)信息率失真函數(shù)信源編碼器 有干擾的假想信道 信息傳輸率R I(X;Y)l 有失真信源編碼器模型有失真信源編碼器模型信源編碼器信源編碼器X Y假想信道假想信道xia1,anyjb1,bm115.1 5.1 信息率失真函數(shù)信息率失真函數(shù)11( ) (|) ( ,)nmijiijijDp

6、 a p ba d a b若p(ai)和d(ai,bj)已定，則平均失真由信道轉移概率p(bj|ai)完全確定，所有滿足平均失真小于等于門限D的信道集合信道集合(|):,1,1DjiPp b aDDinjm 125.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 信息率失真函數(shù)信息率失真函數(shù)l 信息率失真函數(shù)信息率失真函數(shù)R(D)的物理意義：的物理意義： 對于給定信源，在平均失真不超過失真限度對于給定信源，在平均失真不超過失真限度D的的情況下，信息率允許壓縮的最小值為情況下，信息率允許壓縮的最小值為R(D) 。()min (, )DPR DI X Yl 離散無記憶信源的信息率失真函數(shù)離散無記憶信源

7、的信息率失真函數(shù)()min (, )(|)min() (|)log()DDPjiijiPjR DI X Yp bap a p bap b135.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 例例. 設信源符號集為A=a1, a2, a2n, 概率分布為: p(ai)=1/2n (i=1,2,2n) ，失真函數(shù)為:1,( ,)0,ijijd a aij 信源熵H(X)=log(2n) bit/符號. 如果對信源進行無失真編碼，平均每個符號至少需要log(2n) 個二進制碼元. 現(xiàn)討論有失真編碼. 假設失真度為D=1/2. 編碼方案為: a1a1, a2 a2, ,an an, an+1 an, ,

8、a2n an 對應一個確定信道確定信道. H(Y|X)=0, I(X; Y)=H(Y)H(Y|X)=H(Y). 信道輸出Y的概率分布為: p(a1)= p(a2)= p(an-1)=1/2n, p(an)=(1+n)/2n I(X; Y)=H(Y) = log(2n) (1+n)/2nlog(1+n).145.1 5.1 信息率失真函數(shù)信息率失真函數(shù)l 例例. 信源傳輸?shù)男畔⒙视蒷og(2n)壓縮到 H(Y)=log(2n) (1+n)/2nlog(1+n).平均失真: （收到100個符號時，允許出錯的符號個數(shù)50） 111( ) (|) ( ,)2nmijiijijDp a p b a d

9、a b15第第5 5章章 有失真信源編碼有失真信源編碼5.1 5.1 信息率失真函數(shù)信息率失真函數(shù)5.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質5.3 5.3 限失真信源編碼定理限失真信源編碼定理165.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質( ) min ( , ),R DI X Y D Dl 單調性單調性0 Dmax DR(D)1212()()DDR DR D175.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質l R(D)的定義域的定義域: Dmin, Dmaxu0 Dmin；R(Dmin)=H(X).min(|)11(|)111min() (|) (,)m

10、in()(|) (,)()min (,)jijinmijiijp b aijnmijiijp b aijniijjiDp a p ba d a bp ap ba d a bp ad a b185.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質max(|)11(|)111()0(; )0( ,)( )()min( ) () ( ,)min()( ) ( ,)min( ) ( ,)jijiijijnmijijp b aijmnjiijp b ajiniijjiR DI X Yp a bp ap bDp a p b d a bp bp a d a bp a d a buDmax: 195.2

11、5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質l R(D)的值域的值域 0 R(D) H(X).205.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質0110),(),(),(),(12122111badbadbadbaddl 例：例：設輸入輸出符號表示為X=Y=0,1, 輸入概率分布p(x)= 1/3,2/3, 失真矩陣為 求Dmin, R(Dmin), Dmax, R(Dmax)以及相應的編碼器轉移概率? 解解: 當Dmin=0時, R(Dmin)=H(X)=H(1/3,2/3)=0.91bit/符號. 這時信源編碼器無失真, a1 b1, a2b2,編碼器的轉移矩陣為:10.01

12、P215.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質 這時的編碼方案為：a1 b2, a2b2,輸出符號概率p(b1)=0, p(b2)=1, 編碼器的轉移矩陣為:0 1.0 1P 當R(Dmax) =0時, 有2max1112211122221,21minmin, 12121 min01, 10.33333iijjiDp dp dp dp dp d 225.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質l R(D)是關于是關于D的下凸函數(shù)的下凸函數(shù)(01)l R(D)是關于是關于D的連續(xù)函數(shù)的連續(xù)函數(shù)11()()DDR DR D1212(1)( )() (1) ()DDDR

13、DR DR D 235.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質l R(D)是關于是關于D的嚴格遞減函數(shù)的嚴格遞減函數(shù)u允許的失真越大,所要求的信息率越小0 Dmax DR(D)H(X)離散系統(tǒng)信息率失真曲線離散系統(tǒng)信息率失真曲線0 Dmax DR(D)連續(xù)系統(tǒng)信息率失真曲線連續(xù)系統(tǒng)信息率失真曲線245.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質)/(),()|()()|(log)/()()()|(log)();(11111,ijiriijiijrisjijijijrisjjixypxpfxypxpxypxypxpypxypyxpYXIl 信道容量與信息率失真函數(shù)的比較信

14、道容量與信息率失真函數(shù)的比較255.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質u當當p(xi)固定，互信息量固定，互信息量I(X;Y)是信道轉移概率概率是信道轉移概率概率分布分布p(yj|xi)的下凸函數(shù)的下凸函數(shù),存在極小值。存在極小值。信息率失真函數(shù)就是假定信源給定的情況下,在試驗信道（滿足保真度準則的信道）中求平均互信息的極小值,即(/)()min(, )jiDp yxPR DI X Y),(max)(YXICixpl 信道容量與信息率失真函數(shù)的比較信道容量與信息率失真函數(shù)的比較u當p(yj|xi)固定，互信息量I(X;Y)是輸入符號概率p(xi)的上凸函數(shù),存在極大值.信道容

15、量就是假定信道固定的前信道容量就是假定信道固定的前提下提下,選擇一種試驗信源，使平均互信息（信息率）最選擇一種試驗信源，使平均互信息（信息率）最大大,即即 265.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質u信道容量反映的是信道傳輸信息的能力，即信道可傳輸?shù)淖畲笮畔⒙省Ｑ芯啃诺廊萘磕康氖浅浞掷靡呀o信道，使傳輸?shù)男畔⒘孔畲蠖l(fā)生錯誤的概率任意小，即信道編碼問題。信道容量是為了解決通信的可靠性問題，是信息傳輸?shù)睦碚摶A，通過信道編碼增加信息的冗余度來實現(xiàn)。u信息率失真函數(shù)反映的是信源可壓縮的程度，即在可以容忍的失真度內再現(xiàn)信源消息所必須獲得的最小平均信息量。研究信息率失真函數(shù)目的是用盡

16、可能少的碼符號盡快地傳送盡可能多的信源消息，以提高通信的有效性問題，即信源編碼問題，是信源壓縮的理論基礎，通過信源編碼減少信息的冗余度來實現(xiàn)。l 信道容量與信息率失真函數(shù)的比較信道容量與信息率失真函數(shù)的比較275.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質u信道容量只與信道轉移概率分布有關，反映信道特性，與信源無關。u信息率失真函數(shù)只與信源概率分布有關，反映信源特性，與信道特性無關。l 信道容量與信息率失真函數(shù)的比較信道容量與信息率失真函數(shù)的比較28第第5 5章章 有失真信源編碼有失真信源編碼5.1 5.1 信息率失真函數(shù)信息率失真函數(shù)5.2 5.2 信息率失真函數(shù)的性質信息率失真函數(shù)的性質5.3 5.3 限失真信源編碼定理限失真信源編碼