2007 - Exercises I.
1. Consider the following general checksum scheme. Given is a fixed weighting
vector (wi,..., Wk)- A number is encoded with a vector (cii,..., a^) so that
a\W\ + ... cikWk = 0 mod n
for some integer n greater than any possible a.
Prove the following statements.
(a) The checksum scheme can detect a single error occuring in position i if and
only if Wi is relatively prime to n.
(b) The checksum scheme can detect a transposition error occuring in positions
i and j if and only if \wi -- Wj\ is relatively prime to n.
2. Let n, m, d be positive integers. Show that A2(nm,dm) > A2(n,d).
3. (a) Find a binary (10,6, 6)-code.
(b) Find a binary (5, 4, 3)-code.
(c) Let m be a positive integer. Show that
6 if m is even
2
^ ' ' ^ 4 otherwise.
Use the following inequality (Plotkin bound):
. . J 2|_2^i^J if d is even and n < 2d
A2{n,d) _ | 2[^^l\ if d is odd and n < 2d + 1.
4. Let C be a binary (9,6,5)-code which is transmitted over a binary symmetric
channel with error probability p = 0.01 using the nearest neighbour decoding
strategy. Find an upper bound of the word error probability for any codeword.
5. Design a Huffman coding for the following alphabet. Probabilities of occurence
of each character are given.
(a> g)> (&
; g)> (c
> g)> (d, g), (e, g), (/, g), (g, g), (h, - )
What is the average length of encoding? (i.e. How long is the encoding of a
text with n characters?)
6. Show that the code C = {0n
, ln
} is perfect if and only if n is odd.
7. Let us have a message m = 01012414 over a 5-ary alphabet.
Let us have an error correction code
C = {0 i-> 01234,1 !->ˇ 12340, 2 ^ 23401, 3 i-> 34012, 4 ^ 40123}
Let us have a channel X over 5-ary alphabet. For p being a probability of error
and X Ob character from {0,1, 2, 3, 4}:
with probability 1 -- p
with probability p/4
with probability p/4
with probability p/4
with probability p/4
We have sent m encoded by C through X and received
0120000110012301223022401444233333340023
(a) Decode the message.
(b) Is code C always able to correct errors induced by channel XI If not, design
a code that can do it.
(c) Can the code be more efficient if used on a modified channel X1
which works
over 6-ary alphabet?
X h ^ X
X h ^ X + 1 mod 5
X h ^ X + 2 mod 5
X h ^ X + 3 mod 5
X h ^ X + 4 mod 5