• 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!


lecture notes 3

This version was saved 14 years, 7 months ago View current version     Page history
Saved by sidjaggi
on February 10, 2009 at 4:12:14 am


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)


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)



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

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



As asked to prove in PS2, if  Formula we have Formula 





The number of  typical Formula 



Question :                Formula

               to prove   Formula


by l'Hôpital's rule, we haveFormula   



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

the size of largest set class Formula  

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



(a) Formula,Formulacode with expected rate Formula

(b) Formula code with Formulaand expected rate < Formula


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.