Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2011 S2 TEST 2 VERSION A • Time Allowed: 45 minutes
1. Using the LZ78 algorithm a message is encoded as (0, a)(1, b)(2, a)(2, b). The mes- sage is
Copyright By PowCoder代写 加微信 powcoder
(a) aababbaba (b) abbbbabbb (c) abbaaaabb (d) aababaabb (e) aababbabb
2. 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.7p + 0.2 in bits with H(B) = H(0.1 + 0.4p) in bits and p = P(a1). The channel capacity is achieved when p has the value approximately
(a) 0.23 (b) 0.32 (c) 0.70 (d) 0.38 (e) 0.55
3. Let f(x) = x4 +2×2 +2 and g(x) = x2 +3x+2 be polynomials in Z5[x]. The
remainder when f(x) is divided by g(x) in Z5[x] is
(a) 2 (b) x2 + 2x + 4 (c) 3x (d) x + 1 (e) 4x + 4
4. Applying the Pollard-ρ method with x0 = 3 and xi = x2i−1 +1 (mod n) for i > 0 finds which factor of n = 1105 = 5 × 13 × 17 first?
(a) 5 (b) 13 (c) 17 (d) 65 (e) 85
5. Suppose that the linear congruential pseudorandom number generator xi+1≡3xi+5 (mod7)
is given the seed x0 = 3. Then x5 equals
(a) 0 (b) 1 (c) 2 (d) 3 (e) 4
For the multiple choice questions, circle the correct answer; each multiple choice question is worth 2 marks.
For the true/false and written answer questions, use extra paper.
Staple everything together at the end.
6. [10 marks] For each of the following, say whether the statement is true or false and giving a brief reason or showing your working. You will get one mark for a correct true/false answer, and if your true/false answer is correct then you will get one mark for a good reason.
Begin each answer with the word “true” or “false”.
i) If a source S has binary entropy 2.5, then a Huffman coding of the fourth
extension must have average length per original source symbol less than 2.8 .
ii) For a noisy binary channel the entropy of the output is always larger than the
entropy of the input.
iii) 52011 ≡ 12 (mod 13).
iv) There are 42 primitive elements in the field GF(49).
v) InthefieldZ2[x]/⟨x3+x+1⟩,ifαisarootofx3+x+1thenα6 =α2+1.
7. [10 marks] A source S has 5 symbols s1, s2, . . . , s5 with probabilities
1, 1, 1, 2, 1 3 4 5 15 12
respectively.
i) Find the entropy of S in bits.
ii) Find a ternary (radix 3) Shannon-Fano code for S and calculate its expected codeword length.
iii) A binary Shannon-Fano code is constructed for S3. (Do not try to find it.) Find the lengths of the two shortest codewords in this code.
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2011 S2 TEST 2 VERSION B • Time Allowed: 45 minutes
1. Using the LZ78 algorithm a message is encoded as (0, a)(1, b)(0, c)(2, a)(4, c)(5, b). What is the last dictionary entry after decoding?
(a) abacb (b) abcab (c) abac (d) acbcb (e) abbcb
2. 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.8p+0.3 in bits with H(B) = H(0.1+0.5p) in bits where p = P(a1). The channel capacity is achieved when p has the value approximately
(a) 0.25 (b) 0.53 (c) 0.30 (d) 0.36 (e) 0.62
3. Let f(x) = x4 +2×3 +x and g(x) = x2 +x+2 be polynomials in Z5[x]. The
remainder when f(x) is divided by g(x) in Z5[x] is
(a) 2x (b) x + 3 (c) x2 + x + 2 (d) 2x + 1 (e) 2x + 4
4. Applying the Pollard-ρ method with x0 = 3 and xi = x2i−1 +1 (mod n) for i > 0 finds which factor of n = 1001 = 7 × 11 × 13 first?
(a) 7 (b) 11 (c) 13 (d) 91 (e) 143
5. Suppose that the linear congruential pseudorandom number generator xi+1≡3xi+4 (mod7)
is given the seed x0 = 1. Given that the period of the generator is 6, which of these members of Z7 is not generated:
(a) 0 (b) 2 (c) 3 (d) 4 (e) 5
For the multiple choice questions, circle the correct answer; each multiple choice question is worth 2 marks.
For the true/false and written answer questions, use extra paper.
Staple everything together at the end.
6. [10 marks] For each of the following, say whether the statement is true or false and giving a brief reason or showing your working. You will get one mark for a correct true/false answer, and if your true/false answer is correct then you will get one mark for a good reason.
Begin each answer with the word “true” or “false”.
i) If a source S has binary entropy 2.4, then the Shannon-Fano coding of the fifth
extension must have average length per original source symbol less than 2.7 .
ii) For a noisy channel the entropy of the input can be larger than the entropy of
the output.
iii) 22011 ≡ 11 (mod 13).
iv) There are 32 primitive elements in the field GF(121).
v) InthefieldZ2[x]/⟨x3+x2+1⟩,ifαisarootofx3+x2+1thenα6 =α2+1.
7. [10 marks] A source S has 5 symbols s1, s2, . . . , s5 with probabilities
2, 1, 1, 1, 1 5 4 6 10 12
respectively.
i) Find the entropy of S in bits.
ii) Find a ternary (radix 3) Shannon-Fano code for S and calculate its expected codeword length.
iii) A binary Shannon-Fano code is constructed for S2. (Do not try to find it.) Find the lengths of the two longest codewords in this code.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com