In information theory, Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy. A bundle of optical fiber. ... In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ... Entropy of a Bernoulli trial as a function of success probability. ...

The source coding theorem shows that (in the limit, as the length of a stream of i.i.d. data tends to infinity) no compression of the data is possible into a shorter message length than the total Shannon entropy, without it being virtually certain that information will be lost. But compression arbitrarily close to the Shannon entropy is possible, with negligible probability of loss. In probability theory, a sequence or other collection of random variables is independent and identically distributed (i. ...

The source coding theorem for symbol codes places an upper and a lower bound on the minimal possible expected length of codewords as a function of the entropy of the input word (which is viewed as a random variable) and of the size of the target alphabet. A random variable is a mathematical function that maps outcomes of random experiments to numbers. ...

Statements

Source coding is a mapping from (a sequence of) symbols from an information source to a sequence of alphabet symbols (usually bits) such that the source symbols can be exactly recovered from the binary bits (lossless source coding) or recovered within some distortion (lossy source coding). This is the concept behind data compression. A bundle of optical fiber. ... In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ...

Source coding theorem

In information theory, the source coding theorem (Shannon 1948) informally states that:

"N i.i.d. random variables each with entropy H(X) can be compressed into more than NH(X) bits with negligible risk of information loss, as N tends to infinity; but conversely, if they are compressed into fewer than NH(X) bits it is virtually certain that information will be lost." (MacKay 2003).

In probability theory, a sequence or other collection of random variables is independent and identically distributed (i. ... Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ... BITS may have any of the following meanings: In computer science, bits are binary digits, which may each have the value one or zero. ...

Source coding theorem for symbol codes

Let X be a random variable taking values in some finite alphabet Σ₁ and let f be a decipherable code from Σ₁ to Σ₂ where . [TODO: is undefined!] Let S denote the resulting wordlength of f(X).

If f is optimal in the sense that it has the minimal expected wordlength for X, then

(Shannon 1948)

Proof: Source coding theorem

Given X is an i.i.d. source, its time series X₁, ..., X_n is i.i.d. with entropy H(X) in the discrete-valued case and differential entropy in the continuous-valued case. The Source coding theorem states that for any ε > 0 for any rate larger than the entropy of the source, there is large enough n and an encoder that takes n i.i.d. repetition of the source, X^1:n, and maps it to n.(H(X) + ε) binary bits such that the source symbols X^1:n are recoverable from the binary bits with probability at least 1 − ε. In probability theory, a sequence or other collection of random variables is independent and identically distributed (i. ... In statistics and signal processing, a time series is a sequence of data points, measured typically at successive times, spaced apart at uniform time intervals. ... Ice melting - classic example of entropy increasing[1] described in 1862 by Rudolf Clausius as an increase in the disgregation of the molecules of the body of ice. ... Differential entropy (also referred to as continuous entropy) is a concept in information theory which tries to extend the idea of (Shannon) entropy, a measure of average surprisal of a random variable, to continuous probability distributions. ... A bundle of optical fiber. ... Ice melting - classic example of entropy increasing[1] described in 1862 by Rudolf Clausius as an increase in the disgregation of the molecules of the body of ice. ...

Proof for achievablity

Fix some for any ε > 0. The typical set,, is defined as follows:

AEP shows that for large enough n, the probability that a sequence generated by the source lies in the typical set,, defined as approaches one. In particular there for large enough n, (See AEP for a proof): The asymptotic equipartition property (AEP) is a general property used extensively in information theory concerning the output samples of a stochastic source. ... The asymptotic equipartition property (AEP) is a general property used extensively in information theory concerning the output samples of a stochastic source. ...

The definition of typical sets implies that those sequences that lie in the typical set satisfy:

Note that:

• The probability of a sequence from X being drawn from is greater than 1 − ε

• since the probability of the whole set is at most one.

• . For the proof, use the upper bound on the probability of each term in typical set and the lower bound on the probability of the whole set .

Since bits are enough to point to any string in this set.

The encoding algorithm: The encoder checks if the input sequence lies within the typical set; if yes, it outputs the index of the input sequence within the typical set; if not, the encoder outputs an arbitrary n.(H(X) + ε) digit number. As long as the input sequence lies within the typical set (with probability at least 1 − ε), the encoder doesn't make any error. So, the probability of error of the encoder is bounded above by ε

Proof for converse The converse is proved by showing that any set of size smaller than (in the sense of exponent) would cover a set of probability bounded away from 1.

Proof: Source coding theorem for symbol codes

Let s_i denote the wordlength of each possible x_i (). Define , where C is chosen so that .

Then

where the second line follows from Gibbs' inequality and the third line follows from Kraft's inequality: so . In information theory, Gibbs inequality is a statement about the mathematical entropy of a discrete probability distribution. ... This article needs to be cleaned up to conform to a higher standard of quality. ...

For the second inequality we may set

so that

and so

and

and so by Kraft's inequality there exists a prefix-free code having those wordlengths. Thus the minimal S satisfies

Extension to non-stationary independent sources

Fixed Rate lossless source coding for discrete time non-stationary independent sources

Define typical set as:

Then, for given δ > 0, for n large enough, . Now we just encode the sequences in the typical set, and usual methods in source coding show that the cardinality of this set is smaller than . Thus, on an average, bits suffice for encoding with probability greater than 1 − δ, where can be made arbitrarily small, by making n larger.

See also

• Channel coding
• Noisy Channel Coding Theorem
• Error exponent
• Asymptotic Equipartition Property (AEP)
• Data compression