程序代写 MATH3411 INFORMATION, CODES & CIPHERS Test 1, Session 2 2011, SOLUTIONS

MATH3411 INFORMATION, CODES & CIPHERS Test 1, Session 2 2011, SOLUTIONS
Multiple choice: d,b,e,b,e True/False: T, F, F, F, T
(say), and equiprobable input has binary entropy 1. (c) False: it is 8.
(d) False: number of primitive elements is φ(48) = φ(16)φ(3) = (16− 8)×2 = 16.

Copyright By PowCoder代写 加微信 powcoder

(e) True: becausethenα(α2 +1)=α3 +α=1=α7.
(b): I(A,B) = H(B) − H(B|A) = H(0.1 + 0.4p) − (0.7p + 0.2),
differentiating with respect to p gives the turning point at 0.4 log2((0.1 + 0.4p)−1 − 1) = 0.7,
or (0.1 + 0.4p)−1 = 27/4 + 1 ≈ 4.36. Solving for p gives p ≈ 0.32. (e):
(b): We find x1 = 10 and x2 = 101, so |x2 − x1| = 91 = 7 × 13, so gcd(|x2 − x1|, n) = 13 (or use Euclidean algorithm).
(e): the output stream is 3, 0, 5, 6, 2, 4 then repeats. L(n) 1
True: n < H(S) + n, so average has to be less than 2.75. (b) False: entropy of output is zero if all symbols are corrupted to 0 (b) The respective lengths are 1, 2, 2, 2, 3, and the code is then 0, 10, 11, 12, 200 with average length 47 = 1.75. (c) The shortest codeword will correspond to s1s1s1 with probability 3−3. Itslengthisthenlwith2l−1 <33 =27≤2l andweneed l = 5. The second shortest will correspond to s2s1s1 (or some permuta- tion) with probability (32 ×4)−1 = 36−1. So with length l we have 2l−1 <36<2l andsothelengthis6. Multiple Choice: a, c, d, d, e True/False: T, T, T, T, F (say), and equiprobable input has binary entropy 1. (c) False: (d) True: number of primitive elements is φ(120) = φ(8)φ(3)φ(5) = (8−4)×2×4 = 32. (e) False: becausethenα(α2 +1)=α3 +α̸=1,andα7 =1. (c): I(A,B) = H(B)−H(B|A) = H(0.1+0.5p)−(0.8p+0.3), dif- ferentiating with respect to p gives the turning point at 0.5 log2((0.1 + 0.5p)−1 − 1) = 0.8, or (0.1 + 0.5p)−1 = 28/5 + 1 ≈ 4.03. Solving for p gives p ≈ 0.30. (d): (d): We find x1 = 10 and x2 = 101, so |x2 − x1| = 91 = 7 × 13, so gcd(|x2 − x1|, n) = 91 (or use Euclidean algorithm). (e): the output stream is 1, 0, 4, 2, 3, 6 then repeats. L(n) 1 True: n < H(S) + n, so average has to be less than 2.6. (b) True: entropy of output is zero if all symbols are corrupted to 0 (b) The respective lengthes are 1, 2, 2, 3, 3, and the code is then 0, 10, 11, 120, 121 with average length 107 ≈ 1.78. (c) The longest codeword will correspond to s5s5 with probability 12−2. Its length is then l with 2l−1 < 122 = 144 ≤ 2l and we need l = 8. The second longest will correspond to s4s5 (or s5s4) with proba- bility (120)−1. So with length l we have 2l−1 < 120 < 2l and so the length is 7. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com