IV054 Coding, Cryptography and Cryptographic Protocols
2008 ­ Exercises I.
1. Consider the ternary code C = {0000, 1111, 2222} of length 4.
(a) Using the nearest neighbour decoding strategy, find all words uniquely decoded
as the word 1111.
(b) Suppose that any symbol is erroneously received with probability p and
that all symbols are equally likely. Find probability P of the event that a
received word is incorrectly decoded as 1111.
2. For any words x = x1    xm and y = y1    yn, let us define the operation  as
x  y = x1    xmy1    yn. For any (n, M1, d1) code C1 and (m, M2, d2) code C2,
let C3 = {x  y | x  C1, y  C2} be (x, y, z) code. Determine x, y and z.
3. Consider any perfect binary (n, M, 7) code. There are only two possible values
of n. Try to find them.
4. Determine M and d for a q-ary code
C = {x1    xn | x1, . . . , xn  {0, 1, . . . , q - 1}  x1 +    + xn = kq, k  N0}.
5. Consider an ISBN number 0444x50090. Determine x. Try to find out which
book has this ISBN code.
6. Which of the following codes cannot be a Huffman code for any probability
distribution.
(a) C1 = {00, 01, 1}
(b) C2 = {001, 01, 10, 11}
7. Let q > 0. What is the relation (, =, ) between
(a) Aq(n, d) and Aq(n/2, d/2);
(b) Aq(n, d) and Aq(n + 2, d + 1);
(c) Aq(n, d) and A2q(n, d);
(d) Aq(n, d) and Aq(n + 2, 2d);
(e) A2(n, 2d - 1) and A2(n + 1, 2d);
(f) Aq(n, d) and qn-d+1
.
8. Show that for t > 0 there is no perfect binary (n, M, 2t + 1) code, such that
n = 2k
for some k  N.