Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2017 S2 TEST 2 VERSION A • Time Allowed: 45 minutes
1. Using the LZ78 algorithm a message is encoded as (0, b)(0, a)(2, a)(3, b)(3, 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) aaa (b) aab (c) aba (d) baa (e) bab 0.7 0.4
2. A 2-symbol Markov source has transition matrix M = 0.3 0.6 and equilibrium 1 3
distribution p = 4 1 . The (binary) Markov entropy HM is approximately (a) 0.811 (b) 0.904 (c) 0.926 (d) 0.949 (e) 0.961
3. Let H(x) = −xlog2x−(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.1 in bits with 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.36 (d) 0.40 (e) 0.43
4. Use Euler’s Theorem or otherwise to calculate 52272 (mod 3411).
The answer is
(a) 1 (b) 5 (c) 25 (d) 125 (e) 625
5. Use Fermat factorisation to factor n = 1113 as a product n = ab where 2 ≤ b < a. Then a − b equals
(a) 21 (b) 32 (c) 42 (d) 53 (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 bb• is encoded by 0.55.
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) For a source S = {a,b} with probabilities P(a) = 34 and P(b) = 41, the second shortest codewords in the binary Shannon-Fano code for the fourth extension S4 have length 7.
iv) There are 60 primitive elements in the field GF(125).
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. [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) Simplify γ4 + α, 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
2017 S2 TEST 2 VERSION B • Time Allowed: 45 minutes
1. If arithmetic coding with source symbols a, b and stop symbol • with probabilities 0.5, 0.4 and 0.1 is used, then what is the message ab• encoded 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) 0.02 (b) 0.21 (c) 0.36 (d) 0.44 (e) None of these 0.7 0.4
2. A 2-symbol Markov source has transition matrix M = 0.3 0.6 and equilibrium 1 3
distribution p = 5 2 . The (binary) Markov entropy HM is approximately (a) 0.917 (b) 0.926 (c) 0.935 (d) 0.966 (e) 0.971
3. Let H(x) = −xlog2x−(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.5p + 0.1 in bits with H(B) = H(0.3 + 0.7p) in bits and p = P(a1). The channel capacity is achieved when p has the value approximately
(a) 0.11 (b) 0.16 (c) 0.27 (d) 0.38 (e) 0.41
4. Use Fermat factorisation to factor n = 1215 as a product n = ab where 2 ≤ b < a.
Then a − b equals
(a) 12 (b) 14 (c) 16 (d) 18 (e) 20
5. Using Euler’s Theorem or otherwise, calculate 566 (mod 99). The answer is
(a) 5 (b) 14 (c) 25 (d) 31 (e) 82
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) Using the LZ78 algorithm a message is encoded as (0, a)(0, b)(2, a)(2, b)(4, a).
The last dictionary entry after decoding is aba.
ii) For a 3-symbol source S = {s1,s2,s3} with probabilities p1 = 0.6, p2 = 0.3, p3 = 0.1, it is possible to find a ternary encoding of some extension Sn with average word length per original source symbol less than 0.82.
iii) n = 65 is a pseudo-prime to base 8.
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) Given that 5 is a primitive element of Z23, then 20 is also a primitive element.
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 α6. Show your working.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com