UNSW Sydney The School of Mathematics and Statistics November 2017 MATH3411 Information, codes and ciphers (1) TIME ALLOWED – 2 HOURS (2) TOTAL NUMBER OF QUESTIONS – 4 (3) ANSWER ALL QUESTIONS (4) THE QUESTIONS ARE NOT 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 All answers must be written in ink. Except where they are expressly required, pencils may only be used for drawing, sketching or graphical work. November 2017 MATH3411 Page 2 QUESTION 1 Use a separate book clearly marked Question 1 1. i) [14 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-7476-7055-8 is a valid ISBN. b) The binary linear code C with parity check matrix H = 0 1 1 0 00 0 1 1 1 1 1 1 1 0  can be used to correct one error. c) The 5th codeword in the radix 3 standard I-code with codeword lengths 1, 2, 2, 3, 3 is 121. d) A ternary Huffman code on probabilities 0.4, 0.3, 0.2, 0.1 has aver- age codeword length L = 1.3. e) For source S = {s1, s2, s3, s4} with probabilities p1 = 12 , p2 = 14 , p3 = p4 = 1 8 , it is possible to find a binary encoding of some extension Sn with average word length per original source symbol less than 1.5. f) In the field GF(53), 3 and 5 lie in the same cyclotomic set. g) The integer 129 is a strong pseudo-prime to base 3. ii) [6 marks] A ternary linear code C has parity check matrix H = 1 0 0 1 00 1 0 2 1 0 0 1 0 1  where the check bits correspond to columns 1, 2, and 3. a) Explain why this code is 1-error correcting. b) Find a basis for C. c) Correct and decode the received word y = 21002, assuming that it has exactly two errors, neither of which is in the 1st coordinate. Please see over . . . November 2017 MATH3411 Page 3 QUESTION 2 Use a separate book clearly marked Question 2 2. i) [8 marks] A Markov source S = {s1, s2, s3} has transition matrix M =  3 10 1 10 1 10 1 2 1 10 11 20 1 5 4 5 7 20  . a) Show that the equilibrium probability vector for S is p = 1 8 13 4  . b) Find appropriate Huffman codes to encode S as a Markov source. c) Using these Huffman codes, encode the string s1s3s2s2s1. d) A message m = m1m2 with m1,m2 ∈ S is encoded using the above Huffman codes. Calculate the probability that m2 is encoded as 10. ii) [5 marks] Let S = {s1, s2, s3, s4, s5} be a source with associated symbol probabilities p1 = 0.4, p2 = p3 = 0.2, p4 = p5 = 0.1. a) Find a Huffman code of radix r = 4 for S using dummy symbols if necessary. State the average codeword length of this code. b) Find the codeword lengths for a ternary Shannon-Fano code for this source and state its average codeword length LSF(S). c) Calculate lim n→∞ L (n) SF (S) n where L (n) SF (S) is the average codeword length of a ternary Shannon-Fano code for the nth extension of S. iii) [7 marks] A linear code C over Z5 has parity check matrix H = 1 0 0 1 10 1 0 1 2 0 0 1 1 3  . A codeword x = x1 · · ·x5 ∈ C is transmitted through a noisy channel in which the probability of each coordinates xi to be received as yi is constantly and independently equal to p(≤ 1 4 ) if yi ∈ Z5−{xi} and 1−4p if yi = xi. a) Find the minimum distance d(C). b) Calculate the probability that exactly two errors occur. c) Calculate the probability of undetected errors. Please see over . . . November 2017 MATH3411 Page 4 QUESTION 3 Use a separate book clearly marked Question 3 3. i) [7 marks] An English-language message has been enciphered using a Vigene`re cipher. Spaces and punctuation have not been enciphered and appear in the ciphertext as they do in the plaintext. The first part of the ciphertext is as follows. PI FRB FHQ YHHG AKPV, AKLQ FRBU HQZZLU PV JRYULFA, BHB! The letter frequencies of the ciphertext are as follows: 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 3 4 0 0 0 4 1 5 1 1 2 3 0 0 0 3 3 3 0 0 3 2 0 0 2 2 a) Calculate the index of coincidence Ic of the message. 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 = 42 is the total number of letters. c) For such a short ciphertext, this particular estimate is not necessarily 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) [8 marks] Consider the following encryption scheme: pairs of letters are encoded as numbers by mapping the first letter to the number a1 and the second letter to the number a2 using the encoding A B C D E F G H I J K L M 3 4 5 6 7 8 9 10 11 12 13 14 15 N O P Q R S T U V W X Y Z 16 17 18 19 20 21 22 23 24 25 26 27 28 and then replacing (a1, a2) by 29a1 + a2. For example, TO→ (22, 17)→ 29× 22 + 17 = 655. This number is then encrypted using RSA encryption with n = 2279 and encryption exponent e = 437. a) Using Fermat factorisation, or otherwise, factorise n. b) Hence show that φ(n) = 2184. c) Calculate the decryption exponent d. Show your working. d) Decipher the received ciphertext c = 1434, giving your answer as a two-letter word. Please see over . . . November 2017 MATH3411 Page 5 QUESTION 4 Use a separate book clearly marked Question 4 4. i) [10 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 = α2 + α + 1 α1 = α α6 = α3 + α2 α11 = α3 + α2 + α α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) Simplify α8 + α + 1 α11 + α2 to a positive power of α. b) Solve the following set of linear equations in F:( α7 α2 α3 α6 )( x y ) = ( α 1 ) c) A BCH code is obtained from F by replacing a message (c8, c9, . . . , c14) by the coefficients 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 1000001. d) Use the code to correct and decode the message 000010001010000, assuming that at most two errors occurred in transmission. ii) [5 marks] Suppose that C is a binary linear code of length n with 2k codewords and assume that there is no coordinate among the n coordi- nates that is 0 in all codewords. a) Show that the sum of the weights of all the codewords is n2k−1. b) Deduce an upper bound for the minimum distance of this code. Please see over . . . November 2017 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 51作业君版权所有