限失真信源編碼PPT課件

1、2022/6/201/49理論上“消息完全無(wú)失真?zhèn)魉汀钡目蓪?shí)現(xiàn)性 信 道 編 碼 定 理 ： 無(wú) 論 何 種 信 道 ， 只 要 信 息 率R=(Klog2m)/L小于信道容量C，總能找到一種編碼，使在信道上能以任意小的錯(cuò)誤概率和任意接近于C的傳輸率來(lái)傳送信息。反之，若RC，則傳輸總要失真。實(shí)際上“消息完全無(wú)失真?zhèn)魉汀钡牟豢蓪?shí)現(xiàn)性 無(wú)失真?zhèn)魉偷臈l件為RH(x)，而實(shí)際的信源常常是連續(xù)的，H(x)為無(wú)窮大，于是要求R為無(wú)窮大，而信道編碼定理要求RC，必然會(huì)失真。第1頁(yè)/共45頁(yè)2022/6/202/49 有些失真沒(méi)有必要完全消除（限失真信源編碼） 實(shí)際應(yīng)用中，人們一般并不要求獲得完全無(wú)失真的消息

2、，通常只要求近似地再現(xiàn)原始消息，即允許一定的失真存在。 打電話：即使語(yǔ)音信號(hào)有一些失真，接電話的人也能聽(tīng)懂。 放電影：理論上需要無(wú)窮多幅靜態(tài)畫(huà)面，由于人眼的“視覺(jué)暫留性”，實(shí)際上只要每秒放映24幅靜態(tài)畫(huà)面。l信息率失真理論-信息率失真函數(shù)l香農(nóng)定義了信息率失真函數(shù)R(D)。l定理指出：在允許一定失真度D的情況下，信源輸出的信息率可壓縮到的極限最小值為R(D)。第2頁(yè)/共45頁(yè)2022/6/203/49 在允許一定失真程度的條件下，怎樣用盡可能少的信道符號(hào)來(lái)表達(dá)信源的信息，也就是信源熵所能壓縮的極限或者說(shuō)編碼后信源輸出的信息率壓縮的極限值，這就是限失真信源編碼要討論的問(wèn)題。 限失真信源編碼也稱(chēng)保

3、真度準(zhǔn)則下的信源編碼、熵壓縮編碼或者稱(chēng)信息率失真理論，它是量化、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)。 無(wú)失真的冗余度壓縮編碼主要是針對(duì)離散信源。 限失真的熵壓縮編碼主要是針對(duì)連續(xù)信源。第3頁(yè)/共45頁(yè)2022/6/204/49 信息率失真函數(shù)是I(X;Y)的極小值 I(X;Y)是P(X)和P(Y/X)的二元函數(shù)； 固定p(xi) ，變更p(yj /xi)來(lái)求平均互信息的值。 由于I(X;Y)是p(yj /xi)的下凸函數(shù)，所求的極值一定是極小值。 但若X和Y相互統(tǒng)計(jì)獨(dú)立(p(yj /xi)= p(yj )， 求出的I(X;Y)極小值為0，因?yàn)镮(X;Y)是非負(fù)的，0必為極小值，但是這樣求出

4、的極小值0毫無(wú)意義(對(duì)應(yīng)完全失真)。 引入一個(gè)失真函數(shù)，計(jì)算在一定失真的情況下I(X;Y)的極小值才有意義。第4頁(yè)/共45頁(yè)2022/6/205/49 失真度 設(shè)離散無(wú)記憶信源為)(,),(),(,)(2121mmjypypypyyyypYY到接收端信源符號(hào)通過(guò)信道傳送)(,),(),(,)(2121nnixpxpxpxxxxpX)/()/()/()/()/()/()/()/()/()/(212222111211nmnnmmxypxypxypxypxypxypxypxypxypXYp信道的傳遞概率矩陣l對(duì)每一對(duì)(xi,yj)，指定一個(gè)非負(fù)函數(shù)d(xi,yj)0 i=1,2,n j=1,2,m稱(chēng)

5、d(xi,yj)為單個(gè)符號(hào)的失真度/失真函數(shù)。它表示信源發(fā)出一個(gè)符號(hào)xi，在接收端再現(xiàn)yj所引起的誤差或失真。第5頁(yè)/共45頁(yè)2022/6/206/49 均方失真： 絕對(duì)失真： 相對(duì)失真： 誤碼失真：2( , )()( , ) |( , ) |/|ijiiijiiijiiid x yx yd x yx yd x yx yx11( , )(,)Lijikjkkd x yd x yL失真函數(shù)的表達(dá)第6頁(yè)/共45頁(yè)2022/6/207/49常用的失真函數(shù) 失真函數(shù)是根據(jù)人們的實(shí)際需要，人為規(guī)定的。常用的失真函數(shù)有 (1)絕對(duì)失真：漢明失真漢明失真矩陣D通常為方陣，且對(duì)角線上的元素為0。即 (2)均方

6、失真：平方誤差失真函數(shù)如果信源符號(hào)代表信源輸出信號(hào)的幅度值，則上式意味著較大的幅度差值要比較小的幅度差值引起的失真更為嚴(yán)重，嚴(yán)重程度用平方表示。0( ,)1ijijijxyd x yxy01 1110111 1 10D 2( ,)(),ijijd x yxyij 第7頁(yè)/共45頁(yè)2022/6/208/49 失真矩陣 失真度表示成矩陣的形式，稱(chēng)D為失真矩陣。它是nm階矩陣。d(x,y)0 ),(),(),(),(),(),(),(),(),(212221212111mnnnmmyxdyxdyxdyxdyxdyxdyxdyxdyxdD第8頁(yè)/共45頁(yè)2022/6/209/49 平均失真度 平均失真

7、度：平均失真度為失真度的數(shù)學(xué)期望nimjjiijijijiyxdxypxpDyxdEDXYPYXyxd11),()/()(),()(),(由數(shù)學(xué)期望的定義中的統(tǒng)計(jì)平均值的聯(lián)合概率空間和在即，第9頁(yè)/共45頁(yè)2022/6/2010/49 平均失真度意義 是信源統(tǒng)計(jì)特性p(xi) 、信道統(tǒng)計(jì)特性p(yj/xi )和失真度d(xi,yj)的函數(shù) 。 當(dāng)p(xi)，p(yj/xi )和d(xi,yj)給定后，平均失真度就是一個(gè)確定的量。 如果p(xi)和d(xi,yj)一定， 就只是信道統(tǒng)計(jì)特性的函數(shù)。信道傳遞概率不同，平均失真度隨之改變。 保真度準(zhǔn)則 保真度準(zhǔn)則：規(guī)定平均失真度 不能超過(guò)某一限定的上

8、限值D，即 ，則D就是允許失真的上界。該式稱(chēng)為保真度準(zhǔn)則。 將保真度準(zhǔn)則作為信道傳遞概率的約束條件，再求I(X;Y)的最小值就有實(shí)際意義。DDDDD第10頁(yè)/共45頁(yè)2022/6/2011/49試驗(yàn)信道 當(dāng)固定信源（ P(X)已知），符號(hào)失真度也給定時(shí)，選擇信道使 。凡滿足要求的信道稱(chēng)為D失真許可的試驗(yàn)信道 所有試驗(yàn)信道構(gòu)成的集合用PD來(lái)表示，即DDmjniDDxypPijD, 2 , 1, 2 , 1: )/(第11頁(yè)/共45頁(yè)2022/6/2012/49 信息率失真函數(shù) 在信源和失真度給定以后，PD是滿足保真度準(zhǔn)則 的試驗(yàn)信道集合，由于I(X;Y)是信道傳遞概率p(yj /xi)的下凸函數(shù)

9、，所以在PD中一定可以找到某個(gè)試驗(yàn)信道，使I(X;Y)達(dá)到最小，即 R(D)稱(chēng)為信息率失真函數(shù)。 在信源給定以后，總希望在允許一定失真的情況下，傳送信源所需要的信息率越小越好。從接收端來(lái)看，就是在滿足保真度準(zhǔn)則 的條件下，尋找再現(xiàn)信源消息必須的最低平均信息量，即平均互信息的最小值。);(min)()/(YXIDRDijPxypDDDD 第12頁(yè)/共45頁(yè)2022/6/2013/49研究率失真函數(shù)的意義 是為了解決在已知信源和允許失真度D的條件下，使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號(hào)盡快地傳送盡可能多的信源消息，以提高通信的有效性。這是信源編碼問(wèn)題。第13頁(yè)/共45頁(yè)2022/

10、6/2014/49信息率失真函數(shù)的性質(zhì) 率失真函數(shù)的定義域 率失真函數(shù)的定義域問(wèn)題就是在信源和失真函數(shù)已知的情況下，討論允許平均失真度D的最小和最大值問(wèn)題。 D的選取必須根據(jù)固定信源X的統(tǒng)計(jì)特性P(X)和選定的失真函數(shù)d(xi , yj)，在平均失真度 的可能取值范圍內(nèi)。D第14頁(yè)/共45頁(yè)2022/6/2015/49 最小平均失真度Dmin 是非負(fù)函數(shù)d(xi , yj)的數(shù)學(xué)期望，也是一個(gè)非負(fù)函數(shù)，顯然其下限為0。因此允許平均失真度D的下限也必然是0，這就是不允許有任何失真的情況。 允許平均失真度D能否達(dá)到其下限值0，與單個(gè)符號(hào)的失真函數(shù)有關(guān)。 信源最小平均失真度Dmin ：在失真矩陣的每

11、一行找出一個(gè)最小的d(xi , yj) ，對(duì)所有這些不同的最小值求數(shù)學(xué)期望，就是信源的最小平均失真度。DnijijiyxdxpD1min),(min)(第15頁(yè)/共45頁(yè)2022/6/2016/49 信源最大平均失真度Dmax 信源最大平均失真度Dmax ：容忍的失真越大，所需的信息率就越小 。當(dāng)R(D)等于0時(shí)，對(duì)應(yīng)的平均失真D最大，也就是函數(shù)R(D)定義域的上界值Dmax 。 信息率失真函數(shù)是平均互信息的極小值： 當(dāng)R(D) =0時(shí)，即平均互信息的極小值等于0； 當(dāng)DDmax時(shí)，在接收端收不到信源發(fā)送的任何信息，信源符號(hào)的信息率可以壓縮至0。第16頁(yè)/共45頁(yè)2022/6/2017/49結(jié)

12、 論： R(D)的定義域?yàn)?Dmin, Dmax)； 一般情況Dmin =0， R(Dmin)=H(X)； 當(dāng)DDmax時(shí)，R(D)=0； 當(dāng)DminDDmax時(shí)，0R(D)H(X)。 率失真函數(shù)函數(shù)R(D)具有凸?fàn)钚?，它在定義域DminDDmax時(shí)：在D=Dmax處，除某些特例外，S將從某一個(gè)負(fù)值跳到0，S在此點(diǎn)不連續(xù)。在D的定義域0, Dmax內(nèi)，除某些特例外，S將是D的連續(xù)函數(shù)。第29頁(yè)/共45頁(yè)2022/6/2030/49(1) 二元離散信源的率失真函數(shù) 設(shè)二元信源 計(jì)算率失真函數(shù)R(D) 例：二元離散信源的信息率失真函數(shù) 1, 01, 0000211211)(212121yyYxxX

13、DppppxxxpXi輸出符號(hào)集輸入符號(hào)集失真矩陣為，所以，其中第30頁(yè)/共45頁(yè)2022/6/2031/49 先求出DmaxpDDDDDpppppDDDDDDypDyxdxpDjjjjjjmjjypjiniijj2max2121max1)(max1min21)1(001min)(min),()(，故有已知第31頁(yè)/共45頁(yè)2022/6/2032/49第一步：求i，由式(4.2.12)有)1)(1 (1)1 (11)1 (1)1 (1)()(1)()(212121),(22),(11),(22),(1122211211SSSSyxSdyxSdyxSdyxSdepepppeeppexpexpex

14、pexp)12. 2 . 4(), 2 , 1, 0)( , 1)(1),(mjypexpjniyxSdiiji第32頁(yè)/共45頁(yè)2022/6/2033/49第二步：求p(yj)，由式(4.2.11)有SSSSSSSSyxSdyxSdyxSdyxSdmjyxSdjiepepypeeppypepypeypepeypypeypeypeypeypeypji1)1 ()(1)1 ()(1)1 ()()(1)()(1)()(1)()()11. 2 . 4()(12121212),(2),(11),(2),(11),(22122111第33頁(yè)/共45頁(yè)2022/6/2034/49第三步：求p(yj/xi)

15、，由式(4.2.10)有)1)(1 ()1 ()/()1 ()1 ()/()1)(1 ()1 ()/()1 ()1 ()/()()/()()/()()/()()/()10. 2 . 4(,2 , 1;, 2 , 1)()/(222212221211),(2222),(1212),(2121),(1111),(22211211SSSSSSSSSSyxSdyxSdyxSdyxSdyxSdijijeppepxypeeppepxypeepeppxypepeppxypeypxypeypxypeypxypeypxypmjnieypxypji第34頁(yè)/共45頁(yè)2022/6/2035/49第四步：求D(S)，

16、將上述結(jié)果代入式(4.2.14)有SSSSSSSSyxSdyxSdyxSdyxSdyxSdinimjjijieeeppeppepeeepppeyxdypxpeyxdypxpeyxdypxpeyxdypxpSDeyxdypxpSDji1)1 ()1 ()1)(1 (1)1 ()1 (),()()(),()()(),()()(),()()()()14. 2 . 4(),()()()(),(12222),(22121),(11212),(11111),(1122111211第35頁(yè)/共45頁(yè)2022/6/2036/49第五步：求率失真函數(shù)R(S)，將上述結(jié)果代入式(4.2.15)有)1ln()1ln

17、()1 (ln1ln)1 (ln1)()15. 2 . 4(ln)()()(211SSSSSiniieppppeeSppeeSSRxpSSDSR第36頁(yè)/共45頁(yè)2022/6/2037/49對(duì)于這種簡(jiǎn)單信源，可從D(S)解出S與D的顯式表達(dá)式為：DDDDDDDDDDppxypppDxypppDxypppxypDDpypDDpyppDpDDDS212212221211212111111)/(11)/(11)/(11)/(21)1 ()(21)(1111ln將S S代入上面的ii，p p( (yjyj) )和p p( (yjyj/ /xixi) )和R(S)R(S)得：第37頁(yè)/共45頁(yè)2022/

18、6/2038/49ppSpDDDRDDpHRDDHpHppppDDDDDR1ln1,0)(,)()0(, 0)()1ln()1 (ln1ln)1 (ln)(maxmaxmaxmax壓縮的信息率。定失真而可能熵，第二項(xiàng)是因容忍一上式右邊第一項(xiàng)是信源以及第38頁(yè)/共45頁(yè)2022/6/2039/49第六步：通過(guò)以上步驟計(jì)算出來(lái)的R(D)和S(D)如圖4.2.2 。(2) 說(shuō)明：l若=1，把d(xi , yj)當(dāng)成了誤碼，即X和Y不一致時(shí)，認(rèn)為錯(cuò)了一個(gè)碼元，所以d(xi , yj)的數(shù)學(xué)期望就是平均誤碼率。能容忍的失真等效于能容忍的誤碼率。第39頁(yè)/共45頁(yè)2022/6/2040/49 R(D)不僅與D有關(guān)，還與p有關(guān)。概率分布不同， R(D)曲線就不一樣。當(dāng)p=0.25時(shí)，如果能容忍的誤碼率也是0.25，不用傳送信息便可達(dá)到R=0，這就是R(Dmax) =0的含義。第40頁(yè)/共45頁(yè)2022/6/2041/49 當(dāng)D相同時(shí)，信源越趨于等概率分布， R(D)就越大。由最大離散熵定理，信源越趨于等概率分布，其熵越大，即不確定性越大，要去除這不確定性所需的