Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2014 S2 TEST 2 VERSION A • Time Allowed: 45 minutes
1. If arithmetic coding with source symbols s1, s2 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.69 decodes 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) s2s1 • (b) s1s1 • (c) s2s1s1 • (d) s1s1s2 • (e) s2s2s1• 0.75 0.4
2. A 2-symbol Markov source has transition matrix M = 0.25 0.6 and equilibrium 1 8
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
3. Consider a binary channel with source symbols {a1, a2} and output symbols {b1, b2} such that P(a1) = 73, P(b1 | a1) = 45 and P(b2 | a2) = 58. 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) 74H(45)+73H(58) (b) 74H(15) (c) 73H(15)+47H(83) (d) 37H(58) (e) H(15)+H(38)
4. Using Euler’s Theorem or otherwise, calculate 3940 (mod 2014).
(NB: 1007 is not prime.) The answer is
(a) 1 (b) 3 (c) 9 (d) 27 (e) 81
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) The LZ78 algorithm decodes the message (0, a)(1, a)(1, b)(2, a)(2, b)(4, a) as
aaaabaaaaabaaaa.
ii) For a 3-symbol source S = {s1,s2,s3} with probabilities p1 = 4/7, p2 = 2/7, p3 = 1/7, it is possible to find a binary encoding of some extension Sn with average word length per original source symbol less than 1.28.
iii) When using Fermat factorisation to factor n = 6283 as a product n = ab where 2 ≤ a < b, the linear combination a + 2b equals 271.
iv) For symbols s1, s2, s3, s4 with probabilities 0.50, 0.25, 0.13, 0.12 respectively, the binary Shannon-Fano encoding 0101110 encodes the string of symbols s1s2s4.
v) There are 6 primitive elements in the field GF(27).
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) Findthevalueofk∈{1,...,7}forwhich(α+1)k =α2 +α+1.
(iii) Find the minimal polynomial of α3. Show your working.
Name: ...................... Student ID: ................
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2014 S2 TEST 2 VERSION B • Time Allowed: 45 minutes
1. If arithmetic coding with source symbols s1, s2 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) s1s2 • (b) s2s1 • (c) s2s2s1 • (d) s1s1s2 • (e) s2s1s1• 0.7 0.2
2. A 2-symbol Markov source has transition matrix M = 0.3 0.8 and equilibrium 1 2
distribution p = 5 3 . The (binary) Markov entropy HM is approximately (a) 0.712 (b) 0.786 (c) 0.802 (d) 0.818 (e) 0.971
3. Consider a binary channel with source symbols {a1, a2} and output symbols {b1, b2} such that P(a1) = 15, P(b1 | a1) = 45 and P(b2 | a2) = 58. 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) 51H(15)+54H(38) (b) 54H(15) (c) 51H(58) (d) 45H(45)+15H(58) (e) H(45)+H(58)
4. Using Euler’s Theorem or otherwise, calculate 22014 (mod 123). The answer is
(a) 1 (b) 2 (c) 4 (d) 25 (e) 107
5. Which of the following pairs consists of two primitive elements in Z17?
You may use the fact that 3 is a primitive element of Z17.
(a) 5, 9 (b) 5, 10 (c) 9, 10 (d) 9, 12 (e) 12, 13
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 decodes the message (0, a)(1, a)(0, b)(2, a)(2, b)(3, a) as
aaabaaaaabba.
ii) For a 3-symbol source S = {s1, s2, s3} with probabilities p1 = 5/11, p2 = 4/11, p3 = 2/11 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 = 6283 as a product n = ab where 2 ≤ a < b, the linear combination 2a + b equals 215.
iv) For symbols s1, s2, s3, s4 with probabilities 0.5, 0.2, 0.2, 0.1 respectively, the binary Shannon-Fano encoding 01001100 encodes the string of symbols s1s2s4.
v) The number 3 is one of the pseudo-random numbers generated by the linear congruential xi+1 ≡ 2xi + 5 (mod 17), seeded with x0 = 1.
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) Simplify α2 + 1 , giving your answer as a linear combination of 1, α and α2.
α3 + α4 Show your working.
(iii) Find the minimal polynomial of α5. Show your working.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com