World Library  
Flag as Inappropriate
Email this Article

Redundancy (information theory)

Article Id: WHEBN0001953582
Reproduction Date:

Title: Redundancy (information theory)  
Author: World Heritage Encyclopedia
Language: English
Subject: Information theory, Data compression, Error detection and correction, Theil index, Forward error correction
Collection: Information Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Redundancy (information theory)

Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. Informally, it is the amount of wasted "space" used to transmit certain data. Data compression is a way to reduce or eliminate unwanted redundancy, while checksums are a way of adding desired redundancy for purposes of error detection when communicating over a noisy channel of limited capacity.

Contents

  • Quantitative definition 1
  • Other notions of redundancy 2
  • See also 3
  • References 4

Quantitative definition

In describing the redundancy of raw data, the rate of a source of information is the average entropy per symbol. For memoryless sources, this is merely the entropy of each symbol, while, in the most general case of a stochastic process, it is

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

the limit, as n goes to infinity, of the joint entropy of the first n symbols divided by n. It is common in information theory to speak of the "rate" or "entropy" of a language. This is appropriate, for example, when the source of information is English prose. The rate of a memoryless source is simply H(M), since by definition there is no interdependence of the successive messages of a memoryless source.

The absolute rate of a language or source is simply

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

the logarithm of the cardinality of the message space, or alphabet. (This formula is sometimes called the Hartley function.) This is the maximum possible rate of information that can be transmitted with that alphabet. (The logarithm should be taken to a base appropriate for the unit of measurement in use.) The absolute rate is equal to the actual rate if the source is memoryless and has a uniform distribution.

The absolute redundancy can then be defined as

D = R - r ,\,

the difference between the absolute rate and the rate.

The quantity \frac D R is called the relative redundancy and gives the maximum possible data compression ratio, when expressed as the percentage by which a file size can be decreased. (When expressed as a ratio of original file size to compressed file size, the quantity R : r gives the maximum compression ratio that can be achieved.) Complementary to the concept of relative redundancy is efficiency, defined as \frac r R , so that \frac r R + \frac D R = 1. A memoryless source with a uniform distribution has zero redundancy (and thus 100% efficiency), and cannot be compressed.

Other notions of redundancy

A measure of redundancy between two variables is the mutual information or a normalized variant. A measure of redundancy among many variables is given by the total correlation.

Redundancy of compressed data refers to the difference between the expected compressed data length of n messages L(M^n) \,\! (or expected data rate L(M^n)/n \,\!) and the entropy nr \,\! (or entropy rate r \,\!). (Here we assume the data is ergodic and stationary, e.g., a memoryless source.) Although the rate difference L(M^n)/n-r \,\! can be arbitrarily small as n \,\! increased, the actual difference L(M^n)-nr \,\!, cannot, although it can be theoretically upper-bounded by 1 in the case of finite-entropy memoryless sources.

See also

References

  • Reza, Fazlollah M. (1994) [1961]. An Introduction to Information Theory. New York: Dover.  
  •  
  • Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. (2010). "Comparison of Redundancy and Relevance Measures for Feature Selection in Tissue Classification of CT images". Advances in Data Mining. Applications and Theoretical Aspects. Springer. pp. 248–262.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.