===========================================================================
CSC 310H                     Lecture 4 Summary                    Fall 2007
===========================================================================

------
Topics
------

 -  proofs of Kraft and McMillan theorems
 -  reference: section 5.2.

---------------
Kraft's Theorem
---------------

Statement:

    IF Sum_{i=1}^I {2^{-l_i}} <= 1, THEN an ID code exists with codeword
    lengths l_i.

Ideas:

 -  Construct an ID code by selecting codewords from a tree in
    non-decreasing order of length.

 -  Must show we will not run out of options. To do that, consider how many
    codewords at level i' become unusable when we select a codeword at
    level i <= i'.

 -  Use KM inequality to show that when selecting a codeword of length
    l_i', the number of usable codewords at that level is > 0.

Reference: solution to exercise 5.14, pp104-5.

------------------
McMillan's Theorem
------------------

Statement:

    If code is UD, THEN Sum_{i=1}^I {2^{-l_i}} <= 1.

Ideas:

 -  K^N = Sum_{source strings X of length N} of { 2^{-length(c(X))} }

 -  Split sum according to length(c(X))

 -  Note N*l_min <= length(c(X)) <= N*l_max

 -  Define A_j = number of source strings X of length N that have an
    encoding c(X) of length exactly j.

 -  K^N = Sum{j=N*l_min}^{N*l_max} { A_j * 2^{-j} }

 -  By UD, A_j <= 2^{-j}

 -  K^N <= N*l_max

 -  This holds for all N! If K>1, K^N is exponential in N so it eventually
    becomes larger than N*l_max, which is linear in N. Thus, K <= 1.

Reference: proof in section 5.2, on p.95.