Digital Signal Processing
(a) A radio system outputs signals with frequency components only in the range
2.5 MHz to 3.5 MHz. The analog-to-digital converter that you want to use
to digitise such signals can be operated at sampling frequencies that are an
integer multiple of 1 MHz. What is the lowest sampling frequency that you
can use without destroying information through aliasing? [5 marks]
(b) Consider a digital filter with an impulse response for which the z-transform is
H(z) = (z + 1)2
(z − 0.7 − 0.7j)(z − 0.7 + 0.7j)
(i) Draw the location of zeros and poles of this function in relation to the
complex unit circle. [2 marks]
(ii) If this filter is operated at a sampling frequency of 48 kHz, which
(approximate) input frequency will experience the lowest attenuation?
[2 marks]
(iii) Draw a direct form I block-diagram representation of this digital filter.
[5 marks]
(c) Make the following statements correct by changing one word or number in
each case. (Negating the sentence is not sufficient.)
(i) Statistical independence implies negative covariance.
(ii) Group 3 MH fax code uses a form of arithmetic coding.
(iii) Steven's law states that rational scales follow a logarithmic law.
(iv) The Karhunen-Lo`eve transform is commonly approximated by the
z-transform.
(v) 40 dB corresponds to an 80× increase in voltage.
(vi) The human ear has about 480 critical bands.
[6 marks]
10
CST.2008.9.11
12 Computer Systems Modelling
(a) Suppose that you conduct a simulation experiment to estimate the mean µ of
some random variable X. Supposing that your simulation experiment yields a
sample of size n of independent and identically distributed values Xi derive a
100(1 − α) percent confidence interval for the parameter µ. [6 marks]
(b) Explain how you can use your confidence interval derived in part (a) to
construct a rule for determining the length of your simulation so as to ensure
a given size of confidence interval for the parameter µ. [4 marks]
(c) Now suppose that in your simulation you can also observe a second random
variable Y , say, with known mean value µY . Show that
E(X + c(Y − µY )) = µ
where c is any constant value. [4 marks]
(d) Using Y as a control variate for X, determine the best choice of c to minimise
the variance of Z = X + c(Y − µY ). [6 marks]
13 Types
(a) Give an account of the Curry-Howard correspondence between the
polymorphic lambda calculus (PLC) and the second-order intuitionistic
propositional calculus (2IPC). Illustrate your answer by giving a proof in
2IPC of
{} ` ∀p, q, r((p → r) → (q → r) → (p ∨ q) → r)
corresponding to the closed PLC expression
Λp, q, r(λx : p → r, y : q → r, z : p ∨ q (z r x y)).
Here p ∨ q is an abbreviation for ∀r((p → r) → (q → r) → r). [15 marks]
(b) Explain how β-reduction on PLC expressions can be used to simplify proofs
in 2IPC. [5 marks]
11 (TURN OVER)
CST.2008.9.12
14 Denotational Semantics
(a) Show that every continuous function f : D → D on a domain D has a least
prefixed point, fix(f). [3 marks]
(b) Let h : P → P be a continuous function on a domain P. Show that
fix(h) = fix(h ◦ h). [3 marks]
(c) Let D be a domain. Let f : D → D and g : D → D be continuous functions.
Define the continuous function h : D × D → D × D by
h(x, y) = (g(y), f(x))
for x, y ∈ D. Show
fix(h) = (fix(g ◦ f), fix(f ◦ g))

(a) Prove that if X has at least m+n-1 elements and A and B partition X (i.e. A and B are disjoint subsets of X with union X) then either |A|m or |B| n. (b) For a graph G = (V, E) explain what is meant by (i) an independent set of vertices, and a(G), the independence number of G, (ii) a clique, and w(G), the clique number of G, (c) State Ramsey's theorem for graphs, giving a sufficient condition for a graph to have independent sets and cliques of given size.