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