(13 intermediate revisions by the same user not shown)
Line 5: Line 5:
 
[[Category:image processing]]
 
[[Category:image processing]]
  
−
= [[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]] in Communication Networks Signal and Image processing (CS) =
+
<br>
−
= [[QE637_sol2012|Question 5, August 2012(Published on May 2017)]], Problem 2 =
+
<center>
 +
<font size="4"> [[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]] </font>
 +
 
 +
<font size="4"> Communication Networks Signal and Image processing (CS) </font>
 +
 
 +
<font size="4"> [[QE637_sol2012|Question 5, August 2012(Published on May 2017)]]</font>
 +
</center>
 +
 
 +
<font size="4">[[ QE637_sol2012_Q1 | Problem 1]],[[ QE637_sol2012_Q2 |2]]</font>
  
−
:[[QE637_sol2012_Q2| Solution 1]],[[QE637_sol2012_Q2|2]]
 
 
----
 
----
 
===Solution1:===
 
===Solution1:===
  
−
a)<br \>
+
a)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
 
   & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}{a}_{n}\delta (m) \\  
 
   & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}{a}_{n}\delta (m) \\  
 
  & \delta (m,n)=\left\{ \begin{matrix}
 
  & \delta (m,n)=\left\{ \begin{matrix}
−
  1\ m=n=0  \\
+
  1\quad m=n=0  \\
 
  0\qquad O.W  \\
 
  0\qquad O.W  \\
−
\end{matrix},  \right. \delta (m,n-j)=\left\{ \begin{matrix}
+
\end{matrix},  \right. \quad \delta (m,n-j)=\left\{ \begin{matrix}
−
  1\qquad n=j  \\
+
  1\quad m=0;\ n=j  \\
 
  0\qquad O.W  \\
 
  0\qquad O.W  \\
 
\end{matrix} \right. \\  
 
\end{matrix} \right. \\  
Line 26: Line 34:
 
</math>
 
</math>
  
−
b)<br \>
+
b)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
 
   & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}{b}_{m}\delta (n) \\  
 
   & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}{b}_{m}\delta (n) \\  
 
  & \delta (m,n)=\left\{ \begin{matrix}
 
  & \delta (m,n)=\left\{ \begin{matrix}
−
   1\ m=n=0  \\
+
   1\quad m=n=0  \\
 
   0\qquad O.W  \\
 
   0\qquad O.W  \\
−
\end{matrix}, \right. \delta (m-i,n)=\left\{ \begin{matrix}
+
\end{matrix}, \right. \quad \delta (m-i,n)=\left\{ \begin{matrix}
−
   1\ m=i;\ n=0  \\
+
   1\quad m=i;\ n=0  \\
 
   0\qquad O.W  \\
 
   0\qquad O.W  \\
 
\end{matrix} \right. \\  
 
\end{matrix} \right. \\  
Line 40: Line 49:
 
</math>
 
</math>
  
−
c)<br \>
+
c)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
Line 46: Line 56:
 
  & z(m,n)=\sum\limits_{i=-N}^{N}{{{b}_{i}}\ y(m-i,n)=}\sum\limits_{i=-N}^{N}{{{b}_{i}}\ \left( \sum\limits_{j=-N}^{N}{{{a}_{j}}\ x(m-i,n-j)} \right)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ x(m-i,n-j)}}} \\  
 
  & z(m,n)=\sum\limits_{i=-N}^{N}{{{b}_{i}}\ y(m-i,n)=}\sum\limits_{i=-N}^{N}{{{b}_{i}}\ \left( \sum\limits_{j=-N}^{N}{{{a}_{j}}\ x(m-i,n-j)} \right)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ x(m-i,n-j)}}} \\  
 
  & \delta (m-i,n-j)=\left\{ \begin{matrix}
 
  & \delta (m-i,n-j)=\left\{ \begin{matrix}
−
  1\ m=i;\ n=j  \\
+
  1\quad m=i;\ n=j  \\
 
  0\qquad O.W  \\
 
  0\qquad O.W  \\
 
\end{matrix} \right. \\  
 
\end{matrix} \right. \\  
Line 52: Line 62:
 
</math>
 
</math>
  
−
d)<br \>
+
d)
−
Number of multiplies per output point to implement each individual system = 2N+1
+
 
−
So, The number of multiplies per output point to implement each of the two individual systems is 2(2N+1) = 4N+2.
+
Number of multiplies per output point to implement each individual system = 2N+1.
 +
So, the number of multiplies per output point to implement each of the two individual systems is 2(2N+1) = 4N+2.
  
 
Number of multiplies per output point to implement the complete system with a single convolution is <math>\left( 2N+1 \right)\left( 2N+1 \right)\text{ }=4{{N}^{2}}+4N+1</math>
 
Number of multiplies per output point to implement the complete system with a single convolution is <math>\left( 2N+1 \right)\left( 2N+1 \right)\text{ }=4{{N}^{2}}+4N+1</math>
  
 
e)  
 
e)  
 +
 
Implementing the two systems in sequence requires less computation, but it is more complex and more sensitive to noise.
 
Implementing the two systems in sequence requires less computation, but it is more complex and more sensitive to noise.
 
Implementing the two systems in a single complete system requires more computation, but it is simpler, less sensitive to noise, and more stable.
 
Implementing the two systems in a single complete system requires more computation, but it is simpler, less sensitive to noise, and more stable.
Line 65: Line 77:
 
== Solution 2: ==
 
== Solution 2: ==
  
−
a)<br \>
+
a)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
   & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m)\ \delta(n-j)=}= {a}_{n}\ \delta (m) \\  
+
   & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m)\ \delta(n-j)=} {a}_{n}\ \delta (m) \\  
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
b)<br \>
+
<span style="color:green"> The answer is correct, but it's not obvious how the solution is derived. (See Solution 1) </span>
 +
 
 +
b)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
   & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,j)=}\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i)\ \delta(n)=}= {b}_{m}\ \delta (n) \\  
+
   & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i)\ \delta(n)=}{b}_{m}\ \delta (n) \\  
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
c)<br \>
+
<span style="color:green"> The answer is correct, but it's not obvious how the solution is derived. (See Solution 1) </span>
 +
 
 +
c)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
Line 85: Line 104:
 
\end{align}
 
\end{align}
 
</math>
 
</math>
 +
 +
<span style="color:green"> The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)  </span>
  
 
d)  
 
d)  
−
<math> 2N+1 </math> multiplies for each of the two individual systems <br \>
 
−
<math>(2N+1)^2</math> multiplies for the complete system with a single convolution
 
  
−
<span style="color:green"> For the complete system with a single convolution, as in each filter location, we will multiply both <math> a_j </math> and <math> b_i </math>, so we need <math> 2(2N+1)^2 </math> multiplies in total. But if the student consider that we pre-process the system and calculate the complete filter parameters in advance, then <math> (2N+1)^2 </math> multiplies is correct. 
+
Individually: <math> 2(2N+1)=4N+2 </math> <br \>
−
</span>
+
Complete system: <math>{( 2N+1)}^{2}=4{{N}^{2}}+4N+1</math>  
  
−
e) Implement in sequence:
+
e)
−
: Advantage: Less multiplies, faster
+
−
: Disadvantage: Need space for intermediate result
+
  
−
Implement a complete system:
+
Fewer multipliers are required when implementing individually, but the system is more complicated.
−
: Advantage: Intuitive solution. No intermediate result
+
 
−
: Disadvantage: More multiplies, slower
+
More complete for the complete system.
 +
 
 +
<span style="color:green"> The Student didn't mention advantage/disadvantage of the complete system, it is just mentioned that "More complete for the complete system". (See Solution 1)  </span>
  
 
----
 
----
 
===Related Problem===
 
===Related Problem===
−
Consider a 2D linear space-invariant filter with input <math> x(m,n) </math>, output <math> y(m,n) </math>, and impulse response <math> h(m,n) </math>, so that <br \>
+
Consider the following 2-D LSI systems. The first system (S1) has input x(m, n) and output y(m, n), and the second system (S2) has input y(m, n) and output z(m, n).
−
: <math> y(m,n) = h(m,n)* x(m,n). </math> <br \>
+
−
The impulse response is given by
+
<center> <math>\begin{align}
−
: <math>
+
  & y(m,n)=ay(m,n-1)+x(m,n)\qquad (S1) \\
−
h(m,n) = \left\{\begin{matrix}
+
& z(m,n)=bz(m-1,n)+y(m,n)\qquad (S2) \\
−
\frac{1}{(2N+1)^2}, for \  |m|\leq N \  and\  |n|\leq N
+
\end{align}</math></center>  
−
\\
+
−
0, \quad\quad\quad\quad\quad otherwise
+
The third system (S3) is formed by the composition of (S1) and (S2) with input x(m, n) and output z(m,n) and impulse response <math>{{h}_{3}}(m,n)</math>.
−
\end{matrix}\right.
+
 
−
</math>
+
a) Calculate the 2-D impulse response, <math>{{h}_{1}}(m,n)</math>, of the first system (S1).
 +
 
 +
b) Calculate the 2-D impulse response, <math>{{h}_{2}}(m,n)</math>, of the second system (S2).
  
−
a) If implement this filter with 2D convolution, how many multiplies are needed per output value?
+
c) Calculate the 2-D impulse response, <math>{{h}_{3}}(m,n)</math>, of the complete system (S3).
  
−
b) Find a separable decomponsition of <math> h(m,n) </math> so that <br \>
+
d) Calculate the 2-D transfer function, <math>{{H}_{1}}({z}_{1},{z}_{2})</math>, of the first system (S1).
−
: <math> h(m,n) = g(m)f(n) </math> <br \>
+
−
where <math> g(m)</math> and <math> f(n)</math> are 1D functions.
+
  
−
c) How can the functions <math> g(m)</math> and <math> f(n)</math> be used to compute <math> y(m,n)</math>. What are the advantage and disadvantage of this approach?
+
e) Calculate the 2-D transfer function, <math>{{H}_{3}}({z}_{1},{z}_{2})</math>, of the first system (S3).  
  
 +
Refer to  [https://engineering.purdue.edu/~bouman/ece637/previous/ece637S2014/exams/exam1/exam.pdf <u>ECE637 Spring 2014 Exam1 Problem1</u>].<br>
  
 
----
 
----
 
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]:
 
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]:

Latest revision as of 20:43, 2 May 2017



ECE Ph.D. Qualifying Exam

Communication Networks Signal and Image processing (CS)

Question 5, August 2012(Published on May 2017)

Problem 1,2

Solution1:

a)

$ \begin{align} & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}{a}_{n}\delta (m) \\ & \delta (m,n)=\left\{ \begin{matrix} 1\quad m=n=0 \\ 0\qquad O.W \\ \end{matrix}, \right. \quad \delta (m,n-j)=\left\{ \begin{matrix} 1\quad m=0;\ n=j \\ 0\qquad O.W \\ \end{matrix} \right. \\ \end{align} $

b)

$ \begin{align} & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}{b}_{m}\delta (n) \\ & \delta (m,n)=\left\{ \begin{matrix} 1\quad m=n=0 \\ 0\qquad O.W \\ \end{matrix}, \right. \quad \delta (m-i,n)=\left\{ \begin{matrix} 1\quad m=i;\ n=0 \\ 0\qquad O.W \\ \end{matrix} \right. \\ \end{align} $

c)

$ \begin{align} & h(m,n)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}^{{}}\delta (m-i,n-j)}}={{b}_{m}}\ {{a}_{n}} \\ & z(m,n)=\sum\limits_{i=-N}^{N}{{{b}_{i}}\ y(m-i,n)=}\sum\limits_{i=-N}^{N}{{{b}_{i}}\ \left( \sum\limits_{j=-N}^{N}{{{a}_{j}}\ x(m-i,n-j)} \right)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ x(m-i,n-j)}}} \\ & \delta (m-i,n-j)=\left\{ \begin{matrix} 1\quad m=i;\ n=j \\ 0\qquad O.W \\ \end{matrix} \right. \\ \end{align} $

d)

Number of multiplies per output point to implement each individual system = 2N+1. So, the number of multiplies per output point to implement each of the two individual systems is 2(2N+1) = 4N+2.

Number of multiplies per output point to implement the complete system with a single convolution is $ \left( 2N+1 \right)\left( 2N+1 \right)\text{ }=4{{N}^{2}}+4N+1 $

e)

Implementing the two systems in sequence requires less computation, but it is more complex and more sensitive to noise. Implementing the two systems in a single complete system requires more computation, but it is simpler, less sensitive to noise, and more stable.


Solution 2:

a)

$ \begin{align} & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m)\ \delta(n-j)=} {a}_{n}\ \delta (m) \\ \end{align} $

The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)

b)

$ \begin{align} & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i)\ \delta(n)=}{b}_{m}\ \delta (n) \\ \end{align} $

The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)

c)

$ \begin{align} & h(m,n)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ \delta (m-i,n-j)}}=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ \delta (m-i)\ \delta (n-j)}}={{b}_{m}}\ {{a}_{n}} \\ \end{align} $

The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)

d)

Individually: $ 2(2N+1)=4N+2 $
Complete system: $ {( 2N+1)}^{2}=4{{N}^{2}}+4N+1 $

e)

Fewer multipliers are required when implementing individually, but the system is more complicated.

More complete for the complete system.

The Student didn't mention advantage/disadvantage of the complete system, it is just mentioned that "More complete for the complete system". (See Solution 1)

Related Problem

Consider the following 2-D LSI systems. The first system (S1) has input x(m, n) and output y(m, n), and the second system (S2) has input y(m, n) and output z(m, n).

$ \begin{align} & y(m,n)=ay(m,n-1)+x(m,n)\qquad (S1) \\ & z(m,n)=bz(m-1,n)+y(m,n)\qquad (S2) \\ \end{align} $

The third system (S3) is formed by the composition of (S1) and (S2) with input x(m, n) and output z(m,n) and impulse response $ {{h}_{3}}(m,n) $.

a) Calculate the 2-D impulse response, $ {{h}_{1}}(m,n) $, of the first system (S1).

b) Calculate the 2-D impulse response, $ {{h}_{2}}(m,n) $, of the second system (S2).

c) Calculate the 2-D impulse response, $ {{h}_{3}}(m,n) $, of the complete system (S3).

d) Calculate the 2-D transfer function, $ {{H}_{1}}({z}_{1},{z}_{2}) $, of the first system (S1).

e) Calculate the 2-D transfer function, $ {{H}_{3}}({z}_{1},{z}_{2}) $, of the first system (S3).

Refer to ECE637 Spring 2014 Exam1 Problem1.

Back to ECE QE page:

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=QE637_sol2012_Q2&oldid=73130"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett