Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2017 S2 TEST 1 VERSION A • Time Allowed: 45 minutes
1. There may be an error in the check digit in the ISBN number 0-76-535615-4. The correct check digit is
Copyright By PowCoder代写 加微信 powcoder
(a) 2 (b) 5 (c) 7 (d) X (e) None of these
2. The binary code C = {101010, 110011, 101101, 111111} has minimum distance
(a) 1 (b) 2 (c) 3 (d) 4 (e) None of these For the next 3 questions, let C be a binary linear code with check matrix
0 1 0 1 0 H=0 0 1 1 1
Assume that the check bits correspond to the first three columns.
3. How many codewords are there in C?
(a) 2 (b) 3 (c) 4 (d) 5 (e) 8
4. The codeword encoding the message 01 in code C has weight
(a) 1 (b) 2 (c) 3 (d) 4 (e) None of these
5. Which of the following is a generator matrix G for the code C?
(a)11110 (b)11110 (c)00000 (d)11001 (e)Noneofthese
01011 11001 11001 11001
6. A binary code C has minimum distance d = 8. 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,7) (b) (1,6) (c) (2,5) (d) (3,4) (e) (4,3)
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.
7. Consider a compression code with codewords c1 = 10, 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 =1 (c) c4 =011 (d) c4 =111 (e) Noneofthese
8. A binary UD-code has codeword lengths (not necessarily in order) 1, 3, 3, 4, l.
What is the smallest value of l for which such a code exists?
(a) l = 1 (b) l = 2 (c) l = 3 (d) l = 4 (e) l = 5
9. Consider the standard ternary I-code with codeword lengths 1, 3, 3, 3, 3. The codeword c5 corresponding to symbol s5 is given by
(a) 000 (b) 102 (c) 110 (d) 111 (e) None of these
10. A Markov source S = {s1, s2, s3} has transition matrix M.
The Huffman code for the equilibrium distribution is HuffE = [1, 00, 01]. (Thatis,c1 =1,c2 =00andc3 =01.)
The Huffman codes for the columns of M are given by
Huff1 =[00,1,01] Huff2 =[0,10,11] Huff3 =[11,10,0]
The string 001101100 decodes under the Markov Huffman encoding as
(a) s1s1s1s3s1s1 (b) s2s3s3s1s1 (c) s2s3s1s3s2s2s2 (d) s2s2s1s2s3 (e) None of these
11. [5 marks]
(a) Use the Kraft-Mac to show that there is no uniquely decodable ternary code with codeword lengths 1, 1, 2, 2, 2, 3, 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.
Name: …………………. Student ID: …………….
UNSW School of Mathematics and Statistics MATH3411 Information Codes and Ciphers
2017 S2 TEST 1 VERSION B • Time Allowed: 45 minutes
1. A message is sent using a 5-character 8-bit ASCII code which encodes characters in blocks of four together with a 5th character which is used as a check character for even parity in rows and columns, similar to the 9-character 8-bit ASCII code.
The message 10101010 10010110 11001101 00111010 11000011 is received. Assuming at most two errors, which of the following bits could be incorrect?
(a) 3rd (b) 5th (c) 21th (d) 25th (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 a binary code with minimum distance 7 and codeword length 12. The probability that one or more errors are correctly corrected using a minimum distance decoding strategy is
w = 12p(1−p)11 x = 66p2(1−p)10 y = 110p3(1−p)9 z = 220p3(1−p)9 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) w+x+z (e) x+y+z
3. Let C be the code of all vectors x = x1x2x3x4 ∈ Z43 satisfying the check equations
x1 +2×3 +x4 ≡0(mod3)
x1 +x2 + +x4 ≡0(mod3)
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) 1000 (b) 1100 (c) 1110 (d) 0111
4. Let C be the ternary linear code with generator matrix 1 0 0 1 0 1 0 G=0 2 0 0 1 1 0
0011101 How many codewords are there in C?
(a) 3 (b) 8 (c) 16 (d) 27
5. For the code C of Question 4, assume that the first four bits are check bits.
The codeword that encodes m = 001 is then
(a) 0011101 (b) 0012101 (c) 1002001 (d) 1112001 (e) None of these
(e) None of these
6. A binary linear code C has minimum distance d = 4 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
7. A uniquely decodable code has codewords c1 = 1, c2 = 10, c3 = 01, c4 = ?.
Which of the following codewords could c4 be?
(a)c4 =0 (b)c4 =11 (c)c4 =00 (d)c4 =010 (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, 3, 3, 3, respectively is
(a) 2 (b) 3 (c) 4 (d) 5 (e) 6
9. Consider the standard binary I-code with codeword lengths 1, 3, 3, 3, 3. The codeword c5 corresponding to symbol s5 is given by
(a) 001 (b) 010 (c) 100 (d) 110 (e) 111
10. Let S = {s1, s2} be a source with probabilities p1 = 43 , p2 = 14 . The average length per original symbol of a radix 3 Huffman code for the second extension S(2) of this source is
7 2 7 1 1 5 2 .
(a) 23 (b) 23 (c) 27 (d) 27 (e) 5 16 32 16 32 8
[5 marks] A Markov source S = {s1, s2, s3} has transition matrix M = 3
i) Show that p = 1 1 is an equilibrium vector for M.
ii) Show that the Huffman code HuffE for the probability distribution given by p isHuffE =[0,10,11](thatis,c1 =0,c2 =10andc3 =11),andfindthe average codeword length LE for HuffE.
iii) Assuming that the Huffman codes for the columns of M are given Huff1 = [0,11,10] Huff2 = [01,1,00] Huff3 = [0,10,11]
use Markov Huffman encoding to encode the string of source symbols s1s2s1s3s1.
10 231
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com