MATH3411 INFORMATION, CODES & CIPHERS Test 2, Session 2 2012, SOLUTIONS
Multiple choice: c, e, b, d, d True/False: T, T, F, T, T.
(c): Word is s1s1s2, or some permutation thereof, with probability 50/73 ≈ 1/7 .
(e): I(A,B)=H(A)+H(B)−H(A,B).
Copyright By PowCoder代写 加微信 powcoder
(b): I(A,B) = H(B) − H(B|A) = H(0.2 + 0.7p) − (0.5p + 0.7),
differentiating with respect to p gives the turning point at 0.7 log2((0.1 + 0.7p)−1 − 1) = 0.5,
or (0.2 + 0.7p)−1 = 25/7 + 1 ≈ 2.64. Solving for p gives p ≈ 0.26.
φ(2012) = 1004 so 32011 = (31004)233 = 27 in Z2012.
3569 = 83 × 43.
(iii) False: gcd(22, 175) = 1 so inverse exists.
(iv) True: Thepowersof5inZ17 run5,8,6,…,so6=53 inZ17 and gcd(3, φ(17)) = gcd(3, 16) = 1, so 6 is primitive.
(v) True: clearlygcd(7,25)=1inZ25,72 =49=−1so724 =1.
α3=α2 +α=2α+1 α4=2α2 +α=2
α6 =2α2 =2α+2 α7 =2α3 =α+2 α8 =2α4 =1=α0
True: message encodes as (0, a)(0, b)(1, a)(2, b)(3, a)
(ii) True: binary entropy is 0.722 and by Shannon’s theorem we can
get arbitrarily close to this.
(ii) Determinantofthecoefficientmatrixisα11−α7 =(2α+1)−(α+ 2) = α + 2 = α7, so the solution is
x −7α7 2α52 2α7 +2α8 2+2α y =α 2α2 α4 α3 =α α2+α7 = α3+1
So x = 2α + 2 = α6, y = 2α + 2 = α6.
You can also use row reduction: your method for first year will
(iii) The other root of the minimal polynomial will be α21 = α5, as
(α5)3 = α15 = α7. So the polynomial is
(x−α7)(x−α5) = x2 −(α7 +α5)x+α12 = x2 −2x+2 = x2 +x+2.
Multiple Choice: b, c, e, d, a True/False: F, T, T, F, T.
(b): Word is s1s2s2, or some permutation thereof, with probability 6/73 ≈ 1/57.
(c): H(A,B)=H(A)+H(B)−I(A,B)
(e): I(A,B) = H(B) − H(B|A) = H(0.3 + 0.6p) − (0.5p + 0.9),
differentiating with respect to p gives the turning point at 0.6 log2((0.3 + 0.6p)−1 − 1) = 0.5,
or (0.3 + 0.6p)−1 = 25/6 + 1 ≈ 2.78. Solving for p gives p ≈ 0.10.
φ(2012) = 1004 so 52011 = (51004)253 = 125 in Z2012.
5141 = 97 × 53.
(iii) True: gcd(21, 175) = 7 so there is no inverse
(iv) False: The powers of 3 in Z17 run 3, 9, 10, 13, …, so 13 = 34 and gcd(4, φ(17)) = gcd(4, 16) ̸= 1, so 13 is not primitive.
(v) True: clearlygcd(8,21)=1andinZ21,82 =64=1so820 =1.
α3=2α2 +α=2α+2 α4=2α2 +2α=2
α6 =2α2 =α+2 α7 =2α3 =α+1 α8 =2α4 =1=α0
False: message encodes as (0, a)(0, b)(2, a)(3, b)(2, b).
(ii) True: binary entropy is 0.764 and by Shannon’s theorem we can
get arbitrarily close to this.
(ii) Determinant of the coefficient matrix is α7 − α5 = α + 1 − (2α) = 2α + 1 = α2, so the solution is
x −2 α5 2α4 1 6 α5 + 2α6 α3 + α8 y =α 2α α2 α2 =α 2α+α4 = 2α7+α2
So x = 2α = α5, y = α.
You can also use row reduction: your method for first year will work.
(iii) The other root of the minimal polynomial will be α21 = α5, as (α5)3 = α15 = α7. So the polynomial is
(x−α7)(x−α5) = x2 −(α7 +α5)x+α12 = x2 −x+2 = x2 +2x+2.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com