课程名称︰信息论与编码技巧
课程性质︰选修
课程教师︰吴家麟
开课学院：电资学院
开课系所︰资工所
考试日期（年月日）︰2014.04.09 ~ 2014.04.23
考试时限（分钟）：2014.04.09 公布考题, 2014.04.23 上课前缴回
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
以下五项选择一项，前四项为study report，第五项为题目作答:
(1) Adaptive Huffman codes
(2) RVLC-Huffman codes
(3) Auto-sync Huffman codes
(4) Fixed-length codes with similar performance to Huffman codes
(5) Lecture 6-2 p.19 - p.22 四题及以下第五题
1. (Suffix code)
Consider codes that satisfy the suffix condition, which says that no
codeword is a suffix of any other codeword. Show that a suffix condition
code is uniquely decodable, and show that the minimum average length over
all codes satisfying the suffix condition is the same as the average length
of the Huffman code for that random variable.
2. (Huffman codes with costs)
Suppose that X = i with probability P_i, i = 1, 2, ... , m. Let l_i be the
number of binary symbols in the codeword associated with X = i, and let c_i
denote the cost per letter of the codeword when X = i. Thus the average
cost C of the description of X is
m
C = Σ (p_i)(c_i)(l_i)
i=1
-l_i
a) Minimize C over all l_1, l_2, ... , l_m such that Σ2 ≦ 1. Ignore
any implied integer constraints on l_i. Exhibit the minimizing l_1*,
l_2*, ... , l_m* and the associated minimum value C*.
b) How would you use the Huffman code procedure to minimize C over all
uniquely decodable codes? Let C_(Huffman) denote this minimum. Show that
m
C* ≦ C_(Huffman) ≦ C* + Σ (p_i)(c_i)
i=1
3. (The game of Hi-Lo)
A computer generates a number X according to a known prob. mass function
p(x), x ∈ {1, 2, ... , 100}. The player asks arbitrary Yes-No questions
sequentially until X is determined. If he is right (i.e., X is determined),
he receives a prize of value v(x).
a) How should the player proceed to maximize his expected winnings? What is
his expected return?
b) Continuing (a), what if v(x) is fixed, but p(x) can be chosen by the
computer (and then announced to the player)? The computer wishes to
minimize the player's expected return. What should p(x) be? What is the
expected return to the player?
4. Although the codeword lengths of an optimal variable length code are
complicated functions of the message probabilities {p_1, p_2, ... , p_m},
it can be said that less probable symbols are encoded into longer codewords.
Suppose that the message probabilities are given in decreasing order
p_1 ≧ p_2 ≧ ... ≧ p_m.
a) Prove that for any binary Huffman code, if the most probable message
symbol has probability p_1 ＞ 2/5, then that symbol must be assigned a
codeword of length 1.
b) Prove that for any binary Huffman code, if the most probable message
symbol has probability p_1 ＜ 1/3, then that symbol must be assigned a
codeword of length ≧ 2.
5. A computer generates a number X ∈ {1, 2, ... , N}. The player asks
arbitrary Yes-No questions sequentially until X is determined. If the
computer is allowed to make wrong answers for K times, at least how many
questions should be asked to determine X?