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

EDITING (SID)

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)

The largest value of T(k,n) = T(n/2, n)   when k =n/2

Most likely of T(k,n) = T(np, n), when k=np

BSCT

(a) ,code with expected rate

(b)  code with and expected rate <

General Source Coding Theorem

For General case(i  try my best to recall, but... Sorry here i just show a ref about source coding theorem)