MATH3411 INFORMATION, CODES & CIPHERS Test 2, Session 2 2013, SOLUTIONS
Multiple choice: a, e, a, d, e
True/False: T, T, F, T, F .
2. (e): MH = 32 H (0.8) + 31 H (0.4) ≈ 0.805.
Copyright By PowCoder代写 加微信 powcoder
3. (a): I(A, B) = H(B) − H(B|A) = H(0.3 + 0.5p) − (0.4p + 0.6). Differentiating I(A, B) with respect to p and setting I′(A, B) = 0 gives
0.5 log2((0.3 + 0.5p)−1 − 1) = 0.4 ,
so (0.3 + 0.5p)−1 = 20.8 + 1 ≈ 2.74. Solving this gives p ≈ 0.13.
4. (d): φ(2013) = φ(3×11×61) = φ(3)φ(11)φ(61) = 2×10×60 = 1200, so 21203 = 2120023 = 8 in Z2013.
True: We wish to decode the number 0.55 :
code number rescaled
(0.55 − 0.3)/.4 = 0.625 (0.625 − 0.3)/.4 = 0.8125
in interval
[0.3, 0.7) [0.3, 0.7) [0.7, 1)
decoded symbol
The decoded message is then bb• .
(ii) True: The binary entropy is 0.722 and by Shannon’s Theorem,
we can get arbitrarily close to this.
(iii) False: t = ⌈√1333⌉ = 37 gives s2 = t2 − n = 36 = 62 which is
square, so a + b = (s + t) + (t − s) = 2t = 74.
(iv) True: The second smallest symbol probability in S3 is 4 , and
125 = 31.25 < 32 = 25, so the second longest codeword length is 4
(v) False: The numbers xi are 1, 6, 4, 7, 8 .
(i) Here,wehavethatα2 =−1=2.
γ1 =α+1 γ5 =2α+2 γ2=2α γ6=α
γ3 =2α+1 γ7 =α+2 γ4 =2 γ8 =1
(ii) The element γ is primitive, so all of the primitive elements of F are given by γi where gcd(i, 8) = 1; that is all of the 4 elements
γ1 =α+1, γ3 =2α+1, γ5 =2α+2, γ7 =α+2 (iii) α−1 = (γ6)−1 = γ2 = 2α.
(iv) γ7 +α = 2α+2 =2+ 2 =2+2(2α)=2+α γ4+γ α α
Multiple choice: c, d, a, d, c True/False: F, F, T, T, T .
(d): MH = 31 H (0.8) + 23 H (0.4) ≈ 0.888.
(a): I(A, B) = H(B) − H(B|A) = H(0.2 + 0.7p) − (0.4p + 0.7). Differentiating I(A, B) with respect to p and setting I′(A, B) = 0 gives
0.7 log2((0.2 + 0.7p)−1 − 1) = 0.4 ,
so (0.2 + 0.7p)−1 = 2 74 + 1 ≈ 2.49. Solving this gives p ≈ 0.29.
(d): φ(2013) = φ(3×11×61) = φ(3)φ(11)φ(61) = 2×10×60 = 1200, so 51203 = 5120053 = 125 in Z2013.
(c) 414 ≡ 1 (mod 15)
(i) False: We wish to decode the number 0.55 :
code number rescaled
(0.55 − 0.3)/.4 = 0.625 (0.625 − 0.3)/.4 = 0.8125
in interval
[0.3, 0.7) [0.3, 0.7) [0.7, 1)
decoded symbol
The decoded message is then bb• .
(ii) False: The binary entropy is 0.81 which is the lower bound on
average codeword lengths.
(iii) True: t = ⌈√1333⌉ = 37 gives s2 = t2 − n = 36 = 62 which is
square, so a + b = (s + t) + (t − s) = 2t = 74.
(iv) True: The second largest symbol probability in S3 is 16 , and
125 = 7.8125 < 8 = 23, so the second shortest codeword length is 16
(v) True: The numbers xi are 1, 6, 4, 7, 8.
(i) Here,wehavethatα2 =2α+1. i012345678
αi 1 α 2α+1 2α+2 2 2α α+2 α+1 1 3
(ii) The element α is primitive, so all of the primitive elements of F are given by αi where gcd(i, 8) = 1; that is all of the 4 elements
α1 =α, α3 =2α+2, α5 =2α, α7 =α+1 (iii) (2α+1)−1 =(α2)−1 =α6 =α+2.
α2 + 1 2α + 2 α3
(iv) α3+α4 =2α+1=α2 =α
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com