開啟主選單

求真百科

率失真理論

來自 人人文庫 的圖片

中文名:率失真理論

外文名:Rate distortion theory

定 義:碼率下能達到最小期望失真

類 型:理論

應用學科:通信(信息論)

率失真理論是用信息論的基本觀點和方法研究數據壓縮問題的理論,又稱限失真信源編碼理論

率失真理論的基本問題可以歸結如下:對於一個給定的信源分布失真度量,在特定的碼率下能達到的最小期望失真;或者為了滿足一定的失真限制,最小描述碼率可以是多少。[1]

目錄

起源

率失真理論的名稱來源於信息速率失真函數,率失真理論包含兩個中心內容:一是率失真函數失真率函數,二是限失真編碼定理。這就是針對不同的信源、不同的失真量度和不同信源概率分布計算率失真函數和證明相應的限失真編碼定理。

量度

率失真理論涉及三個基本概念:信源編碼失真量度

失真量度是這一理論特有的。它是對編譯碼器輸入x和輸出y之間的失真所給予的量度,即d(x,y)。數學上,任何範數或距離(度量)都可作為失真量度。但在具體選擇時要考慮到物理上或主觀上應有意義,且數學上易處理和計算方便。

已有的失真量度按量度的性質可分為範數失真量度擬範數失真量度,按高階失真量度與一階失真量度的關係又可分為可加性量度非可加性量度

現在常用的是差值失真量度漢明失真量度。均方誤差失真量度,即d(x,y)=(x-y)2,既屬於範數失真量度,也屬於距離失真量度,又是一種差值失真量度,不僅有明確的物理意義,而且數學上也易於處理。

計算

率失真函數和失真率函數(即率失真函數的反函數)是通過互信息的概念加以定義的。

將編譯碼器看成是一種信道,稱為試驗信道有條件概率P(y|x)。這一信道的輸入x和輸出y分別對應編碼的輸入和譯碼的輸出。試驗信道輸入輸出間的互信息相當於信源通過編譯碼器給信宿的信息量。這樣,率失真函數R(D)被定義為試驗信道輸入輸出間的平均失真量度,失真量度不超過D的條件下,試驗信道輸入輸出間互信息量的最小值,即如 R(D)=min I(X;Y) P(y|x)

而D=Ed(x,y),失真率函數D(R)則相反,它是指互信息的值不超過R的條件下,失真度D可能達到的最小值。

這兩個函數的計算在原則上都可以用拉格朗日乘子法或變分法來解決,但除了一些簡單的情況,如獨立二元信源,平穩高斯信源以外,一般很難得到解析解。R.E.勃拉赫特提出的迭代算法為獲得數值解提供了一種通用的算法。

此外,在某些情況下利用求出上下界的辦法對函數進行估計。

限失真編碼定理

在最簡單的離散、無記憶、平穩信源和分組編況下,設信源的率失真函數是R(D),當R>R(D)時,一定存在一種具體的編碼方法,使其失真小於D+ε,其中ε是一個無窮小量。反之若R<R(D),則不論用什麼編碼方法,其失真必大於D;對一般遍歷信源,平穩非遍歷信源、漸近平穩非遍歷信源等其它信源,以及移不變碼(滑動分組碼)等非分組碼的情況下,也有類似的定理。

該定理的證明所使用的是隨機編碼的方法,雖然不能從中得到一種具體的編譯碼方法,但卻證明了這樣的好碼必然存在。這樣,信源編碼定理就在數據壓縮的具體編碼方法和率失真函數之間建立起一種聯繫,對具體編碼方法的研究起到了指導作用。

應用

率失真理論的主要應用有兩種:

①數據壓縮。為數據壓縮的性能提供理論極限和比較標準,對具體編碼方法的研究起方向指導作用;

②模式識別。統計模式識別數據壓縮是兩個具有交叉領域的學科。率失真理論在模式分類、特徵選擇等問題上有重要的應用。

率失真理論在應用中,也存在一些問題。例如:它解決得較好的信源是平穩遍歷信源,而在實際中,信源經常是非平穩非遍歷的;它解決得比較好的編碼是分組碼,但在實際應用中,非分組碼相當普遍。同時,理論上要求對信源建立精確的模型,但實際上只能得到近似的模型;理論上假定已有正確的失真量度,但如何得到這量度尚無有效的辦法。[2]

參考資料

  1. 率失真函數PPT課件,人人文庫
  2. 06圖像編碼1,無憂文檔