Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2015 S2 TEST 2 VERSION A • Time Allowed: 45 minutes
1. If arithmetic coding with source symbols a, b and the stop symbol • corresponding to the intervals [0,0.4), [0.4,0.9) and [0.9,1) is used, then the message bba• could encode as
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) 0.60 (b) 0.64 (c) 0.69 (d) 0.74 (e) 0.80 0.5 0.7
2. A 2-symbol Markov source has transition matrix M = 0.5 0.3 and equilibrium 1 7
distribution p = 12 5 . The (binary) Markov entropy HM is approximately (a) 0.931 (b) 0.941 (c) 0.951 (d) 0.967 (e) 0.980
3. Consider a binary channel with source symbols {a1, a2} and output symbols {b1, b2} such that P(a1) = 41, P(b1 | a1) = 47 and P(b2 | a2) = 38. Recall the function
H(x) = −x log2 x − (1 − x) log2(1 − x)
and note that H(x) = H(1 − x). The noise entropy H(B | A) can be written as
(a)41H(74)+34H(58) (b)38H(14)+47H(34) (c)47H(14)+38H(34) (d)43H(47)+14H(38) (e)83H(43)+47H(41)
4. Using Euler’s Theorem or otherwise, calculate 22015 (mod 125).
The answer is
(a) 2 (b) 6 (c) 9 (d) 18 (e) 36
5. For which of the following numbers a is n = 28 a pseudoprime to base a?
(a) 2 (b) 3 (c) 7 (d) 9 (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) The LZ78 algorithm encodes the message aaaabaaaaabaaaa as
(0, a)(1, a)(1, b)(2, a)(2, b)(4, a) .
ii) For a 3-symbol source S = {s1,s2,s3} with probabilities p1 = 4/9, p2 = 2/9, p3 = 1/3 it is possible to find a binary encoding of some extension Sn with average word length per original source symbol less than 1.5.
iii) When using Fermat factorisation to factor n = 1891 as a product n = ab where 2 ≤ a < b, the linear combination 2a − b equals 1.
iv) A source S = {s1, s2} has probabilities P (s1) = 54 , P (s2) = 51 . The second longest codeword length in the binary Shannon-Fano code for the third exten- sion S3 is 5.
v) There are 16 primitive elements in the field GF(49).
7. [5marks]LetF=Z2(α)whereαisarootofthepolynomialx3+x+1∈Z2[x].
(i) Express all nonzero elements of F as powers of α and as linear combinations over Z2 of 1, α, and α2.
(ii) Solve the set of linear equations
α3 α5x α α2 α3 y = α6
(iii) Find the minimal polynomial of α5. Show your working.
Name: ...................... Student ID: ................
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2015 S2 TEST 2 VERSION B • Time Allowed: 45 minutes
1. If arithmetic coding with source symbols a, b and the stop symbol • corresponding to the intervals [0, 0.4), [0.4, 0.9) and [0.9, 1) is used, then the message 0.35 decodes as
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) aa• (b) aab• (c) ab• (d) ba• (e) baa• 0.8 0.5
2. A 2-symbol Markov source has transition matrix M = 0.2 0.5 and equilibrium 1 5
distribution p = 7 2 . The (binary) Markov entropy HM is approximately (a) 0.801 (b) 0.861 (c) 0.863 (d) 0.887 (e) 0.921
3. Consider a binary channel with source symbols {a1, a2} and output symbols {b1, b2} such that P(a1) = 56, P(b1 | a1) = 35 and P(b2 | a2) = 27. Recall the function
H(x) = −x log2 x − (1 − x) log2(1 − x)
and note that H(x) = H(1 − x). The noise entropy H(B | A) can be written as
(a)72H(65)+35H(16) (b)16H(35)+56H(27) (c)56H(35)+16H(57) (d)53H(56)+27H(16) (e)72H(61)+35H(65)
4. Using Euler’s Theorem or otherwise, calculate 32015 (mod 125). The answer is
(a) 1 (b) 3 (c) 5 (d) 25 (e) 32
5. For which of the following numbers a is n = 24 a pseudoprime to base a?
(a) 2 (b) 3 (c) 5 (d) 7 (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) The LZ78 algorithm encodes the message aaabaaaaabba as
(0, a)(1, a)(0, b)(2, a)(2, b)(3, a) .
ii) For a 3-symbol source S = {s1,s2,s3} with probabilities p1 = 1/2, p2 = 1/6, p3 = 1/3, it is possible to find a binary encoding of some extension Sn with average word length per original source symbol less than 1.5.
iii) When using Fermat factorisation to factor n = 2257 as a product n = ab where 2 ≤ a < b, the linear combination 2a − b equals 1.
iv) A source S = {s1, s2} has probabilities P (s1) = 51 , P (s2) = 54 . The second shortest codeword length in the binary Shannon-Fano code for the third ex- tension S3 is 3.
v) Given that 3 is a primitive element of Z19, then 15 is also a primitive element.
7. [5marks]LetF=Z2(α)whereαisarootofthepolynomialx3+x2+1∈Z2[x].
(i) Express all nonzero elements of F as powers of α and as linear combinations over Z2 of 1, α, and α2.
(ii) Solve the set of linear equations
α2 α5 x α3 α4 α6 y = 1
(iii) Find the minimal polynomial of α3. Show your working.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com