信息冗余

维基百科,自由的百科全书
跳转至: 导航搜索

信息论中,信息冗余是传输消息所用数据位的数目与消息中所包含的实际信息的数据位的数目的差值。数据压缩是一种用来消除不需要的冗余的方法,校验和是在经过有限信道容量的噪声信道中通信,为了进行错误校正而增加冗余的方法。

定量定义[编辑]

在描述原始数据的冗余时,信源信息率为平均每个符号的。对于无记忆信源,这仅是每个符号的熵;而对于一个随机过程的最普遍形式为前 n 个符号的联合熵除以 n 之后,随着 n 趋于无穷时的极限

r = \lim_{n \to \infty} \frac{1}{n} \Eta(M_1, M_2, \dots M_n),

在信息论中经常提及一种语言的“熵率”或者“信息熵”。当信源是英文散文时这是正确的。由于无记忆信源的消息之间没有相互依赖性,所以无记忆信源的信息率为\Eta(M)

信源的绝对信息率

R = \log |\mathbb M| ,\,

即是消息空间基数对数值。这个公式也称作Hartley函数。这是传送用这个字母表表示的信息的最大信息率。其中对数要根据所用的测量单位选择合适的底数当且仅当信源是无记忆的且均匀分布的时候,绝对信息率等于信息率。

绝对信息冗余定义为

 D = R - r

即信息率与绝对信息率之间的差。

\frac D R称为相对信息冗余,它表示了最大的数据压缩率,这个压缩率用文件大小减小比例所表示。当用原始文件与压缩后的文件表示的时候,R : r表示能够得到的最大压缩率。与相对信息冗余互补的是效率\frac r R ,于是\frac r R + \frac D R = 1。均匀分布的无记忆信源的冗余为0,效率为100%,因此无法压缩。

其它的冗余概念[编辑]

两个变量之间冗余的度量是互信息或者正规化变量。多个变量之间冗余的度量是全相关(total correlation)。

压缩数据的冗余是指 n 个消息的期望压缩数据长度为L(M^n) \,\!(或期望数据熵率 L(M^n)/n \,\!)与熵值 nr \,\!(或熵率 r \,\!)的差。(这里我们假设数据是遍历的也是平稳的,例如无记忆信源。)虽然熵率之差 L(M^n)/n-r \,\! 会随着 n \,\! 增加而任意小,实际的差 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.