課程名稱︰消息理論
課程性質︰選修
課程教師︰林茂昭
開課學院：電資學院
開課系所︰電信所
考試日期（年月日）︰2013.4.23
考試時限（分鐘）：1hr50min
是否需發放獎勵金：yes
（如未明確表示，則不予發放）
試題 :
Midterm Exam of Information Theory
April 23, 2013
1.Let X be a discrete random variable and g(X) be a function of X.
Please show that H(g(X)) <= H(X). (10%)
2.(a)Derive the channel capacity of the binary symmetric channel with
transition probability ε. (10%)
(b)Derive the channel capacity the channel with the following channel
transition matrix. (10%)
| 0 1 E
------------------------
0| 0.7 0.1 0.2
1| 0.1 0.7 0.2
3.Consider a discrete random variable X = {1,2,3,4,5} with probabilities
p(1)=0.3, p(2)=0.5, p(3)=0.2, p(4)=0.15, p(5)=0.1.
(a)Please find a Huffman code for X. (7%)
(b)Please find a Shannon-Fano Elias code for X. (8%)
4.Please describe the Kraft inequality and the McMillan inequality. (10%)
5.Consider a two-state stationary Markov chain with state transition
probabilities p_11=1-a, p_12=a, p_21=b, p_22=1-b. Please find the associated
entropy rate. (10%)
6.Describe the channel coding theorem and its converse for the discrete
memoryless channel. (10%)
7.Let X={0,1} be a source with probabilities and X^10000 be an extended source.
Consider a binary symmetric channel with input X and output Y, where the
transition probabilities are p(y|x)=0.9 for y=x and p(y|x)=0.1 for y!=x,
(a)Please show an example of a typical sequence in X^10000. (5%)
(b)Please show an example of a typical joint sequence in (X^10000,Y^10000).
(5%)
(c)Please show an example of a nontypical joint sequence in (X^10000,Y^10000)
(5%)
8.Let {X_i} be a discrete stationary stochastic process with entropy H(X).
Show that
(1/n)H(X_n,...,X_1 | X_0,X_-1,...,X_-k) -> H(X)
for k=1,2,... (10%)
9.For a stationary stochastic process X_1,X_2,...,X_n,..., show that
lim (1/2n)I(X_1,X_2,...,X_n;X_n+1,X_n+2,...,X_2n) = 0 (10%)
n->inf
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.29.119