微信客服：xiaoxionga100
微信客服：ITCS521
MATH3411-无代写
时间：2024-11-22
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
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
