Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2016 S2 TEST 2 VERSION A • Time Allowed: 45 minutes
1. Using the LZ78 algorithm a message is encoded as (0, a)(0, b)(2, a)(3, b)(4, a). What is the last dictionary entry after decoding?
Copyright By PowCoder代写 加微信 powcoder
(a) abab (b) abba (c) baab (d) aabb (e) baba
2. A Markov source S = {s1,s2,s3} has transition matrix M. The Huffman code for the equilibrium distribution is HuffE = [1, 00, 01] (so c1 = 1, c2 = 00 and c3 = 01.) Huffman codes for the columns of M are given by
Huff1 = [00, 1, 01], Huff2 = [0, 10, 11] and Huff3 = [11, 10, 0].
The string 001101100 decodes under the Markov Huffman encoding as
(a) s2s1s1s3s1s1 (b) s2s3s3s1s1 (c) s3s3s1s3s2s2s2 (d) s2s2s1s2s3 (e) none of these
3. Consider a binary channel with source symbols {a1, a2} and output symbols {b1, b2} such that P(a1) = 52, P(b1 | a1) = 58 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)52H(83)+35H(57) (b)27H(25)+58H(35) (c)58H(25)+27H(35) (d)53H(58)+25H(27) (e)72H(53)+58H(52)
4. Using Euler’s Theorem or otherwise, calculate 51155 (mod 2016).
The answer is
(a) 1 (b) 5 (c) 25 (d) 125 (e) 625
5. For which of the following numbers a is n = 121 a strong pseudo-prime to base a?
(a) 2 (b) 3 (c) 5 (d) 7 (e) None of these
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.
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.6.
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 ternary encoding of some extension Sn with average word length per original source symbol less than 1.
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) = 13 and P(b) = 32, the second longest codewords in the binary Shannon-Fano code for the fifth extension S5 have length 7.
v) There are 100 primitive elements in the field GF(125).
7. [5marks]LetF=Z3(α)whereαisarootofthepolynomialx2+2x+2∈Z3[x].
(i) Express all nonzero elements of F as powers of α and as linear combinations over Z3 of 1 and α.
(ii) Solve the set of linear equations
α3 α4 x α2 αα6 y=1
(iii) Find the minimal polynomial of α5. Show your working.
Name: ...................... Student ID: ................
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2016 S2 TEST 2 VERSION B • Time Allowed: 45 minutes
1. Using the LZ78 algorithm a message is encoded as (0, a)(0, b)(2, a)(2, b)(4, b). What is the last dictionary entry after decoding?
(a) aba (b) abb (c) bab (d) bba (e) bbb
2. A Markov source S = {s1,s2,s3} has transition matrix M. The Huffman code for the equilibrium distribution is HuffE = [1, 00, 01] (so c1 = 1, c2 = 00 and c3 = 01.) Huffman codes for the columns of M are given by
Huff1 = [00, 1, 01], Huff2 = [0, 10, 11] and Huff3 = [11, 10, 0].
Given the string of source symbols s1s2s1s3s1, the Markov Huffman encoding is (a) 0100110 (b) 111011011 (c) 1001011 (d) 1100111 (e) None of these
3. Consider a binary channel with source symbols {a1, a2} and output symbols {b1, b2} such that P(a1) = 41, P(b1 | a1) = 38 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(41)+38H(34) (b)34H(38)+14H(27) (c)14H(38)+34H(57) (d)83H(14)+27H(34) (e)72H(43)+38H(41)
4. Using Euler’s Theorem or otherwise, calculate 22016 (mod 123). The answer is
(a) 4 (b) 9 (c) 25 (d) 36 (e) 100
5. For which of the following numbers a is n = 25 a strong pseudo-prime to base a?
(a) 2 (b) 3 (c) 5 (d) 7 (e) None of these
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.
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.4), [0.4, 0.8) and [0.8, 1) is used, then the message ba• is encoded by 0.55.
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 ternary encoding of some extension Sn with average word length per original source symbol less than 0.9.
iii) When using Fermat factorisation to factor n = 2257 as a product n = ab where 2 ≤ a < b, the linear combination 2a − b equals 13.
iv) A source S = {s1, s2} has probabilities P (s1) = 41 , P (s2) = 43 . The second shortest codeword length in the binary Shannon-Fano code for the fourth ex- tension S4 is 3.
v) Given that 5 is a primitive element of Z17, then 6 is also a primitive element.
7. [5marks]LetF=Z3(α)whereαisarootofthepolynomialx2+x+2∈Z3[x].
(i) Express all nonzero elements of F as powers of α and as linear combinations over Z3 of 1 and α.
(ii) Solve the set of linear equations
α3 α4 x α2 α4 α6 y = α5
(iii) Find the minimal polynomial of α2. Show your working.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com