Name: ……………………… UNSW
MATH3411 Semester 2, 2011
• Time Allowed: 45 minutes
Student Id: ……………. Tutorial…………….
Copyright By PowCoder代写 加微信 powcoder
School of Mathematics and Statistics
Information Codes and Ciphers
TEST 1 VERSION A
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.
1. There may be an error in the check digit in the ISBN number 0-752-87712-8. The correct check digit is
(a) 0 (b) 4 (c) 7 (d) X (e) None of these
2. A message is sent using a 5-character 8-bit ASCII code, which encodes characters in blocks of four together with a 5th character which is used as a check character for even parity in rows and columns. (This is similar to the 9-character 8-bit and 8-character 8-bit ASCII codes studied in lectures.)
The message 11010100 01101111 01100100 01100101 10101010 is received. Assuming at most one error, which bit is wrong:
(a) 10th (b) 20th (c) 30th (d) 40th (e) no error
3. In the Hamming (7,4) code with the usual parity check matrix the codeword 0110110 decodes to:
(a) 1101 (b) 1011 (c) 1110 (d) 1111 (e) 1001
4. Let C be the code consisting of all vectors x = x1x2x3x4 ∈ Z54 satisfying the check equations
x1 +2×2 +3×3 +4×4 ≡ 0 (mod 5), 2×1 +3×2 +4×3 +x4 ≡ 0 (mod 5)
Assuming that x3 and x4 are the information bits, the codeword which encodes the message 21 is:
(a) 1221 (b) 1321 (c) 4421 (d) 2421 (e) 4121
5. Consider the standard binary I-code with codeword lengths l1 = 2, l2 = 3, l3 = 3,
l4 = 3, l5 = 3. The codeword c3 corresponding to symbol s3 is given by (a) 011 (b) 110 (c) 100 (d) 010 (e) 111
6. [10 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 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) A binary linear code with weight w = 7 can be used to correct all triple errors
in a codeword.
ii) There is a binary linear code C with |C| = 8 and codewords of length 8 that can correct 2 errors.
iii) Thebinarycodec1 =0,c2 =01,c3 =10,c4 =101isaUDcode.
iv) There is a ternary (radix 3) I-code with codewords of lengths 1, 2, 2, 2, 2, 3, 3.
7 2 7 3 10 5
v) TheMarkovmatrixM= 1 1 5 2 hasequilibriumvectorp=1 1 . 231 1
7. [10 marks] Consider the source S = {s1, s2, s3, s4, s5, s6, s7} with probabilities
p1 =3/10, p2 =1/4, p3 =3/20, p4 =1/10, p5 =1/10, p6 =1/20, p7 =1/20.
(i) Find the standard binary Huffman code for the source S. Show your working.
(ii) Calculate the average length L for this code. Show your working. (Leave your answer as a fraction.)
Name: ……………………… UNSW
MATH3411 Semester 2, 2011
• Time Allowed: 45 minutes
Student Id: ……………. Tutorial…………….
School of Mathematics and Statistics
Information Codes and Ciphers
TEST 1 VERSION B
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.
1. There may be an error in the check digit in the ISBN number 0-752-87721-8. The correct check digit is
(a) X (b) 3 (c) 5 (d) 6 (e) None of these
2. A message is sent using a 5-character 8-bit ASCII code, which encodes characters in blocks of four together with a 5th character which is used as a check character for even parity in rows and columns. (This is similar to the 9-character 8-bit and 8-character 8-bit ASCII codes studied in lectures.)
The message 11110110 01101111 01110100 01100101 10101000 is received. Assuming at most one error, which bit is wrong:
(a) 5th (b) 15th (c) 25th (d) 35th (e) no error
3. What is the maximum number of information bits k in a binary 2-error correcting
code C with codewords of length n = 7?
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5
4. In a binary linear code C the codeword 001010101100101 has minimum weight among non-zero codewords. The maximum number of errors that C can correct is
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5
5. The minimum radix that would be needed to create a UD-code for the source S = {s1,s2,s3,s4,…,s8}
with codeword lengths 1, 1, 1, 2, 2, 2, 2, 3, respectively is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
6. [10 marks] For each of the following, say whether the statement is true or false and give 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 C is the code consisting of all vectors x = x1x2x3x4 ∈ Z54 satisfying the
check equations
x1 +2×2 +3×3 +4×4 ≡ 0 (mod 5), 2×1 +3×2 +4×3 +x4 ≡ 0 (mod 5)
then 1234 is a valid code word in C.
ii) The Hamming (7,4) code with the usual parity check matrix contains the code-
word 0010110.
iii) Thebinarycodec1 =0,c2 =100,c3 =101,c4 =1101isaUD-code.
iv) In the standard binary I-code with codeword lengths l1 = 2, l2 = 3, l3 = 3, l4 = 3, l5 = 3, the codeword c5 corresponding to symbol s5 is 111.
6 1 1 1 v) TheMarkovmatrixM= 1 1 7 8 hasequilibriumvectorp=1 3 .
10 5 321 1
7. [10 marks] Consider the source S = {s1, s2, s3, s4, s5, s6, s7} with probabilities
p1 =3/10, p2 =1/5, p3 =3/20, p4 =3/20, p5 =1/10, p6 =1/20, p7 =1/20.
(i) Find the standard binary Huffman code for the source S. Show your working.
(ii) Calculate the average length L for this code. Show your working. (Leave your answer as a fraction.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com