Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2018 S2 TEST 3 VERSION A • Time Allowed: 45 minutes
0.75 0.4
Copyright By PowCoder代写 加微信 powcoder
1. A 2 symbol Markov source has transition matrix M = 0.25 0.6 and equilibrium
distribution p = 13 5 . The (binary) Markov entropy HM is approximately
(a) 0.716 (b) 0.961 (c) 0.891 (d) 0.873 (e) 0.910
2. A source S = {s1, s2} has probabilities P (s1) = 54 , P (s2) = 51 . The second least likely codewords in the binary Shannon-Fano code for the third extension S3 have length
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
3. Consider a binary channel with source symbols {a1, a2} and output symbols {b1, b2}
such that P(a1) = 37, P(b1 | a1) = 45 and P(b2 | a2) = 58. Recall the function H(x) = −x log2 x − (1 − x) log2(1 − x) .
The noise entropy H(B | A) can be written as
(a) 47H(45)+73H(58) (b) 74H(15) (c) 73H(15)+47H(83) (d) 37H(58) (e) H(15)+H(38)
4. Use Euler’s Theorem or otherwise to calculate 101001 (mod 1001). The answer is
(a) 1 (b) 10 (c) 100 (d) 101 (e) 901
5. For which of the following numbers a is n = 28 a pseudo-prime to base a?
(a) 3 (b) 9 (c) 12 (d) 18 (e) none of these
For the multiple choice questions, circle the correct answer; each multiple choice question is worth 1 mark.
For the true/false and written answer questions, use extra paper. Staple everything together at the end.
6. [5 marks] For each of the following, say whether the statement is true or false, giving a brief reason or showing your working. You will get 12 mark for a correct true/false answer, and if your true/false answer is correct, then you will get 12 mark for a good reason.
Begin each answer with the word “True” or “False”.
i) There are 11 units in Z22.
ii) Z2[x]/⟨x3 + x + 1⟩ is a field.
iii) When applied to n = 17 with a = 3, Lucas’ test indicates that n is prime.
iv) Given that 5 is a primitive element of Z18, 11 is also a primitive element of Z18.
v) There are 60 primitive elements in U125.
7. [5 marks] Let F = Z3[x]/⟨x2 + x + 2⟩.
(i) Express each nonzero element of F as a power of a primitive element α and as a linear combination over Z3 of 1 and α.
(ii) Simplify α2 + 1 , giving your answer as a linear combination of 1 and α. α3 + α4
Show your working.
(iii) Find the minimal polynomial of α2.
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2018 S2 TEST 3 VERSION B • Time Allowed: 45 minutes
1. A 2 symbol Markov source has transition matrix M = 0.3 0.8 and equilibrium
distribution p = 5 3 . The (binary) Markov entropy HM is approximately
(a) 0.767 (b) 0.971 (c) 0.801 (d) 0.818 (e) 0.786
2. If a channel has input entropy H(A) = 0.93, output entropy H(B) = 0.76 and
mutual information I(A, B) = 0.56, then the joint entropy H(A, B) is approximately (a) 1.69 (b) 0.20 (c) 1.13 (d) 0.73 (e) 0.37
3. Use Euler’s Theorem or otherwise to calculate 52018 (mod 2018). (Note that 1009 is prime.) The answer is
(a) 1 (b) 5 (c) 25 (d) 125 (e) 625
4. Which of the following pairs consists of two primitive elements in Z17?
You may use the fact that 5 is a primitive element of Z17.
(a) 2, 13 (b) 4, 11 (c) 6, 9 (d) 10, 6 (e) 13, 5
5. A source S = {s1, s2} has probabilities P (s1) = 75 , P (s2) = 72 . The second most likely codewords in the ternary Shannon-Fano code for the third extension S3 have length
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
For the multiple choice questions, circle the correct answer; each multiple choice question is worth 1 mark.
For the true/false and written answer questions, use extra paper. Staple everything together at the end.
6. [5 marks] For each of the following, say whether the statement is true or false, giving a brief reason or showing your working. You will get 12 mark for a correct true/false answer, and if your true/false answer is correct, then you will get 12 mark for a good reason.
Begin each answer with the word “True” or “False”.
i) There are 24 units in Z48.
ii) The polynomial m(x) = x3 + x2 + 1 ∈ Z2[x] is irreducible.
iii) There are 8 primitive elements in U31.
iv) n = 65 is a pseudo-prime to base 5.
v) When applied to n = 61 with a = 3, Lucas’ test indicates that n is prime.
7. [5 marks] Let F = Z3[x]/⟨x2 + 2x + 2⟩.
(i) Express all nonzero elements of F as a power of a primitive element α and as a linear combination over Z3 of 1, α.
(ii) Solve the set of linear equations
α4 α5x 2
α2 α7 y = α3
(iii) Find the minimal polynomial of α5. Show your working.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com