资讯冗余

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

定量定义

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

 

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

信源的绝对资讯率

 

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

绝对资讯冗余定义为

 

即资讯率与绝对资讯率之间的差。

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

其它的冗余概念

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

压缩数据的冗余是指   个消息的期望压缩数据长度为 (或期望数据熵率  )与熵值  (或熵率  )的差。(这里我们假设数据是遍历的也是平稳的,例如无记忆信源。)虽然熵率之差   会随着   增加而任意小,实际的差   已不能(尽管理论上可以)在有限熵的无记忆信源情况下上界为 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 .