Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2016 S2 TEST 1 VERSION A • Time Allowed: 45 minutes
1. Consider a binary channel with bit-error probability p, where errors in different positions are independent. Suppose that a codeword x is sent from a binary linear code with minimum distance 6 and codeword length 9. The probability that one or more errors are correctly corrected using a minimum distance decoding strategy is
Copyright By PowCoder代写 加微信 powcoder
w = (1−p)9 x = 9p(1−p)8 y = 36p2(1−p)7 z = 84p3(1−p)6
The probability that one or more errors are correctly corrected using a minimum
distance decoding strategy is
(a) w (b) w+x (c) w+x+y (d) x+y (e) x+y+z
2. Let C be the code of all vectors x = x1x2x3x4 ∈ Z47 satisfying the check equations x1 + + x3 + x4 ≡0(mod7)
2×2 +2×3 +3×4 ≡0 (mod7)
Assuming that x1 and x2 are the information bits, find the codeword which encodes
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.
the message 10.
(a) 1042 (b) 1024 (c) 4210 (d) 2410
3. Let C be the ternary linear code with generator matrix
1 0 0 0 2 1 1 G=0 1 0 0 1 0 0 0 0 1 0 0 1 0
0001002 How many codewords are there in C?
(a) 4 (b) 7 (c) 16 (d) 27
4. For the code C of Question 3, assume that the last three bits are check bits.
The codeword that encodes m = 1021 is then
(a) 1021021 (b) 1011021 (c) 1021200 (d) 1021122 (e) None of these
(e) None of these
5. A binary linear code C has minimum distance d = 3 and length n = 7. The maximal possible number of information bits k for such a code is
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5
6. Consider a linear code C with a 7 × 10 parity check matrix H.
The number of codewords in a basis for C is
(a) 1 (b) 3 (c) 7 (d) 10 (e) none of these
7. Consider a compression code with codewords c1 = 1, c2 = 11, 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
8. The minimum radix that would be needed to create a UD-code for the source S = {s1,s2,…,s7}
with codeword lengths 1, 2, 2, 2, 2, 3, 4, respectively, is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
9. Consider the standard binary I-code with codeword lengths 1, 2, 3, 4, 4. The codeword c5 corresponding to symbol s5 is given by
(a) 0011 (b) 0110 (c) 1100 (d) 1110 (e) 1111
10. Let S = {s1, s2} be a source with probabilities p1 = 65 , p2 = 16 . The average length
of a radix 3 Huffman code for the second extension S(2) of this source is (a) 53 (b) 53 (c) 7 (d) 7 (e) 53
11. [5 marks]
(a) Show that there is no uniquely decodable binary code with codeword lengths 1, 2, 3, 4, 4, 4, respectively.
(b) Symbol s1 of the source S = {s1, s2} occurs with probability 4/5 and symbol s2 occurs with probability 1/5. 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.
36 72 6 12 12
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2016 S2 TEST 1 VERSION B • Time Allowed: 45 minutes
1. You are given the following 7-bit ASCII codewords:
C 1000011 o 1101111 d 1100100 e 1100101
$ 0100100 − 0101101 i 1101001 Z 1011010
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 ASCII code studied in lectures.)
The message “Code” together with its check character is given by:
(a) Code$ (b) Code- (c) Codei (d) CodeZ (e) None of these 2. Let C be the code of all vectors x = x1x2x3x4 ∈ Z47 satisfying the check equations
2×1 +x2 +2×3 + x4 ≡0(mod7) x1 + x3 +4×4 ≡0(mod7)
There are two information bits but you are not told in which positions they lie. Which of the following codewords could possibly encode the message 10?
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.
(a) 1050 (b) 1500 (c) 5100 (d) 0015
3. Let C be the binary linear code with generator matrix
0 1 0 1 1 0 0 0 G=1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0
11101001 How many codewords are there in C?
(a) 4 (b) 8 (c) 16 (d) 32
4. For the code C of Question 3, assume that the first four bits are information bits.
The codeword that encodes m = 1011 is then
(a) 10110001 (b) 10001011 (c) 11001011 (d) 10111111 (e) None of these
(e) None of these
5. A binary linear code C has minimum distance d = 5 and length n = 8. The maximal possible number of information bits k for such a code is
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5
6. Consider a linear code C with a 6 × 11 parity check matrix H.
The number of codewords in a basis for C is
(a) 1 (b) 5 (c) 6 (d) 11 (e) none of these
7. A uniquely decodable code has codewords c1 = 1, c2 = 01, c3 = 001, c4 = ?. Which of the following codewords could c4 be?
(a)c4 =0 (b)c4 =00 (c)c4 =10 (d)c4 =11 (e)Noneofthese
8. The minimum radix that would be needed to create a UD-code for the source S = {s1,s2,…,s7}
with codeword lengths 1, 1, 2, 2, 2, 2, 2, respectively is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
9. Consider the standard binary I-code with codeword lengths 2, 2, 3, 3, 4, 4. The codeword c5 corresponding to symbol s5 is given by
(a) 0011 (b) 1100 (c) 1101 (d) 1110 (e) 1111
10. Let S = {s1, s2} be a source with probabilities p1 = 45 , p2 = 15 . The average length
of a radix 3 Huffman code for the second extension S(2) of this source is (a) 39 (b) 39 (c) 6 (d) 3 (e) 1
11. [5 marks]
(a) Show that there is no uniquely decodable ternary (i.e. radix 3) code with
codeword lengths 1, 1, 2, 2, 2, 3, respectively.
(b) Symbol s1 of the source S = {s1, s2} occurs with probability 5/6 and symbol s2 occurs with probability 1/6. 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.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com