Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2013 S2 TEST 2 VERSION A • Time Allowed: 45 minutes
1. Using the LZ78 algorithm a message is encoded as (0, a)(1, a)(1, b)(2, a)(3, b)(4, a). What is the last dictionary entry after decoding?
Copyright By PowCoder代写 加微信 powcoder
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.
(a) aaaa (b) aaab (c) abba (d) baaa (e) bbba 0.8 0.4
2. A 2-symbol Markov source has transition matrix M = 0.2 0.6 and equilibrium 1 2
distribution p = 3 1 . The (binary) Markov entropy HM is approximately (a) 0.791 (b) 0.918 (c) 0.846 (d) 0.888 (e) 0.805
3. Let H(x) = −xlog2 x − (1 − x)log2(1 − x), so that H′(x) = log2(x−1 − 1). An asymmetric binary channel with input A = {a1,a2} and output B = {b1,b2} has noise entropy H(B | A) = 0.4p + 0.6 in bits, output entropy H(B) = H(0.3 + 0.5p) in bits and p = P(a1). The channel capacity is achieved when p has the value approximately
(a) 0.13 (b) 0.26 (c) 0.31 (d) 0.36 (e) 0.43
4. Using Euler’s Theorem or otherwise, calculate 21203 (mod 2013)
(NB: 2013 is not prime). The answer is
(a) 1 (b) 2 (c) 4 (d) 8 (e) 16
5. For which of the following numbers a is n = 14 a pseudoprime to base a?
(a) 2 (b) 3 (c) 4 (d) 5 (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 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) If arithmetic coding with source symbols a, b and stop symbol • corresponding to the intervals [0,0.3), [0.3,0.7) and [0.7,1) is used, then the message 0.55 decodes as bb•.
ii) For a 2-symbol source S = {s1,s2} with probabilities p1 = 1/5, p2 = 4/5 it is possible to find a binary encoding of some extension Sn with average word length per original source symbol less than 0.8.
iii) When using Fermat factorisation to factor n = 1333 as a product n = ab where 2 ≤ a < b, the sum a + b equals 71.
iv) For a source S = {a,b} with probabilities P(a) = 15 and P(b) = 54, the second longest codewords in the binary Shannon-Fano code for the third extension S3 have length 5.
v) The number 5 is one of the pseudo-random numbers generated by the linear congruential xi+1 ≡ 4xi + 2 (mod 11), seeded with x0 = 1.
7. [5 marks] Let F = Z3(α) where α is a root of the polynomial x2 + 1 ∈ Z3[x].
(i) Express all nonzero elements of F as a power of γ = α + 1 and as a linear
combination over Z3 of 1 and α.
(ii) Find the primitive elements of F.
(iii) Find the inverse of α in F.
(iv) Simplify γ7 + α, giving your answer as a linear combination of 1 and α.
γ4 +γ Show your working.
Name: ...................... Student ID: ................
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2013 S2 TEST 2 VERSION B • Time Allowed: 45 minutes
1. Using the LZ78 algorithm a message is encoded as (0, a)(1, a)(1, b)(2, a)(3, b)(5, a). What is the last dictionary entry after decoding?
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.
(a) aaaa (b) aaab (c) abba (d) baaa (e) bbba 0.2 0.4
2. A 2-symbol Markov source has transition matrix M = 0.8 0.6 and equilibrium 1 1
distribution p = 3 2 . The (binary) Markov entropy HM is approximately (a) 0.791 (b) 0.918 (c) 0.846 (d) 0.888 (e) 0.805
3. Let H(x) = −xlog2 x − (1 − x)log2(1 − x), so that H′(x) = log2(x−1 − 1). An asymmetric binary channel with input A = {a1,a2} and output B = {b1,b2} has noise entropy H(B | A) = 0.4p + 0.7 in bits, output entropy H(B) = H(0.2 + 0.7p) in bits and p = P(a1). The channel capacity is achieved when p has the value approximately
(a) 0.29 (b) 0.33 (c) 0.37 (d) 0.40 (e) 0.43
4. Using Euler’s Theorem or otherwise, calculate 51203 (mod 2013).
(NB: 2013 is not prime). The answer is
(a) 1 (b) 5 (c) 25 (d) 125 (d) 625
5. For which of the following numbers a is n = 15 a pseudoprime to base a?
(a) 2 (b) 3 (c) 4 (d) 5 (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 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) If arithmetic coding with source symbols a, b and stop symbol • corresponding to the intervals [0,0.3), [0.3,0.7) and [0.7,1) is used, then the message 0.55 decodes as b•.
ii) For a 2-symbol source S = {s1,s2} with probabilities p1 = 1/4, p2 = 3/4 it is possible to find a binary encoding of some extension Sn with average word length per original source symbol less than 0.8.
iii) When using Fermat factorisation to factor n = 1333 as a product n = ab where 2 ≤ a < b, the sum a + b equals 74.
iv) For a source S = {a,b} with probabilities P(a) = 15 and P(b) = 54, the second shortest codewords in the binary Shannon-Fano code for the third extension S3 have length 3.
v) The number 7 is one of the pseudo-random numbers generated by the linear congruential xi+1 ≡ 4xi + 2 (mod 11), seeded with x0 = 1.
7. [5marks]LetF=Z3(α)whereαisarootofthepolynomialx2+x+2∈Z3[x].
(i) Express all nonzero elements of F as a power of α and as a linear combination
over Z3 of 1 and α.
(ii) Find the primitive elements of F.
(iii) Findtheinverseof2α+1inF.
(iv) Simplify α2 + 1 , giving your answer as a linear combination of 1 and α.
α3 + α4 Show your working.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com