信息論與編碼第四章

1、信息論與編碼第四章*1第1頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼2第4章 限失真信源編碼4.1平均失真和信息率失真函數(shù) 失真函數(shù) 平均失真 信息率失真函數(shù) 信息率失真函數(shù)的性質(zhì)4.2離散信源和連續(xù)信源的計(jì)算4.3限失真信源編碼定理4.4常用信源編碼方法簡介 游程編碼 算術(shù)編碼 矢量量化 預(yù)測編碼 變換編碼習(xí) 題第2頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼3第4章 限失真信源編碼控制信息失真的原因? 在實(shí)際問題中，信號有一定的失真是可以容忍的。但是當(dāng)失真大于某一限度后，信息質(zhì)量將被嚴(yán)

2、重?fù)p傷，甚至喪失其實(shí)用價值。要規(guī)定失真限度，必須先有一個定量的失真測度。 例如：語音、圖像第3頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼44.1平均失真和信息率失真函數(shù)失真函數(shù) 失真函數(shù)定義:信源編碼Xx1x2xnYy1y2ym第4頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼54.1平均失真和信息率失真函數(shù)失真函數(shù)失真矩陣第5頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼6失真函數(shù)例設(shè)信源符號X0，1,編碼器輸出符號Y0,1,2,規(guī)定失真函

3、數(shù)為 d(0,0)d(1,1)0; d(0,1)d(1,0)=1; d(0,2)d(1,2)0.5，求失真矩陣。 解:由式得失真矩陣第6頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼7失真函數(shù) (1)常用失真函數(shù) 均方失真： 絕對失真： 相對失真： 誤碼失真： 說明:第7頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼8失真函數(shù)說明: (2) 最常用的失真函數(shù)及其適用性 均方失真函數(shù)、絕對失真函數(shù)、相對失真函數(shù)適用于連續(xù)信源；誤碼失真適用于離散信源。 (3) 失真函數(shù)困難性比較 均方失真和絕對失真

4、只與(xi-yj)有關(guān)，而不是分別與xi及yj有關(guān)，在數(shù)學(xué)處理上比較方便。第8頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼9失真函數(shù) 失真函數(shù)的定義的推廣-序列編碼 如果假定離散信源輸出符號序列Xx1 x2xi xn，其中L長符號序列X=X1X2 XL的取值設(shè)為 xi=xi1 xi2 xiL，經(jīng)信源編碼后，接收端收到符號序列Y=y1 y2yjym，其中L長符號序列yj=yj1 yj2 yjL 則失真函數(shù)定義為 式中d(xik,yjk)是信源輸出第i個L長符號xi中的第k個符號xik，接收端收到第j個L長符號yj中的第k個符號yjk的失真函數(shù)。

5、 第9頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼10平均失真失真矩陣信源編碼Xx1x2xnYy1y2ym第10頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼11平均失真平均失真 失真函數(shù)的數(shù)學(xué)期望稱為平均失真。 對于連續(xù)隨機(jī)變量的平均失真連續(xù)隨機(jī)變量的聯(lián)合概率密度第11頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼12信息率失真函數(shù)1. 信息率失真函數(shù)R(D)問題產(chǎn)生? 對于信道容量為C的信道傳輸信息傳輸率為R的信源時，如果RC，就必須對信源

6、壓縮，使其壓縮后信息傳輸率R小于信道容量C，但同時要保證壓縮所引入的失真不超過預(yù)先規(guī)定的限度D。信息壓縮問題就是對于給定的信源，在滿足平均失真 的前提下，使信息率盡可能小。 （舉例語音）第12頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼13信息率失真函數(shù)2 D允許信道（D允許的試驗(yàn)信道） 對于離散無記憶信道(假想信道，實(shí)際上是信源編碼)3 信息率失真函數(shù)R(D)對于離散無記憶信源第13頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼14信息率失真函數(shù)例4-1-2 已知, 編碼器輸入的概率分布為:

7、 p(x)0.5，0.5， 信道矩陣分別為: 求: 互信息。 x1x2y1y20.60.40.20.8第14頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼15信息率失真函數(shù)例4-1-2 分析 p(x)0.5，0.5 x1x2y1y20.60.40.20.8第15頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼16信息率失真函數(shù)解 (1) 因p(xiyj)p(xi)p(yj/xi)； p(x1y1)=0.3， p(x1y2)0.2， p(x2y1)=0.1， p(x2y2)0.4 因?yàn)閜(yi)=

8、所以p(y1)0.4，p(y2)0.6 x1x2y1y20.60.40.20.8第16頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼17信息率失真函數(shù)又因?yàn)閜(xi/yj)=p(xiyj)/p(yj) 所以 p(x1/y1)=3/4, p(x1/y2) =1/3, p(x2/y1)=1/4, p(x2/y2)=2/3 根據(jù)互信息公式代入可得 比特/符號 用pij代入進(jìn)行同樣的運(yùn)算可得 I(X;Y)=0.397 比特符號 第17頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼18信息率失真函數(shù)補(bǔ)充例

9、 已知, 編碼器輸入的概率分布為: p(x)0.5，0.5， 信道模型分別為: 求: 互信息、平均失真。 x1x2y1y20.990.010.010.09x1x2y1y211x1x2y1y20.90.10.10.9x1x2y1y20.60.40.40.6x1x2y1y20.50.50.50.5第18頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼19信息率失真函數(shù)補(bǔ)充例 編碼器輸入的概率分布為: p(x)0.5，0.5 x1x2y1y211第19頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼20信

10、息率失真函數(shù)補(bǔ)充例 編碼器輸入的概率分布為: p(x)0.5，0.5， x1x2y1y20.990.01 0.010.99第20頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼21信息率失真函數(shù)補(bǔ)充例 編碼器輸入的概率分布為: p(x)0.5，0.5， x1x2y1y20.90. 1 0. 10. 9第21頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼22信息率失真函數(shù)補(bǔ)充例 編碼器輸入的概率分布為: p(x)0.5，0.5， x1x2y1y20.60. 4 0. 40. 6第22頁，共51頁，2

11、022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼23信息率失真函數(shù)補(bǔ)充例 編碼器輸入的概率分布為: p(x)0.5，0.5， x1x2y1y20.50. 5 0. 50. 5第23頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼24信息率失真函數(shù)補(bǔ)充例 總結(jié) x1x2y1y20.50. 5 0. 50. 5當(dāng)信源固定，變動信道，這里指信源編碼的一種方式，信道轉(zhuǎn)移概率可變。第24頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼25信息率失真函數(shù)補(bǔ)充例總結(jié) x1x2y1y

12、20.990.010.010.09x1x2y1y211x1x2y1y20.90.10.10.9x1x2y1y20.60.40.40.6x1x2y1y20.50.50.50.51-pppI(X;Y)DR(D)第25頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼26信息率失真函數(shù)例設(shè)信源的符號表為A=a1,a2,a2n,概率分布為p(ai)1/2n，i1,2,2n，失真函數(shù)規(guī)定為由信源概率分布可求出信源熵為設(shè)想采用下面的編碼方案：等效試驗(yàn)信道第26頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼27信

13、息率失真函數(shù)例設(shè)信源的符號表為A=a1,a2,a2n,概率分布為p(ai)1/2n，i1,2,2n，失真函數(shù)規(guī)定為平均失真D為等效試驗(yàn)信道第27頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼28信息率失真函數(shù)由該信道模型知，它是一個確定信道由互信息公式可得 I(X;Y)=H(Y)-H(Y/X)=H(Y)信道輸出概率分布為所以概率分布為則輸出熵H(Y)為第28頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼29信息率失真函數(shù)信息率失真函數(shù)的意義： 在一定允許失真度D的條件下，用盡可能少的碼符號來傳送

14、信源消息，以提高通信系統(tǒng)的可靠性。 作業(yè)：4-1本次課小結(jié)： 1 失真函數(shù) 2 平均失真度 3 信息率失真函數(shù)第29頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼30信息率失真函數(shù)的性質(zhì)1.R(D)函數(shù)的定義域 R(D)的定義域?yàn)镈0，Dmax2.R(D)函數(shù)的下凸性和連續(xù)性3.R(D)函數(shù)的單調(diào)遞減性例:R(D)在定義域內(nèi)是下凸的,連續(xù)的。R(D)的單調(diào)遞減性可以作如下理解：容許的失真度越大，所要求的信息率越小。第30頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼31信息率失真函數(shù)的性質(zhì)得出如

15、下結(jié)論：R(D)是非負(fù)的實(shí)數(shù)，即R(D)0。其定義域?yàn)?Dmax，其值為0H(X)。當(dāng)DDmax時,R(D)0。R(D)是關(guān)于D的下凸函數(shù)，因而也是關(guān)于D的連續(xù)函數(shù)。R(D)是關(guān)于D的嚴(yán)格遞減函數(shù)。第31頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼324.2離散信源和連續(xù)信源的計(jì)算某些特殊情況下R(D)的表示式為：率失真函數(shù)第32頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼334.2離散信源和連續(xù)信源的計(jì)算例設(shè)輸入輸出符號表為X=Y=0，1，輸入概率分布p(x)=p，1-p，0p1/2，失真

16、矩陣為 求信息率失真函數(shù)R(D). 解:簡記 (1) 按下式解方程 解得第33頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼344.2離散信源和連續(xù)信源的計(jì)算(2) 按下式解方程 解得(3) 得轉(zhuǎn)移概率分布第34頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼354.2離散信源和連續(xù)信源的計(jì)算(4) 求s(s=log)第35頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼364.2離散信源和連續(xù)信源的計(jì)算(5)計(jì)算R(D)，將上面各式代入， 則有(D

17、)=H(p)-H(D)，p為參數(shù)第36頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼374.3限失真信源編碼定理限失真信源編碼定理： 設(shè)離散無記憶信源X的信息率失真函數(shù)R(D)，則當(dāng)信息率RR(D)，只要信源序列長度L足夠長，一定存在一種編碼方法，其譯碼失真小于或等于D+，為任意小的正數(shù)；反之，若RR(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。 如果是二元信源，對于任意小的0，每一個信源符號的平均碼長滿足如下公式 在失真限度內(nèi)使信息率任意接近R(D)的編碼方法存在。第37頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京

18、工商大學(xué)信息工程學(xué)院 信息論與編碼384.4常用信源編碼方法簡介游程編碼游程長度 在二元序列中，只有兩種符號，即“0”和“1”，這些符號可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。它們的長度分別稱為游程長度L(0)和L(1). 對于多元序列也存在相應(yīng)的游程序列。例如m元序列中，可有m種游程。連著出現(xiàn)符號ar的游程，其長度L(r)就是“r”游程長度。設(shè)有多元信源序列(x1，x2，xm1， y，y，y， xm1+1，xm1+2，xm2， y，y，其中x是含有信息的代碼，取值于m元符號集A，可稱為信息位；y是冗余位，它們可為全零，即使未曾傳送在收端也能恢復(fù)。這樣的序列可用

19、下列兩個序列來代替： 111，100，000111，111000和 x1，x2，xm1，xm1+1， xm1+2，xm2， 前一個序列中，用“1”表示信息位，用“0”表示冗余位；后一個序列是取消冗余位后留下的所有信息位。第38頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼39算術(shù)編碼算術(shù)編碼的基本思路 從全序列出發(fā)，將各信源序列的概率映射到0，1區(qū)間上，使每個序列對應(yīng)這區(qū)間內(nèi)的一點(diǎn)，也就是一個二進(jìn)制的小數(shù)。積累概率 則例如有一序列S=011，這種三個二元符號的序列可按自然二進(jìn)數(shù)排列，000，001，010，則S的積累概率為 P(S)=p(000

20、)+p(001)+p (010)如果S后面接一個“0”，積累概率就成為 P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101) =p(000)+p(001)+p(010)=P(S) 信源的符號概率和積累概率第39頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼40算術(shù)編碼如果S后面接一個“1”，則其積累概率是 P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+ p(0101)+p(0110) =P(S)+p(0110) =P(S)+p(S)p0上面兩式可

21、統(tǒng)一寫作一般的遞推公式序列的概率的公式 第40頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼41算術(shù)編碼實(shí)用中，采用積累概率P(S)表示碼字C(S)，符號概率p(S)表示狀態(tài)區(qū)間A(S)，則有實(shí)際編碼過程: 先置兩個存儲器C和A，起始時可令 其中 代表空集。每輸入一個信源符號，存儲器C和A就按照上式更新一次，直至程序結(jié)束，就可將存儲器C的內(nèi)容作為碼字輸出。第41頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼42算術(shù)編碼例有簡單的四個符號a，b，c，d構(gòu)成序列S=abda，各符號及其對應(yīng)概率如表算

22、術(shù)編解碼過程如下:設(shè)起始狀態(tài)為空序列，則A()=1，C()=0。表4-4-1各符號及其對元概率符號符號符號概率pi符號概率pi符號累積概率Pj符號累積概率Pjabcd0.100(1/2)0.010(1/4)0.001(1/8)0.001(1/8)0.0000.1000.1100.111第42頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼43算術(shù)編碼算術(shù)碼編碼過程第43頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼44算術(shù)編碼據(jù)遞推公式的相反過程譯出符號。具體譯碼順序是后編的先譯，故稱為LIFO算

23、術(shù)碼，步驟如下：C(abda)=0.010111010,0.1) 第一個符號為a；放大至0,1) :C(abda)20.101110.1,0.110)第二個符號為b；去掉累積概率Pb:0.10111-0.1=0.00111放大至0,1) :0.00111 =0.1110.111,1)第三個符號為d去掉累積概率Pd：0.111-0.111=0放大至0,1) ：0 =00,0.1) 第四個符號為a。第44頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼45矢量量化標(biāo)量量化 連續(xù)信源進(jìn)行編碼的主要方法是量化，即將連續(xù)的樣值x離散化成為yi，i=1,2,

24、3,n。設(shè)信源符號的取值區(qū)間為(a0，an)，即a0 xan，a0可為負(fù)無限，an可為正無限，所以上述假設(shè)不失一般性。量化就是將上面的區(qū)間分成n個小區(qū)間，每個區(qū)間內(nèi)定一個量化值yi，若各區(qū)間端點(diǎn)為ai-1和ai，必有 a0y1a1y2an-1ynan最佳標(biāo)量量化就是在一定的n值時，選擇各ai和yi以使失真最小。此時的信息率為 R=log n第45頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼46矢量量化量化噪聲 當(dāng)一個樣值x經(jīng)量化后所產(chǎn)生的誤差為也就是在信號值x上疊加了一個樣值為 的噪聲信號。以語音信號量化常用的脈碼調(diào)制(PCM)為例。 設(shè)語音

25、信號的準(zhǔn)峰值為L，由于語音信號是雙向性的，則其取值范圍為-L,L。量化級數(shù)為n，量化級差為2L/n，用中心值作為量化值yi。語音信號樣值x的概率密度是負(fù)指數(shù)分布經(jīng)推導(dǎo)計(jì)算(見參考文獻(xiàn)2)可得信號功率與噪聲功率之比即信噪比為第46頁，共51頁，2022年，5月20日，1點(diǎn)17分，星期一*北京工商大學(xué)信息工程學(xué)院 信息論與編碼47矢量量化壓擴(kuò)技術(shù) 綜合考慮大、小功率的情況，將它們區(qū)別對待，即非均勻量化，小功率時量化級差小；大功率時量化級差大。這樣就減小了小功率時的量化噪聲，增大了大功率時的量化噪聲。使得在較低的比特數(shù)編碼時，既保證了小功率時的信噪比，又利用了大功率時信噪比的富余量。矢量量化 在前面的最佳編碼中可看到將離散信源的多個符號聯(lián)合編碼可提高效率。連續(xù)