ECE Ph.D. Qualifying Exam in Communication Networks Signal and Image processing (CS), Question 5, August 2011

Problem 1 , 2

Problem 2

Consider the following 2-D LSI systems. The first system has input $ x(m,n) $ and output $ y(m,n) $, and the second system has input $ y(m,n) $ and output $ z(m,n) $. $ y(m,n) = \sum\limits_{j = - N}^N {{a_j}x(m,n - j)} \quad\quad S1 $
$ z(m,n) = \sum\limits_{i = - N}^N {{b_i}y(m-i,n)} \quad\quad S2 $

a) Calculate the 2-D impulse response, $ h_1(m,n) $, of the first system.

b) Calculate the 2-D impulse response, $ h_2(m,n) $, of the second system.

c) Calculate the 2-D impulse response, $ h(m,n) $, of the complete system.

d) How many multiplies does it take per output point to implement each of the two individual systems? How, many multiplies does it take per output point to implements the complete system with a single convolution.

e) Explain the advantages and disadvantages of implementing the two systems in sequence versus a single complete system.

Solution:

a)
$ h_1(m,n) = \sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)} $

b)
$ h_2(m,n) = \sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)} $

c)
$ \begin{align} h(m,n) &= {h_1}(m,n)*{h_2}(m,n)\\ &= (\sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)}) * (\sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)})\\ &= \sum\limits_{j = - N}^N {\sum\limits_{i = - N}^N {{a_j}{b_i}\delta (m - i,n - j)} } \end{align} $

d)
S1: need 2N+1 multiplies
S2: need 2N+1 multiplies
To implement the complete system with a single convolution: filter $ h(m,n) $ is a $ (2N+1)\times(2N+1) $ filter, and for each location we need 2 multiplies, so in total, we need $ 2(2N+1)^2 $ multiplies.

As $ a_j b_i $ can be calculated offline, if we consider that $ a_j b_i $ are merged in the filter $ h(m,n) $, then will need $ (2N+1)^2 $ multiplies to implement the complete system with a single convolution.

e) Two systems in sequence:

advantages: need $ (2N+1)^2 $ multiplies per output point, so it is computationally better;

disadvantages: as there are two systems, may introduce more noise.

Need only $ 2(2N+1) $ multiplies per output point. System S1 is to filter $ x(m,n) $ along one dimension, then we get the intermediate result $ y(m,n) $. System S2 is to filter $ y(m,n) $ along the other dimension. We then obtain $ z(m,n) $. So we only need $ 2(2N+1) $ multiplies per output point when intermediate results have been stored.

A single complete system:

advantages: more stable, less sensitive to noise;

disadvantages: need $ 2(2N+1)^2 $ multiplies per output point, so it needs more computation.

Solution From Another Student:

a)
$ h_1(m,n) = \sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)} $

b)
$ h_2(m,n) = \sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)} $

c)
$ h(m,n) = \sum\limits_{i = - N}^N {\sum\limits_{j = - N}^N {{b_i}{a_j}\delta (m - i,n - j)} } $

d) $ 2N+1 $ multiplies for each of the two individual systems
$ (2N+1)^2 $ multiplies for the complete system with a single convolution

For the complete system with a single convolution, as in each filter location, we will multiply both $ a_j $ and $ b_i $, so we need $ 2(2N+1)^2 $ multiplies in total. But if the student consider that we pre-process the system and calculate the complete filter parameters in advance, then $ (2N+1)^2 $ multiplies is correct.

e) Implement in sequence:

Advantage: Less multiplies, faster

Disadvantage: Need space for intermediate result

Implement a complete system:

Advantage: Intuitive solution. No intermediate result

Disadvantage: More multiplies, slower

Related Problem

Consider a 2D linear space-invariant filter with input $ x(m,n) $, output $ y(m,n) $, and impulse response $ h(m,n) $, so that

$ y(m,n) = h(m,n)* x(m,n). $

The impulse response is given by

$ h(m,n) = \left\{\begin{matrix} \frac{1}{(2N+1)^2}, for \ |m|\leq N \ and\ |n|\leq N \\ 0, \quad\quad\quad\quad\quad otherwise \end{matrix}\right. $

a) If implement this filter with 2D convolution, how many multiplies are needed per output value?

b) Find a separable decomponsition of $ h(m,n) $ so that

$ h(m,n) = g(m)f(n) $

where $ g(m) $ and $ f(n) $ are 1D functions.

c) How can the functions $ g(m) $ and $ f(n) $ be used to compute $ y(m,n) $. What are the advantage and disadvantage of this approach?

Back to ECE QE page: