Information about 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.
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
, 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
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
the difference between the absolute rate and the rate.
The quantity
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 
gives the maximum compression ratio that can be achieved.) Complementary to the concept of relative redundancy is efficiency, defined as 
so that 
. A memoryless source with a uniform distribution has zero redundancy (and thus 100% efficiency), and cannot be compressed.
Redundancy of compressed data refers to the difference between the expected compressed data length of
messages 
(or expected data rate 
) and the entropy 
(or entropy rate 
). (Here we assume the data is ergodic and stationary, e.g., a memoryless source.) Although the rate difference 
can be arbitrarily small as increased, the actual difference 
, cannot, although it can be theoretically upper-bounded by 1 in the case of finite-entropy memoryless sources.
(See for formats and for codecs)
Quantitative definition
In describing the redundancy of raw data, recall that 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
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
, 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
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
the difference between the absolute rate and the rate.
The quantity
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 gives the maximum compression ratio that can be achieved.) Complementary to the concept of relative redundancy is efficiency, defined as so that . 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
messages (or expected data rate ) and the entropy (or entropy rate ). (Here we assume the data is ergodic and stationary, e.g., a memoryless source.) Although the rate difference can be arbitrarily small as increased, the actual difference , cannot, although it can be theoretically upper-bounded by 1 in the case of finite-entropy memoryless sources.
See also
References
- Fazlollah M. Reza. An Introduction to Information Theory. New York: McGraw-Hill 1961. New York: Dover 1994. ISBN 0-486-68210-2
- B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, Inc. 1996. ISBN 0-471-12845-7
| Lossless compression methods |
| ||||
|---|---|---|---|---|---|
| Audio compression methods |
| ||||
| Image compression methods |
| ||||
| Video compression |
| ||||
| Timeline of information theory, data compression, and error-correcting codes | |||||
Information theory is a branch of applied mathematics and engineering involving the quantification of information to find fundamental limits on compressing and reliably communicating data.
..... Click the link for more information.
..... Click the link for more information.
data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an un-encoded representation would use through use of specific encoding schemes.
..... Click the link for more information.
..... Click the link for more information.
checksum is a form of redundancy check, a simple way to protect the integrity of data by detecting errors in data that are sent through space (telecommunications) or time (storage).
..... Click the link for more information.
..... Click the link for more information.
In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data (information) integrity across noisy channels and less-than-reliable storage media.
..... Click the link for more information.
..... Click the link for more information.
In electrical engineering and computer science, channel capacity is the tightest upper bound on the amount of information that can be reliably transmitted over a communications channel.
..... Click the link for more information.
..... Click the link for more information.
The entropy rate of a stochastic process is, informally, the time density of the average information in a stochastic process. For stochastic processes with a countable index, the entropy rate is the limit of the joint entropy of members of the process divided by , as tends to
..... Click the link for more information.
..... Click the link for more information.
The joint entropy is an entropy measure used in information theory. The joint entropy measures how much entropy is contained in a joint system of two random variables. If the random variables are and , the joint entropy is written .
..... Click the link for more information.
..... Click the link for more information.
Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable.
Shannon entropy quantifies the information contained in a piece of data: it is the minimum average message length, in bits (if using base-2 logarithms), that must
..... Click the link for more information.
Shannon entropy quantifies the information contained in a piece of data: it is the minimum average message length, in bits (if using base-2 logarithms), that must
..... Click the link for more information.
logarithm (to base b) of a number x is the exponent y that satisfies x = by. It is written logb(x) or, if the base is implicit, as log(x).
..... Click the link for more information.
..... Click the link for more information.
In mathematics, the cardinality of a set is a measure of the "number of elements of the set". There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers.
..... Click the link for more information.
..... Click the link for more information.
The Hartley function is a measure of uncertainty, introduced by Ralph Hartley in 1928. If we pick a sample from a finite set A uniformly at random, the information revealed after we know the outcome is given by the Hartley function
..... Click the link for more information.
..... Click the link for more information.
discrete uniform distribution is a discrete probability distribution that can be characterized by saying that all values of a finite set of possible values are equally probable.
..... Click the link for more information.
..... Click the link for more information.
Data compression ratio, also known as compression power, is a computer-science term used to quantify the reduction in data-representation size produced by a data compression algorithm.
..... Click the link for more information.
..... Click the link for more information.
In probability theory and information theory, the mutual information, or transinformation, of two random variables is a quantity that measures the mutual dependence of the two variables.
..... Click the link for more information.
..... Click the link for more information.
The total correlation (Watanabe 1960) is one of several generalizations of the mutual information. It is also known as the multivariate constraint (Garner 1962) or multiinformation (Studenı & Vejnarová 1999).
..... Click the link for more information.
..... Click the link for more information.
expected value (or mathematical expectation, or mean) of a discrete random variable is the sum of the probability of each possible outcome of the experiment multiplied by the outcome value (or payoff).
..... Click the link for more information.
..... Click the link for more information.
Ergodic theory, the study of ergodic transformations, grew out of an attempt to prove the ergodic hypothesis of statistical physics. Much of the early work in what is now called chaos theory was pursued almost entirely by mathematicians, and published under the title of "ergodic
..... Click the link for more information.
..... Click the link for more information.
Stationary can mean:
..... Click the link for more information.
- Fixed in position, or mode: immobile.
- Unchanging in condition or character.
- In statistics and probability: a stationary process.
- In mathematics: a stationary point.
- In mathematics: a stationary set.
..... Click the link for more information.
data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an un-encoded representation would use through use of specific encoding schemes.
..... Click the link for more information.
..... Click the link for more information.
Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy.
The source coding theorem shows that (in the limit, as the length of a stream of i.i.d.
..... Click the link for more information.
The source coding theorem shows that (in the limit, as the length of a stream of i.i.d.
..... Click the link for more information.
In 1943 Erwin Schrödinger used the concept of “negative entropy” in his popular-science book What is life?. Later, Léon Brillouin shortened the expression to a single word, negentropy.
..... Click the link for more information.
..... Click the link for more information.
Exformation is a term meaning explicitly discarded information. It was coined by Danish physicist Tor Nørretranders in his book The User Illusion published in English 1998.
..... Click the link for more information.
..... Click the link for more information.
data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an un-encoded representation would use through use of specific encoding schemes.
..... Click the link for more information.
..... Click the link for more information.
Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. This can be contrasted to lossy data compression, which does not allow the exact original data to be reconstructed from the
..... Click the link for more information.
..... Click the link for more information.
Information theory is a branch of applied mathematics and engineering involving the quantification of information to find fundamental limits on compressing and reliably communicating data.
..... Click the link for more information.
..... Click the link for more information.
Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable.
Shannon entropy quantifies the information contained in a piece of data: it is the minimum average message length, in bits (if using base-2 logarithms), that must
..... Click the link for more information.
Shannon entropy quantifies the information contained in a piece of data: it is the minimum average message length, in bits (if using base-2 logarithms), that must
..... Click the link for more information.
In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity
..... Click the link for more information.
..... Click the link for more information.
In information theory an entropy encoding is a lossless data compression scheme that is independent of the media’s specific characteristics.
One of the main types of entropy coding assigns codes to symbols so as to match code lengths with the probabilities of the
..... Click the link for more information.
One of the main types of entropy coding assigns codes to symbols so as to match code lengths with the probabilities of the
..... Click the link for more information.
Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way
..... Click the link for more information.
..... Click the link for more information.
Adaptive Huffman coding (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding, building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
