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

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.246.87 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1397301315.A.71A.html