Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2018 S2 TEST 2 VERSION A • Time Allowed: 45 minutes
1. Let C be the ternary linear code with parity check matrix
Copyright By PowCoder代写 加微信 powcoder
2 0 0 2 0 1 1 H=0 1 0 0 1 0 1
Here, the first three bits are check bits. The codeword that encodes m = 1221 is
(a) 1221011 (b) 2021221 (c) 1221221 (d) 1221000 (e) None of these
2. A message m′ has been encoded using the code C in Question 1 and has been
corrupted by a single error to give the received word y = 0021210. The message m′ is (a) 0020 (b) 0021 (c) 1010 (d) 1110 (e) None of these
3. Let C be the code of all vectors x = x1x2x3x4 ∈ Z43 satisfying the check equations
x1 +2×3 +2×4 ≡0(mod3)
x1 +x2 + +2×4 ≡0(mod3)
There are two information bits but you are not told in which positions they lie.
Which of the following codewords could possibly encode the message 10?
(a) 1001 (b) 1100 (c) 1201 (d) 0121 (e) None of these
4. Consider a compression code with codewords c1 = 0, c2 = 11, c3 = 101, c4 =? where c4 is to be chosen from the list of four possibilities below.
Which choice, if any, of c4 makes the resulting code uniquely decodable?
(a) c4 =1 (b) c4 =011 (c) c4 =000 (d) c4 =010 (e) Noneofthese
5. The minimum radix that would be needed to create a UD-code for the source S = {s1,s2,…,s7}
with codeword lengths 1, 1, 2, 2, 2, 2, 3, respectively, is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
For multiple choice questions, circle the correct answer; each question is worth 1 mark.
6. If arithmetic coding with source symbols a, b and stop symbol • with probabilities 0.4, 0.3 and 0.3 is used, then what is the message ba• encoded as?
(a) 0.25 (b) 0.3 (c) 0.5 (d) 0.55 (e) None of these 7. 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?
(a) a (b) aa (c) ba (d) aaa (e) None of these
8. Let S = {s1, s2, s3, s4} be a source with probabilities p1 = 0.4, p2 = 0.3, p3 = 0.2, p4 = 0.1. The average length of a radix 3 Huffman code for S is
(a) 1 (b) 1.3 (c) 1.6 (d) 1.9 (e) None of these
9. Let S be the source in Question 8. The average length per symbol of a radix 3
Huffman code for S(n) converges, as n → ∞, to approximately
(a) 1.06 (b) 1.16 (c) 1.43 (d) 1.85 (e) 2.12
10. Let S be the source in Question 8. Using the binary Shannon-Fano code for S, the message m = s1s4s2 is encoded as
(a) 00101001 (b) 00110001 (c) 010101001 (d) 0111010 (e) None of these
11. [5 marks]
A Markov source S has transition matrix and equilibrium probability distribution 0.7 0.2 0.1 6
17 M=0.20.60.4 and p=17.
0.1 0.2 0.5 4
(a) Find appropriate binary Huffman codes to encode S as a Markov source. (b) Determine the average codeword length LM for this encoding.
(c) Using these Huffman codes, encode the string s1s3s2s1.
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2018 S2 TEST 2 VERSION B • Time Allowed: 45 minutes
1. Let C be the ternary linear code with parity check matrix
2 0 0 2 0 1 1 H=0 1 0 0 1 0 1
Here, the last three bits are check bits. The codeword that encodes m = 1221 is
(a) 1221011 (b) 2021221 (c) 1221221 (d) 1221000 (e) None of these
2. A message m′ has been encoded using the code C in Question 1 and has been
corrupted by a single error to give the received word y = 1111111. The message m′ is (a) 1111 (b) 1121 (c) 1211 (d) 1101 (e) None of these
3. Let C be the code of all vectors x = x1x2x3x4 ∈ Z43 satisfying the check equations x1 +x3 +2×4 ≡0(mod3)
x1 + 2×2 + + x4 ≡ 0 (mod3)
There are two information bits but you are not told in which positions they lie.
Which of the following codewords could possibly encode the message 10?
(a) 1001 (b) 1100 (c) 0122 (d) 1201 (e) None of these
4. Consider a compression code with codewords c1 = 0, c2 = 11, c3 = 100, c4 =? where c4 is to be chosen from the list of four possibilities below.
Which choice, if any, of c4 makes the resulting code uniquely decodable?
(a) c4 =00 (b) c4 =011 (c) c4 =000 (d) c4 =101 (e) Noneofthese
5. The minimum radix that would be needed to create a UD-code for the source S = {s1,s2,…,s7}
with codeword lengths 1, 2, 2, 2, 2, 3, 4, respectively, is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
For multiple choice questions, circle the correct answer; each question is worth 1 mark.
6. If arithmetic coding with source symbols a, b and stop symbol • with probabilities 0.4, 0.4 and 0.2 is used, then what is the message ab• encoded as?
(a) 0.25 (b) 0.3 (c) 0.5 (d) 0.55 (e) None of these
7. Using the LZ78 algorithm a message is encoded as (0, b)(1, a)(2, a)(3, b)(3, a).
What is the last dictionary entry after decoding?
(a)a (b)aa (c)ba (d)baa (e)baaa
8. Let S = {s1, s2, s3, s4, s5} be a source with probabilities p1 = 0.4, p2 = 0.2, p3 = 0.2, p4 = 0.1, p5 = 0.1. The average length of a radix 4 Huffman code for S is
(a) 1.2 (b) 1.4 (c) 1.6 (d) 2.2 (e) None of these
9. Let S be the source in Question 8. The average length per symbol of a radix 4
Huffman code for S(n) converges, as n → ∞, to approximately
(a) 1.06 (b) 1.16 (c) 1.43 (d) 1.85 (e) 2.12
10. Let S be the source in Question 8. Using the binary Shannon-Fano code for S, the message m = s1s4s2 is encoded as
(a) 01100100 (b) 001001010 (c) 001000010 (d) 01100100 (e) None of these
11. [5 marks]
A Markov source S has transition matrix and equilibrium probability distribution 1 1 1
4 2 4 2 1 1
M= 3 3 2
1 1 1
(a) Find appropriate binary Huffman codes to encode S as a Markov source. (b) Determine the average codeword length LM for this encoding.
(c) Using these Huffman codes, encode the string s1s3s2s1.
10 and p=113.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com