資訊冗餘

在資訊理論中，資訊冗餘是傳輸訊息所用數據位的數目與訊息中所包含的實際資訊的數據位的數目的差值。數據壓縮是一種用來消除不需要的冗餘的方法，校驗和是在經過有限頻道容量的雜訊頻道中通訊，為了進行錯誤校正而增加冗餘的方法。

定量定義

在描述原始數據的冗餘時，信源資訊率為平均每個符號的熵。對於無記憶信源，這僅是每個符號的熵；而對於一個隨機過程的最普遍形式為前 n 個符號的聯合熵除以 n 之後，隨着 n 趨於無窮時的極限

${\displaystyle r=\lim _{n\to \infty }{\frac {1}{n}}\mathrm {H} (M_{1},M_{2},\dots M_{n}),}$

在資訊理論中經常提及一種語言的「熵率」或者「資訊熵」。當信源是英文散文時這是正確的。由於無記憶信源的訊息之間沒有相互依賴性，所以無記憶信源的資訊率為${\displaystyle \mathrm {H} (M)}$。

信源的絕對資訊率為

${\displaystyle R=\log |\mathbb {M} |,\,}$

即是訊息空間基數的對數值。這個公式也稱作Hartley函數。這是傳送用這個字母表表示的資訊的最大資訊率。其中對數要根據所用的測量單位選擇合適的底數。若且唯若信源是無記憶的且均勻分佈的時候，絕對資訊率等於資訊率。

絕對資訊冗餘定義為

${\displaystyle D=R-r}$，

即資訊率與絕對資訊率之間的差。

${\displaystyle {\frac {D}{R}}}$稱為相對資訊冗餘，它表示了最大的數據壓縮率，這個壓縮率用檔案大小減小比例所表示。當用原始檔案與壓縮後的檔案表示的時候，${\displaystyle R:r}$表示能夠得到的最大壓縮率。與相對資訊冗餘互補的是效率${\displaystyle {\frac {r}{R}}}$，於是${\displaystyle {\frac {r}{R}}+{\frac {D}{R}}=1}$。均勻分佈的無記憶信源的冗餘為0，效率為100%，因此無法壓縮。

其它的冗餘概念

兩個變數之間冗餘的度量是相互資訊或者正規化變數。多個變數之間冗餘的度量是全相關（total correlation）。

壓縮數據的冗餘是指 ${\displaystyle n}$ 個訊息的期望壓縮數據長度為${\displaystyle L(M^{n})\,\!}$（或期望數據熵率 ${\displaystyle L(M^{n})/n\,\!}$）與熵值 ${\displaystyle nr\,\!}$（或熵率 ${\displaystyle r\,\!}$）的差。（這裏我們假設數據是遍歷的也是平穩的，例如無記憶信源。）雖然熵率之差 ${\displaystyle L(M^{n})/n-r\,\!}$ 會隨着 ${\displaystyle n\,\!}$ 增加而任意小，實際的差 ${\displaystyle L(M^{n})-nr\,\!}$ 已不能（儘管理論上可以）在有限熵的無記憶信源情況下上界為 1。

參見

• 信源編碼
• 信源編碼定理
• 數據壓縮
• 負熵

參考文獻

• Reza, Fazlollah M. An Introduction to Information Theory. New York: Dover. 1994 [1961]. ISBN 0-486-68210-2.
• Schneier, Bruce. Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, Inc. 1996. ISBN 0-471-12845-7.
• Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. Comparison of Redundancy and Relevance Measures for Feature Selection in Tissue Classification of CT images. Advances in Data Mining. Applications and Theoretical Aspects. Springer. 2010: 248–262. CiteSeerX: 10.1.1.170.1528.