信息冗餘

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

定量定義

在描述原始數據的冗餘時，信源信息率為平均每個符號的熵。對於無記憶信源，這僅是每個符號的熵；而對於一個隨機過程的最普遍形式為前 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.