ECE Ph.D. Qualifying Exam: CS-5 (637)

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.

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.

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

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

Back to ECE QE page: