課程名稱︰資訊理論與編碼技巧
課程性質︰選修
課程教師︰吳家麟
開課學院：電資學院
開課系所︰資工所
考試日期（年月日）︰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?