Some notations in symbol-by-symbol source coding

: alphabet set

     c(x): the codeword of x, or the bit sequence of x

                   l(x): length of the codeword of x, or the number of bits of the bit sequence

                   : the maximum length among all codewords

                   L: the expected length of codewords. i.e.

                       If there are m symbols in , then

Definitions of different classes of code:

1. nonsingular code

    Eevery element in  maps into a different codeword string.

    i.e.      

2. uniquely decodabl code

    Different sequences maps into different streams of codewords.

   i.e.      

     (If , then  the codeword stream for )

3. Prefix code (a.k.a prefix-free code, instantaneous code)

    No codeword is the prefix of any other code.

Relationship between these classes of code:

Plugin error: That plugin is not available.

Question in Problem Set 4

Q2

(b)

                              //can be any sequence consisting of N symbols; is the length of

Compare the two expressions, we find that if i is , then A(i) is the number of source sequences mapping into length-i codeword stream.

The size of length-i codeword stream is (binary case).

By the definition of uniquely decodable code, at most one source sequence is mapped into one codeword stream.

Therefore, no more than  source sequences can be mapped into length-i codeword, i.e.

Take Nth root at both side, we get .

(c)

The inequality we derived in (b) holds for any N.

In order to find the upper bound for the LHS, we need to minimize the RHS.

By simple analysis, the minimum value of RHS, 1, is reached when n is infinity.

So, . The Kraft Inequality holds in this specific case.

Follow the same procedure, we can prove that all uniquely decodable code satisfy the Kraft Inequality.

Q3 is basically skipped in class.

Some questions to think about:

 is H(X) is good lower bound for L? Is it possible to get an equality? The answers are affirmative.

(e.g. fair coin tossing)

Q4

(a)

Why is it hard to achieve the entropy bound?

l(i) is always an integer while log(1/p(i)) is usually not a rational number. They are not equal generally.

The easiest way to make it an integer is