Consider an alphabet of 5 symbols whose probabilities are as follows: A B C D E 1 16 1 4 1 8 1 16 1 2 One of these symbols has been selected at random and you need to discover which symbol it is by asking 'yes/no' questions that will be truthfully answered. (i) What would be the most efficient sequence of such questions that you could ask in order to discover the selected symbol? [2 marks] (ii) By what principle can you claim that each of your proposed questions in the sequence is maximally informative? [2 marks] (iii) On average, how many such questions will need to be asked before the symbol is discovered? What is the entropy of the symbol set? [2 marks] (iv) Construct a uniquely decodable prefix code for the symbols. Explain why it is uniquely decodable and why it has the prefix property. [2 marks] (v) Relate the bits in the code words forming your prefix code to the 'yes/no' questions that you proposed in (i). [2 marks] (b) Explain how the bits in an IrisCode are set by phase sequencing. Discuss how quantisation of the complex plane into phase quadrants sets each pair of bits; why it is beneficial for quadrant codes to form a Gray Code; how much entropy is thereby typically extracted from iris images; and why such bit sequences enable extremely efficient identity searches and matching. [5 marks] (c) Consider a noisy analog communication channel of bandwidth  = 1 MHz, which is perturbed by additive white Gaussian noise whose total spectral power is N0 = 1. Continuous signals are transmitted across such a channel, with average transmitted power P = 1,000. Give a numerical estimate for the channel capacity, in bits per second, of this noisy channel. Then, for a channel having the same bandwidth  but whose signal-to-noise ratio P N0 is four times better, repeat your numerical estimate of capacity in bits per second. [5 marks]

Continuous Mathematics

The complex form of the Fourier series is:

f(x) =

+

X

k=

ckei2kx

where ck is a complex number and ck = ck.

(a) Prove that the complex coeffiffifficient, ck, encodes the amplitude and phase

coeffiffifficients, Ak and k, in the alternative form:

f(x) =

+

X

k

=0

Ak cos(2kx k)

[10 marks]

(b) What is special about the case k = 0? [2 marks]

(c) Explain how the coeffiffifficients, ck, of the Fourier series of the periodic function,

f(x):

f(x) = f(x + T), x

can be obtained from the Fourier transform, FL(), of the related function,

fL(x):

fL(x) = f(x

),

T

2 6 x < T

2

0

,

otherwise

[8 marks]

2 Concurrent Systems

An interprocess communication environment is based on synchronous message

passing. A server is to be designed to support a moderate number of simultaneous

client requests.

Clients send a request message to the server, continue in parallel with server

operation, then wait for the server's reply message.

Discuss the design of the server's interaction with the clients. Include any problems

you foresee and discuss alternative solutions to them. [20 marks]

2CST.2001.4.3

3 Further Java

(a) Describe how mutual-exclusion locks provided by the synchronized keyword

can be used to control access to shared data structures. In particular you

should be clear about the behaviour of concurrent invocations of difffferent

synchronized methods on the same object, or of the same synchronized method

on difffferent objects. [6 marks]

(b) Consider the following class defifinition:

class Example implements Runnable {

public static Object o = new Object();

int count = 0;

public void run() {

while (true) {

synchronized (o) {

count ++;

}

}

}

}

Show how to start two threads, each executing this run method. [2 marks]

(c) When this program is executed, only one of the count fifields is found to

increment, even though threads are scheduled preemptively. Why might this

be? [2 marks]

(d) Defifine a new class FairLock. Each instance should support two methods, lock

and unlock, which acquire and release a mutual exclusion lock such that calls

to unlock never block the caller, but will allow the longest-waiting blocked

thread to acquire the lock. The lock should be recursive, meaning that the

thread holding the lock may make multiple calls to lock without blocking.

The lock is released only when a matched number of unlock operations have

been made.