Shannon's source coding theorem - Alchetron, the free social encyclopedia

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.

The source coding theorem shows that (in the limit, as the length of a stream of independent and identically-distributed random variable (i.i.d.) data tends to infinity) it is impossible to compress the data such that the code rate (average number of bits per symbol) is less than the Shannon entropy of the source, without it being virtually certain that information will be lost. However it is possible to get the code rate arbitrarily close to the Shannon entropy, with negligible probability of loss.

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.

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.

Source coding theorem

In information theory, the source coding theorem (Shannon 1948) informally states that (MacKay 2003, pg. 81, Cover:Chapter 5):

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

Source coding theorem for symbol codes

Let Σ₁, Σ₂ denote two finite alphabets and let Σ∗
1 and Σ∗
2 denote the set of all finite words from those alphabets (respectively).

Suppose that X is a random variable taking values in Σ₁ and let f be a uniquely decodable code from Σ∗
1 to Σ∗
2 where |Σ₂| = a. Let S denote the random variable given by the word length f (X).

If f is optimal in the sense that it has the minimal expected word length for X, then (Shannon 1948):

H ( X ) log 2 ⁡ a ≤ E S < H ( X ) log 2 ⁡ a + 1

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 − ε.

Proof of Achievability. Fix some ε > 0, and let

p ( x 1 , … , x n ) = Pr [ X 1 = x 1 , ⋯ , X n = x n ] .

The typical set, Aε
n, is defined as follows:

A n ε = { ( x 1 , ⋯ , x n ) : | − 1 n log ⁡ p ( x 1 , ⋯ , x n ) − H n ( X ) | < ε } .

The Asymptotic Equipartition Property (AEP) shows that for large enough n, the probability that a sequence generated by the source lies in the typical set, Aε
n, as defined approaches one. In particular, for sufficiently large n, P ( ( X 1 , X 2 , ⋯ , X n ) ∈ A n ε ) can be made arbitrarily close to 1, and specifically, greater than 1 − ε (See AEP for a proof).

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

2 − n ( H ( X ) + ε ) ≤ p ( x 1 , ⋯ , x n ) ≤ 2 − n ( H ( X ) − ε )

Note that:

The probability of a sequence ( X 1 , X 2 , ⋯ X n ) being drawn from Aε
n is greater than 1 − ε.

| A n ε | ≤ 2 n ( H ( X ) + ε ) , which follows from the left hand side (lower bound) for p ( x 1 , x 2 , ⋯ x n ) .

| A n ε | ≥ ( 1 − ε ) 2 n ( H ( X ) − ε ) , which follows from upper bound for p ( x 1 , x 2 , ⋯ x n ) and the lower bound on the total probability of the whole set Aε
n.

Since | A n ε | ≤ 2 n ( H ( X ) + ε ) , n . ( H ( X ) + ε ) 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 of Converse. The converse is proved by showing that any set of size smaller than Aε
n (in the sense of exponent) would cover a set of probability bounded away from 1.

Proof: Source coding theorem for symbol codes

For 1 ≤ i ≤ n let s_i denote the word length of each possible x_i. Define q i = a − s i / C , where C is chosen so that q₁ + ... + q_n = 1. Then

H ( X ) = − ∑ i = 1 n p i log 2 ⁡ p i ≤ − ∑ i = 1 n p i log 2 ⁡ q i = − ∑ i = 1 n p i log 2 ⁡ a − s i + ∑ i = 1 n p i log 2 ⁡ C = − ∑ i = 1 n p i log 2 ⁡ a − s i + log 2 ⁡ C ≤ − ∑ i = 1 n − s i p i log 2 ⁡ a ≤ E S log 2 ⁡ a

where the second line follows from Gibbs' inequality and the fifth line follows from Kraft's inequality:

C = ∑ i = 1 n a − s i ≤ 1

so log C ≤ 0.

For the second inequality we may set

s i = ⌈ − log a ⁡ p i ⌉

so that

− log a ⁡ p i ≤ s i < − log a ⁡ p i + 1

and so

a − s i ≤ p i

and

∑ a − s i ≤ ∑ p i = 1

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

E S = ∑ p i s i < ∑ p i ( − log a ⁡ p i + 1 ) = ∑ − p i log 2 ⁡ p i log 2 ⁡ a + 1 = H ( X ) log 2 ⁡ a + 1

References

Shannon's source coding theorem Wikipedia

(Text) CC BY-SA