信息科學(xué)基礎(chǔ)文2015fis

1、第7章信源的率失真函數(shù)與熵壓縮編碼7.17.2熵壓縮編碼和信源的率失真函數(shù)率失真函數(shù)的基本性質(zhì)2015/6/2馬盡文17.1熵壓縮編碼和信源的率失真函數(shù)信源的冗余度壓縮編碼無失真保熵信源的熵壓縮編碼有失真熵壓縮n 離散信源熵率冗余度有效傳輸(壓縮保熵)n 連續(xù)信源(及一些離散信源)可以有失真(無法保存全部信息)近似表示(減在失真不超過少信息量或降低熵率)一定限度下編碼后熵率壓縮到最小(熵率壓縮)22015/6/2馬盡文7.1熵壓縮編碼和信源的率失真函數(shù)常用的失真函數(shù)：(1)Hamming 失真若 x = y若 x ¹ yd (x, y) = (x - y)2d (x, y) = &#

2、236;0,íî1,(2)平方誤差失真優(yōu)點(diǎn)：簡(jiǎn)單，并且分別與差錯(cuò)概率或最小均方誤差相。缺點(diǎn)：對(duì)于具有延時(shí)信號(hào)不合適，因?yàn)樾〉难訒r(shí)可能帶來大的失真。32015/6/2馬盡文7.1熵壓縮編碼和信源的率失真函數(shù)定義7.1.2 設(shè)x = (x1 ,K, xn ) 與 y = ( y1 ,K, yn )分別表示長(zhǎng)度為n的源字和碼字，那么x 與y之間的（平均或單字母）失真度量為碼的平均失真：字失真的統(tǒng)計(jì)平均其中q(y | x) 為源字x 通過編碼轉(zhuǎn)換為y 的轉(zhuǎn)移概率。實(shí)際上，若采用確定性編碼規(guī)則，則有42015/6/2馬盡文Ed (x, y) = åå p(x)q(

3、y | x)d (x, y)xynd (x, y) = 1 å d ( x , y )niii =17.1熵壓縮編碼和信源的率失真函數(shù)q(y | x) = ì1,如果y是x的編碼其它í0，î通過q(y | x) 在輸入序列與輸出序列之間建立起了一種，其互信息為 I (X; Y) = I ( X n ;Y n ) = H (Y n ) - H (Y n | X n )若將編碼器看作一個(gè)信道,則I (X n ;Y n ) 就是信源通過該信道傳輸?shù)男畔⑺俾省＠硐氲撵貕嚎s編碼器就是在失真限定的情況下信源通過該編碼器達(dá)到最低的傳輸信息速率。該編碼器取決于信源的分布

4、，分組碼長(zhǎng)度 n ，失真p(ak )52015/6/2馬盡文7.1熵壓縮編碼和信源的率失真函數(shù)矩陣和的最大平均失真D 。Rn (D) = minI ( X;Y) : Ed (x, y) £ DnnQ其中，min是在平均失真滿足:Ed (x, y) = åå p(x)q(y | x)d (x, y) £ Dxy的所有的轉(zhuǎn)移概率矩陣 Q 中取的。1 RR(D) = inf(D)nnn稱為信息速率失真函數(shù)，簡(jiǎn)稱為率失真函數(shù)。率失真函數(shù)R(D)給出了熵壓縮編碼可能達(dá)到的最小熵率和失真的關(guān)系。它代表了一定失真水平下所能達(dá) 到的最小信息速率,其逆函數(shù)D(R)稱為失真

5、率函數(shù)。62015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)在具體計(jì)算離散無記憶信源的信息率失真函數(shù)R(D)之前，先對(duì)這一函數(shù)的一般性質(zhì)作一些討論，下面是R(D)的主要性質(zhì)。性質(zhì)7.2.1Rn (D)關(guān)于D是非負(fù)單調(diào)下降函數(shù)。證：從定義可得。性質(zhì)7.2.2Rn (D)的定義域?yàn)?Dmin , ¥) 。證：根據(jù)失真的定義，碼的平均失真為Ed (x, y) = åå p(x)q(y | x)d (x, y)xy= åå p(x, y)d (x, y)xy72015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)n= åå p(x, y)

6、1 å d (x , y )iini=1xy= ååå 1 p(x , y )d (x , y )niiiini=1xiyi1nnååå p(xi )q( yi | xi )d (xi , yi )=i=1xiyi= åå p(xi )q( yi | xi )d (xi , yi )xiyi= åå p(x)q( y | x)d (x, y)xy若 d (x, y) = min d (x, y¢)y '其它ìï1 ,q( y | x) =若取

7、37;ïî0, 82015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)則可得到可能的最小平均失真 D為min= å p(x)d (x, yx )Dminxd (x, y) = min d (x, y)其中。xy另一方面，定義= min å p(x)d (x, y)Dmaxyx并使編碼器在任何輸入的源字下都取使得上式成立的碼字 y ，則此時(shí)有Ed (x, y) = åå p(x)q(y | x)d (x, y)xyåx= minyp(x)d (x, y) = Dmax92015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)則I ( X

8、n ;Y n ) = H (Y n ) - H (Y n | X n )= H (Y n ) = 0這說明當(dāng)D = Dmax時(shí)，Rn (D) = 0。反之，若 Rn (D) = 0 ，則達(dá)到此信息速率的熵壓縮編碼器的輸入x 和輸出y之間是統(tǒng)計(jì)的，此時(shí)碼的平均失真為Ed (x, y) = åå p(x)q(y | x)d (x, y)xy= åå p(x) p(y)d (x, y) = å p(y)å p(x)d (x, y)xy³ å p(y) × Dmaxyyx= Dmax102015/6/2馬盡文7.

9、2率失真函數(shù)的基本性質(zhì)故當(dāng) Rn (D) = 0 時(shí)，必有D ³ Dmax 。由此可知，Rn (D) 的定義域?yàn)?Dmin , ¥)，并在 D ³ Dmax之后，Rn (D) = 0。性質(zhì)7.2.3Rn (D) 為D 的凸函數(shù)，即若有l(wèi)1 , l2 , D1, D2，其中l(wèi)1 + l2= 1, 0 £ l1 £ 1, D = l1 D1 + l2 D2和 D，則有證：設(shè)q1 (y | x) 是達(dá)到Rn ( D1) 的轉(zhuǎn)移概率，q2 (y | x) 為達(dá)到Rn (D2 ) 的轉(zhuǎn)移概率，且這兩個(gè)轉(zhuǎn)移概率下的互信息分別為 1nn和I ( X n ;Y

10、 n )，從而有I ( X ;Y )2I ( X n ;Y n ) = R ( D ) ,E d (x, y) £ D1n111I ( X n ;Y n ) = R ( D ) ,E d (x, y) £ D2n222112015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)重新定義轉(zhuǎn)移概率如下：1(y | x) + l2 q2 (y | x)在此轉(zhuǎn)移概率下編碼的平均失真滿足：Ed (x,y) = l1E1d (x, y) + l2 E2d (x, y)£ l1 D1 + l2 D2 = D又設(shè)在上述轉(zhuǎn)移概率下編碼器的輸入/輸出互信息為 I ( X n ;Y n )，則

11、R (D) = R (l D + l D ) £ I ( X n ;Y n )nn1122而由于互信息是轉(zhuǎn)移概率的凸函數(shù)，即I ( X ;Y ) £ l;Y ) + lI ( X ;Y ) = lR ( D ) + l R ( D )nnnnnnI ( X1 1221n12n2122015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)故有Rn ( D) £ l1Rn ( D1) + l2Rn ( D2 )性質(zhì)7.2.4 對(duì)于離散無記憶信源，有證：對(duì)于任意的n ，我們分兩步證明，即分別證明Rn (D) ³ n R1 (D)和。Rn (D) £ n R1

12、(D)（1）取定 D ，設(shè) q(y | x)為達(dá)到 Rn (D) 的轉(zhuǎn)移概率， 此時(shí)有I ( X n ;Y n ) = R (D), 且 Ed (x, y) £ Dnnp(x) = Õ p(xi )i=1由于是離散無記憶信源，從而有132015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)故反復(fù)利用公式 H ( X ,Y ) = H ( X | Y ) + H (Y ) ，有I ( X n ;Y n ) = H ( X n ) - H ( X n | Y n )n= å H ( X ) - H ( X n | Y n )ii=1n= å H ( X ) - H

13、 ( X| Y n ) - H ( X,Y n )L| Xi121i=1n³ åH ( Xi ) - H ( Xi | Yi )i=1= å I ( Xi ;Yi )i=1n若記Di為信源字和碼字中第 i 個(gè)位置字母之間142015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)I ( Xi ;Yi ) ³ R1 (Di )£ D，于是有的平均失真，則有n而Ed ( X n ,Y n ) = 1 åDini=1nnR (D) = I ( X n ;Y n ) ³ å I ( X ;Y ) ³ å R (

14、 D )nii1ii=1i=1利用 Rn (D) 的凸性，有1nR ( D ) ³ R ( 1nnåååD ) ³ R ( D) ÞR ( D ) ³ nR (D)1i1i11i1nni=1i=1i=1故 Rn (D) ³ nR1(D) 。（2）"D ，設(shè)q( y | x)為達(dá)到R1 (D) 的字母轉(zhuǎn)移概率，即 I ( X ;Y ) = R1 (D), Ed ( X ,Y ) £ D ，并且取定n編碼器的轉(zhuǎn)移概率為( y | x )iii=1152015/6/2馬盡文7.2率失真函數(shù)的基本性質(zhì)這時(shí)，編碼器相當(dāng)于一個(gè)離散無記憶信道，根據(jù)定理5.1.1，則nI ( X n ;Y n ) £ å I ( X ;Y )iii=1所以 I ( X n ;Y n ) £ n R (D)1而此時(shí)的平均失真為n1nåEd ( X ,Y ) £D = Dnni=1Rn (D) £ I ( X;Y) &