Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2015 S2 TEST 1 VERSION A • Time Allowed: 45 minutes
1. There may be an error in the check digit in the ISBN number 0-19-861133-X. The correct check digit is
Copyright By PowCoder代写 加微信 powcoder
(a) 1 (b) 4 (c) 7 (d) X (e) None of these
2. Consider a binary channel with bit-error probability p where errors in different positions are independent. Suppose that a codeword x is sent from the binary repetition code with codewords of length 6. Define
w = (1−p)6 x = 6p(1−p)5 y = 15p2(1−p)4 z = 20p3(1−p)3
The probability that one or more errors are correctly corrected using a minimum
distance decoding strategy is
(a) x (b) x+y (c) x+y+z (d) w+x+y (e) w+x+y+z
3. Let C be the binary linear code with generator matrix
0 1 1 0 1 0 0 0 G=0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0
00010001 How many codewords are there in C?
(a) 4 (b) 16 (c) 64 (d) 256 (e) 1024
4. For the code C of Question 4, assume that the first four bits are check bits.
The codeword that encodes m = 1011 is then
(a) 11001011 (b) 10011011 (c) 11101011 (d) 11011011 (e) 10101011
For multiple choice questions, circle the correct answer; each multiple choice question is worth 1 mark.
For written answer questions, use extra paper.
Staple all papers together when finished.
5. Let C be the code of all vectors x = x1x2x3x4 ∈ Z45 satisfying the check equations x1 + x3 + x4 ≡0(mod5)
2×2 +3×3 +2×4 ≡0 (mod5) Which, if any, of the following is a valid code word?
(a) 1212 (b) 1221 (c) 3434 (d) 3443 (e) None of these
6. Consider a compression code with codewords c1 = 1, c2 = 10, 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 =0 (b) c4 =011 (c) c4 =000 (d) c4 =1010 (e) Noneofthese
7. The minimum radix that would be needed to create a UD-code for the source S = {s1,s2,…,s9}
with codeword lengths 1, 1, 1, 2, 2, 2, 2, 3, 4, respectively, is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
8. Consider the standard binary I-code with codeword lengths 2, 2, 3, 3, 4, 4. The codeword c6 corresponding to symbol s6 is given by
(a) 0011 (b) 1111 (c) 1100 (d) 1110 (e) 1101
9. Let S = {s1, s2} be a source with probabilities p1 = 75 , p2 = 27 . The average length
of a radix 3 Huffman code for the second extension S(2) of this source is (a) 10 (b) 6 (c) 9 (d) 12 (e) 73
10. 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). The Huffman codes for the columns of M are given by
Huff1 =(01,00,1) Huff2 =(10,0,11) Huff3 =(11,0,10) The Markov Huffman encoding of the string of source symbols s2s1s3s2s3 is
(a) 00101011 (b) 000110010 (c) 00101101 (d) 00110011 (e) 00100111 11. [5 marks] Let C be the binary linear code with check matrix
1 0 0 0 1 H=0 1 0 1 0.
(i) Find a generator matrix G for the code C. (ii) Write down all the codewords in C.
(iii) Find Hamming weights of each codeword in C.
(iv) Find the Hamming distances between each pair of distinct codewords in C.
(v) What are the error correcting and error detecting capabilities of C?
7 7 7 7 49
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2015 S2 TEST 1 VERSION B • Time Allowed: 45 minutes
1. There may be an error in the check digit in the ISBN number 0-245-58345-9. The correct check digit is
(a) 0 (b) 3 (c) 6 (d) 9 (e) None of these
2. Let C be the code of all vectors x = x1x2x3x4 ∈ Z45 satisfying the check equations
x1 + x2 +x3 ≡0(mod5) x1 +3×2 +2×4 ≡0(mod5)
Which, if any, of the following is a valid code word?
(a) 1122 (b) 2121 (c) 4343 (d) 3344 (e) None of these
3. Consider a binary channel with bit-error probability p where errors in different po- sitions are independent. Suppose that a codeword x is sent from a binary repetition code with codewords of length 4. The probability that undetected error(s) occur is
(a) 4p3(1 − p) (b) 6p2(1 − p)2 (c) p4 (d) 4p3(1 − p) + p4 (e) 0
4. Let C be the binary linear code with generator matrix
0 1 0 1 1 0 0 G=1 0 0 1 0 1 0
1011001 How many codewords are there in C?
(a) 8 (b) 16 (c) 32 (d) 64 (e) 128
5. For the code C of Question 4, assume that the first four bits are check bits.
The codeword that encodes m = 011 is then
(a) 0101011 (b) 0010011 (c) 0110011 (d) 1100011 (e) 0100011
For multiple choice questions, circle the correct answer; each multiple choice question is worth 1 mark.
For written answer questions, use extra paper.
Staple all papers together when finished.
6. Consider a code with codewords c1 = 1, c2 = 01, c3 = 001, c4 =?
where c4 is to be chosen from the list of four possibilities below.
Which choice, if any, of c4 makes the resulting code not uniquely decodable?
(a)c4 =0001 (b)c4 =000 (c)c4 =00 (d)c4 =0000 (e)Noneofthese
7. The minimum radix that would be needed to create a UD-code for the source S = {s1,s2,s3,s4,…,s10}
with codeword lengths 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, respectively is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
8. Consider the standard binary I-code with codeword lengths 1, 3, 3, 4, 4, 4. The codeword c6 corresponding to symbol s6 is given by
(a) 0011 (b) 1110 (c) 1100 (d) 1101 (e) 1111
9. Let S = {s1, s2} be a source with probabilities p1 = 74 , p2 = 37 . The average length
of a radix 3 Huffman code for the second extension S(2) of this source is (a) 82 (b) 9 (c) 6 (d) 9 (e) 10
10. 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). The Huffman codes for the columns of M are given by
Huff1 = (01, 00, 1) Huff2 = (10, 0, 11) Huff3 = (11, 0, 10).
The Markov Huffman encoding of the string of source symbols s3s2s1s2s3 is
(a) 010100001 (b) 010100011 (c) 10001010 (d) 01001011 (e) 01010001
11. [5 marks] Let C be the binary linear code with parity check matrix
1 0 0 1 1 H=0 1 0 0 1
(i) Find a generator matrix G for the code C. (ii) Write down all the codewords in C.
(iii) Find Hamming weights of each codeword in C.
(iv) Find the Hamming distances between each pair of distinct codewords in C.
(v) What are the error correcting and error detecting capabilities of C?
49 14 7 7 7
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com