理論極限與基本途徑

壓縮編碼技術(shù)

1信源發(fā)出的消息： 是一個(gè)隨機(jī)過(guò)程，它是時(shí)間與空間的函數(shù)：語(yǔ)音信號(hào)——時(shí)間函數(shù)X（t）；

靜止平面圖象——空間函數(shù)X（x，y）；

電視信號(hào)——時(shí)間空間信號(hào)X（x，y，t）；

電報(bào)信號(hào)——時(shí)間離散信號(hào)；

書(shū)信——空間離散的符號(hào)序列——文字實(shí)際信源——抽象成一個(gè)隨機(jī)序列來(lái)討論2信源是產(chǎn)生消息的源，根據(jù)信源的不同情況可分為：

根據(jù)信源的統(tǒng)計(jì)特性，離散信源又分為兩種：離散信源

取值為離散集合。連續(xù)信源取值為連續(xù)的信源無(wú)記憶信源

X的各時(shí)刻取值相互獨(dú)立。有記憶信源

X的各時(shí)刻取值互相有關(guān)聯(lián)。信源的數(shù)學(xué)模型混合信源

取值兩者皆有。3§3.1離散無(wú)記憶信源

§3.2聯(lián)合信源§3.3隨機(jī)序列§3.4率失真理論第三章理論極限與基本途徑4§

3.1離散無(wú)記憶信源若時(shí)間t為有限數(shù)n，則信源可用n維隨機(jī)矢量來(lái)表示：若該信源是平穩(wěn)的又稱(chēng)為離散無(wú)記憶平穩(wěn)信源——簡(jiǎn)稱(chēng)離散無(wú)記憶信源：是時(shí)間離散、幅度離散的隨機(jī)過(guò)程。不同時(shí)刻的隨機(jī)變量是獨(dú)立同分布的，且符號(hào)集中的符號(hào)數(shù)目是有限的或可數(shù)的。（3.1.3）5

3.1.1自信息量和一階熵記字符出現(xiàn)的概率為，有

（3.1.5）

自信息量定義:

（3.1.6）6對(duì)數(shù)所用“底”不同，信息量單位也不同：

比特（bit）：r=2

奈特（Nat）：r=e(自然對(duì)數(shù)之底)

哈特（Hart）：r=10理解：亦稱(chēng)自信息函數(shù)，含義是：隨機(jī)變量X

取值為時(shí)所攜帶信息的度量。7信息熵（簡(jiǎn)稱(chēng)熵，Entropy）定義：

自信息量的概率平均，即隨機(jī)變量的數(shù)學(xué)期望值（3.1.7）8理解:

一階熵，表示集合中某字符出現(xiàn)的平均不確定性，即為了確定集合中某一字符出現(xiàn)所需的平均信息量（觀察之前）；或代表每出現(xiàn)一個(gè)字符所給出的平均信息量（觀察之后）。9當(dāng)處于事件發(fā)生之前，根據(jù)先驗(yàn)概率，就有不同的不確定性存在，因此是不確定性的度量；當(dāng)處于事件發(fā)生之時(shí)，是一種驚奇度度量；當(dāng)處于事件發(fā)生之后，不確定性已被解除，則是獲得信息的度量；還可以理解為是事件隨機(jī)性的度量，因其僅僅對(duì)概率取另一個(gè)坐標(biāo)而已。詳細(xì)解釋?zhuān)?/p>

就是離散無(wú)記憶信源進(jìn)行無(wú)失真編碼時(shí)的基本極限10當(dāng)強(qiáng)調(diào)各事件的概率分布、并構(gòu)成概率向量（m維）時(shí)，熵也習(xí)慣地寫(xiě)成：11

3.1.2基本途徑之一——概率匹配對(duì)字符的編碼長(zhǎng)度為：對(duì)信源編碼的平均碼長(zhǎng)l為：(3.1.8)12熵具有極值性，即：(3.1.9)其中等號(hào)僅在成立。對(duì)于離散無(wú)記憶平穩(wěn)信源，

1)準(zhǔn)確得到字符概率；

2)對(duì)各字符的編碼長(zhǎng)度都達(dá)到它的自信息量。數(shù)據(jù)壓縮的途徑之一13例：對(duì)概率分別為p和(1-p)的二進(jìn)制無(wú)記憶信源，求信源的熵。解：信源的熵為當(dāng)p=0.5時(shí)，H(X)=1，取得最大值，即不確定度最大。當(dāng)p=0或p=1時(shí)，H(X)=0。即是確定性事件集，不確定度為0。二進(jìn)制熵函數(shù)如圖所示：從物理意義上來(lái)說(shuō):

二進(jìn)制信源所含的信息量總低于1bit；

只有當(dāng)符號(hào)0或1的概率p0=p1=1/2時(shí)，才含有1bit的信息量。14定理3.1(最大離散熵)所有概率分布所構(gòu)成的熵,以等概率時(shí)為最大,即:(3.1.10)對(duì)于二進(jìn)制碼字R位二進(jìn)制碼字包含Rbit的自信息量若各字符以等概率出現(xiàn)15信源所含的冗余度最大值與熵之間的差值(3.1.11)離散無(wú)記憶信源的冗余度隱含在信源符號(hào)的非等概率分布之中，只要信源不是等概率分布，就存在著數(shù)據(jù)壓縮的可能性。統(tǒng)計(jì)編碼的基礎(chǔ)16數(shù)據(jù)壓縮比定義壓縮前每個(gè)信源符號(hào)(取樣)的編碼位數(shù)(logm)與壓縮后平均每符號(hào)的編碼位數(shù)（l）之比編碼效率:上界：(3.1.12）(3.1.13）(3.1.14）17例3-1信源X的分布為：采用2進(jìn)制編碼，需要

R=log4=2bit表示平均碼長(zhǎng)為：數(shù)據(jù)壓縮比：編碼效率：①18采用某種與相匹配的二元編碼，如：平均碼長(zhǎng)為：②小于編碼方法①的平均碼長(zhǎng)，達(dá)到了該信源的熵所表示的基本極限數(shù)據(jù)壓縮比：編碼效率：19§3.1離散無(wú)記憶信源

§3.2聯(lián)合信源§3.3隨機(jī)序列§3.4率失真理論第三章理論極限與基本途徑203.2聯(lián)合信源多個(gè)信源構(gòu)成的聯(lián)合信源

音響設(shè)備有多個(gè)聲道；彩色電視信號(hào)可分解為紅、綠、藍(lán)（R,G,B）三種基色；遙感圖像包含多個(gè)波段；21

3.2.1聯(lián)合熵和條件熵設(shè)信源X

取值于：信源Y

取值于：對(duì)X和Y做笛卡兒乘積構(gòu)成聯(lián)合信源（X，Y）22符號(hào)關(guān)系定義：聯(lián)合概率

邊緣概率條件概率(3.2.1a)(3.2.1b)(3.2.2a)(3.2.2b)23聯(lián)合熵（JointEntropy）(3.2.3)——聯(lián)合信源（X,Y）的熵表示聯(lián)合概率分布所具有的信息量的概率平均；表示兩個(gè)事件集聯(lián)合發(fā)生時(shí)所能得到的總的平均信息量。24條件自信息量——由條件概率定義(3.2.4a)

(3.2.4b)表示在發(fā)現(xiàn)信源Y取值為時(shí),對(duì)猜測(cè)信源X是否取的不確定程度。25互信息量——自信息量與條件自信息量之差(3.2.5)表示所含的信息量（不確定度）；表示知道后還保留的信息量；代表信源符號(hào)為所提供的信息量。26平均互信息量——互信息量的概率平均(3.2.6)條件熵(平均條件自信息量)(3.2.7a)(3.2.7b)27平均互信息量表示信源X的平均不確定性與其在信源Y被確定條件下仍保留的平均不確定性之差。(3.2.8a)28表示了隨機(jī)變量Y

對(duì)X

所提供的平均信息量。表示兩個(gè)事件集聯(lián)合發(fā)生時(shí)所能得到的總的平均信息量。與區(qū)別：(3.2.10)29(3.2.8b)對(duì)稱(chēng)性由于：平均互信息量具有:(3.2.8a)30非負(fù)性(3.2.12)由于：(3.2.11 a)(3.2.11b)31基本途徑之二

—對(duì)獨(dú)立分量進(jìn)行編碼(3.2.11 a)(3.2.11b)條件熵必定不大于無(wú)條件熵只有當(dāng)X與Y相互獨(dú)立時(shí)，式(3.2.11)中等號(hào)成立。32(3.2.10)由于平均信息量非負(fù)，(3.2.13)聯(lián)合信息熵必定不大于各分量信息熵之和，只有當(dāng)X與Y相互獨(dú)立時(shí)，式(3.2.13)中等號(hào)成立。33一般情況下，聯(lián)合信源的冗余度，就是兩者之差(3.2-14)兩信源的相關(guān)性越大，冗余度越大34對(duì)于聯(lián)合信源，

1)冗余度隱含在信源的相關(guān)性中；

2)盡量去除各分量間的相關(guān)性，再對(duì)各獨(dú)立分量進(jìn)行編碼。數(shù)據(jù)壓縮的途徑之二變換編碼的基礎(chǔ)35例3-2為消除彩色電視信號(hào)R、G、B分量間的相關(guān)性并保持與黑白電視兼容，可按下面的彩色空間變換矩陣將其轉(zhuǎn)換為亮度（Y）和色度（U，V）。再對(duì)相關(guān)性較弱的Y、U、V分量分別編碼(3.2.15)36文氏圖（VennDiagram）圖3.2

表示信息熵關(guān)系的Venn圖聯(lián)合信息熵和平均互信息量之和等于各分量之和(3.2.16)37X、Y信源相互獨(dú)立時(shí)兩圓互相離開(kāi)，條件熵增大，相關(guān)性減弱。38X、Y信源完全相關(guān)時(shí)兩圓互相重合，條件熵為零，聯(lián)合熵等于單個(gè)信源的熵。39§3.1離散無(wú)記憶信源

§3.2聯(lián)合信源§3.3隨機(jī)序列§3.4率失真理論第三章理論極限與基本途徑403.3隨機(jī)序列有記憶信源：源字X的各分量不是互相獨(dú)立的

極限熵把n個(gè)信源符號(hào)當(dāng)作一個(gè)n維隨機(jī)矢量X，其聯(lián)合概率為P(X),熵為：平均符號(hào)熵為:(3.3.1)(3.3.2)41若把前n-1個(gè)符號(hào)作為條件,則可求得最后一個(gè)符號(hào)Xn

的熵為:信息論中已證明：對(duì)于離散平穩(wěn)信源X，如果它的H(X1)<∞,下述結(jié)論成立:與均為隨n增大而單調(diào)不增函數(shù);①當(dāng)n增大(考慮更多的元素互相依從關(guān)系)時(shí),熵值將會(huì)進(jìn)一步降低;42為極限熵或極限信息量,用H∞表示③(3.3.4)②(3.3.3)43基本途徑之三—利用條件概率

對(duì)于離散有記憶平穩(wěn)信源，

1)理論上，可通過(guò)它的條件概率計(jì)算極限熵；

2)實(shí)踐中，可利用條件概率進(jìn)行編碼，階越高越有利。數(shù)據(jù)壓縮的途徑之三對(duì)于離散平穩(wěn)信源，

1)理論上，可通過(guò)它的條件概率計(jì)算極限熵；

2)實(shí)踐中，可利用條件概率進(jìn)行編碼，階越高越有利。44H∞的計(jì)算極其困難假定信源平穩(wěn);測(cè)得n足夠大的條件概率以近似計(jì)算H∞;假定信源的記憶有限。Xp只與其前面M個(gè)符號(hào)Xp-1,

Xp-2,…,

Xp-M有關(guān)M階Markov鏈：表示這M+1個(gè)符號(hào)(Xp-M,

Xp-M+1,,

Xp-1,Xp)組成的序列。45M=1→

一階Markov鏈P(Xp|Xp-1,

Xp-2,Xp-3,,

Xp-M)=P(Xp|Xp-1)P(X)=P(X1)P(X2|X1)P(X3|X2)P(Xn|Xn-1)M→

M階Markov鏈P(Xp|Xp-1,

Xp-2,Xp-3,,

Xp-M)P(X)=P(X1)P(X2|X1)P(X3|X2,X1)P(Xn|Xn-1,X

n-2,,Xn-M)46得到平均符號(hào)熵HM+1

M=1→2階條件熵H2H(X|Y)

和

H(Y|X)

M=0→1階熵H1

(信源無(wú)記憶)H(X)

0階熵H0(信源的最大離散熵)簡(jiǎn)化:信源等概率分布,有m種取值H0=logm=R47對(duì)于一般平穩(wěn)信源，有：有時(shí)只能得到H1，甚至H0，傳輸更浪費(fèi)。只能計(jì)算HM，只好用傳送HM的手段，傳輸不經(jīng)濟(jì)。實(shí)際符號(hào)熵是H∞，理論上只要傳送H∞的手段即可。未能完全掌握其概率分布（3.3-5）48對(duì)于PCM編碼的數(shù)據(jù),其無(wú)失真壓縮的理論極限為:(3.3-6)49等長(zhǎng)的PCM編碼:傳送

H0測(cè)得各符號(hào)出現(xiàn)的概率,并按無(wú)記憶信源考慮的統(tǒng)計(jì)編碼傳送

H1,獲得信息變差

I01=H0-H1

(統(tǒng)計(jì)了信源概率后獲得的信息)進(jìn)一步考慮利用前一取樣值進(jìn)行預(yù)測(cè)(DPCM)傳送H2,獲得信息變差I(lǐng)02=H0–H2若利用前M-1個(gè)取樣值進(jìn)行預(yù)測(cè)傳送HM,獲得信息變差I(lǐng)0M=H0-HM50表3.18幅典型黑白電視圖象的實(shí)測(cè)熵值序號(hào)圖像內(nèi)容H(X0)H(X0|X1)H(X0|X2)H(X0|X5,X1)H(X0|X1,X2)1戴胸花的女郎6.41454.04404.08243.26613.25472雙人6.22003.98483.83972.95832.96983教授7.21003.64563.53954男孩與玩具7.13255.02684.79785戴草帽的婦女7.00304.58824.32756船7.03844.93804.86522.70252.66777水池7.35695.19145.4112

8分辨率測(cè)試卡6.94125.43865.4716熵值計(jì)算時(shí)所選的相鄰像素位置關(guān)系X2X1X0X3X1X5X2X4X0圖像1~2:美國(guó)電影電視工程師協(xié)會(huì)(SMPTE)測(cè)試圖像圖像3~8:歐洲廣播聯(lián)盟(EBU)測(cè)試圖像51但計(jì)算量卻增加很快在實(shí)際分析性能時(shí),以求能看到

Hn(X)~n

曲線(xiàn)出現(xiàn)平穩(wěn)即可。對(duì)于實(shí)際的圖像信號(hào):

2階熵比1階熵小得多

3階熵比2階熵小更高階的熵減小得就不明顯了52基本途徑之四—利用聯(lián)合概率數(shù)據(jù)壓縮的途徑之四對(duì)于離散平穩(wěn)信源，

1)理論上，可通過(guò)聯(lián)合概率計(jì)算極限熵；

2)實(shí)踐中，可將多個(gè)符號(hào)合并成向量，利用其聯(lián)合概率

進(jìn)行編碼，符號(hào)越多越有利。53在一定條件下，利用聯(lián)合概率進(jìn)行編碼的思想，也適用于離散無(wú)記憶信源。變換編碼利用M階的最佳變換得到HM，并獲得I=H0-HM的信息變差54基本途徑之五

—對(duì)平穩(wěn)子信源進(jìn)行編碼語(yǔ)音、圖像等信源的統(tǒng)計(jì)特性一般是非平穩(wěn)的計(jì)算H∞的前提不成立解決辦法：在一段時(shí)間內(nèi)作為平穩(wěn)信源對(duì)待，

即將非平穩(wěn)信源S看成多個(gè)平穩(wěn)子

信源Si

(i=1,2,…,L)構(gòu)成的組合信源。55非平穩(wěn)信源S多路選擇平穩(wěn)信源S1平穩(wěn)信源S2平穩(wěn)信源SL輸出圖3.3

非平穩(wěn)信源的組合平穩(wěn)模型56組合信源中的L個(gè)子信源的符號(hào)集相同，為Am={a1,a2,…,am}，設(shè)各子信源在S中的出現(xiàn)概率為Pi，組合信源模型可描述為：Si(Pi;P(a1|i),P(a2|i),…,P(am|i))(3.3-7)常把實(shí)際信源近似看成平穩(wěn)信源,統(tǒng)計(jì)是上述模型的平均:SM(P(a1),P(a2),…,P(am))(3.3-8)可以證明:(3.3-7)復(fù)合信源的熵HC≤(3.3-8)平均混合信源的熵HM57定理3.2(信源的自適應(yīng)編碼)一個(gè)信源復(fù)合模型的熵HC小于混合模型的熵

HM數(shù)據(jù)壓縮的途徑之五對(duì)于離散非平穩(wěn)信源，

1)設(shè)法將其劃分成若干個(gè)近似平穩(wěn)的子信源分別編碼；

2)提高編碼效率的關(guān)鍵是對(duì)平穩(wěn)子信源的自適應(yīng)識(shí)別。58例3-4預(yù)測(cè)編碼:使預(yù)測(cè)誤差為最小的維納預(yù)測(cè)過(guò)程即使采用最佳的不定長(zhǎng)編碼，也不過(guò)是趨近于把預(yù)測(cè)信號(hào)作為混合平穩(wěn)信源看待時(shí)的熵HM；只有把預(yù)測(cè)誤差信號(hào)按照組合信源看待并做自適應(yīng)編碼，才可能達(dá)到更低的組合信源熵HC；59§3.1離散無(wú)記憶信源

§3.2聯(lián)合信源§3.3隨機(jī)序列§3.4率失真理論第三章理論極限與基本途徑603.4率失真理論限失真編碼（失真不超過(guò)某給定條件下的編碼）率失真理論研究的問(wèn)題：最佳編碼：使限失真條件下比特?cái)?shù)最少的編碼最佳編碼：使限失真條件下比特?cái)?shù)最少的編碼限失真編碼（失真不超過(guò)某給定條件下的編碼）最佳編碼：使限失真條件下比特?cái)?shù)最少的編碼61

1959年，Shannon又進(jìn)一步確立了率失真理論，

從而完善了信源編碼的理論基礎(chǔ)；

1948年，Shannon在“通信的數(shù)學(xué)原理”中首次

提到信息率—失真函數(shù)的概念；

T.Berger等人接著進(jìn)行了深入的研究。62率失真函數(shù)的基本含義信源編碼的過(guò)程：輸入符號(hào)集：Am={a1,a2,…,am}輸出符號(hào)集：Bn={b1,b2,…,bn}編碼器映射互信息量概念：I(aj|bk)

和I(bk|aj)63例3-5設(shè)信源編碼器是一個(gè)簡(jiǎn)單的一一對(duì)應(yīng)的關(guān)系，即m=n，且：aj→bj，j=1,2,3,…,m用概率表示：P(ak|bk)=1或P(bj|aj)=1I(ak|bk)=0或I(bj|aj)=0也就是說(shuō)：此時(shí)：bj提供了aj

全部信息，或者說(shuō)解除了aj

的全部不確定性。I(aj;bk)=I(aj)64信息保持編碼aj

：12345678bj

：000001010011100101110111aj

：1,23,45,67,8bj

：00011011當(dāng)允許存在一定誤差,假設(shè)一個(gè)實(shí)際信源,有8不同消息,但卻發(fā)現(xiàn)1,2;3,4;5,6;7,8兩兩相差不多，可用同一碼字代表:3bit編碼2bit編碼誤差的產(chǎn)生是由于對(duì)信源的某些符號(hào)進(jìn)行了合并,減少了事件的數(shù)目,從而使新信源的熵降低。當(dāng)集合中事件結(jié)構(gòu)發(fā)生變化時(shí)，就會(huì)引起信源概率結(jié)構(gòu)的變化，從而影響信源概率的變化。65只要允許誤差（量化）的存在，就可以減少編碼輸出的字符數(shù)，因而也就可以降低碼率。信息論術(shù)語(yǔ)：即要確定每個(gè)編碼符號(hào)至少應(yīng)提供的關(guān)于信源符號(hào)的信息量。在給定的失真條件下，最起碼需要多大的碼率，才能保證不超過(guò)允許的失真。討論：66率失真函數(shù)的基本含義：在一定的失真條件下，要找出平均互信息量，即：的最小值

minI(X;Y)。X表示信源的隨機(jī)變量集合，I(X)表示信源信息;

Y表示編碼符號(hào)的隨機(jī)變量集合，I(Y)表示編碼輸出信息。67平均信息量的公式可寫(xiě)為：或者：(3.4-1)(3.4-2)68因此,可知平均互信息量由下面幾個(gè)方面決定：信源符號(hào)概率P(aj)編碼輸出符號(hào)概率Q(bk)已知信源符號(hào)出現(xiàn)的條件概率Q(bh|aj)在確定信源條件下,P(aj)已確定,所謂選擇編碼方法,就是通過(guò)改變條件概率Q(bh|aj)的分布來(lái)控制平均信息量。69離散信源的率失真函數(shù)對(duì)失真的度量：具有隨意性，對(duì)不同信源及不同場(chǎng)合,可引入不同的失真度量。常用的有：圖像、語(yǔ)音編碼中：

常常希望用人的視覺(jué)、聽(tīng)覺(jué)特性來(lái)加權(quán)。均方差:

信源發(fā)出aj

，被編碼成bk

，其誤差平方為(aj-bk)2;

7000b2b1a2a1d2d1(a)(b)圖3.4

失真測(cè)量流圖與矩陣對(duì)離散信源：常用失真測(cè)量流圖或矩陣作為失真的度量71以d(aj,bk)代表失真度量,則平均失真(失真函數(shù))：(3.4-3)若要求平均失真D(Q)≤D，則必存在這樣一個(gè)條件概率Q(bk|aj)，使D(Q)不超過(guò)D，記：QD=Q(D(Q)≤D

)(3.4-4)為保證失真在允許范圍D內(nèi)的條件概率的集合。72率失真函數(shù)R(D)(亦稱(chēng)碼率-失真函數(shù))定義為:(3.4-5)率失真函數(shù)是在允許失真為D的條件下,信源編碼給出的平均互信息量的下界,也就是數(shù)據(jù)壓縮的極限數(shù)碼率(基本極限)。在Q(D)范圍