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

d(xi,yj)≥0

i=1,2,…,n

j=1,2,…,m稱d(xi,yj)為符號失真度(失真函數)。符號失真度表示信源發出一個符號xi，在接收端再現yj

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

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

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

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

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

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

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

R（D）

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

D1,D2

Dmax），則下式成立：

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

R(D2)率失真函數R(D)是連續單調函數2/3/2023154.4率失真函數例:求率失真函數已知信源{x1=0，x2=1}，概率分布為（δ，1-δ),δ<0.5，信道輸出符號Y={y1=0，y2=1}，失真測度為漢明（Hamming）失真測度，求率失真函數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δ的范圍內，計算R(D）根據熵的性質：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率失真函數2/3/2023174.4率失真函數對于漢明失真度，平均失真度為：在R(D)的定義中，要求滿足平均失真度小于等于D，取等號則：

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

H(δ)-H(D)

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

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

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

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

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

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