1、信息學院 信息工程教研室牛秋娜Information Theory & Coding 第四章第四章 限失真信源編碼限失真信源編碼（計劃學時計劃學時 12）第四章第四章 限失真信源編碼限失真信源編碼4.1 信源的有損壓縮信源的有損壓縮 1 4.2 率失真函數率失真函數 24.3 保真度準則下的信源編碼保真度準則下的信源編碼 1 4.4 連續信源的限失真編碼連續信源的限失真編碼 2 4.5 預測編碼預測編碼 34.6 變換編碼變換編碼 3 教學目的與要求教學目的與要求深刻理解限失真編碼的意義。深刻理解限失真編碼的意義。理解率失真函數的概念，了解變化規理解率失真函數的概念，了解變化規律。律。

2、了解離散信源和連續信源的限失真編了解離散信源和連續信源的限失真編碼。碼。了解預測編碼和變換編碼的原理，及了解預測編碼和變換編碼的原理，及其在語音和圖像壓縮中的應用。其在語音和圖像壓縮中的應用。 參考文獻參考文獻1.吳樂南吳樂南：數據壓縮數據壓縮 電子工業出版社（2001年6月第一版） 2.吳偉陵吳偉陵：信息處理與編碼信息處理與編碼 人民郵電出版社（1999年7月第一版）3.曹雪虹：曹雪虹：信息論與編碼信息論與編碼 北京北京郵電大學出版社（郵電大學出版社（20012001年年8 8月第一版）月第一版） 第四章第四章 限失真信源編碼限失真信源編碼4.1 4.1 信源的有損壓縮信源的有損壓縮本節主要

3、內容本節主要內容限失真信源編碼定義限失真信源編碼定義失真度的定義失真度的定義單個符號的失真度單個符號的失真度平均符號失真度平均符號失真度序列的平均失真度序列的平均失真度限失真信源編碼：限失真信源編碼： distortion constraint source coding 失真度：失真度：distortion 平均失真度：平均失真度：average distortion 外語關鍵詞外語關鍵詞溫舊引新溫舊引新信源編碼：壓縮代碼長度的編碼。信源編碼：壓縮代碼長度的編碼。平均互信息的極值性：平均互信息的極值性：當信道給定時，互信息僅由信源決定，總當信道給定時，互信息僅由信源決定，總存在一個信源能使互

4、信息取極大值；當信存在一個信源能使互信息取極大值；當信源給定時，互信息僅由信道決定，總存在源給定時，互信息僅由信道決定，總存在一個信道能使互信息取極小值一個信道能使互信息取極小值。傳信率與平均互信息：傳信率與平均互信息： Rt =RBI(X;Y)連續信源的連續信源的相對熵：相對熵：dxxpxpxh)(log)()( 4.1 4.1 信源的有損壓縮信源的有損壓縮4.1.1 信源有損壓縮的實際意義信源有損壓縮的實際意義 在許多情況下，比如連續信源，數字通信不可能在許多情況下，比如連續信源，數字通信不可能實現對消息的完全無失真傳輸。實現對消息的完全無失真傳輸。實際問題中，即使存在少量失真，往往并不會

5、明實際問題中，即使存在少量失真，往往并不會明顯影響通信質量。顯影響通信質量。既然允許一定的失真存在，就可以人為地削減一既然允許一定的失真存在，就可以人為地削減一些信息，信息率便可大大降低，對于提高通信效些信息，信息率便可大大降低，對于提高通信效率與節約成本都有利。率與節約成本都有利。信源有損壓縮實例信源有損壓縮實例話音通信中信息的有損壓縮：話音通信中信息的有損壓縮： PCM脈沖編碼調制脈沖編碼調制 LPC語音參數編碼語音參數編碼圖像處理中信息的有損壓縮：圖像處理中信息的有損壓縮： 傳真通信傳真通信 圖像壓縮存儲（圖像壓縮存儲（JPG與與GIF格式）格式）視頻傳輸中信息的有損壓縮：視頻傳輸中信息

6、的有損壓縮： 數字電視數字電視 VCD與與DVD 然而，有損壓縮不能無限制地進行，過大的壓縮必然造成然而，有損壓縮不能無限制地進行，過大的壓縮必然造成較大的失真，將嚴重影響通信質量。較大的失真，將嚴重影響通信質量。因此，科學的語言是因此，科學的語言是限限失真信源編碼，而不是失真信源編碼，而不是有有失真信源失真信源編碼。編碼。在在容許失真且限定失真的條件下壓縮信源代碼長度的編碼容許失真且限定失真的條件下壓縮信源代碼長度的編碼，叫做叫做限失真信源編碼限失真信源編碼。本章本章理論上需要探討的問題是理論上需要探討的問題是：所限定的失真度與信道最所限定的失真度與信道最少需要傳輸的信息率的關系。這個關系叫

7、做少需要傳輸的信息率的關系。這個關系叫做率失真函數。率失真函數。實踐上需要解決的問題是實踐上需要解決的問題是：在保證失真不超過規定大小的在保證失真不超過規定大小的條件下，如何通過編碼把信源消息壓縮到最小。條件下，如何通過編碼把信源消息壓縮到最小。兩種限失真傳輸：兩種限失真傳輸：l一種是離散信源限失真傳輸，這里主要是編一種是離散信源限失真傳輸，這里主要是編碼的問題。碼的問題。l另一類是連續信源限失真傳輸，主要是數字另一類是連續信源限失真傳輸，主要是數字化的問題。化的問題。更廣義的認識，凡是更廣義的認識，凡是不要求完全無失真不要求完全無失真地恢復地恢復原信號的信號處理過程，都可當作限失真傳輸原信號

8、的信號處理過程，都可當作限失真傳輸過程，比如圖像技術中廣泛使用的變換編碼、過程，比如圖像技術中廣泛使用的變換編碼、預測編碼以及語音系統中的聲碼合成技術等。預測編碼以及語音系統中的聲碼合成技術等。 1 1、單個符號的失真度、單個符號的失真度：對于所收發的每一對符號對于所收發的每一對符號(ui ,vj)定義一個非負的函數：定義一個非負的函數： d(ui , vj)0 ( i = 1,2,3,r； j = 1,2,3,s ) 稱為稱為單個符號的失真度單個符號的失真度，用它來測度信源發出符號，用它來測度信源發出符號ui而在而在接收端再現成符號接收端再現成符號vj的失真程度。的失真程度。這個函數的定義應

9、當使這個函數的定義應當使d值的大小能反映失真的大小，值的大小能反映失真的大小，d=0應代表沒有失真。應代表沒有失真。信源信源信源編碼信源編碼信宿譯碼信宿譯碼信宿信宿廣義廣義無擾信道無擾信道U UV Vp p( (ui ,vj) )4.1.2 4.1.2 失真度的定義失真度的定義 失真函數的形式失真函數的形式 失真函數失真函數d (ui, vj)的具體形式，在不同問題的具體形式，在不同問題中可以有不同的規定。中可以有不同的規定。常見的形式：常見的形式：2( ,)()ijijd u vuv平方失真：平方失真：絕對失真：絕對失真：(,) |ijijd uvuv相對失真：相對失真：|(,)|ijiji

10、uvd uvu誤碼失真：誤碼失真：1( ,)( ,)0ijijijijuvd u vu vuv失真度矩陣失真度矩陣由于有由于有r個個ui和和s個個vj，所以可定義出，所以可定義出rs個個 d (ui , vj)，構成一個，構成一個失真度矩陣失真度矩陣：111212122212( ,)( ,)( ,)(,)(,)(,)(,)(,)(,)ssrrrsd u vd u vd u vd u vd u vd u vd u vd u vd u vD例例1 求漢明失真（即誤碼失真）的失真度矩陣。求漢明失真（即誤碼失真）的失真度矩陣。 由誤碼失真定義，若經傳輸后再現的接收符號由誤碼失真定義，若經傳輸后再現的接

11、收符號與發送符號相同，則無失真；若不同，則不論與發送符號相同，則無失真；若不同，則不論是其他哪個符號，都有相同的失真度是其他哪個符號，都有相同的失真度1。于是失真矩陣必然是對角為零，非對角元為于是失真矩陣必然是對角為零，非對角元為1的的形式：形式： 0 1 111 0 111 1 10D0110D對二元對稱信源，對二元對稱信源，d (0,0) = d (1,1)=0；d (1,0) = d (0,1)=1：例例2已知已知U =0,1,2,V =0,1,2,求平求平方失真度矩陣。方失真度矩陣。如果信宿感覺到失真的嚴重程度與幅度偏差的平如果信宿感覺到失真的嚴重程度與幅度偏差的平方成正比的話，可按方

12、成正比的話，可按平方失真平方失真d(ui,vj)=(ui-vj) 2定義定義失真度，則：失真度，則：d(0,0)d(1,1)d(2,2)0d(0,1)d(1,0)d(1,2)d(2,1)1d(0,2)d(2,0)4 0 1 41 0 14 1 0D所以：所以：小結：小結：單個符號的失真度單個符號的失真度d(ui,vj)定義了該種誤碼（若發定義了該種誤碼（若發送送ui而接收的是而接收的是vj ）對通信質量的影響程度。）對通信質量的影響程度。單符號失真度排列成的失真度矩陣單符號失真度排列成的失真度矩陣D，它與信道，它與信道傳輸矩陣傳輸矩陣P一樣，一樣， “行行”為發送符號，為發送符號，“列列”為為

13、接收符號。但是接收符號。但是P的矩陣元是各種傳輸情況出現的矩陣元是各種傳輸情況出現的概率，的概率，D卻反映各種傳輸情況失真的大小。卻反映各種傳輸情況失真的大小。失真度的定義是人為的，因事而異的，旨在體現失真度的定義是人為的，因事而異的，旨在體現誤碼對該問題影響的嚴重程度。一般說來，對于誤碼對該問題影響的嚴重程度。一般說來，對于不同的發送接收符號對，失真度是不同的。不同的發送接收符號對，失真度是不同的。2 2、平均符號失真度、平均符號失真度：通信過程中不同符號的失真程度一般是不一樣通信過程中不同符號的失真程度一般是不一樣的，我們可以用平均失真度來定義系統收發每的，我們可以用平均失真度來定義系統收

14、發每對符號的的平均失真度：對符號的的平均失真度：, ( ,)() ( , )ijU VDE d u vP uv d u vP P( (uv) )是聯合概率密度，利用是聯合概率密度，利用P P( (uv)=)=P P( (u) )P P( (v|u) )則：則：11() (,)rsijijijDP u vd u v11( ) (/) ( ,)rsijiijijP u P vu d u v若定義失真函數為絕對若定義失真函數為絕對失真，失真，求平均求平均失真度。失真度。解：按解：按絕對失真絕對失真d(ui,vj)=|ui-vj|的定義，有：的定義，有：101210D聯合概率：聯合概率：00. 035

15、. 015. 005. 015. 030. 0)|()()(uvpupuvp0 . 07 . 03 . 01 . 03 . 06 . 0)|(uvp例例3已知等概信源已知等概信源U =0,1，信宿，信宿V =0,1,2，信道傳輸矩陣，信道傳輸矩陣為：為：平均失真度：平均失真度：11() (,)rsijijijDP u vd u v=00.3 +10.15 +20.05 +10.15+ 00.35 +10=0.43 3、序列的平均失真度：、序列的平均失真度：信源發出長為信源發出長為K的序列的序列i ，各符號均取自同一符，各符號均取自同一符號集號集U=u1 u2.ur ，經信道再現為長為，經信道再

16、現為長為K的的序列序列j ，各符號取自符號集，各符號取自符號集V=v1 v2vs，于是在于是在r K 個個i與與sK個個j之間可定義之間可定義序列失真度序列失真度：1()(,)(,)llKijijlD Kdd uv （i=1,2,=1,2, ,rK；j j=1,2,=1,2, , ,sK） 序列的平均失真度序列的平均失真度： 11()() (,)KKrsijijijD KPd 111() (/)(,)KKllrsKijiijijlPPd u v如果信源和信道都是無記憶的，則序列的平均如果信源和信道都是無記憶的，則序列的平均失真度等于各位符號的平均失真度之和：失真度等于各位符號的平均失真度之和：

17、1()KllD KD 是序列中第是序列中第l個符號的單符號平均失真度。個符號的單符號平均失真度。lD在離散信源為平穩信源的情況下在離散信源為平穩信源的情況下，序列先后發出，序列先后發出 K個符號時統計性質不因時間而變化，所以：個符號時統計性質不因時間而變化，所以：lDD于是：于是：()D KK D第四章第四章 限失真信源編碼限失真信源編碼4.24.2 率失真函數率失真函數本節主要內容本節主要內容保真度準則保真度準則率失真函數的定義率失真函數的定義率失真函數的性質率失真函數的性質率失真函數的計算率失真函數的計算保真度準則：保真度準則：Fidelity Criteria 率失真函數：率失真函數：r

18、ate distortion function 漢明失真：漢明失真：Hamming distortion 外語關鍵詞外語關鍵詞外語關鍵詞外語關鍵詞4.2.1 4.2.1 保真度準則保真度準則 作為限失真傳輸，首先，允許失真存在，其次，作為限失真傳輸，首先，允許失真存在，其次，要限制失真的大小。要限制失真的大小。為了定量化，可預先指定一個允許失真的上限為了定量化，可預先指定一個允許失真的上限值值D，叫做，叫做保真度保真度，要求通信系統的平均每符，要求通信系統的平均每符號失真度不得大于此值：號失真度不得大于此值：DD即滿足即滿足保真度準則：保真度準則： 對于平穩無記憶信源序列，保真度準則為：對于平

19、穩無記憶信源序列，保真度準則為： ()D KKD4.2.2 4.2.2 率失真函數的定義率失真函數的定義保真度要求越高（保真度要求越高（D值小），需要傳輸給信宿值小），需要傳輸給信宿信息就應越多；無失真系統，應該傳送全部信信息就應越多；無失真系統，應該傳送全部信源信息（當然冗余可被壓縮掉）。源信息（當然冗余可被壓縮掉）。若允許失真，就可以少傳輸一些信息；保真度若允許失真，就可以少傳輸一些信息；保真度要求越低，需要傳輸的信息量就可以越少。要求越低，需要傳輸的信息量就可以越少。在滿足保真度準則下，必須傳輸給信宿的在滿足保真度準則下，必須傳輸給信宿的傳信傳信率率R有一個下限值，這個下限值有一個下限值

20、，這個下限值R是保真度是保真度D值值的函數，的函數，函數函數R(D)就叫做（信息）率失真函數就叫做（信息）率失真函數。 引言引言求率失真函數的理論依據求率失真函數的理論依據本質上講，失真是因為沒有得到足夠多的互信息，而本質上講，失真是因為沒有得到足夠多的互信息，而滿足保真要求則必須獲得滿足保真要求則必須獲得起碼數量的互信息起碼數量的互信息。互信息是信源符號概率和信道傳輸概率的泛函。互信息是信源符號概率和信道傳輸概率的泛函。互信息的極值性告訴我們：在信道給定的情況下，總互信息的極值性告訴我們：在信道給定的情況下，總存在一種信源能使互信息取極大值（求信道容量就是存在一種信源能使互信息取極大值（求信

21、道容量就是尋找這個極大值的問題）；尋找這個極大值的問題）；在信源給定的情況下，總在信源給定的情況下，總存在一種信道能使互信息取極小值。存在一種信道能使互信息取極小值。如果給定信源能使互信息的極小值（最差信道）滿足如果給定信源能使互信息的極小值（最差信道）滿足保真要求的最小數額，則其他任何信道滿足保真度都保真要求的最小數額，則其他任何信道滿足保真度都將沒有問題。將沒有問題。因此求率失真函數，就是在滿足保真度準則的約束下因此求率失真函數，就是在滿足保真度準則的約束下求互信息極小值的問題。求互信息極小值的問題。施加保真約束的方案施加保真約束的方案一是首先在所有信道中求出給定信源的互信息極小值一是首先

22、在所有信道中求出給定信源的互信息極小值( (即得到最差信道即得到最差信道) )，然后計算該信道的，然后計算該信道的 ，并檢驗它，并檢驗它是否滿足保真度準則。是否滿足保真度準則。 若滿足則得到結果，但若不滿足則很難繼續進行下去。若滿足則得到結果，但若不滿足則很難繼續進行下去。二是先把所有滿足滿足保真度準則的信道求出來，然二是先把所有滿足滿足保真度準則的信道求出來，然后在這些信道中求互信息的極小值。后在這些信道中求互信息的極小值。 這個極小值作為預先指定的這個極小值作為預先指定的D值值的函數就是率失真函數。的函數就是率失真函數。DDD求互信息極小的約束條件是滿足保真度準則求互信息極小的約束條件是滿

23、足保真度準則 。DD而而 是信源符號概率和信道傳輸概率的泛函，在信源是信源符號概率和信道傳輸概率的泛函，在信源給定的情況下，給定的情況下， 取決于信道。取決于信道。存在兩種施加保真約束的方案：存在兩種施加保真約束的方案：求率失真函數的思路求率失真函數的思路求率失真函數求率失真函數滿足保真度準則下求滿足保真度準則下求R極小值極小值R =RBI(X;Y)把時間效應計入把時間效應計入RB中，中， R正比于正比于I(X;Y)采用單符號信息率采用單符號信息率R =I(X;Y)滿足保真度準則下滿足保真度準則下求互信息的極小值求互信息的極小值求滿足保真度準則的求滿足保真度準則的信道集合信道集合BD在信道集合

24、在信道集合BD中尋求能使中尋求能使互信息取極小值的信道互信息取極小值的信道);()()|(YXIDRMinDijBuvP率失率失真函真函數數例例1二元等概信源失真度矩陣為二元等概信源失真度矩陣為: :1010D 求率求率失真函數失真函數。解：解：先來尋求滿足保真度準則的信道集合先來尋求滿足保真度準則的信道集合BD ： 首先，首先，它應當與它應當與D矩陣一樣是矩陣一樣是2行行3列，并應具有如下形式：列，并應具有如下形式：ppppP10011 1、失真度、失真度Dij為為的矩陣元表明的矩陣元表明該傳輸犯有該傳輸犯有不能容許的錯誤，不能容許的錯誤，相應的傳輸矩陣元只能是相應的傳輸矩陣元只能是0 0，

25、否則便產生無窮失真。，否則便產生無窮失真。2 2、失真度、失真度Dij為為0 0的矩陣元表明的矩陣元表明該傳輸無失真該傳輸無失真，相應接收符號，相應接收符號為正確碼；而為正確碼；而Dij為為1 1的矩陣元表明接收符號為誤碼。從歸的矩陣元表明接收符號為誤碼。從歸一化考慮，其概率可分別設為一化考慮，其概率可分別設為1-1-p與與 p 。其次其次，由聯合概率矩陣：，由聯合概率矩陣：ppppxyP100121)(可求出平均失真度為：可求出平均失真度為：pppyxDxypDyx2121),()(, 可見，對于任意預先指定的失真度可見，對于任意預先指定的失真度D，只要是上述形式的，只要是上述形式的信道，且

26、信道，且pD，就是能滿足保真度準則的信道集合，就是能滿足保真度準則的信道集合BD。然后在滿足保真度準則的信道然后在滿足保真度準則的信道BD中求互信息的極小值：中求互信息的極小值： 接收符號概率為：接收符號概率為：xpppxypyp,21,21)()(后驗概率為：后驗概率為：2/1102/101)()()|(ypxypyxP后驗熵為：后驗熵為：pyxpxypYXHyx,)|(log)()|(互信息為：互信息為：I(X;Y)=H(X)-H(X|Y)=1-p其極小值發生在其極小值發生在p極大處，即：極大處，即：R( (D)=1-)=1-DDR( (D) )0 111、率失真函數、率失真函數R(D)是

27、信源的屬性是信源的屬性，每給定一個信源，就，每給定一個信源，就存在一個互信息的極小值，也就是存在一組信息率與平存在一個互信息的極小值，也就是存在一組信息率與平均失真度的依賴關系，即率失真函數。均失真度的依賴關系，即率失真函數。只要信源給定，率失真函數就被確定。只要信源給定，率失真函數就被確定。找遍信道集合找遍信道集合BD只是對搜尋范圍的一種限制，并不表只是對搜尋范圍的一種限制，并不表示它是信道的函數。即使不去找，這個極小值也存在，示它是信道的函數。即使不去找，這個極小值也存在，極小值并不會因為尋求它的方法而改變。極小值并不會因為尋求它的方法而改變。2、率失真函數還與失真度的定義有關、率失真函數

28、還與失真度的定義有關，D的定義不同，的定義不同，R(D)的形式也就不同。的形式也就不同。3 3、率失真函數是保真度準則下信源信息率的下限值、率失真函數是保真度準則下信源信息率的下限值，在，在設計限失真信源編碼時，信息的削減壓縮就應當以此為設計限失真信源編碼時，信息的削減壓縮就應當以此為界，盡量接近它，但不能小于它。界，盡量接近它，但不能小于它。對率失真函數的理解對率失真函數的理解信道容量和率失真函數比較信道容量和率失真函數比較RR(D)信源編碼定理信源編碼定理RR(D),信源編碼定理信源編碼定理研究信息率失真函數是為研究信息率失真函數是為了解決在已知信源和允許了解決在已知信源和允許失真度失真度

29、D的條件下，使信的條件下，使信源必須傳送給用戶的信息源必須傳送給用戶的信息量最小，即，在一定量最小，即，在一定D條條件下，用最少的碼符號來件下，用最少的碼符號來傳送信源消息，提高通信傳送信源消息，提高通信的有效性的有效性信源編碼問信源編碼問題。題。1. R(D)的變化形式的變化形式 （1）在）在0DD max區間：區間： R (D)0（3 3）在）在D = =0處：處：l連續信源連續信源R(0)(0)l離散信源離散信源 R(0)=(0)=H( (U) )4.2.3 4.2.3 率失真函數的性質率失真函數的性質 D0 DmaxR(D)H(U)連續信源連續信源離散信源離散信源R=0區區圖圖4.14

30、.1 R (D)隨隨D單調遞減連續變化單調遞減連續變化（1）D min ：2 2R(D)的定義域的定義域11( ) (/) ()0rsijiijijDP u P vu d u v 保真度準則保真度準則 DD D 亦應是非負，即亦應是非負，即0minmin DD D = 0= 0代表無失真，無失真傳輸時信道損失熵為零，所以代表無失真，無失真傳輸時信道損失熵為零，所以該點的信息率等于信源熵：該點的信息率等于信源熵：R( (Dmin) = ) = R(0)= (0)= H(U) 對于連續信源，信息熵為無窮大，使對于連續信源，信息熵為無窮大，使R(0)，允許的失真度越大，需要傳送的信息就可以越少，率失

31、允許的失真度越大，需要傳送的信息就可以越少，率失真函數真函數R (D)是隨著失真度是隨著失真度D的變大而減小的。的變大而減小的。R (D)作為互信息是一個非負的值，最小為零。作為互信息是一個非負的值，最小為零。R(D)減減小到零時對應的小到零時對應的D，就是，就是R (D) 非零區的右端點非零區的右端點D max ，即：即： R (D max) = 0 就是說失真大到一定程度后，從收到的符號已經完全得就是說失真大到一定程度后，從收到的符號已經完全得不到發送符號的信息了。即使繼續增大不到發送符號的信息了。即使繼續增大D值，互信息也值，互信息也不可能為負。這個失真度區域的左端點就是不可能為負。這個

32、失真度區域的左端點就是D max 。在。在D D max的區域，的區域，R (D)將一直保持零。可見將一直保持零。可見D max是是R (D)的的 非零非零區域與區域與全零全零區域的分界點。區域的分界點。 （2）D max：D max 可以由可以由R (D)=0的區域求出的區域求出：在在R (D)=0的區域，也就是的區域，也就是I (U; V) 0的區域，的區域，輸出符號與輸入符號已統計獨立，應有：輸出符號與輸入符號已統計獨立，應有：)()/(vQuvP于是，在此區域：于是，在此區域：VUvudvQuPD,),()()(D max是是R(D)=0 0區的左端點，應有：區的左端點，應有：VUvQ

33、vudvQuPD,)(max),()()(min式中，取極小是選擇各種信道的接收符號概率式中，取極小是選擇各種信道的接收符號概率Q(v)，使求和最小。由于使求和最小。由于Q(v)已與已與u u無關，所以：無關，所以： UVvQvuduPvQD),()()(min)(max選擇：先固定接收符號，使選擇：先固定接收符號，使 取最小的取最小的那個那個Q(v)=1，而其他，而其他Q(v)=0 ，則必然使對則必然使對V的求和為的求和為最小，其值為：最小，其值為： UvuduP),()(UVvuduPD),()(minmax例例2已知信源已知信源U=0,1, 2，概率概率P (U) = 0.5, 0.3,

34、 0.2 ， 求平方失真度下率失真函數的定義域。求平方失真度下率失真函數的定義域。 014101410D解：解：顯然顯然Dminmin = 0 0 所以所以 D max = min 1.1, 0.7, 2.3=0.7 1.1 0.7 2.31.1 0.7 2.3計算過程為：計算過程為： 0.50.5 0.30.3 0.20.202 . 08 . 03 . 003 . 00 . 25 . 00UVvuduPD),()(minmax由由： 0 1 41 0 14 1 0D和和： 各列相加各列相加4.2.4 4.2.4 漢明失真情況下率失真函數的計算漢明失真情況下率失真函數的計算 理論上，給定信源概

35、率分布和失真度，通過計理論上，給定信源概率分布和失真度，通過計算泛函極值可以求得該信源的算泛函極值可以求得該信源的R (D)。但一般情況下，求率失真函數但一般情況下，求率失真函數R (D)的顯式表的顯式表達達比較復雜。比較復雜。在某些特殊的情況下，有一些較簡捷的辦法計在某些特殊的情況下，有一些較簡捷的辦法計算算R (D)。特別。特別當失真度定義為漢明失真時，當失真度定義為漢明失真時，可以較簡單地求出可以較簡單地求出R (D)。 理由理由1:在漢明失真的情況下，可以證明平均失在漢明失真的情況下，可以證明平均失真度等于平均錯誤概率。真度等于平均錯誤概率。理由理由2:可以利用費諾不等式來計算后驗熵。

36、可以利用費諾不等式來計算后驗熵。證明證明: : 因因() ( ,)ijijUVDp u vd u v)(0)(1),(),(jijijivudji漢明失真：漢明失真： iijjuvjivupD)()(代入得：代入得：可見：可見： EPD EPD 求證求證在漢明失真的情況下，平均失真度等于在漢明失真的情況下，平均失真度等于平均錯誤概率，即平均錯誤概率，即而漢明失真條件下的譯碼規則應當是而漢明失真條件下的譯碼規則應當是F( (vj )= uj，錯誤概率為：錯誤概率為： iijjuvjiEvupP)()(解釋費諾不等式解釋費諾不等式 H(U|V)H(PE) +PE log(r-1)（見課本（見課本P

37、73P73頁）頁）H(X|Y) log m log (m-1)0 (r-1)/r 1 PE 平均錯誤概率和損失熵平均錯誤概率和損失熵( (后驗熵后驗熵) ) 從不同角度定義了類從不同角度定義了類似的概念。費諾似的概念。費諾(Fano)(Fano)不等式給出了他們的關系。不等式給出了他們的關系。 通信過程完成后，對信源所通信過程完成后，對信源所發符號仍存在的不確定度來自發符號仍存在的不確定度來自兩部分。第一部分是發生概率兩部分。第一部分是發生概率PE錯誤的不確定性錯誤的不確定性H(PE)；第；第二部分是哪個輸入符號發生錯二部分是哪個輸入符號發生錯誤的不確定性，它不會大于除誤的不確定性，它不會大于

38、除a*外的其余外的其余m-1 1個符號等概出個符號等概出錯的不確定性錯的不確定性PE E log (m-1) )；因：因：I (U ;V)=H(U)-H(U|V)利用費諾不等式：利用費諾不等式：H(U|V)H(PE) +PE log(r-1)以及以及EPD 和和 DD 就有：就有： H(U|V)H(D) + D log(r-1) 于是：于是： I (U ; V)H(U)-H(D) -D log(r-1) 所以：所以： R(D)=minI (U ; V)=H(U)-H(D)-D log(r-1) );(min)()/(VUIDRDBuvP回到率失真函數：回到率失真函數：解：解：對漢明失真有公式對

39、漢明失真有公式 R(D)=H(U)-H(D)-D log(r-1) 將將r=2代入得：代入得：R(D)=H(U)- -H(D) =H()- -H(D)H( ()=-)=-log- -(1-) log (1-)H( (D)=-)=-DlogD - -(1-D) log (1-D)對于不同的信源對于不同的信源，作圖。，作圖。例例3二元對稱信源二元對稱信源U = 0,1，P (u) = , 1- - ，（1/21/2），而接收變量，而接收變量V = 0,1，失真度采用，失真度采用漢明失真，求在漢明失真，求在0 D 區間的率失真函數區間的率失真函數R (D) 。R(D)=0.5=0.5=0.4=0.4

40、=0.3=0.3=0.2=0.2=0.1=0.1 1.0 0.8 0.6 0.4 0.2 0.0 D 0 0.1 0.2 0.3 0.4 0.5課后課后復習題復習題 v思考題：思考題：如何理解率失真函數的曲線形狀？如何理解率失真函數的曲線形狀？v作業題作業題： 教材教材158158頁習題四頁習題四 1 1，2 2，4 4，題。，題。第四章第四章 限失真信源編碼限失真信源編碼4.3 4.3 保真度準則下的信源編碼保真度準則下的信源編碼 本節主要內容本節主要內容香農第三定理香農第三定理離散信源的限失真編碼離散信源的限失真編碼限失真信源編碼：限失真信源編碼： distortion constrain

41、t source coding 失真度：失真度：distortion 平均失真度：平均失真度：average distortion 外語關鍵詞外語關鍵詞溫舊引新溫舊引新香農第一香農第一(無失真信源編碼無失真信源編碼)定理：定理： 對離散無記憶信源對離散無記憶信源S的的N次擴展次擴展SN進行編碼，總可進行編碼，總可以找到一種編碼方法，構成唯一可譯碼，使平均碼長以找到一種編碼方法，構成唯一可譯碼，使平均碼長NrHrHNNl1loglog香農第二香農第二( (有噪信道編碼有噪信道編碼) )定理：定理： 離散無記憶信道的容量為離散無記憶信道的容量為C，當傳信率，當傳信率RC時，只時，只要碼長要碼長n足

42、夠長，總存在一種編碼與相應的譯碼規則，足夠長，總存在一種編碼與相應的譯碼規則，使錯誤概率任意小。使錯誤概率任意小。4.3 4.3 保真度準則下的信源編碼保真度準則下的信源編碼4.3.1香農第三定理（限失真信源編碼定理）香農第三定理（限失真信源編碼定理）1.定理：定理： 對于任何指定的失真度對于任何指定的失真度D0，只要編碼后每個符號的，只要編碼后每個符號的信息傳輸率信息傳輸率 ，總可以找到一種編碼，總可以找到一種編碼C，使平均失真度使平均失真度 。式中。式中M為編碼為編碼C的碼字個數，的碼字個數， n為碼字長度。為碼字長度。)(logDRnMRDD 2逆定理：逆定理： 任何一種編碼，如果平均每

43、個信源符號的信息傳輸率任何一種編碼，如果平均每個信源符號的信息傳輸率R小于信息率失真函數小于信息率失真函數R(D)，就不能保證在保真度準則下，就不能保證在保真度準則下再現信源信息。再現信源信息。 3 3定理的意義：定理的意義：（1）它證明了通過信源編碼實現保真準則下）它證明了通過信源編碼實現保真準則下的通信是可行的。的通信是可行的。（2）它指出了實現限失真編碼的條件，即信）它指出了實現限失真編碼的條件，即信息壓縮的下限值是息壓縮的下限值是RR(D)。從而為實際編碼。從而為實際編碼工作指明了一個目標，避免了無謂的努力。工作指明了一個目標，避免了無謂的努力。（3）從）從R(D) 隨隨D的增大而減小

44、的曲線可知，的增大而減小的曲線可知，允許較大的失真，就可以減小信息傳輸率；反允許較大的失真，就可以減小信息傳輸率；反之亦然。之亦然。4 4香農三個定理的區別與聯系：香農三個定理的區別與聯系：(1)三個定理各有自己管轄的范圍，各指出信息率的一個理三個定理各有自己管轄的范圍，各指出信息率的一個理論極限：論極限：第一定理第一定理負責無失真信源編碼；負責無失真信源編碼； 給出給出無失真信源編碼信息率的極限無失真信源編碼信息率的極限R log m，這里這里m是是編碼使用的符號集的符號個數。編碼使用的符號集的符號個數。第二定理第二定理負責信道編碼；負責信道編碼； 指出指出無差錯信道編碼傳信率的極限無差錯信

45、道編碼傳信率的極限RC，這里這里C是信道是信道容量。容量。第三定理第三定理負責限失真信源編碼；負責限失真信源編碼；指出指出滿足指定保真度下限失真信源編碼傳信率的極限滿足指定保真度下限失真信源編碼傳信率的極限RR(D)，R (D)是信源的率失真函數。是信源的率失真函數。(2)(2)香農三個定理的聯系與區別香農三個定理的聯系與區別第一定理是第三定理第一定理是第三定理D=0的特例。的特例。第一定理要求增大信息率，第一定理要求增大信息率， 第二定理和第三定理卻要求減小信息率。第二定理和第三定理卻要求減小信息率。雖然第二定理與第三定理都是減少信息率，但二者雖然第二定理與第三定理都是減少信息率，但二者 目

46、的不同目的不同（一個是糾錯，另一個是壓縮）（一個是糾錯，另一個是壓縮） 手段不同手段不同(一個是添加冗余，另一個是削減次要的信息一個是添加冗余，另一個是削減次要的信息) 要求也不同要求也不同（一個是（一個是RC ，另一個是，另一個是RR(D) ， C只取決于信道，而只取決于信道，而R(D)不僅取決于信源，還與預先指不僅取決于信源，還與預先指定的保真度定的保真度D有關）。有關）。香農三個定理相互聯系，可以集中表現在同一香農三個定理相互聯系，可以集中表現在同一張率失真函數曲線圖上：張率失真函數曲線圖上：沿縱軸壓縮碼長增大信息率沿縱軸壓縮碼長增大信息率第一定理第一定理沿某垂直線添加冗余減小信息率沿某

47、垂直線添加冗余減小信息率第二定理第二定理沿指定失真度削減信息減小信息率沿指定失真度削減信息減小信息率第三定理第三定理可保真區可保真區可糾錯區可糾錯區logMRCH0 D1 D2 D信息率信息率RC是第二定理要求的可糾錯區，信息是第二定理要求的可糾錯區，信息率率RR(D)是第三定理要求的可保真區。是第三定理要求的可保真區。二者之間存在共同區域：二者之間存在共同區域：R(D)RC。在這個。在這個區域，總可以對信息做足夠復雜的處理（包括區域，總可以對信息做足夠復雜的處理（包括信源編碼和信道編碼），使接收到滿足保真度信源編碼和信道編碼），使接收到滿足保真度要求的信息。要求的信息。若沿若沿D1直線處理則

48、不經過這個區域，始終直線處理則不經過這個區域，始終C R (D)，那么要保真則不能糾錯，要糾錯則不，那么要保真則不能糾錯，要糾錯則不能保真，無論用什么辦法，也不能以保真度能保真，無論用什么辦法，也不能以保真度D的要求再現信源信息。的要求再現信源信息。 引入率失真函數引入率失真函數R(D)和信道容量和信道容量C兩個概念，兩個概念，就能允許我們把通信系統中復雜的信息處理過就能允許我們把通信系統中復雜的信息處理過程明確地分為信源編碼和信道編碼兩個功能：程明確地分為信源編碼和信道編碼兩個功能：前者只對保真度負責，致力于如何壓縮信息率，前者只對保真度負責，致力于如何壓縮信息率，而不必管信道的具體情況；后

49、者只考慮信道噪而不必管信道的具體情況；后者只考慮信道噪聲與糾檢錯而不必關心信源特征，這樣分工明聲與糾檢錯而不必關心信源特征，這樣分工明確，各盡其責，很好解決了有效性與可靠性的確，各盡其責，很好解決了有效性與可靠性的矛盾。矛盾。 4.3.2 4.3.2 離散信源的限失真編碼離散信源的限失真編碼香農第三定理指出了限失真編碼的可行性與理論香農第三定理指出了限失真編碼的可行性與理論極限，但未指出實現編碼的途徑。極限，但未指出實現編碼的途徑。限失真編碼與檢糾錯編碼之間存在一種互逆反演限失真編碼與檢糾錯編碼之間存在一種互逆反演關系：關系：每種糾錯碼都可以演化出一種相應的限失真編碼。每種糾錯碼都可以演化出一

50、種相應的限失真編碼。信道編碼：信道編碼：信源信息信源信息 添加的冗余添加的冗余信道傳輸的碼字信道傳輸的碼字限失真編碼：限失真編碼：保留信息保留信息 可削減信息可削減信息信源的碼字分組信源的碼字分組例如：三連重復碼用三個連例如：三連重復碼用三個連0（“000”）表示信源符）表示信源符號號0，用三個連，用三個連1表示信源符號表示信源符號1，它實際上是一位信息，它實際上是一位信息，二位監督的二位監督的(3, 1)線性分組碼，漢明距離為線性分組碼，漢明距離為3，可自動，可自動糾正一個錯位。糾正一個錯位。信道信道1111101010111000100010000 000 0 000 1 111 1 11

51、1 0 01 1信源信源 信道編碼信道編碼接收碼接收碼譯碼譯碼現在將它作為限失真編碼，反過來使用：現在將它作為限失真編碼，反過來使用：111110101011100010001000信源信源限失真編碼限失真編碼 無擾信道無擾信道 譯碼譯碼 000 0 0 000000 0 0 000 111 1 1 111 111 1 1 111比如信源發出：比如信源發出： 000000，101101，100100， 110110，011011，111111，001001，編碼為：編碼為： 000000，111111，000000， 111111，111111，111111，000000，壓縮為：壓縮為： 0

52、 , 1 , 0, 1, 1 1, 00 , 1 , 0, 1, 1 1, 0，.傳輸及接收：傳輸及接收： 0 , 1 , 0, 1, 1 1, 00 , 1 , 0, 1, 1 1, 0，.譯碼為：譯碼為： 000000，111111，000000， 111111，111111，111111，000000，每個碼字視為一個符號，則信源概率為：每個碼字視為一個符號，則信源概率為：p p(U)=1/8(U)=1/8； 把限失真編碼、譯碼都并入廣義信道，發送把限失真編碼、譯碼都并入廣義信道，發送8 8個序列（個序列（000,000,001,010,100,011,101,110,111),001,

53、010,100,011,101,110,111),接收接收2 2個序列個序列(000,111)(000,111)，則傳輸概率為則傳輸概率為：1010101001010101)|(UVp而失真度矩陣為：而失真度矩陣為：0111111111111110),(vuD序列平均失真度：序列平均失真度：86),()|()()(,jijiijivuduvpupKD也可以按簡單的辦法來計算序列失真度。也可以按簡單的辦法來計算序列失真度。8個序列中個序列中有有6個失真，個失真，2個不失真，失真的個不失真，失真的dij=1，不失真的，不失真的dij=0，信源是等概信源是等概(p=1/8 )的，所以序列失真度：的，

54、所以序列失真度：86) 11101110(81)(KD單符號平均失真度：單符號平均失真度： 418631)(1KDKD最后信宿收到的只是最后信宿收到的只是000000與與111111，并不是原來的信息，并不是原來的信息，而是有失真的消息。而是有失真的消息。這種編碼方式能把信息率降低為原來的這種編碼方式能把信息率降低為原來的1/31/3，原來傳，原來傳3 3個符號的現在只需傳個符號的現在只需傳1 1個符號。代價是產生了每符號個符號。代價是產生了每符號1/41/4的平均失真度。的平均失真度。 再由漢明失真的率失真函數公式：再由漢明失真的率失真函數公式：43log4341log4121log2121

55、log21)41()21()()()(HHDHPHDR =0.189 bit /0.189 bit /符號符號可知，限定失真為可知，限定失真為1/41/4時，理論上信息率最小可減到時，理論上信息率最小可減到0.189；現在；現在R= =1/3=0.333，還遠沒達到這個下限。，還遠沒達到這個下限。 香農理論的成功之處是給出了這個極限。但是香農理論的成功之處是給出了這個極限。但是實際工作中還有兩大困難。一是難以定義一個實際工作中還有兩大困難。一是難以定義一個主、客觀都符合實際的失真度的標準，也難以主、客觀都符合實際的失真度的標準，也難以計算率失真函數；二是如何尋找編碼的具體方計算率失真函數；二是

56、如何尋找編碼的具體方法，香農理論無所提示。法，香農理論無所提示。課后課后復習題復習題 v思考題：思考題：如何理解香農的三個定理的關系？如何理解香農的三個定理的關系？v作業題作業題： 教材教材158158頁習題四頁習題四 第第7 7題。題。第四章第四章 限失真信源編碼限失真信源編碼4.4 連續信源的限失真編碼連續信源的限失真編碼本節主要內容本節主要內容連續信源的率失真函數連續信源的率失真函數最佳標量量化最佳標量量化 矢量量化方法簡介矢量量化方法簡介連續信源連續信源：continuous information source離散信源離散信源：discrete information source

57、標量量化標量量化 ：scalar quantizing 矢量量化矢量量化：vector quantizing外語關鍵詞外語關鍵詞溫舊引新溫舊引新離散信源失真度的定義離散信源失真度的定義離散信源的率失真函數離散信源的率失真函數離散信源的限失真編碼離散信源的限失真編碼連續信源的信息熵連續信源的信息熵 4.4 4.4 連續信源的限失真編碼連續信源的限失真編碼2)(),(yxyxd連續信源的編碼就是實現數字化。連續信源的編碼就是實現數字化。連續信源信息熵為無窮，不可能無失真地由連續信號連續信源信息熵為無窮，不可能無失真地由連續信號轉變為離散信號，只能是限失真編碼。轉變為離散信號，只能是限失真編碼。限失

58、真壓縮的理論極限是率失真函數。限失真壓縮的理論極限是率失真函數。4.4.1 4.4.1 連續信源的率失真函數連續信源的率失真函數1 1、失真函數：、失真函數： 收發均為連續變量收發均為連續變量x和和y時時,可定義二元連續型的失真函數：可定義二元連續型的失真函數：（1 1）平方失真：）平方失真： 2)(),(yxyxd（2 2）絕對失真：）絕對失真： |),(yxyxd（3 3）誤碼失真：）誤碼失真： 10),(),(yxyxdyxyx當當2 2、平均失真、平均失真設為聯合概率密度，設為聯合概率密度，x為輸入，為輸入，y為輸出。則平為輸出。則平均失真為：均失真為： dxdyyxdyxPyxdED

59、),(),(),(（1）平方失真情況下，當方差一定時，高斯信）平方失真情況下，當方差一定時，高斯信源（正態分布）的率失真函數為最小。源（正態分布）的率失真函數為最小。 3 3、率失真函數、率失真函數);()()()/(yxIMinDRDPxyP即當即當 且且給定時給定時: 2)(),(yxyxd22221)(xexP有解析解為：有解析解為： ;log)(DDR（2 2）絕對失真情況下，當平均偏離）絕對失真情況下，當平均偏離一定時，負指一定時，負指數分布信源的率失真函數為最小。數分布信源的率失真函數為最小。 |),(yxyxd即當即當 且且給定時給定時: |2)(xexpDDR1log)(有解析

60、解為：有解析解為： （3 3）誤碼失真情況下，信源為二值分布（其實就誤碼失真情況下，信源為二值分布（其實就是二元離散信源）時，率失真函數的解析解為：是二元離散信源）時，率失真函數的解析解為： )()()(DHUHDR 只有在以上提及的特殊情況下，可求得解析解。只有在以上提及的特殊情況下，可求得解析解。 均勻分布信源的率失真函數均勻分布信源的率失真函數R(D)卻未獲得解析卻未獲得解析表達。表達。4.4.2 4.4.2 最佳標量量化最佳標量量化所謂標量量化，指對每個抽樣值獨立地進行量所謂標量量化，指對每個抽樣值獨立地進行量化，不計樣值之間的關聯。化，不計樣值之間的關聯。抽樣值抽樣值 x 取值范圍在取值范圍