Name: ……………………… UNSW
MATH3411 Semester 2, 2012
• 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. Consider a binary channel with bit-error probability p, where errors in different positions are independent (that is, white noise). Suppose that a codeword x is sent from a binary linear code with weight 4 and codewords of length 10, and the word y is received. Then the probability that an error is detected, using a pure error detection strategy, is
(a) 45p2(1−p)8 (b) 10p(1−p)9 +45p2(1−p)8 +120p3(1−p)7 (c) 1−p−p2 (d) 10p(1 − p)9 + 45p2(1 − p)8 (e) none of these
2. A binary linear code C has basis {101010100110, 010101011001}. Its weight w is (a) 1 (b) 2 (c) 4 (d) 6 (e) 12
3. Consider a code with codewords c1 = 00, c2 = 10, c3 = 1100, c4 =?, where c4 is to be chosen from the list of four possibilities below. Which choice of c4, if any, makes the resulting code uniquely decodable?
(a) c4 =0000, (b) c4 =1011, (c) c4 =1010, (d) c4 =11, (e) noneofthese
4. A binary UD-code of has codewords lengths (not necessarily in order) 2, 2, 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) none of these.
5. A Markov source S = {s1,s2,s3} has transition matrix M. The Huffman code for the equilibrium distribution is HuffE = [1, 00, 01]. (That is, c1 = 1, c2 = 00 and c3 = 01.) Huffman codes for the columns of M are given by Huff1 = [00, 1, 01], Huff2 = [0, 10, 11] and Huff3 = [11, 10, 0]. Given the string of source symbols s1s2s1s3s1, the Markov Huffman encoding is
(a) 0100110 (b) 111011011 (c) 1001011 (d) 1100111
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) The code 0-01-616376-2 is a valid ISBN-11 number.
ii) The 8-character 8-bit ASCII burst code can detect all triple errors in a block.
iii) It is possible to construct a binary linear code C with |C| = 12 and codewords of length 9 and that can correct 2 errors.
iv) The two binary I-codes {0, 100, 110, 1010, 1110} and {1, 000, 001, 0100, 0101} are equivalent.
v) If S is a source with two symbols of probabilities 75 and 72 then a binary Huffman coding of S2 has average length per original source symbol less than
7. [10 marks] Let C be the binary linear code with check matrix
1 0 0 0 1 1 H=0 1 0 1 0 1,
where the last three columns correspond to information bits.
(i) Find a generator matrix G for the code C.
(ii) Find a basis for the code C.
(iii) Encode 011 with this code C
(iv) Define the minimum distance d(C) of a code C and calculate d(C) for the code above, with explanation.
Name: ……………………… UNSW
MATH3411 Semester 2, 2012
• 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. Consider a binary channel with bit-error probability p, where errors in different positions are independent (that is, white noise). Suppose that a codeword x is sent from a binary linear code with weight 5 and codewords of length 10, and the word y is received. Then the probability that any errors are correctly corrected with the standard strategy is
(a) 45p2(1−p)8 (b) 10p(1−p)9 +45p2(1−p)8 +120p3(1−p)7 (c) 1−p−p2 (d) 10p(1 − p)9 + 45p2(1 − p)8 (e) none of these
2. Consider a code with codewords c1 = 01, c2 = 11, c3 = 1011, c4 =?, where c4 is to be chosen from the list of four possibilities below. Which choice of c4, if any, makes the resulting code uniquely decodable?
(a) c4 =0111, (b) c4 =1, (c) c4 =10, (d) c4 =100, (e) c4 =noneofthese.
3. A radix 3 instantaneous code (I-code) has codeword lengths (not necessarily in
order)1,3,4,4,4,landK=4/9. Thenlisgivenby
(a) l=1 (b) l=2 (c) l=3 (d) l=4 (e) l=5
4. Let S = {s1, s2} be a source with probabilities p1 = 85 , p2 = 38 ,. 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) 127 (b) 103 (c) 11 (d) 103 (e) 11 128 64 8 128 16
5. A Markov source S = {s1,s2,s3} has transition matrix M. The Huffman code for the equilibrium distribution is HuffE = [1, 00, 01]. (That is, c1 = 1, c2 = 00 and c3 = 01.) Huffman codes for the columns of M are given by Huff1 = [00, 1, 01], Huff2 = [0, 10, 11] and Huff3 = [11, 10, 0]. The string 001101100 decodes under the Markov Huffman encoding as
(a) s2s1s1s3s1s1 (b) s2s3s3s1s1 (c) s3s3s1s3s2s2s2 (d) s2s2s1s2s3
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) The code 0-00-716376-2 is a valid ISBN-11 number.
ii) The 8-character 8-bit ASCII burst code cannot detect all quadruple errors in a block.
iii) A binary code C with |C| = 12 that can correct 2 errors must have codewords of length at least 9.
iv) The binary linear code C with basis {101010101001, 010101010101} has weight 5.
v) The two binary I-codes {0, 100, 110, 1010, 1110} and {0, 101, 110, 1000, 1111} are equivalent.
7. [10 marks] Let C be the binary linear code with check matrix
1 1 1 1 1 1 1 H=0 1 0 0 0 1 1.
0 0 1 0 1 1 1 0001110
where the last three columns correspond to information bits.
(i) Reduce H to row reduced echelon form and hence find a generator matrix G
for the code C.
(ii) Hence or otherwise encode 101 with the code C.
(iii) Define the minimum distance d(C) of a code C and calculate d(C) for the code above, with explanation.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com