4. (20 points) Consider the following method for generating a code for a random vari- able...

 

Transcribed Image Text:

4. (20 points) Consider the following method for generating a code for a random vari- able X which takes on m values {1,2,...,m} with probabilities p... Pm. Define i-1 F = Pk k=1 the sum of the probabilities of all symbols less than i. Then the codeword for i is the binary representation of number F = [0, 1] rounded off to l; bits, where li = [log1 11 1 16 16 (a) (5 points) Construct the code for the probability distribution (2) (b) (5 points) Show that the code constructed by this process is a prefix code. (c) (5 points) Show that in general if p is a dyadic distribution, i.e., p = 2- for some positive integer ls, the average length for this code matches H(X). (d) (5 points) Show that there are sources where the relative gap to entropy L/H(X) is arbitrarily large. 4. (20 points) Consider the following method for generating a code for a random vari- able X which takes on m values {1,2,...,m} with probabilities p... Pm. Define i-1 F = Pk k=1 the sum of the probabilities of all symbols less than i. Then the codeword for i is the binary representation of number F = [0, 1] rounded off to l; bits, where li = [log1 11 1 16 16 (a) (5 points) Construct the code for the probability distribution (2) (b) (5 points) Show that the code constructed by this process is a prefix code. (c) (5 points) Show that in general if p is a dyadic distribution, i.e., p = 2- for some positive integer ls, the average length for this code matches H(X). (d) (5 points) Show that there are sources where the relative gap to entropy L/H(X) is arbitrarily large.