SOLUTIONS MANUAL
1
,Codes: An Introduction to Information Communication and
Cryptography by Norman Biggs
Answers to Exercises
In some cases the ‘answer’ is just a hint, in others there is a full discussion. The
answers to the odd-numbered exercises are as published in the book.
Chapter 1
1.1. ‘Canine’ has six letters and ends in ‘nine’. The second message has
two possible interpretations.
1.2. About 136 years.
1.3. The mathematical bold symbols A and B.
1.4. Modern Greek 24, Russian Cyrillic 33.
1.5. This exercise illustrates the point that decoding a message requires the
making and testing of hypotheses. Here the rules are fairly simple, but that is
not always so. In the first example, it is a fair guess that the numbers
represent letters, and the simplest way of doing that is to let 1, 2, 3, . . .
H
represent A, B, C, . . . . The number 27 probably represents a space.
Testing this hypothesis, we find the message GOOD LUCK. The second
example has the same number of symbols as the first, and each is represented
by a word with 5 bits. How is this word related to the corresponding number
in the first example?
1.6 Suppose the coded message is x1x2x3 . . . . There are two steps.
Step 1: locate the spaces. Step 2: if xi and xj are consecutive spaces,
—
switch the symbols xi+k and xj−k for k = 1, 2, . . . (j i)/2.
1.7. s1s2 and s3s1 are both coded as 10010.
1.8. Yes, because the coded message can be split into blocks of the given
length, each of which is a codeword representing a unique symbol.
1.9. In both cases S is the 27-symbol alphabet A. In the first example T
{ } , and the coding function uses only strings of length 1. In
= 1, 2, . . . , 27
2
,the
second example T = B, and the coding function→S B∗ is an injection into
the subset B5 of B∗ .
1.10 S contains the 26 letters of the English alphabet, the 10 digits, a number (at
least 6) of accented letters, and a number (at least 4) of punctuation marks.
The set T contains the dot and the dash, plus the three kinds of pauses
mentioned in the text. (It is an interesting exercise to put the code-alphabet
into a purely binary form.)
1.11. SOS; MAYDAY.
1.12. The code is — • • • • — — • • , which is also the code for DEAD.
1.13. The number of ways of choosing 2 positions out of 8 is the binomial
×
number 28 = (8 7)/2 = 28. Hence at most 28 symbols can be represented
in the semaphore code.
1.14. Buy, Sell, Sell.
1.15. Using words of length 2 there are only 4 possible codewords, so we
need words of length 3, where we can choose any 6 of the 8 possibilities, say
1 '→ 001 2 '→ 010 3 '→ 011 4 '→ 100 5 '→ 101 6 '→ 110.
With this code, if one bit in a codeword is wrong, then the result is likely
to be another codeword: for example, if the first bit in 110 is wrong, we get
the codeword 010. This problem cannot be avoided if we are restricted to
using words of length 3. In order to overcome the problem we must use
codewords with the property that any two differ in at least two bits. In that
case, if one bit
3
, in any codeword is in error, then the result is not a codeword, and the error
will be detected. This can be arranged if we use codewords of length 4, for
example
1 '→ 0000 2 '→ 1100 3 '→ 1010 4 '→ 1001 5 '→ 0110 6 '→ 0101.
1.16. MATHS
H IS
H GOOD
H FOR
H YOU.
1.17. No, because the message refers to ENGLAND, which did not exist in
Caesar’s time. Also it is written in English.
1.18. Any permutation of the 26 letters can be used in place of the
cyclic permutation in the Caesar system.
Chapter 2
2.1. s3s4s2s1s4s2s3s1.
2.2. The codeword representing s1 is a prefix of the codeword representing s3.
2.3. The new code is
s1 '→ 10, s2 '→ 1, s3 '→ 100.
Clearly it is not prefix-free, since 1 is a prefix of both 10 and 100. However, it
can be decoded uniquely by noting that each codeword has the form 1
followed by a string of 0’s Alternatively decoding can be done by reading the
codeword backwards. If the last bit is 1, the last symbol must be s2. If it is
0, looking at the last-but-one bit enables us to decide if the last symbol is s1 or
s3. Repeating the process the entire word can be decoded uniquely. For
example 110101100 decodes as s2s1s1s2s3.
2.4. Suppose the word q′ is a prefix of a codeword q. This implies that
⊙
q′ is shorter than q. But the only occurrence of in q is the last symbol, so q′
⊙ ⊙
cannot contain and is not a codeword. If the symbol is not used, then
(for
example) the codeword for D is a prefix of the codeword for B.
2.5. The code can be extended by adding words such as 011, 101, without
losing the PF property.
2.6. The code can be extended.
4
1
,Codes: An Introduction to Information Communication and
Cryptography by Norman Biggs
Answers to Exercises
In some cases the ‘answer’ is just a hint, in others there is a full discussion. The
answers to the odd-numbered exercises are as published in the book.
Chapter 1
1.1. ‘Canine’ has six letters and ends in ‘nine’. The second message has
two possible interpretations.
1.2. About 136 years.
1.3. The mathematical bold symbols A and B.
1.4. Modern Greek 24, Russian Cyrillic 33.
1.5. This exercise illustrates the point that decoding a message requires the
making and testing of hypotheses. Here the rules are fairly simple, but that is
not always so. In the first example, it is a fair guess that the numbers
represent letters, and the simplest way of doing that is to let 1, 2, 3, . . .
H
represent A, B, C, . . . . The number 27 probably represents a space.
Testing this hypothesis, we find the message GOOD LUCK. The second
example has the same number of symbols as the first, and each is represented
by a word with 5 bits. How is this word related to the corresponding number
in the first example?
1.6 Suppose the coded message is x1x2x3 . . . . There are two steps.
Step 1: locate the spaces. Step 2: if xi and xj are consecutive spaces,
—
switch the symbols xi+k and xj−k for k = 1, 2, . . . (j i)/2.
1.7. s1s2 and s3s1 are both coded as 10010.
1.8. Yes, because the coded message can be split into blocks of the given
length, each of which is a codeword representing a unique symbol.
1.9. In both cases S is the 27-symbol alphabet A. In the first example T
{ } , and the coding function uses only strings of length 1. In
= 1, 2, . . . , 27
2
,the
second example T = B, and the coding function→S B∗ is an injection into
the subset B5 of B∗ .
1.10 S contains the 26 letters of the English alphabet, the 10 digits, a number (at
least 6) of accented letters, and a number (at least 4) of punctuation marks.
The set T contains the dot and the dash, plus the three kinds of pauses
mentioned in the text. (It is an interesting exercise to put the code-alphabet
into a purely binary form.)
1.11. SOS; MAYDAY.
1.12. The code is — • • • • — — • • , which is also the code for DEAD.
1.13. The number of ways of choosing 2 positions out of 8 is the binomial
×
number 28 = (8 7)/2 = 28. Hence at most 28 symbols can be represented
in the semaphore code.
1.14. Buy, Sell, Sell.
1.15. Using words of length 2 there are only 4 possible codewords, so we
need words of length 3, where we can choose any 6 of the 8 possibilities, say
1 '→ 001 2 '→ 010 3 '→ 011 4 '→ 100 5 '→ 101 6 '→ 110.
With this code, if one bit in a codeword is wrong, then the result is likely
to be another codeword: for example, if the first bit in 110 is wrong, we get
the codeword 010. This problem cannot be avoided if we are restricted to
using words of length 3. In order to overcome the problem we must use
codewords with the property that any two differ in at least two bits. In that
case, if one bit
3
, in any codeword is in error, then the result is not a codeword, and the error
will be detected. This can be arranged if we use codewords of length 4, for
example
1 '→ 0000 2 '→ 1100 3 '→ 1010 4 '→ 1001 5 '→ 0110 6 '→ 0101.
1.16. MATHS
H IS
H GOOD
H FOR
H YOU.
1.17. No, because the message refers to ENGLAND, which did not exist in
Caesar’s time. Also it is written in English.
1.18. Any permutation of the 26 letters can be used in place of the
cyclic permutation in the Caesar system.
Chapter 2
2.1. s3s4s2s1s4s2s3s1.
2.2. The codeword representing s1 is a prefix of the codeword representing s3.
2.3. The new code is
s1 '→ 10, s2 '→ 1, s3 '→ 100.
Clearly it is not prefix-free, since 1 is a prefix of both 10 and 100. However, it
can be decoded uniquely by noting that each codeword has the form 1
followed by a string of 0’s Alternatively decoding can be done by reading the
codeword backwards. If the last bit is 1, the last symbol must be s2. If it is
0, looking at the last-but-one bit enables us to decide if the last symbol is s1 or
s3. Repeating the process the entire word can be decoded uniquely. For
example 110101100 decodes as s2s1s1s2s3.
2.4. Suppose the word q′ is a prefix of a codeword q. This implies that
⊙
q′ is shorter than q. But the only occurrence of in q is the last symbol, so q′
⊙ ⊙
cannot contain and is not a codeword. If the symbol is not used, then
(for
example) the codeword for D is a prefix of the codeword for B.
2.5. The code can be extended by adding words such as 011, 101, without
losing the PF property.
2.6. The code can be extended.
4
