Source Coding Theorem (Achievability) (Scribe: LIANG Tong)

We now derive and use properties of the to obtain a source code.

`As shown in the previous class/notes, 

                             (1)

To remind ourselves, this bound arises by first proving that the probability that a sequence is atypical is , where

is defined as the relative entropy between two probability mass functions p(x) and q(x) (also called the Kullback-Leibler divergence), where the  denotes the sample space of the random variable X.

Second, as asked to prove in PS2, if   we have . Combining these two results gives (1).

For a "reasonable" source code we would expect that be very small, or in fact asymptotically negligible in n. This is possible if we let be a function of n, and set . In all that follows, we condition on the assumption that is indeed typical, and that

                                                                                      (2)

Bound on the size of the typical set

The number of  typical  

                (here we assume that p < 1/2; if p>1/2, a similar argument yields an upper bound of )

Question :                

               By the Taylor series expansion of H(p),   for some p' in . For fixed p distinct from 0 and 1, the maximum value of can be bounded by some c (that is a function of p, but not of )

Therefore, the size of the typical set is at most .

Source coding scheme

1. Use the first bit to describe whether the sequence is typical or not

2(a). If the sequence is atypical, describe the entire sequence uncompressed using n bits.

2(b). If the sequence is typical, describe the index number of the sequence in the set of typical sequences, using bits.

Expected total # bits transmitted  (one bit to describe to whether typical or not, and then bits to describe the sequence (typical/atypical) )

 .

Note that the size of the typical set decreases as epsilon decreases, but corresponding the probability of atypicality increases.

Discussion of typicality

p <1/2 and n =10 in the following figures

Fig1: the relation between #of heads and probability,

Fig2: between # of heads and size of T(k,n)

Note that the value of k for which the elements of T(k,n) have the largest (individual) probabilities is k=0 (Figure 1), and the value of k for which the size of the set T(k,n) is largest is k =n/2 (Figure 2).

However, as we saw via the analysis before, the most likely T(k,n) (the type-class with the largest probability of occuring) is T(np, n), i.e., when k=np.

Binary source coding theorem

(a) such that for all n>N, , code with expected rate and 0-error.

(b)  code with and expected rate < (we shall prove this "converse" in a later class).

The above theorem can be generalized to general i.i.d. sources over finite alphabets, with the only difference being in how the corresponding entropy function is defined -- the achievability is left as an excercise for the reader.