Extra Problems for Chapter 5

T.M. Cover and J.A. Thomas

  1. Non-singular codes: The discussion in class and in the text focussed on instantaneous codes, with extensions to uniquely decodable codes. Both these are required in cases when the code is to be used repeatedly to encode a sequence of outcomes of a random variable. But if we need to encode only one outcome and we know when we have reached the end of a codeword, we do not need unique decodability - only the fact that the code is non-singular would suffice. Eg. if a random variable X takes on 3 values a, b and c, we could encode them by 0, 1, and 00. Such a code is non-singular but not uniquely decodeable.

    In the following, assume that we have a random variable X which takes on m values with probabilities tex2html_wrap_inline655 and that the probabilities are ordered so that tex2html_wrap_inline657 .

    1. By viewing the non-singular binary code as a ternary code with three symbols, 0,1 and ``STOP'', show that the expected length of a non-singular code tex2html_wrap_inline659 for a random variable X satisfies the following inequality:

      equation599

      where tex2html_wrap_inline663 is the entropy of X in bits. Thus the average length of a non-singular code is at least a constant fraction of the average length of an instantaneous code.

    2. Let tex2html_wrap_inline667 be the expected length of the best instantaneous code and tex2html_wrap_inline669 be the expected length of the best non-singular code for X. Argue that tex2html_wrap_inline673 .
    3. Give a simple example where the average length of the non-singular code is less than the entropy.
    4. The set of codewords available for an non-singular code is tex2html_wrap_inline675 . Since tex2html_wrap_inline677 , show that this is minimized if we allot the shortest codewords to the most probable symbols.

      Thus tex2html_wrap_inline679 , tex2html_wrap_inline681 , etc. Show that in general tex2html_wrap_inline683 , and therefore tex2html_wrap_inline685 .

    5. The previous part shows that it is easy to find the optimal non-singular code for a distribution. However, it is a little more tricky to deal with the average length of this code. We now bound this average length. It follows from the previous part that tex2html_wrap_inline687 . Consider the difference

      equation604

      Prove by the method of Lagrange multipliers that the maximum of tex2html_wrap_inline689 occurs when tex2html_wrap_inline691 , where tex2html_wrap_inline693 and tex2html_wrap_inline695 is the sum of the harmonic series, i.e.,

      equation608

      (This can also be done using the non-negativity of relative entropy.)

    6. Complete the arguments for

      eqnarray613

      Now it is well known (see, e.g. Knuth, ``Art of Computer Programming'', Vol. 1) that tex2html_wrap_inline697 (more precisely, tex2html_wrap_inline699 where tex2html_wrap_inline701 , and tex2html_wrap_inline703 Euler's constant tex2html_wrap_inline705 ). Either using this or a simple approximation that tex2html_wrap_inline707 , which can be proved by integration of tex2html_wrap_inline709 , it can be shown that tex2html_wrap_inline711 . Thus we have

      equation615

      A non-singular code cannot do much better than an instantaneous code!

  2. Huffman codes.
    1. Construct a binary Huffman code for the following distribution on 5 symbols tex2html_wrap_inline713 . What is the average length of this code?
    2. Construct a probability distribution tex2html_wrap_inline715 on 5 symbols for which the code that you constructed in part (a) has an average length (under tex2html_wrap_inline715 ) equal to its entropy tex2html_wrap_inline719 .
  3. Huffman codes: Consider a random variable X which takes 6 values tex2html_wrap_inline723 with probabilities (0.5,0.25,0.1, 0.05,0.05,0.05) respectively.
    1. Construct a binary Huffman code for this random variable. What is its average length?
    2. Construct a quaternary Huffman code for this random variable, i.e., a code over an alphabet of four symbols (call them a,b,c and d). What is the average length of this code?
    3. One way to construct a binary code for the random variable is to start with a quaternary code, and convert the symbols into binary using the mapping tex2html_wrap_inline731 , tex2html_wrap_inline733 , tex2html_wrap_inline735 and tex2html_wrap_inline737 . What is the average length of the binary code for the above random variable constructed by this process?
    4. For any random variable X, let tex2html_wrap_inline741 be the average length of the binary Huffman code for the random variable, and let tex2html_wrap_inline743 be the average length code constructed by first building a quaternary Huffman code and converting it to binary. Show that

      equation621

    5. The lower bound in the previous example is tight. Give an example where the code constructed by converting an optimal quaternary code is also the optimal binary code?
    6. The upper bound, i.e., tex2html_wrap_inline745 is not tight. In fact, a better bound is tex2html_wrap_inline747 . Prove this bound, and provide an example where this bound is tight.
  4. Data compression. Find an optimal set of binary codeword lengths tex2html_wrap_inline749 (minimizing tex2html_wrap_inline751 ) for an instantaneous code for each of the following probability mass functions:
    1. tex2html_wrap_inline753
    2. tex2html_wrap_inline755
  5. Bad wine
    One is given 6 bottles of wine. It is known that precisely one bottle has gone bad (tastes terrible). From inspection of the bottles it is determined that the probability tex2html_wrap_inline757 that the tex2html_wrap_inline759 bottle is bad is given by tex2html_wrap_inline761 . Tasting will determine the bad wine.

    Suppose you taste the wines one at a time. Choose the order of tasting to minimize the expected number of tastings required to determine the bad bottle. Remember, if the first 5 wines pass the test you don't have to taste the last.

    1. What is the expected number of tastings required?
    2. Which bottle should be tasted first?

    Now you get smart. For the first sample, you mix some of the wines in a fresh glass and sample the mixture. You proceed, mixing and tasting, stopping when the bad bottle has been determined.

    (c)
    What is the minimum expected number of tastings required to determine the bad wine?
    (d)
    What mixture should be tasted first?
  6. Huffman coding

    Let X have probability mass function tex2html_wrap_inline765

    1. Find the binary Huffman code for X.
    2. Find the ternary (D=3) Huffman code for X.
  7. Huffman vs. Shannon

    A random variable X takes on three values with probabilities 0.6, 0.3, and 0.1.

    1. What are the lengths of the binary Huffman codewords for X? What are the lengths of the binary Shannon codewords tex2html_wrap_inline777 for X?
    2. What is the smallest integer D such that the expected Shannon codeword length with a D-ary alphabet equals the expected Huffman codeword length with a D-ary alphabet?
  8. Arithmetic coding.
    Let tex2html_wrap_inline787 be binary stationary Markov with transition matrix tex2html_wrap_inline789
    1. Find tex2html_wrap_inline791
    2. How many bits tex2html_wrap_inline793 can be known for sure if it is not known how X=01110 continues?
  9. Tunstall Coding: The normal setting for source coding maps a symbol (or a block of symbols) from a finite alphabet onto a variable length string. An example of such a code is the Huffman code, which is the optimal (minimal expected length) mapping from a set of symbols to a prefix free set of codewords. Now consider the dual problem of variable-to-fixed length codes, where we map a variable length sequence of source symbols into a fixed length binary (or D-ary) representation. A variable-to-fixed length code for an i.i.d. sequence of random variables tex2html_wrap_inline799 is defined by a prefix-free set of phrases tex2html_wrap_inline801 , where tex2html_wrap_inline803 is the set of finite length strings of symbols of tex2html_wrap_inline805 , and tex2html_wrap_inline807 . Given any sequence tex2html_wrap_inline809 , the string is parsed into phrases from tex2html_wrap_inline811 (unique because of the prefix free property of tex2html_wrap_inline811 ), and represented by a sequence of symbols from a D-ary alphabet. Define the efficiency of this coding scheme by

    equation627

    where tex2html_wrap_inline817 is the expected length of a phrase from tex2html_wrap_inline811 .

    1. Prove that tex2html_wrap_inline821 .
    2. The process of constructing tex2html_wrap_inline811 can be considered as a process of constructing an m-ary tree whose leaves are the phrases in tex2html_wrap_inline811 . Assume that D= 1+k(m-1) for some integer tex2html_wrap_inline831 .

      Consider the following algorithm due to Tunstall:

      1. Start with tex2html_wrap_inline833 with probabilities tex2html_wrap_inline835 . This corresponds to a complete m-ary tree of depth 1.
      2. Expand the node with the highest probability. For example, if tex2html_wrap_inline839 is the node with the highest probability, the new set is tex2html_wrap_inline841 .
      3. Repeat step 2 until the number of leaves (number of phrases) reaches the required value.

      Show that the Tunstall algorithm is optimal, in the sense that it constructs a variable to fixed code with the best tex2html_wrap_inline843 for a given D, i.e., the largest value of tex2html_wrap_inline817 for a given D.

    3. Show that there exists a D such that tex2html_wrap_inline853 .
  10. Huffman algorithm for tree construction: Consider the following problem: m binary signals tex2html_wrap_inline857 are available at times tex2html_wrap_inline859 , and we would like to find their sum tex2html_wrap_inline861 using 2-input gates, each gate with 1 time unit delay, so that the final result is available as quickly as possible. A simple greedy algorithm is to combine the earliest two results, forming the partial result at time tex2html_wrap_inline863 . We now have a new problem with tex2html_wrap_inline865 , available at times tex2html_wrap_inline867 . We can now sort this list of T's, and apply the same merging step again, repeating this until we have the final result.
    1. Argue that the above procedure is optimal, in that it constructs a circuit for which the final result is available as quickly as possible.
    2. Show that this procedure finds the tree that minimizes

      equation629

      where tex2html_wrap_inline869 is the time at which the result alloted to the i-th leaf is available, and tex2html_wrap_inline873 is the length of the path from the i-th leaf to the root.

    3. Show that

      equation631

      for any tree T.

    4. Show that there exists a tree such that

      equation633

  11. Generating random variables: One wishes to generate a random variable X

    equation635

    You are given fair coin flips tex2html_wrap_inline885 . Let N be the (random) number of flips needed to generate X. Show that tex2html_wrap_inline891 .

  12. Huffman coding.
    1. Give the binary Huffman code for p=(.54,.12,.08,.08,.08,.06,.04).
    2. Find the 5-ary (D=5) Huffman code for this distribution.
  13. Data compression. Find an optimal set of binary codeword lengths tex2html_wrap_inline749 (minimizing tex2html_wrap_inline751 ) for an instantaneous code for each of the following probability mass functions:
    1. tex2html_wrap_inline753
    2. tex2html_wrap_inline755
  14. Codes

    Which of the following codes are

    1. uniquely decodable?
    2. instantaneous?

    displaymath639

  15. Huffman

    Give the Huffman code with alphabet size D=4 for the distribution tex2html_wrap_inline907 .

  16. Huffman.
    Find the Huffman D-ary code for tex2html_wrap_inline911 and the expected word length
    1. for D=2.
    2. for D=4.
  17. Entropy of encoded bits Let tex2html_wrap_inline917 be a nonsingular but nonuniquely decodable code. Let X have entropy H(X).
    1. Compare H(C(X)) to H(X).
    2. Compare tex2html_wrap_inline927 to tex2html_wrap_inline929 .
  18. Code rate.
    Let X be a random variable with alphabet tex2html_wrap_inline933 and distribution

    displaymath640

    The data compression code for X assigns codewords

    displaymath641

    Let tex2html_wrap_inline937 be independent identically distributed according to this distribution and let tex2html_wrap_inline939 be the string of binary symbols resulting from concatenating the corresponding codewords.For example, 122 becomes 01010.

    1. Find the entropy rate tex2html_wrap_inline945 and the entropy rate tex2html_wrap_inline947 in bits per symbol. Note that Z is not compressible further.
    2. Now let the code be

      displaymath642

      and find the entropy rate tex2html_wrap_inline951

    3. Finally, let the code be

      displaymath643

      and find the entropy rate tex2html_wrap_inline951


Latex file

Postscript file

 

Joy Thomas
Sat Aug 15 06:53:54 EDT 1998