Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2014 S2 TEST 1 VERSION A • Time Allowed: 45 minutes
1. You are given the following 7-bit ASCII codewords:
Copyright By PowCoder代写 加微信 powcoder
0 0110000 1 0110001 2 0110010 3 0110011
4 0110100 5 0110101 6 0110110 7 0110111
Define a 4-character 8-bit ASCII burst code by encoding characters in blocks of three together with a 4th 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 00110011 10110010 00110111 10110100 is received but contains a single error.
What is the corrected and decoded message?
(a) 127 (b) 307 (c) 325 (d) 327 (e) None of these.
For the next 3 questions, let C be a binary linear code with check matrix
1 0 0 1 1 1 1 H=0 1 1 1 0 1 0
Assume that the information bits correspond to columns 3, 4, 6, and 7.
2. The codeword encoding the message 1101 in code C is
(a) 0111101 (b) 1011101 (c) 1101101 (d) 1101011 (e) 1101101
3. A generator matrix G corresponding to the check matrix H for the code C has size (a) 4×7 (b) 3×7 (c) 4×3 (d) 3×4 (e) None of these
4. The minimum distance d(C) of the code C is
(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 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 one or more errors occur and are detected but cannot be corrected is
(a) 4p3(1−p) (b) 6p2(1−p)2 (c) p4 (d) 4p3(1−p)+p4 (e) 6p2(1−p)2 +p4
6. Let C be the binary linear code with basis {0101100, 1001010, 1011001}.
How many codewords are there in C?
(a) 3 (b) 4 (c) 8 (d) 16 (e) 128
7. The message s2s4s2s1 was encoded using a comma code of length 4. The encoded message is
(a) 010001011 (b) 101110100 (c) 11011111100 (d) 0100010101 (e) 101110110
8. A binary UD-code has codewords lengths (not necessarily in order) 1, 2, 3, 5, l.
What is the smallest value of l for which the code exists?
(a) l = 1 (b) l = 2 (c) l = 3 (d) l = 4 (e) l = 5
9. Consider a compression code with codewords c1 = 1, c2 = 01, 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 =001 (e)Noneofthese
10. Let S = {s1, s2} be a source with probabilities p1 = 51 and p2 = 45 .
The average length per original symbol of a radix 3 Huffman code for the second extension S2 of this source (constructed with the usual strategies) is
(a) 3 (b) 39 (c) 34 (d) 34 (e) 6 5 50 25 50 5
11. [5 marks]
(a) Show that there is no uniquely decodable ternary (i.e. radix 3) code with
codeword lengths 1, 2, 2, 2, 2, 2, 2, 3, respectively.
(b) The symbol s1 of the source S = {s1,s2} occurs with probability 5/7 and symbol s2 occurs with probability 2/7. 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.
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2014 S2 TEST 1 VERSION B • Time Allowed: 45 minutes
1. There may be an error in the check digit in the ISBN number 0-19-061133-X. The correct check digit is
(a) 2 (b) 4 (c) 6 (d) 8 (e) None of these.
For the next 3 questions, let C be a binary linear code with check matrix
1 0 0 0 0 1 0 H=0 1 0 1 1 0 0 0 0 1 0 1 0 0
Assume that the check bits correspond to columns 1, 2, 3, and 7.
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.
2. The codeword encoding the message 101 in code C is
(a) 1011101 (b) 0011010 (c) 1101010 (d) 1110101
(e) 1111010 3. A generator matrix G corresponding to the check matrix H for the code C has size
(a) 3×7 (b) 4×7 (c) 4×3 (d) 3×4 (e) None of these
4. The minimum distance d(C) of the code C is
(a) 0 (b) 1 (c) 2 (d) 3 (e) 4
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. Let C be the code consisting 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) 4341 (d) 3344 (e) None of these
7. The message s2s1s4s3 was encoded using a comma code of length 4. The encoded message is
(a) 1011110110 (b) 1011111110 (c) 1101011110 (d) 0111110010 (e) 1001110110
8. A binary UD-code with minimal average codeword length has codeword lengths (not
necessarily in order) 2, 2, 3, 3, 4, 4, l. What is the value of l?
(a) l = 1 (b) l = 2 (c) l = 3 (d) l = 4 (e) None of these
9. Consider a binary Huffman code for a source with 8 symbols S = {s1, . . . , s8}, where the source symbols are given in non-increasing probability order. Suppose that the codeword for symbol s7 is c7 = 1100. Then the codeword for symbol s8 is
(a) 010 (b) 110 (c) 1101 (d) 1110 (e) 1111
10. Let S = {s1,s2,s3,s4,s5} be a source with probabilities p1 = 52, p2 = 15, p3 = 51,
p4 = 2 , p5 = 1 . The average length of a radix 3 Huffman code for this source 15 15
(using the usual strategies) is
(a) 13 (b) 14 (c) 6 (d) 22 (e) 7 15 15 5 15 5
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, 3, 3, 4, respectively.
(b) The symbol s1 of the source S = {s1,s2} occurs with probability 3/5 and s2 occurs with probability 2/5. 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