lecture notes 3


 

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

 

 

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

 

`As shown in the previous class/notes, 

 

Formula                             (1)

 

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

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

 

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

 

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

          Formula                                                                            (2)

  

 

Bound on the size of the typical set

 

The number of  typical Formula 

               Formula

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

Question :                Formula

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

 

 

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

 

 

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 Formula bits.

 

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

 Formula.

 

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) Formula such that for all n>N, Formula, Formulacode with expected rate Formula and 0-error.

(b) Formula code with Formulaand expected rate < Formula (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.