Section A    Data Compression

Question 1

(a)  Consider the sequence m:

m = aababccabdabbdec

Compress the sequence m using:

i.  Huffman coding;                                                              [5 Marks]

ii. Shannon coding;                                                              [5 Marks]

iii.  LZ78;                                                                               [5 Marks]

iv.  LZW.                                                                               [5 Marks]

Show your working.

(b)  Let Xm   = {a1 , . . . ,a2m} and let X  be a random variable on Xm  with

probabilies P(X  =  ai )  = pi .   Without  loss,  1  ≥ p1   ≥ p2   ≥  · · ·  ≥ p2m    ≥ 0.  Say X is incompressible if it has a Huffman code C such that all the codewords of C have length exactly m.  Clearly, if m = 1, X is incompressible; so assume m ≥ 2 henceforth.

i.  Prove that if X is uniform, then it is incompressible.        [3 Marks]

ii.  Prove that if X is incompressible, then p1  <  .                [2 Marks]

iii.  Give an  infinite family  (Xm   :  m  ≥  2) of incompressible  random variables with entropy lower than m for all m  ≥ 2.  You need to justify that Xm  is incompressible for all m and you need to compute

its entropy exactly. You will get full marks for an entropy of the form H(Xm ) = m − Ω(1),

and partial marks otherwise.                                           [10 Marks]

Question 2

We are given a collection of m real numbers y = (y1 , . . . ,ym )⊤ , which we want to compress by using a polynomial of degree n − 1, where n ≤ m:

F(x) = c0 + c1 x + ··· + cn−1xn−1 .

That is, the encoding maps y to c = (c0 , . . . ,cn−1)⊤ , and the reconstruction maps c to (F(1), . . . ,F(m))⊤ . Our goal is to find c minimising the mean square

difference

MSD =   |F(i) − yi |2 .

(a) We first consider the case n = m. Prove that there is a unique polynomial F(x) of degree at most m − 1 such that F(i) = yi  for all i = 1, . . . ,m:

F(x) =工(m)yk         u      . [6 Marks]

We now consider the general case. Let A be the m × n matrix with

aij  = ij−1,        i = 1, . . . ,m,    j = 1, . . . ,n.

and η := Ac − y .

(b)  Prove that minimising the MSD corresponds to minimising ∥η∥2 . [3 Marks] (c) The vector c that minimises the MSD is actually given by

c = (A⊤A)−1A⊤y .

Consider the following collection of m = 4 values:

y1  = 3.02,    y2  = 4.90,    y3  = 7.15,    y4  = 8.80.

Compute the minimum MSD for n = 1 and n = 2.  Comment on your results.               [6 Marks]

Section B    Error-correcting codes

Question 3

(a)  Give the conversion exponential-polynomial for GF(25) generated by x2 + x + 2.                                                                                    [12 Marks]

(b)  Determine the generator  polynomial of the  narrow-sense  BCH code of length 24 and design distance 3 over GF(5).                            [8 Marks]

Question 4

Let C be a binary code of length n. The distancing of C is

δ(C) :=   min   maxdH (c, x).

x∈GF(2)n   c∈C

(a)  Explain why the distancing is the smallest radius of a ball that contains all codewords.                  [3 Marks]

(b)  Prove that the whole space GF(2)n  is the only binary code of length n with distancing n.   [3 Marks]

(d)  Let C be a binary linear code of length n such that dmin (C⊥ ) ≥ 2.

i. Show that, for any 1 ≤ i  ≤ n,  half the codewords c  ∈ C satisfy