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

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

We remind ourselves that the *relative entropy* between two probability mass functions *p(x)* and *q(x)* is defined as

(also called the *Kullback-Leibler divergence*), where the denotes the sample space of the random variable **X**.

As asked to prove in PS2, if we have

EDITING IN PROGRESS (Sid)

The number of typical

Question :

to prove

by **l'HÃ´pital's rule, we have **

the number of the typical type-class and the number of the typical element

the size of largest set class

Expected # bits (the typical part + the atypical part)

the typical set decrease, as the epsilon decrease.

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 <

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

## Comments (0)

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