Name: . . . . . . . . . . . . . . . . . . . . . . Student ID: . . . . . . . . . . . . . . . .
UNSW School of Mathematics and Statistics
MATH3411 Information Codes and Ciphers
2018 S2 TEST 3 VERSION A
• Time Allowed: 45 minutes
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.
1. A 2 symbol Markov source has transition matrix M =
(
0.75 0.4
0.25 0.6
)
and equilibrium
distribution p =
1
13
(
8
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) = 45 , P (s2) = 15 . 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) =
3
7
, 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) 4
7
H(4
5
)+3
7
H(5
8
) (b) 4
7
H(1
5
) (c) 3
7
H(1
5
)+4
7
H(3
8
) (d) 3
7
H(5
8
) (e) H(1
5
)+H(3
8
)
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
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 1
2
mark for a correct
true/false answer, and if your true/false answer is correct, then you will get 1
2
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
α3 + α4
, giving your answer as a linear combination of 1 and α.
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
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.
1. A 2 symbol Markov source has transition matrix M =
(
0.7 0.2
0.3 0.8
)
and equilibrium
distribution p =
1
5
(
2
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) = 57 , P (s2) = 27 . 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
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 1
2
mark for a correct
true/false answer, and if your true/false answer is correct, then you will get 1
2
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 α5
α2 α7
)(
x
y
)
=
(
2
α3
)
in F.
(iii) Find the minimal polynomial of α5.
Show your working.