• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

• You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View

# lecture notes 3

View current version     Page history
Saved by
on February 10, 2009 at 4:12:14 am

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)