UNSW Sydney The School of Mathematics and Statistics 2019T3 MATH3411 Information, Codes and Ciphers (1) TIME ALLOWED – 2 HOURS (2) TOTAL NUMBER OF QUESTIONS – 3 (3) ANSWER ALL QUESTIONS (4) THE QUESTIONS ARE OF EQUAL VALUE (5) ANSWER EACH QUESTION IN A SEPARATE BOOK (6) THIS PAPER MAY BE RETAINED BY THE CANDIDATE (7) ONLY CALCULATORS WITH AN AFFIXED “UNSW APPROVED” STICKER MAY BE USED (8) THE VIGENE`RE TABLE IS PRINTED ON THE LAST PAGE OF THIS EXAM PAPER All answers must be written in ink. Except where they are expressly required, pencils may only be used for drawing, sketching or graphical work. 2019T3 MATH3411 Page 2 QUESTION 1 Use a separate book clearly marked Question 1 1. i) [10 marks] For each of the following, say whether the statement is true or false and give a brief reason or show your working. You will get one mark for a correct true/false answer, and if your true/false answer is correct, then you will also get one mark for a good reason. Begin each answer with the word “True” or “False”. a) The sequence 0-9091-1706-4 is a valid ISBN. b) The 6th codeword in the radix 3 standard I-code with codeword lengths 1, 2, 2, 3, 3, 3 is 121. c) A ternary Huffman code on probabilities 0.4, 0.3, 0.2, 0.1 has average codeword length L = 1.3. d) If M = 1 10 7 3 11 6 4 2 1 5 and p = 1 38 1613 9 are the transition matrix and equilibrium vector of a Markov source S, then the average codeword length LM for the Huffman code HuffM for S is 105 76 . e) For source S = {a, b, •} with probabilities P (a) = 0.3, P (b) = 0.2, P (•) = 0.5, the codeword 0.3 is a valid encoding of the message bab• when using arithmetic coding. ii) [4 marks] A binary linear code C has parity check matrix H = 1 0 0 10 1 0 1 0 0 1 1 . A codeword x = x1 · · ·x4 ∈ C is transmitted through a noisy channel in which each bit xi is corrupted with equal and independent probability p. a) Find the probability that there is at least one error and that all errors are corrected correctly when using the minimum distance decoding strategy. b) Find the probability of detecting at least one error when using the pure error-detecting strategy. iii) [6 marks] A Markov source S = {s1, s2, s3} has transition matrix M and equilibrium vector p M = 1 5 1 5 3 5 3 10 1 10 1 10 1 2 7 10 3 10 and p = 1 74 2813 33 . a) Find appropriate Huffman codes to encode S as a Markov source. b) Using these Huffman codes, decode 00010000 . c) Using the Huffman codes from part a), suppose that a message m is encoded as three bits, exactly one of which is 1. Find all such messages m. Please see over . . . 2019T3 MATH3411 Page 3 QUESTION 2 Use a separate book clearly marked Question 2 2. i) [6 marks] Let S = {s1, s2, s3, s4, s5} be a source with associated symbol probabilities p1 = 0.4, p2 = 0.2, p3 = 0.2, p4 = 0.1, p5 = 0.1. a) Find a Huffman code of radix r = 4 for S, using dummy symbols if necessary. State the average codeword length L of this code. b) Find the ternary Shannon-Fano code for this source. State the average codeword length LSF of this code. c) Calculate lim n→∞ L (n) SF (S) n where L (n) SF (S) is the average codeword length of a binary Shannon-Fano code for the nth extension of S. ii) [6 marks] A binary channel has input symbols A = {a1, a2} and output symbols B = {b1, b2}, and P (a1) = x and P (b1 | a1) = P (b2 | a2) = 3 7 . a) Find the entropy H(A) and the conditional entropy H(B|A). b) Calculate the entropy H(B) and the mutual information I(A,B). c) Hence or otherwise, find the channel capacity C(A,B). iii) [3 marks] The following ciphertext was enciphered using either plaintext feedback or ciphertext feedback with the keyword MATH. TAEMDAJYDEPX ! Determine the method used for enciphering and decipher the message. iv) [5 marks] Suppose that C is a linear code over a finite field with parity check matrix H. a) Prove that w(C) = d(C). b) Prove that d(C) = min{r : at least one set of r columns of H is linearly dependent}. Please see over . . . 2019T3 MATH3411 Page 4 QUESTION 3 Use a separate book clearly marked Question 3 3. i) [8 marks] An English-language message has been enciphered using a Vigene`re cipher: KMHZ HTS, Q OWWM APHB FWB KYCZP APPA LFHU HVK MURVGLL APL KVCYAL! Spaces and punctuation appear in the ciphertext as they do in the plaintext. The letter frequencies of the ciphertext are as follows, given by the odd and even letter positions: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 2 1 2 0 0 1 1 0 0 0 2 1 3 0 0 4 1 1 0 1 1 1 2 0 0 1 3 1 0 0 0 1 0 5 0 0 2 4 0 0 1 1 0 0 1 0 1 2 1 0 2 1 a) Calculate the index of coincidence Ic of the message, and show your working. b) Estimate the keyword length r (ignoring spaces and punctation), using the estimate r ≈ 0.0273n (n− 1)Ic − 0.0385n+ 0.0658 where n = 51 is the total number of letters. c) For such a short ciphertext, this particular estimate is not accurate. Luckily, we can decipher such a short ciphertext by trial and error, and it turns out that a keyword of length r = 2 was used. Find this keyword. d) Decipher the message. ii) [4 marks] The Morse code is a ternary compression code developed roughly 175 years ago by Samuel Morse and Alfred Vail for communicating via their telegraph network. The code has symbols •, −, and p which are used to encode the letters of the English language. Some of the codewords and their letter frequencies are as follows: letter frequency codeword letter frequency codeword letter frequency codeword A 8.2% •−p H 6.1% ••••p P 1.9% •−−•p B 1.5% −•••p I 7.0% ••p R 6.0% •−•p C 2.8% −•−•p K 0.8% −•−p S 6.3% •••p D 4.3% −••p L 4.0% •−••p T 9.1% −p E 12.6% •p M 2.4% −−p U 2.8% ••−p F 2.2% ••−•p N 6.7% −•p W 2.4% •−−p G 2.0% −−•p O 7.5% −−−p Y 2.0% −•−−p The remaining letters J, Q, V, X, and Z have total frequency 1.4%, and the Morse codeword of each of these letters has length 5. We will view these five rare letters as a single “letter”. a) Calculate the average codeword length L of the Morse code, and show your working. (Hint: Remember to include the “letter” consisting of J, Q, V, X, and Z.) b) The average codeword length LH = 2.7 of a ternary Huffman code on the 22 “letters” is shorter than that of the Morse code. Suggest two ways by which to reduce the average codeword length of the Morse code. Please see over . . . 2019T3 MATH3411 Page 5 iii) [8 marks] Let m1(x) = x 4 + x + 1 in Z2[x] and F = Z2[x]/〈m1(x)〉. Let α be a root of m1(x). You may assume that F is a field with the following description of its non-zero elements: α0 = 1 α5 = α2 + α α10 = ? α1 = α α6 = α3 + α2 α11 = ? α2 = α2 α7 = α3 + α + 1 α12 = α3 + α2 + α + 1 α3 = α3 α8 = α2 + 1 α13 = α3 + α2 + 1 α4 = α + 1 α9 = α3 + α α14 = α3 + 1 a) Express α10 and α11 as linear combinations of some of the powers 1, α, α2, and α3. b) Solve the following set of linear equations in F:( α2 α4 α3 α3 )( x y ) = ( α4 α8 ) c) A BCH code is obtained from F by replacing a message (c8, c9, . . . , c14) by the coeffi- cients of a polynomial C(x) ∈ Z2[x] where C(x) = CI(x) + CR(x) CI(x) = c8x 8 + c9x 9 + · · ·+ c14x14 CR(x) = CI(x) modm(x) m(x) = m1(x)m3(x) = 1 + x 4 + x6 + x7 + x8 . and m3(x) = x 4 + x3 + x2 + x+ 1 is the minimal polynomial of α3. Using this code, encode the message m = 1110001. d) Use the code to correct and decode the message y = 111110000000000, assuming that at most two errors occurred in transmission. Please see over . . . 2019T3 MATH3411 Page 6 Vigene`re Table A | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ------------------------------------------------------- A | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B | B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C | C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D | D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E | E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z | Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Table of Caesar substitution ciphers END OF EXAM
欢迎咨询51作业君
