Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2013 S2 TEST 1 VERSION A • Time Allowed: 45 minutes
1. You are given the following 7-bit ASCII codewords:
Copyright By PowCoder代写 加微信 powcoder
L 1001100 o 1101111 v 1110110 e 1100101
$ 0100100 0 0110000 h 1101000 d 1011011
Define a 5-character 8-bit ASCII burst code by encoding characters in blocks of four together with a 5th character which is used as a check codeword. (This is similar to the 9-character 8-bit and 8-character 8-bit ASCII code studied in lectures.)
The message “Love” together with its check character is given by:
(a) Love$ (b) Love0 (c) Loveh (d) Lovet (e) Loved For the next 3 questions, let C1 be a binary linear code with check matrix
1 1 0 0 1 0 1 H=0 1 1 0 1 0 0
Assume that the check bits correspond to columns 1, 2, and 4.
2. The codeword encoding the message 1010 in code C1 is
(a) 1101110 (b) 1110010 (c) 1101100 (d) 0111110 (e) 0110100
3. A generator matrix G corresponding to the check matrix H for the code C1 has size (a) 4×7 (b) 3×7 (c) 4×3 (d) 3×4 (e) none of these.
4. Supposing that the word 1110011 is received using code C1, what is the minimum number of errors that could have occurred?
(a) 0 (b) 1 (c) 2 (d) 3 (e) 4
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. Consider a binary 2-error correcting code C with k = 3 information bits and m = 5 check bits. What is the largest possible number of codewords in C?
(a) 3 (b) 4 (c) 5 (d) 6 (e) 7
6. A binary code C has minimum distance d = 7. Suppose this is used to correct a errors and detect b errors. Which of the following pairs (a, b) does not give a valid strategy for decoding C?
(a) (0,6) (b) (1,5) (c) (2,4) (d) (3,3) (e) (4,2)
7. The message s3s2s4s2 was encoded using a comma code of length 4. The encoded
message is
8. A binary UD-code has codewords lengths (not necessarily in order) 1, 3, 3, 4, 4, l. What is the minimum value must l take in order for the code to exist?
(a) l = 1 (b) l = 2 (c) l = 3 (d) l = 4 (e) l = 5.
9. Consider a binary Huffman code for a source with 6 symbols, where the source symbols are given in non-increasing probability order. Suppose that the codeword for symbol s6 is c6 = 1011. Then the codeword for symbol s5 is
(a) 101 (b) 1010 (c) 1111 (d) 0011 (e) 011
10. Let S = {s1, s2} be a source with probabilities p1 = 53 , p2 = 25 . The average length per original symbol of a radix 3 Huffman code for the second extension S(2) of this source (constructed with the usual strategies) is
(a) 7 (b) 1 (c) 41 (d) 41 (e) 7 10 25 50 5
11. [5 marks]
(a) Show that there is no uniquely decodable ternary (i.e. radix 3) code for the
(a) 10011111110 (b) 1100111110 (c) 11010111110 (d) 01111100110 (e) 11010111010
with codeword lengths 1, 1, 2, 2, 3, 3, 3, 4, respectively.
(b) The symbol s1 of the source S = {s1,s2} occurs with probability 5/8 and s2 occurs with probability 3/8. Find a uniquely decodable binary code of minimal average length for S2, assuming that successive symbols occur independently, and state the average length per original source symbol of the code.
S = {s1,s2,s3,s4,s5,s6,s7,s8}
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2013 S2 TEST 1 VERSION 1B • Time Allowed: 45 minutes
1. A message is sent using a 5-character 8-bit ASCII burst code, which encodes charac- ters in blocks of four together with a 5th character which is used as a check codeword 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 00001001 11111111 10101011 11001011 11010100 is received and has been corrupted by a burst of noise that has converted all 0s to 1 but left all 1s as 1. What is the minimum length of the noise burst?
(a) 3 (b) 4 (c) 5 (d) 6 (e) none of these.
For the next 3 questions, let C1 be a binary linear code with check matrix
1 1 0 0 0 0 1 H=0 1 1 0 1 0 1 0 0 0 1 1 0 1
Assume that the check bits correspond to columns 1, 3, 4 and 6.
2. The codeword encoding the message 110 in code C1 is
(a) 1001110 (b) 0010100 (c) 0011100 (d) 1110100 (e) 1101100
3. A generator matrix G corresponding to the check matrix H for the code C1 has size (a) 3×7 (b) 4×7 (c) 4×3 (d) 3×4 (e) none of these.
4. If the word 1101001 is received using code C1, what is the minimum number of errors that could have occurred?
(a) 0 (b) 1 (c) 2 (d) 3 (e) 4
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 a binary 1-error correcting code with k information bits, m = 3 check bits and 2k codewords. The maximum possible value for k is
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5
6. A binary code C has minumum distance d = 12. Suppose this is used to correct a errors and detect b errors. Which of the following pairs (a, b) gives a valid strategy for decoding C?
(a) (0,12) (b) (3,9) (c) (4,8) (d) (5,6) (e) (7,4)
7. The message s2s1s4s3 was encoded using a comma code of length 4. The encoded
message is
(a) 1001110110 (b) 1011011110 (c) 1101011110 (d) 0111110010 (e) 1001110100
8. A binary UD-code has codewords lengths (not necessarily in order) 2, 2, 3, 4, 4, l. What is the smallest value must l take in order for the code to exist?
(a) l = 2 (b) l = 3 (c) l = 4 (d) l = 5 (e) none of these.
9. Consider a binary Huffman code for a source with 7 symbols, where the source symbols are given in non-increasing probability order. Suppose that the codeword for symbol s7 is c7 = 01101. Then the codeword for symbol s6 is
(a) 010 (b) 0110 (c) 11011 (d) 01110 (e) 01100
10. Let S = {s1,s2,s3,s4,s5,s6} be a source with probabilities p1 = 6 , p2 = 4 ,
p3 = 3 , p4 = 2 , p5 = p6 = 1 . The average length of a radix 4 Huffman code for 17 17 17
this source (using the usual strategies) is
(a) 4 (b) 12 (c) 21 (d) 24 (e) 31 17 17 17 17 17
11. [5 marks]
(a) Find an instantaneous ternary (i.e. radix 3) UD-code for the source
S = {s1,s2,s3,s4,s5,s6,s7,s8} with codeword lengths 1, 2, 2, 2, 2, 4, 4, 4, respectively.
(b) The symbol s1 of the source S = {s1,s2} occurs with probability 7/10 and s2 occurs with probability 3/10. Find a binary UD-code of minimal average length for S2, assuming that successive symbols occur independently, and state the average length per original source symbol of the code.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com