信息論第七講率失真函數(shù)

4.4率失真函數(shù)(RateDistortionFunction)引言上面我們介紹的編碼也稱為無失真編碼（無損編碼），另外一類編碼稱為限失真編碼（有損編碼）。率失真理論研究的就是在允許一定失真的前提下，對(duì)信源的壓縮編碼。率失真信源編碼定理（香農(nóng)第三定理）指出：率失真函數(shù)R(D)就是在給定失真測(cè)度條件下，對(duì)信源壓縮的最低程度。也就是說：為了提高傳輸效率，可以給定一個(gè)失真度，求出在平均失真小于給定值的條件下，信源所能壓縮的程度的極限值，即率失真函數(shù)R(D)。2/3/202314.4率失真函數(shù)4.4.1失真度與平均失真度(1)符號(hào)失真度設(shè)單符號(hào)離散無記憶信源、信宿及信道為：DMCXY2/3/202324.4率失真函數(shù)定義：對(duì)每一對(duì)(xi,yj)，指定一個(gè)非負(fù)函數(shù)

d(xi,yj)≥0

i=1,2,…,n

j=1,2,…,m稱d(xi,yj)為符號(hào)失真度(失真函數(shù))。符號(hào)失真度表示信源發(fā)出一個(gè)符號(hào)xi，在接收端再現(xiàn)yj

所引起的誤差或失真。2/3/202334.4率失真函數(shù)(2)平均失真度d(xi,yj)只能表示兩個(gè)特定的具體符號(hào)xi和yj之間的失真。平均失真度：平均失真度為失真度的數(shù)學(xué)期望。2/3/202344.4率失真函數(shù)(3)平均失真度意義它是在平均意義上，對(duì)整個(gè)系統(tǒng)失真情況的總體描述。它是信源統(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è)確定的量。如果信源和失真度一定，它就只是信道統(tǒng)計(jì)特性的函數(shù)。信道不同，平均失真度隨之改變。2/3/202354.4率失真函數(shù)(4)失真度描述失真度一般用失真度矩陣來描述。2/3/202364.4率失真函數(shù)例：漢明（Hamming）失真度X={x1,x2,…,xn}，Y={y1,y2,…,yn}，約定失真度用矩陣表示為式中dij≥0i,j=1,2,…,n為信源方發(fā)送符號(hào)xi而信宿方判為yj引起的失真度。2/3/202374.4率失真函數(shù)例:平方誤差失真度X={0,1,2}，Y={0,1,2}

，給出失真度dij=(xi-yj)2

i,j=0,1,2則失真度矩陣為

2/3/202384.4率失真函數(shù)例:絕對(duì)誤差失真度X={0,1,2}，Y={0,1,2}

，給出失真度dij=︱xi-yj︱

i,j=0,1,2則失真度矩陣為:

2/3/202394.4.2率失真函數(shù)(1)允許失真度D對(duì)于單符號(hào)離散無記憶信源X、信宿Y及信道P(Y/X)：給定信源X概率分布p(x)和失真度矩陣[d]=[dij]，如果信道轉(zhuǎn)移概率矩陣[P]=[p(Y/X)]滿足如下關(guān)系，則式中的D則稱為允許失真度，關(guān)系式稱為保真度準(zhǔn)則。4.4率失真函數(shù)2/3/2023104.4率失真函數(shù)(2)率失真函數(shù)R(D)我們知道：當(dāng)信源p(x)一定時(shí)，平均交互信息量I(X;Y)是信道轉(zhuǎn)移概率函數(shù)p(y/x)的下凸函數(shù)。也就是說：平均互信息量I(X;Y)關(guān)于p(y/x)存在極小值。定義：平均交互信息量關(guān)于信道轉(zhuǎn)移概率的極小值為率失真函數(shù)R(D)，即：2/3/2023114.4率失真函數(shù)(3)率失真函數(shù)的含義通過選擇合適的信道轉(zhuǎn)移概率p(y/x)（實(shí)際上選擇某種信道編碼方法），在滿足一定的失真度要求前提下（平均失真度<允許失真度D），使平均交互信息量達(dá)到最小值R(D)。率失真函數(shù)表明了在滿足平均失真度小于D條件下，信源傳輸信息量（信息速率）可壓縮的最低程度。在信源和失真度給定以后，存在滿足保真度準(zhǔn)則的信道集合，一定有某個(gè)信道，使I(X;Y)達(dá)到最小。2/3/2023124.4率失真函數(shù)(4)率失真函數(shù)的定義域R(D)的值域率失真函數(shù)的值域?yàn)?

R（D）

H（X）D的最小值Dmin在給定的失真度矩陣中，對(duì)每一個(gè)xi，找一個(gè)最小的dij，然后對(duì)所有的i=1,2,…,n求統(tǒng)計(jì)平均值，就是D的最小值，即DDmax0DminH（X）R(D)2/3/2023134.4率失真函數(shù)D的最大值Dmax當(dāng)R(D)達(dá)到其最小值Rmin（D）=0時(shí)，對(duì)應(yīng)的失真最大，這種情況下D對(duì)應(yīng)著R(D)函數(shù)定義域的上界值Dmax。DDmax0DminH（X）R(D)2/3/2023144.4率失真函數(shù)(5)率失真函數(shù)的性質(zhì)率失真函數(shù)R(D)是D的下凸函數(shù)。分別給定兩個(gè)失真度D1和D2（Dmin

D1,D2

Dmax），則下式成立：

R(α1D1+α2D2)≤α1R(D1)+α2

R(D2)率失真函數(shù)R(D)是連續(xù)單調(diào)函數(shù)2/3/2023154.4率失真函數(shù)例:求率失真函數(shù)已知信源{x1=0，x2=1}，概率分布為（δ，1-δ),δ<0.5，信道輸出符號(hào)Y={y1=0，y2=1}，失真測(cè)度為漢明（Hamming）失真測(cè)度，求率失真函數(shù)R(D)。(1)求出R(D)的定義域Dmin=0·δ+0·(1-δ)=0Dmax=min{1-δ,δ}=δ

2/3/202316(2)求出R(D)的值域R(Dmin=0)=H(X)=-δlogδ-(1-δ)log(1-δ)=H

(δ)R(Dmax)=R(δ)=0(3)在0

Dδ的范圍內(nèi)，計(jì)算R(D）根據(jù)熵的性質(zhì)：H(X,Y)

H(X)

H(X/Y)又由：H(X)＝

H()則平均互信息量

I(X;Y)＝H(X)-H(X／Y)，得到

I(X;Y)＝

H(δ)-H(X／Y)4.4率失真函數(shù)2/3/2023174.4率失真函數(shù)對(duì)于漢明失真度，平均失真度為：在R(D)的定義中，要求滿足平均失真度小于等于D，取等號(hào)則：

H(X/Y)≤H(Pe)=H(D)則：I(X;Y)

H(δ)-H(D)

根據(jù)定義:(信道誤碼率）可知：0≤Pe≤D≤δ(Fano不等式）2/3/2023184.4率失真函數(shù)Fano不等式設(shè)X，Y為離散隨機(jī)變量，分別取值為:X:(x1,x2,……xn)Y:(y1,y2,……yn)Pe=P{X≠Y}.則:2/3/2023194.4率失真函數(shù)(4)求出P(Y/X)找到一個(gè)信道轉(zhuǎn)移概率矩陣為[P]的信道，使H(X/Y)=H(D)，且[P]中的每一個(gè)元素p(yj︱xi)都滿足p(yj︱xi)0

i,j=1,2根據(jù)[d]的對(duì)稱性，假設(shè)一個(gè)反向信道(Y→X)由假設(shè)的反向信道計(jì)算平均失真度，得（滿足失真準(zhǔn)則）2/3/2023204.4率失真函數(shù)這時(shí)計(jì)算條件熵（反向信道噪聲上）則平均互信息量I(X;Y)=H(X)-H(X/Y)=H(δ)-H(D)，假設(shè)的[q(x/y)]確實(shí)在滿足失真準(zhǔn)則條件下，使

I(X;Y)=H(δ)-H(D)從而有

2/3/202321求正向信道轉(zhuǎn)移概率可得:由上面方程組解出，由P(X),P(Y)和P(X/Y)就可以求出相應(yīng)的P(Y/X).以一個(gè)特例說明存在這樣的信道轉(zhuǎn)移概率矩陣[P].4.4率失真函數(shù)2/3/2023224.4.3限失真信源編碼定理香農(nóng)第三編碼定理設(shè)離散無記憶信源的信息率失真函數(shù)為R(D)，只要滿足R>R(D)，當(dāng)信源序列足夠長時(shí)，一定存在一種編碼方法，其譯碼失真小于或等于D+ε，其中ε是任意小的正數(shù)；反之，若R<R(D)，則無論采用什么樣的編碼方法，其譯碼失真必大于D。這個(gè)定理給出了限失真信源編碼的極限。只要允許一定的失真就可以降低熵速率。4.4率失真函數(shù)2/3/2023234.4率失真函數(shù)率失真函數(shù)的理解(Rate+Distortion=Function)信息率失真函數(shù)是在滿足平均失真不大于D的條件下，信源必須輸出的最小信息量。如果信源輸出信息速率R小于R(D)，則無論對(duì)于什么信道，無法找到編碼方法使信宿收到的信息保證失真度要求。如果信源輸出信息速率R不小于R(D)，則無論對(duì)于什么信道，總可以找到編碼方法使信宿收到的信息保證失真度要求。2/3/2023244.4率失真函數(shù)R(D)與C的比較信道容量C表示一個(gè)信道的最大傳輸能力。它反映的是信道本身的特性，與信源無關(guān)?；蛘哒f信道容量是在最好的參考信源條件下的信道轉(zhuǎn)移概率的函數(shù)。不同的信道有不同的信道容量。信息率失真函數(shù)R(D)是保真度條件下一個(gè)信源的信息速率可以被壓縮的最低限度。它反映的是信源本身的特性，與信道無關(guān)?；蛘哒f信息率失真函數(shù)是在最差的參考信道條件下的信源先驗(yàn)概率和D的函數(shù)。不同的信源有不同的率失真函數(shù)。I(X,Y)P(Y/X)R(D)2/3/2023254.5信源編碼綜述4.5.1信源編碼概述在通信系統(tǒng)模型中，編碼的目的就是實(shí)現(xiàn)有效、可靠和安全的信息傳輸、交換、存儲(chǔ)和識(shí)別。廣義地講，針對(duì)三個(gè)目的有三大類編碼，分別是信源編碼、信道編碼和保密編碼（密碼學(xué)）。（常存在矛盾）從信息論角度講，信源編碼分為無失真信源編碼和限失真信源編碼。無失真編碼：主要用于離散信源（數(shù)字信號(hào)）；限失真編碼：主要用于連續(xù)信源（模擬信號(hào)）；信源編碼的主要性能指標(biāo)是編碼效率，它的本質(zhì)就是理論碼率和實(shí)際碼率的比。2/3/2023264.5信源編碼綜述無失真編碼也稱為可逆編碼（信源符號(hào)經(jīng)過編碼后，可以從編碼中無失真地恢復(fù)信源符號(hào)）。已知符號(hào)概率即可計(jì)算信源熵H，就可以使平均碼長任意接近H。編碼的方法的基本思想就是概率與碼長的匹配。對(duì)于符號(hào)概率不可知，或者非平穩(wěn)，或長相關(guān)信源無法應(yīng)用。限失真編碼也稱為不可逆編碼（連續(xù)信源編碼后無法無失真的恢復(fù)）。根據(jù)率失真理論進(jìn)行限失真編碼；在失真小于D的條件下碼率可以壓縮到R(D)，但是定理沒有給出實(shí)現(xiàn)途徑?，F(xiàn)有的方法就是最佳量化問題，標(biāo)量量化不行，需要矢量量化（多個(gè)符號(hào)合成一個(gè)矢量再編碼）。有記憶信源的熵小，去掉相關(guān)性可以降低碼率，解決的方法就是預(yù)測(cè)編碼和變換編碼。2/3/2023274.5信源編碼綜述4.5.2信源編碼方法無失真信源編碼可逆編碼，無損編碼、熵編碼(EntropyCoding）Huffman編碼，算術(shù)編碼，游程編碼，LZW編碼等。限失真信源編碼不可逆編碼，有損編碼、源編碼(SourceCoding

）預(yù)測(cè)編碼：利用過去和當(dāng)前的數(shù)據(jù)對(duì)在時(shí)間或空間上將來的數(shù)據(jù)進(jìn)行預(yù)測(cè)，從而達(dá)到壓縮的目的，如DM、ADPCM。變換編碼：利用數(shù)學(xué)變換方法，將原時(shí)域或空域的數(shù)據(jù)變換到頻率域或其它域，利用數(shù)據(jù)在變換域中的冗余或人類感覺的冗余特征實(shí)現(xiàn)的壓縮，如DCT、DWT。分層編碼：將原數(shù)據(jù)在時(shí)空域或頻域上分成若干子區(qū)域，利用人類感覺的特征進(jìn)行壓縮編碼，然后再合并，如子帶編碼其他編碼：如矢量量化、運(yùn)動(dòng)補(bǔ)償、音感編碼。2/3/2023284.5信源編碼綜述混合編碼方法(HybridCoding)熵編碼+源編碼大多數(shù)壓縮標(biāo)準(zhǔn)都采用混合編碼的方法，一般是先利用源編碼進(jìn)行有損壓縮，再利用熵編碼做進(jìn)一步的無損壓縮。如H.26X、JPEG、MPEG等。2/3/2023294.5信源編碼綜述4.5.3信源編碼與數(shù)據(jù)壓縮技術(shù)以山農(nóng)信源編碼為基礎(chǔ)，結(jié)合信號(hào)處理和多媒體通信技術(shù)的發(fā)展，逐步形成了系統(tǒng)的數(shù)據(jù)壓縮技術(shù)。信源數(shù)據(jù)壓縮的基本條件是信源消息符號(hào)原始存在的狀態(tài)冗余。1）信源數(shù)據(jù)中存在或多或少的冗余，這種冗余既存在信源本身的相關(guān)性中，也存在于信源概率分布的不均勻中；如空間冗余、時(shí)間冗余、結(jié)構(gòu)冗余、知識(shí)冗余及紋理統(tǒng)計(jì)冗余；2）對(duì)于圖像、音頻和視頻等特殊信源，人的感知可容忍某些細(xì)節(jié)信息的丟失（失真）（感知冗余）。2/3/2023304.5信源編碼綜述4.5.4算術(shù)編碼(arithmeticcoding)算術(shù)編碼引出：算術(shù)編碼和Huffman編碼一樣，也是一種熵編碼，無失真編碼。Huffman編碼是建立了一種原始信源符號(hào)Si與信道碼字Wi的一一對(duì)應(yīng)的映射關(guān)系。因此也稱為塊碼(Block)，或者分組碼(Group)。Huffman編碼的不足：不太適合二進(jìn)制信源；符號(hào)相關(guān)性沒有充分考慮；碼長必須為整數(shù)位，碼長與符號(hào)概率匹配性不是太好。2/3/2023314.5信源編碼綜述算術(shù)編碼思想：針對(duì)序列進(jìn)行編碼，建立遞推關(guān)系。不用二整數(shù)代碼來表示符號(hào)，而改用[0，1)半開區(qū)間中實(shí)數(shù)的二元小數(shù)序列來表示。[0，1)可以分為n個(gè)子區(qū)間，每個(gè)寬度值等于一個(gè)符號(hào)的先驗(yàn)概率，符號(hào)表中的所有符號(hào)剛好布滿整個(gè)[0，1)區(qū)間（概率和為1）。編碼過程就是把輸入符號(hào)串（數(shù)據(jù)流）映射成[0，1)區(qū)間中對(duì)應(yīng)子區(qū)間中的一個(gè)實(shí)數(shù)值。2/3/2023324.5信源編碼綜述算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)(如JPEG，JBIG)中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實(shí)數(shù)進(jìn)行編碼。算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)概率和它的編碼間隔。編碼效率取決于符號(hào)概率和編碼間隔，編碼間隔取決于符號(hào)概率和符號(hào)相關(guān)性，而這些間隔包含在0到1之間。2/3/2023334.5信源編碼綜述編碼舉例

假設(shè)信源符號(hào)為{00,01,10,11}，這些符號(hào)的先驗(yàn)概率分別為{0.1,0.4,0.2,0.3}，根據(jù)這些先驗(yàn)概率可把間隔[0,1)分成4個(gè)子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)，二進(jìn)制序列的輸入為：10001100101101。2/3/2023344.5信源編碼綜述2/3/2023354.5信源編碼綜述算術(shù)編碼是一種二元碼的編碼方法。在不考慮信源統(tǒng)計(jì)的情況下，不管統(tǒng)計(jì)是平穩(wěn)的或非平穩(wěn)的，編碼的碼率總能趨近于信源熵，每次迭代時(shí)的編碼算法只處理一個(gè)數(shù)據(jù)符號(hào)，并且只有算術(shù)運(yùn)算。隨著被編碼數(shù)據(jù)流符號(hào)的輸入，子區(qū)間寬度逐漸縮小。表示為數(shù)值精度逐漸提高，二進(jìn)制代碼逐漸加長。2/3/2023364.5信源編碼綜述新子區(qū)間的起始位置=前子區(qū)間的起始位置+當(dāng)前符號(hào)的區(qū)間左端×前子區(qū)間長度；0.5=0.5+0X0.2;0.514=0.5+0.7X0.022/3/2023374.5信源編碼綜述新子區(qū)間的長度=前子區(qū)間的長度×當(dāng)前符號(hào)的概率（等價(jià)于范圍長度）；0.02=0.2X0.1;0.0006=0.006X0.12/3/2023384.5信源編碼綜述最后得到的子區(qū)間的長度(一個(gè)小數(shù)）決定了表示該區(qū)域內(nèi)的某一個(gè)數(shù)所需的位數(shù)。算術(shù)編碼在編、譯碼的過程中，子區(qū)間的起始位置和長度值的小數(shù)點(diǎn)后的位數(shù)越來越長，實(shí)際中無法實(shí)現(xiàn)。因此較實(shí)用的改進(jìn)算法是限制小數(shù)點(diǎn)后的位數(shù)。2/3/2023394.5信源編碼綜述例如：已知信源X=(0,1);(0.25,0.75)試對(duì)1011進(jìn)行算術(shù)編碼.0.01.00.2510110.251.00.250.43750.2968750.43750.332031250.4375輸出2/3/2023404.5信源編碼綜述最后的子區(qū)間起始位置C＝（0.332