**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.

## Comments (10)

## Cho Yiu Ng said

at 11:23 am on Jan 29, 2009

No comments?

## sidjaggi said

at 12:37 am on Feb 2, 2009

Hmm, I really would like the class to join in and comment a bit on this, before I jump in and edit. Open for comments until Friday the 6th of Feb.

## Mak said

at 2:45 pm on Feb 2, 2009

You wrote: "the typical set decrease, as the epsilon decrease." What does that mean? Thanks.

## Silas said

at 10:13 am on Feb 4, 2009

I cannot follow the logical flow easily in this scribe note. May you add some connectives between statements?

Thanks a lot.

## Silas said

at 10:18 am on Feb 4, 2009

Since H(p) is not an increasing function, H(p+\epsilon) >= H(k/n) does not hold in general. Therefore, I don't understand why it is true in the middle of the scribe note. Please correct me if I am wrong.

## Tong said

at 11:38 am on Feb 4, 2009

"Since H(p) is not an increasing function, H(p+\epsilon) >= H(k/n) does not hold in general"

Here, p< 1/2. and p+\epsilon < 1/2 (i think it is because the epsilon is a small number)

## Cho Yiu Ng said

at 11:14 am on Feb 5, 2009

What is the script X in your definition of divergence?

Please make sure all the symbols are defined and state the assumptions explicitly.

## Tong said

at 11:51 am on Feb 5, 2009

the set of the value which x can take

## Cho Yiu Ng said

at 5:03 pm on Feb 5, 2009

Please put this in the scribe note.

## sidjaggi said

at 8:10 am on Feb 10, 2009

Finished my revision -- if there are any comments, speak now, or forever hold your peace :)

You don't have permission to comment on this page.