第14章信息論與壓縮技術(shù)

1、第 14 章 信息論與壓縮技術(shù)通信系統(tǒng)的根本目的是將信息從信源可靠地傳輸?shù)侥康牡亍?Shannon 開創(chuàng)性論文中信息論的發(fā)明為現(xiàn)代通信系統(tǒng)提供了概念、見解和數(shù)學(xué)基礎(chǔ)。Shannon 的論文發(fā)表以前，并不清楚消息的信息量是什么。 只是基本了解如何傳輸波形和處理接收波形， 但并未從根本上理解如何將消息轉(zhuǎn)換為數(shù)據(jù)比特并實(shí)現(xiàn)傳輸。對(duì)各種調(diào)制技術(shù)如 AM 、 FM 和 PCM 有基本了解，但很少理解基本原理的概念upon which to compare their relative performance 。 Shannon 論文的基本研究結(jié)果 （？結(jié)論） 之一是他證明了信源信息在某信道傳輸?shù)膯栴}可以

2、用該信道上一串二進(jìn)制數(shù)據(jù)和一串發(fā)送的隨機(jī)二進(jìn)制序列分為表示信源信息的獨(dú)立問題。 這就暗示著， 所有種類的通信， 無(wú)論本身是模擬通信還是數(shù)字通信，都等效于二進(jìn)制數(shù)據(jù)的產(chǎn)生、 傳輸和接收。那時(shí)，Shannon 提出了通信傳輸?shù)膬蓚€(gè)基本問題：精確度量信源的最低速率（比特/符號(hào)）是多少？在各處都存在噪聲的條件下，實(shí)現(xiàn)可靠通信的極限傳輸速率是多少？這就是信道編碼定理。本章我們學(xué)習(xí)了 Shannon 就這些問題給出的答案。 Shannon 在信源編碼定理中證明了每一信源都存在極限最低速率，低于該速率時(shí)， 信息不能壓縮。 按照 Shannon 理論， 該最低速率不可能小于信源的嫡H。Shannon最意外的研

3、究結(jié)果是他的信道編碼定理，即，通信信道用叫做信道容量C 的參數(shù)來(lái)表征，使得速率R<C 的隨機(jī)二進(jìn)制數(shù)據(jù)可以以任意低的差錯(cuò)率在信道上傳輸。 信道編碼定理最意外的研究結(jié)果是： 由信道噪聲確定性能極限并不準(zhǔn)確， 但 以該速率傳輸時(shí)數(shù)據(jù)能可靠地傳輸。為把精力集中在信息理論的概念，我們來(lái)分析數(shù)字通信系統(tǒng)簡(jiǎn)化的方框圖，如圖 14.1 所示。術(shù)語(yǔ)離散時(shí)間信道指的是調(diào)制器、物理信道和解調(diào)器的級(jí)聯(lián)。注意，按照 Shannon 理論，信源編碼和信道編碼已被隔開，而并未損失最佳性能。 （with out any loss of optimality） 。 于是， 最優(yōu)信道編碼方案和最優(yōu)信源壓縮方案可以相互獨(dú)立

4、地設(shè)計(jì)。 我們?cè)诒菊乱矊W(xué)習(xí)了文 本、圖像和數(shù)字電視信號(hào)的壓縮方法。信道編碼是第 15 章的主題。本章分為如下幾節(jié)：14.1 信息論的基本概念本節(jié)介紹度量離散隨機(jī)變量的熵的概念。我們定義了聯(lián)合熵和條件熵且創(chuàng)立了熵的鏈?zhǔn)椒▌t （chain rule for entropy） 。 本節(jié)末尾介紹了微分熵的概念和兩個(gè)隨機(jī)變量之間的互信息。14.2 信源編碼我們?cè)诒竟?jié)考慮離散無(wú)記憶信道的信息量。然后導(dǎo)出與Shannon 的信源編碼定理，它創(chuàng)立了能實(shí)現(xiàn)表示信源壓縮量的極限。14.3 信道編碼本節(jié)介紹離散無(wú)記憶信道、互信息和信道容量的概念和信道容量的概念。然后學(xué)習(xí)Shannon 的信道編碼定理，它定義了噪聲信

5、道上能傳輸?shù)男畔⒘康幕鞠拗啤?4.4 AWGN 信道的容量根據(jù)平均功率限制，可以導(dǎo)出 AWGN 信道的信息容量。然后我們導(dǎo)出了每比特SNR的極限值， 低于該值時(shí)， 不能實(shí)現(xiàn)任意比特率的通信。 本節(jié)的末尾介紹了各種數(shù)字傳輸載波 方案與實(shí)現(xiàn)容量的系統(tǒng)中，每比特SNR 與頻譜效率中的折中。14.5 無(wú)損壓縮技術(shù)本節(jié)分析了原文件必須精確恢復(fù)的條件下，減少表示信息文件所需比特?cái)?shù)的無(wú)損壓縮技術(shù)。學(xué)習(xí)變長(zhǎng)編碼方案（如 Huffman 編碼 ）后，本節(jié)以介紹Lempel-ziv 壓縮算法作為結(jié)尾。14.6 圖像壓縮： JPEG本節(jié)介紹譯碼得到不完全復(fù)原信源圖像的有損編碼。我們學(xué)習(xí)用在許多圖像和視頻壓 縮標(biāo)準(zhǔn)

6、中的二維離散余弦變換、變長(zhǎng)編碼和色彩二次抽樣技術(shù)。本節(jié)的末尾介紹了JPEG標(biāo)準(zhǔn)。14.7 數(shù)字視頻壓縮：MPEG本節(jié)介紹幀間編碼以減少數(shù)字視頻信號(hào)的時(shí)間冗余。然后解釋了運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)技術(shù)及 其MPEG標(biāo)準(zhǔn)的實(shí)現(xiàn)。本節(jié)以 MPEG標(biāo)準(zhǔn)的介紹及其特性作為結(jié)尾。本章以結(jié)束語(yǔ)和挑選 的參考文獻(xiàn)表作為結(jié)尾。14.1 信息論的基本概念Shannon的論文發(fā)表以前，消息及其信息量的概念并未準(zhǔn)確地理解或定義。按照Shannon的理論，消息應(yīng)視為多個(gè)可選對(duì)象之間的選擇，一套可選對(duì)象的例子是我們每天相互傳遞信息中所用的英語(yǔ)字母表。Shannon進(jìn)一步提出，消息的信息量由與一套可選對(duì)象相關(guān)的概率決定而不是由它們所表示

7、的內(nèi)容決定。為了規(guī)范化( formalize)信息的概率模型，我們來(lái)考 慮取值為Ax =刈，刈,.,Xk 、PMFpx (x )= pfx = x ,x w A的離散隨機(jī)變量x的信息量。目前環(huán)境下，x可以表示信源信息的輸出或者通信信道。隨機(jī)變量x的嫡定義為:(x)=£ Px(X )og2 Px (為)(14.1)XiAH(x)是隨機(jī)變量x值的不確定性度量?；蛘?alternatively),嫡可以解釋為觀察實(shí)現(xiàn)x時(shí)所獲得的信息量。注意， H(x)總是PMF中x的函數(shù)。(a function of PMF of x)。H (x 尸H (px® 力 (14.2)式(14.1)中

8、，當(dāng)對(duì)數(shù)的底為 2時(shí)，隨機(jī)變量x的嫡用比特表示。例14.1考慮概率為0.5,0.2,0.15,0.10,0.05的隨機(jī)變量。計(jì)算 x的嫡。解 H x =-0.5log2 0.5 -0.2log 2 0.2 一0.1510g2 0.15-0.1log2 0.1 )0.05log2 0.05 )=1.923bits由于我們常碰到二進(jìn)制隨機(jī)變量，所以我們將二進(jìn)制的嫡函數(shù)H(p)定義為：H (p jj -plog2 P -(1 -p )og 2(1 - P )(14.3)圖14.2示出了二進(jìn)制嫡函數(shù)H(p)。當(dāng)p=0或p=1時(shí)，二進(jìn)制隨機(jī)變量的嫡為0。每種情況下的隨機(jī)變量值可以預(yù)測(cè)，所以沒有不確定性，

9、且觀察隨機(jī)變量實(shí)現(xiàn)時(shí)沒有得到信息。當(dāng)p=1/2時(shí)，即，兩個(gè)值不可預(yù)測(cè)的程度相同時(shí)，H(p)出現(xiàn)最大值。從例14.2得出結(jié)論，若假定所有制等概率發(fā)生，則觀察隨機(jī)變量的實(shí)現(xiàn)可得到最大信息量。這可用下面的正式表述：離散隨機(jī)變量X有K個(gè)可選對(duì)象或結(jié)果Xi,X2，,xk時(shí)，它的不確定性H(x)是有界的：0-H x _log2K (14.4)當(dāng)且僅當(dāng)某i值對(duì)應(yīng)的pi=1時(shí)，上式左邊的等號(hào)成立。當(dāng)且僅當(dāng)所有i值者酹t足pi=K時(shí)，上式右邊的等號(hào)成立。相應(yīng)的證明見Cover和Thomax的文獻(xiàn)?，F(xiàn)在我們把嫡的定義擴(kuò)展到一對(duì)隨機(jī)變量。14.1.1 聯(lián)合嫡和條件嫡隨機(jī)變量對(duì)(x,y)的聯(lián)合嫡定義為：H(X，y)=

10、£ 工 Pxy(X，yi )og2 Pxy (Xi，y )(14.5)Xi ex y ©y假定x和y的取值分別為字母表 Ax= xi,X2，,xk和字母表Ay= yi,y2,yL。若x與y統(tǒng) 計(jì)獨(dú)立，則pxy(x，yi )=Px(xi 2y(X )。將其代入式(143),得：H x,y -Pxy xi,yj 10g2 Pxy xi y(14.6)xmy©二，' Px x Py V j10g2Pxx二 三PxxPyV 10g2PyV x -A y -Ax -A y -Ai x 1 _ vi _ x j _ yPx x 10g2 Px Xi Py Vj log

11、2 Py Vjx exVi ey=H x H y事件y=yj條件下，隨機(jī)變量x的條件嫡定義為：H(xy = yj)=£ Px(X y =Vj )1og2 Px(Xi y = yj )(14.7)X =AxH(xy = x聲示觀察到事件y=yj后我們關(guān)于x的不確定性。類似地，可以定義H (y x=Xi )= £ Py(Vj x=Xi )1og2 Py(Vj|x = Xi )(14.8)yj .Ay隨機(jī)變量y給定后隨機(jī)變量x的條件信息量總平均值(equivocation)或者平均條件嫡定義 為：H (x y 尸 £ Py (yj H (x y=yj )(14.9)Vj

12、 - AV=-£ 2Py(Vj )Px(x y = x Wg2 Px(xj y = yj)xi鞏Vj八、PP Pxy 冷 Vj二一Pxy Xi , Vj 10g 2 xi 鞏 yj * Pxy x,y j iX1 5AxH (x y )表布觀察隨機(jī)變量y后，對(duì) x剩余不確定性(renaining uncertainty)的度量。注意H (x y = yj )是事件發(fā)生條件下的嫡，而 H (x y )不是嫡而是平均嫡。現(xiàn)在我們來(lái)證明隨機(jī)變量對(duì)的聯(lián)合嫡 H (x, y )是一個(gè)嫡加上其他的條件嫡。即：H (x,y ) = H (x)+y(y|x)(14.10)將式(14.5)展開并利用式

13、(14.9),得到H(x,y )的表達(dá)式:H x, y -八 9 Pxy x,yj log2 Pxy Xi ,yj xi ZAx yj TAy=Pxy X，yj log2 Px Xi Py Yj X =XiXi 八 yj =Ay-=£ Z PXy(X,yj J10g2 Px (Xi工 PXy”，yj )l0g2Py(yj X=Xi )Xi =Ax yj =AyX 三Ax yj 三Ay=一£ Px(Xi )10g 2 Px (Xi )一£ 工 Pxy (X,yj )10g2 Py(y j X = Xi ) Xi .AXXi FA, yj 汽=H (x )+H (y

14、x )式(14.10)表明(x,y)對(duì)的不確定性等于x的不確定性加上觀察x后對(duì)y的剩余不確定性。類似地，可以證明：H (x,y )= H (y)+H (x y)(14.11)我們可以根據(jù)聯(lián)合嫡 h (x, y )寫出平均條件嫡的如下表達(dá)式：H (x y )=H (x,y )H (y )(14.12)H (y x 尸H (x,y )H (x)(14.13)當(dāng)x和y統(tǒng)計(jì)獨(dú)立時(shí)，用式(14.9)容易證明H (x y )=H (x )(14.14)H (y x )=H (y )(14.15)式(14.14)與式(14.15)表明，若x和y是統(tǒng)計(jì)獨(dú)立的隨機(jī)變量，并未減小另一個(gè)的 不確定性。容易證明平均條

15、件嫡滿足如下的不等式：H (x y )<H(x )(14.16)H (y x )<H (y )(14.17)當(dāng)且僅當(dāng)x與y是統(tǒng)計(jì)獨(dú)立的隨機(jī)變量時(shí)，上面兩個(gè)式子的等號(hào)成立。不等式式(14.16)與式(14.17)表明conditioning絕不會(huì)增大不確定性。嫡的鏈?zhǔn)椒▌t式(14.10)與式(14.11)可用歸納法推廣到如下n個(gè)隨機(jī)變量的情形H (X1,X2,.,Xn )=H(X1)+H(X2Xi)+H(X3Xi,X2 )+. +H (XnXi,X2,.,Xn)(14.18)H (Xn X1,X2,.,Xn4淡示觀察到X1,X2，,Xn-1后我們關(guān)于Xn的不確定性。若隨機(jī)變量X1,X

16、2，,Xn統(tǒng)計(jì)獨(dú)立，則式(14.18)簡(jiǎn)化為：nH (不),., Xn 尸 H (Xi )+H(X2 )+H(X3 )+. +H (Xn ) = 2 H (Xi )(14.19)i 1例14.3隨機(jī)變量x和y的聯(lián)合PMF pxy(,yj )如下表y1y2y3y4x11/81/161/321/32x21/321/81/161/32x31/321/321/81/16x41/161/321/321/8求 H(x 卜 H(y)、H(x, y)、H(xyDH(yx)解 將上表中的各項(xiàng) Pxy (x , yj )代入式(14.5)可求得聯(lián)合嫡 H ( x,y )：H x,y =-二 二 pxy xi，yj

17、 log? Pxy %, yjxi%yj三Ay1 . c 1 ,“2 ,“=4 log 2 8 log 216 一log 2 32816324=0.26 0.1733 0.2166loge2= 3.75比特通過(guò)分別求各行的和、各列的和，可以得到marginal PMF的Px(xi)和py(yj)如下：px Xi =14.14,14,14：，py yj =，：14,14,14,14：，由于x和y等概率，則它們的嫡為：H x )=log2 4=2比特H y)= log2 4 =2t匕特下面我們用式(14.12)和式(14.13)來(lái)求平均條件嫡：H (x y )=H(x,y)H (y) =3.75

18、2 =1.75t匕特H yx =H(x,y)-H(x)=3.75-2 =1.75t匕特14.1.2微分嫡現(xiàn)在我們引入連續(xù)隨機(jī)變量x的微分嫡的概念。離散隨機(jī)變量x的概率密度函數(shù)為fx(x)時(shí)，它的微分嫡定義為：h(x) = -j fx(x)log fx(x)dx (14.20)同離散隨機(jī)變量的情況一樣，微分嫡僅取決于隨機(jī)變量的概率密度函數(shù)。盡管微分嫡的概念在許多方面類似于離散隨機(jī)變量的嫡，但它不能解釋為連續(xù)隨機(jī)變量x的不確定性。實(shí)際上，表示連續(xù)隨機(jī)變量x的無(wú)窮個(gè)值需要無(wú)限個(gè)比特。例14.4考慮均勻分布在 a與b之間的連續(xù)隨機(jī)變量，它的概率密度函數(shù)為fx(x) = b -a0,0 <x<b其他-b 1它的微分嫡為：h(x)之一 a b - a,1logdx = log(b - a)b -a(14.21)注意，b-a<1時(shí)，log(b-a)<0 ,且微分嫡可以為負(fù)值。例14.5考慮高斯隨機(jī)變量x|_N(0,g2)。它的 PDF 值為:fx(x)二-= ,2JIG-x2-o 2e 2。2xx2/h(x) - " fx(x)log 2fx(x)dx - - "fx(x)log2 JOO_2二x dx=J：fx(x)10g 2 1二21:“/詈2 - x2-：Cxx2d