DIGITAL SIGNAL PROCESSING

2001

Special Instructions for Invigilators: None

Information for Candidates:

Sequence z-transform

δ (n) 1

1
u (n)
1 − z −1
1
n
a u (n) 1 − az −1

Table 1 : z-transform pairs

δ (n) is defined to be the unit impulse function.

u (n) is defined to be the unit step function.

Numbers in square brackets against the right margin of the following pages are a guide to the
marking scheme.

Page 1 of 5
1. (a) Describe and compare linear convolution and circular convolution. Include relevant [4]
definitions.

(b) Consider the two sequences p(n) = [1 2 0 1] and q(n) = [2 2 1 1] .

[4]
Compute the linear convolution of these two sequences.
[4]
Compute the Discrete Fourier Transform (DFT) of p(n) and of q(n).

Using the above DFT result, compute the circular convolution of p(n) and q(n). [4]

Also using the above DFT result, show in detail how to compute the linear [4]
convolution of p(n) and q(n). It is not necessary to carry out the computation but a
detailed description of the computation procedure is required.

2. Computationally efficient algorithms for computing the DFT normally exploit the
following two properties.

Symmetry: W Nk + N / 2 = −W Nk
Periodicity: W Nk + N = W Nk

What does W represent in this context? Show that these properties are satisfied for [4]
illustrative values of k and N.
[6]
Explain clearly what is meant by the terms Radix-2 and Decimation-in-Time in the
context of efficient algorithms for computing the DFT.
[10]
Derive the 4-point radix-2 decimation-in-time FFT algorithm and draw the signal
flow graph.

Page 2 of 5
3. (a) State the significant differences between FIR and IIR discrete-time filters. [4]

(b) A continuous-time filter H c (s ) has the following properties:

1−δ ≤ H c ( jΩ) ≤ 1+ δ for Ω ≤ Ω p

and H c ( jΩ) ≤ λ for Ω ≥ Ω s

where δ and λ are constants which describe the passband ripple and stopband
attenuation respectively, Ω p is the upper limit of the passband and Ω s is the lower
limit of the stopband.

Consider a discrete-time lowpass filter H α (z ) for which the upper limit of the
passband is ω p . This discrete-time filter is derived from H c (s ) using the
transformation

 2 1 − z −1 
Hα ( z ) = H c  ⋅  0 ≤α ≤ ∞ .
 α 1 + z −1 
 

π [12]
Find an expression for α in terms of Ω p such that ω p = .
2

For a given constant value of Ω p , sketch a graph showing ω p as a function of α [4]

over the range of α from 0 to ∞ .

Page 3 of 5
4. (a) Describe the principles and applications of discrete-time Quadrature Mirror Filters
(QMF). Write down the relationships between a prototype filter H 0 ( z ) and its QMF [5]
mirror filter H 1 ( z ) in terms of the impulse responses and the frequency responses.

(b) Consider the system in Figure 1 in which H 0 ( z ) is an FIR filter of order 4. Draw the [5]
signal flow graph of the filter.

Show how the Noble Identities can be used to improve the computational efficiency
of the system of Figure 1. Draw a signal flow graph of the filter for the system with [10]
improved efficiency and comment on the implementation of this filter.

x(n) y(n)
H 0 ( z) L

Figure 1

5. A causal digital filter has an output y (n) for input x (n) given by

y (n) = x(n) + x(n − 2) − y (n − 1) − 0.5 y (n − 2)

where n is the discrete time index.

Find the poles and zeros associated with this filter and sketch a plot of them on the z-
plane. [6]
Determine an expression for the impulse response of the filter and show that the
impulse response is real valued. [8]

Draw a labelled sketch of the impulse response and comment briefly on its significant
features. [6]

Page 4 of 5
6. (a) Show how a filter H ( z ) can be represented in Type 1 polyphase form. [2]

Hence show that the analysis filter in a mulitrate filter bank with K channels can be [5]
described using matrix notation as
h( z ) = E( z L )e( z )

for which bold lower-case letters represent vectors and bold upper-case letters
represent matrices and E( z ) is known as the polyphase component matrix.

(b) Figure 2 shows a general polyphase analysis-synthesis filter bank. Consider the 3-
phase case of Figure 2 in which the polyphase component matrix P is given by

1 1 1
P = 1 − 1 1 .
1 0 − 1

What are the filters H 0 ( z ), H 1 ( z ) and H 2 ( z ) that are represented by the polyphase [5]
analysis filter bank?

State the relationship between y (n) and x(n) for which the analysis-synthesis filter
bank is said to have the property of perfect reconstruction. [3]

State the conditions on Q for the analysis-synthesis filter bank to have the property of
perfect reconstruction and determine synthesis filters G0 ( z ), G1 ( z ) and G 2 ( z ) as
represented by the polyphase synthesis filter bank such that the perfect reconstruction [5]
conditions are satisfied.

x(n)
L L
−1
z z −1
L Q L
P
z −1 z −1
• • •
• • •
• • •

z −1
z −1 y(n)
L L

Figure 2

Page 5 of 5
DIGITAL SIGNAL PROCESSING
2001

SOLUTIONS

Page 1 of 11
1. (a) Describe and compare linear convolution and circular convolution. Include relevant
definitions.

Book-work.

(b) Consider the two sequences p(n) = [1 2 0 1] and q(n) = [2 2 1 1] .

Compute the linear convolution of these two sequences.

By the simple “graphical method” we obtain the convolution as [2 6 5 5 4 1 1].

Compute the Discrete Fourier Transform of p(n) and of q(n).

W 0 =1 W 1 = e − jπk / 2 W 2 = e − jπk W 3 = e − j 3πk / 2

P ( 0) = 1 + 2 + 0 + 1 = 4 Q ( 0) = 2 + 2 + 1 + 1 = 6
P (1) = 1 − j 2 + j = 1 − j Q(1) = 2 − j 2 − 1 + j = 1 − j
P (2) = 1 − 2 − 1 = −2 Q ( 2) = 2 − 2 + 1 − 1 = 0
P (3) = 1 + j 2 − j = 1 + j Q(3) = 2 + j 2 − 1 − j = 1 + j

Using the above DFT result, compute the circular convolution of p(n) and q(n).

The circular convolution is found from the IDFT of the product P(k)Q(k):

 4 * 6 = 24  24 − j 2 + j 2 6
(1 − j )(1 − j ) = −2 j     
P. * Q =   from which we can find the IDFT as 1  24 + 2 + 2  = 7 
 0  4 24 + j 2 − j 2 6
     
 (1 + j )(1 + j ) = 2 j   24 − 2 − 2  5

Also using the above DFT result, show in detail how to compute the linear
convolution of p(n) and q(n). It is not necessary to carry out the computation but a
detailed description of the computation procedure is required.

To perform linear convolution, we zero pad the two sequences. In this case 3 zeros are
required for each signal.

p' (n) = [1 2 0 1 0 0 0] and q (n) = [2 2 1 1 0 0 0]

We then form the IDFT of the product P’(k)Q’(k). Marks will be given for setting up the
computations, either directly or in matrix form, show the twiddle factors and the way in which
the products are formed. Bonus mark if the symmetry of the DFT matrix is noted or exploited.

Page 2 of 11
2. Computationally efficient algorithms for computing the DFT normally exploit the
following two properties.

Symmetry: WNk + N / 2 = −WNk

Periodicity: WNk + N = W Nk

Explain these properties and give an illustrative example of each.

WN is the complex exponential term e − j 2π / N . The periodicity and symmetry can be seen
when the complex exponential is written in its trigonometric form.

Explain what is meant by the terms Radix-2 and Decimation-in-Time in the context of
efficient algorithms for computing the DFT.

An approach to the computation of an N-point DFT is to factor N as N = r1 r2 r3 ... where the

factors are prime. In the special case when all the factors are equal so that r j = r ∀j then the
computation has a regular pattern and r is known as the radix. In radix-2 computations, N has
to be an integer power of 2 and the computation is broken down into many 2-point DFTs; an
approach which turns out to be very efficient.

Decimation-in-time refers to sub-sampling the input signal in the time domain so that, for a 2-
point FFT, the signal is divided into the even indexed samples and the odd indexed samples.

Derive the 4-point radix-2 decimation-in-time FFT algorithm and draw the signal
flow graph.

Starting from the definition of the DFT

N −1
X (k ) = ∑ x(n)W
n =0
nk
N k = 0,1,..., N − 1

We can write a 2-point DFT:

X (0) = x(0) + x(1)

X (1) = x(0) − x(1)

Expanding the definition for N = 4 we obtain:

3
X (k ) = ∑ x(n)W
n =0
4
nk

The derivation continues by performing decimation in time and employing symmetry

properties of W (which should be shown explicitly) and leads to
X (k ) = X e (k ) + W4k X o (k ) k = 0,1,2,3
where the subscripts e and o indicate the even and odd indexed sub-sequences. Hence the 4-
point DFT is written as two 2-point DFTs.

The last stage of the derivation is to formulate the recombination equations

Page 3 of 11
 X (0) = X e (0) + X o (0)
X (1) = X e (1) + W41 X o (1)
X ( 2) = X e ( 0) − X o ( 0)
X (3) = X e (1) − W41 X o (1)

The signal flow graph follows:

x(0) X(0)

x(2) -1
X(1)

x(1)
-1 X(2)

x(3) -1 X(3)
-1
W41

Page 4 of 11
3. (a) State the significant differences between FIR and IIR discrete-time filters.

Bookwork

(b) A continuous-time filter H c (s ) has the following properties:

1−δ ≤ H c ( jΩ) ≤ 1+ δ for Ω ≤ Ω p

and H c ( jΩ ) ≤ λ for Ω ≥ Ω s

where δ and λ are constants which describe the passband ripple and stopband
attenuation respectively, Ω p is the upper limit of the passband and Ω s is the lower
limit of the stopband.

Consider a discrete-time lowpass filter H α (z ) for which the upper limit of the
passband is ω p . This discrete-time filter is derived from H c (s ) using the
transformation

 2 1 − z −1 
Hα ( z ) = H c  ⋅  0 ≤α ≤ ∞ .
 α 1 + z −1 
 

π
Find an expression for α in terms of Ω p such that ω p = .
2

The above transformation indicates that:

 2 1 − z −1 
s is replaced by  ⋅ 
 α 1 + z −1 
 
For frequency response we use z = e jω so that
 2 1 − e − jω  2 e jω / 2 − e − jω / 2 2 j ω p 
jΩ p =  ⋅ = ⋅ = tan 
 2 

 α 1 + e − jω  α e jω / 2 + e − jω / 2 α
   
2 ω p 
and therefore Ω p = tan  .

α  2 
π 2
Since we require ω p = then we can write that α = .
2 Ωp

Page 5 of 11
 (c) For a given constant value of Ω p , sketch a graph showing ω p as a function of α
over the range of α from 0 to ∞ .

2 ω p  α Ω p 
From part (b) we know that Ω p = tan   and so ω p = 2 arctan 
α   2 .
 2   
For small α , ω p ≈ α Ω p
For α → ∞ ωp →π

3.5

2.5

2
wp

1.5

0.5

0
0 100 200 300 400 500 600 700 800 900 1000
alpha

Page 6 of 11
4. Describe the principles and applications of discrete-time Quadrature Mirror Filters
(QMF). Derive the relationships in the time domain and frequency domain between a
prototype filter H 0 ( z ) and its QMF mirror filter H 1 ( z ) .

QMF filters are used in, for example, the design of multirate filterbanks. They are related
such that
h1 (n) = (−1) n h0 (n)
H 1 ( z ) = H 0 (− z ) .

In frequency terms

H 1 (e jω ) = H 0 (e j (ω −π ) )

so that if, typically, H 0 ( z ) is a lowpass halfband filter then H 1 ( z ) will be a highpass

halfband filter with the same response characteristics as the prototype but in a mirror image.
The frequency shift of π is equivalent to “reflection” in this case because of the periodicity
of the spectrum of discrete time signals and systems.

x(n) y(n)
H 0 ( z) L

Figure 1

Consider the system in Figure 1 in which H 0 ( z ) is an FIR filter of order 4. Draw the
signal flow graph of the filter.

x(n) z −1 z −1 z −1 z −1

b(0) b(1) b(2) b(3) b(4)

Show how the Noble Identities can be used to improve the computational efficiency
of the system of Figure 1. Draw the signal flow graph of the filter for the system with
improved efficiency and comment on the implementation of this filter.

x(n) y(n)
L H 0 ( z1 / L )

x(n) z −1 / L z −1 / L z −1 / L z −1 / L

b(0) b(1) b(2) b(3) b(4)

Direct implementation of the fractional delays is not normally done. Instead, the original filter
could be decomposed into L phases using Type 1 polyphase representation so that, after
application of the Noble identities, only integer delays are employed.

Page 7 of 11
5. A finite impulse response causal digital filter has an output y (n) for input x (n)
given by

y (n) = x(n) + x(n − 2) − y (n − 1) − 0.5 y (n − 2)

where n is the discrete time index.

Find the poles and zeros associated with this filter and sketch a plot of them on the z-
plane.
Y ( z) 1 + z −2
=
X ( z ) 1 + z −1 + 0.5 z −2

Zeros at z = ± j
Poles at z = −0.5 + j 0.5 and − 0.5 − j 0.5

0.8

0.6

0.4
Imaginary Part

0.2

-0.2

-0.4

-0.6

-0.8

-1

-1 -0.5 0 0.5 1
Real Part

Determine an expression for the impulse response of the filter and show that the
impulse response is real valued.

1 + z −2
H ( z) =
1 + z −1 + 0.5 z −2
1 + z −2
= where p = −0.5 + j 0.5
(1 − pz −1 )(1 − p * z −1 )
− z −1 + 0.5 z −2
= 1+
(1 − pz −1 )(1 − p * z −1 )

The inverse z-transform of 1 is δ (n) .

The inverse z-transform of the fraction is found by partial fraction expansion.

− z −1 + 0 . 5 z −2 A A*
= + where p = −0.5 + j 0.5 and A = −0.5 − j.
1 + z −1 + 0.5 z − 2 z − p z − p *
leading to
h(n) = δ (n) + A. p n u (n − 1) + A* ( p * ) n u (n − 1)

Page 8 of 11
To show that his is real-valued, note that δ (n) is real by definition and show that the 2nd and
3rd terms on the RHS are real by writing

A = A e jα and p = p e jβ .

So that
n
( ) n
A. p n u (n − 1) + A* ( p * ) n u (n − 1) = A p e j (α + β ) + e − j (α + β ) u (n − 1) = 2 A p cos(α + β ) u (n − 1)

c) Draw a labelled sketch of the impulse response and comment briefly on its significant
features.
Impulse Response
1.5

0.5

-0.5

-1
0 10 20 30 40 50 60 70 80 90 100

• Decaying envelope
• Oscillation at frequency 3π / 4 .
• Initial value of 1.

Page 9 of 11
 6. (a) Show how filter H ( z ) can be represent in Type 1 polyphase form.

L −1
H ( z) = ∑z
l =0
−l
El ( z L ) with El ( z ) = ∑ e ( n) z
n
l
−n
and el (n) = h(nL + l )

Hence show that the analysis filter in a mulitrate filter bank with K channels can be
described using matrix notation as
h( z ) = E( z L )e( z )

for which bold lower-case letters represent vectors and bold upper-case letters
represent matrices and E ( z ) is known as the polyphase component matrix.

By extending the above result for one channel to a new result for K channels, we can write
L −1
H k ( z) = ∑z
l =0
−l
E kl ( z L ) k = 0,1,..., K − 1 .

This corresponds to a set of K equations that can be written in the required matrix form if
h( z ) = [H 0 ( z ) H 1 ( z )...H L −1 ( z )]
T

 E00 ( z ) E 01 ( z ) ... 
 
E( z ) =  E10 ( z ) ... 
 ... E ( z ) 
 L −1, L −1 
[
e( z ) ) = z 0 z −1 ... z −(l −1) ]
T

x(n)
L L
−1
z z −1
L Q L
P
z −1 z −1
• • •
• • •
• • •

z −1
z −1 y(n)
L L

Figure 2

(b) Figure 2 shows a general polyphase analysis-synthesis filter bank. Consider the 3-
phase case of Figure 2 in which the polyphase component matrix P is given by

1 1 1
P = 1 − 1 1
1 0 − 1

What are the filters H 0 ( z ), H 1 ( z ) and H 2 ( z ) that are represented by the polyphase
analysis filter bank?

Page 10 of 11
Start with the above equation h( z ) = E( z L )e( z ) with E set to P. We are dealing here with a
simple special case since the given P is independent of z. The matrix equation can be written
out in full as
 H 0 ( z )  1 1 1  1 
 H ( z )  = 1 − 1 1  z −1 
 1    
 H 2 ( z ) 1 0 − 1  z − 2 
and therefore we have
H 0 ( z ) = 1 + z −1 + z −2 , H 1 ( z ) = 1 − z −1 + z −2 , H 2 ( z ) = 1 − z −2

State the relationship between y (n) and x(n) for which the analysis-synthesis filter
bank is said to have the property of perfect reconstruction.

y (n) = Cx(n − τ ) where C and tau are constants.

State the conditions on Q for the analysis-synthesis filter bank to have the property of
perfect reconstruction and determine synthesis filters G0 ( z ), G1 ( z ) and G 2 ( z ) as
represented by the polyphase synthesis filter bank such that the perfect reconstruction
conditions are satisfied.

In the simplest case, we can set Q = P −1 . More strictly, we require that PQ is pseudo-
circulant, for which the identity matrix is an example case.

Inverting P gives
0.25 0.25 0.5

Q =  0.5 − 0.5 0
0.25 0.25 − 0.5

From the diagram, we have three paths to the output, one through each of
G0 ( z ), G1 ( z ) and G 2 ( z ) . We can therefore write
T
G0 ( z )  0.25 0.25 0.5
 1  [
 G ( z )  = z −2 z −1
]
1  0 .5 − 0 .5 0
G 2 ( z ) 0.25 0.25 − 0.5

and so finally

G0 ( z ) = 0.25 z −2 + 0.5 z −1 + 0.25, G1 ( z ) = 0.25 z −2 − 0.5 z −1 + 0.25, G 2 ( z ) = 0.5 z −2 − 0.5

As an additional point (no extra marks, sadly), we can verify PR by computing

T = H 0 ( z )G0 ( z ) + H 1 ( z )G1 ( z ) + H 2 ( z )G2 ( z )
= (1 + z −1 + z −2 )(0.25 + 0.5 z −1 + 0.25 z − 2 ) + (1 − z −1 + z − 2 )(0.25 − 0.5 z −1 + 0.25 z − 2 ) + (1 − z − 2 )(−0.5 + 0.5 z −2 )
= (0.25 + 0.75 z -1 + z - 2 + 0.75 z -3 + 0.25 z - 4 ) + (0.25 − 0.75 z −1 + z − 2 − 0.75 z −3 + 0.25 z − 4 ) + (−0.5 + z − 2 − 0.5 z − 4 )
= 3z − 2

Page 11 of 11