Multiple choice: c, c, a, d, d True/False: T, F, T, T, T .
MATH3411 INFORMATION, CODES & CIPHERS
(c): Encode the message bba• :
subinterval start
Copyright By PowCoder代写 加微信 powcoder
0 0.4 0.4+0.4×0.5=0.6 0.6 0.6+0.9×0.1=0.69
1 0.5 0.5×0.5=0.25 0.4×0.25=0.1 0.1×0.1=0.01
Session 2 2015 SOLUTIONS
(ii) False: The binary entropy is approximately 1.53 .
(iii) True: t = 46 and s = 15, so a = 31 and b = 61.
(iv) True: The longest two codeword lengths are 5 and 7.
(v) True: There are φ(48) = 16 primitive elements in GF(49).
so the message encodes as a number in the interval [0.69, 0.70). (c): MH = 7 H(0.5) + 5 H(0.7) ≈ 0.951.
12 12 (a): Note that H(85) = H(83).
(d): φ(125) = φ(53) = 53 − 52 = 100, so by Euler’s Theorem,
22015 ≡(2100)20×215 ≡120×(27)2×2≡1282×2≡32×2≡18
(d) gcd(9,28) = 1 and 927 ≡ 1 (mod 28).
True: a|aa|ab|aaa|aab|aaaa
Here,wehavethatα3 =α+1:
sox=0andy=α3 =α+1.
(iii) {α5, α10 = α3, α6, α12 = α5, . . .} = {α3, α5, α6}, so the minimal polynomial of α5 is
α3 α5 αR1=α4R1 1 α2 α5R2=R2−R1 1 α2
α5 1 α2 α5
−−−−−−→ −−−−−−−→
α2 α3 α6 R2=α−2R2 1 α α4
R2=α3R2 1 α2 α5 R1=R1−α2R2 1 0 0
α5 =α2+α+1 α6 =α2+1
0 α2+α α4−α5 −−−−−−→ 0 1 α3 −−−−−−−−→ 0 1 α3
(x−α3)(x−α5)(x−α6)=x3 −(α3 +α5 +α6)x2 +(α3α5 +α3α6 +α5α6)x−α3α5α6 =x3 +(α+1+α2 +α+1+α2 +1)x2 +(α+α2 +α4)x+1
=x3 +x2 +(α+α2 +α2 +α)x+1 = x3 + x2 + 1 .
Multiple choice: c, a, c, e, e True/False: T, T, F, T, T .
(c): code number rescaled 0.35
0.35/.4 = 0.875 (0.875 − 0.4)/.5 = 0.95
in interval
[0, 0.4) [0.4, 0.9) [0.9, 1)
decoded symbol
(a): MH = 57H(0.8) + 72H(0.5) ≈ 0.801.
(e): φ(125) = φ(53) = 53 − 52 = 100, so by Euler’s Theorem,
(i) True: a|aa|b|aaa|aab|ba
(ii) True: The binary entropy is approximately 1.46 and by Shannon’s Theorem, we can get arbi-
32015 ≡(3100)20×315 ≡120×(35)3 ≡2433 ≡(−7)3 ≡−343≡32
trarily close to this.
(iii) False: a = 37 and b = 61, so 2a − b = 13.
(iv) True: The two shortest codeword lengths are 1 and 3.
(v) True: 35 ≡ 15 (mod 19) and gcd(5, 18) = 1.
7. (i)Here,wehavethatα3=α2+1:
α4 =α2+α+1 α5 =α+1
α2 α5 α3 R1=α−2R1 1 α3 αR2=R2−R1 1 −−−−−−−→ −−−−−−−→
α 1 α3 α
α4 α6 1 R2=α3R2 1 α2 α3 R1=R1−α3R2 1 0 α+1
01 α4 sox=α+1=α5 andy=α4 =α2+α+1.
(iii) {α3, α6, α12 = α5, α10 = α3, . . .} = {α3, α5, α6}, so the minimal polynomial of α3 is
(x−α3)(x−α5)(x−α6)=x3 −(α3 +α5 +α6)x2 +(α3α5 +α3α6 +α5α6)x−α3α5α6 =x3 +(α2 +1+α+1+α2 +α)x2 +(α+α2 +α2 +α+1)x+1
= x3 + x + 1 .
α3 0 α2+α3
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com