(45 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
<br>  
 
<br>  
 +
<center>
 +
<font size="4"> [[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]] </font>
  
= [[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]] in Communication Networks Signal and Image processing (CS) =
+
<font size="4"> Communication Networks Signal and Image processing (CS) </font>
= [[QE637_sol2013|Question 5, August 2013(Published on May 2017)]],
+
:[[ QE637_sol2013_Q1 | Problem 1]],[[ QE637_sol2013_Q2 |2]]
+
  
 +
<font size="4"> [[QE637_sol2013|Question 5, August 2013(Published on May 2017)]]</font>
 +
</center>
 +
 +
<font size="4">[[ QE637_sol2013_Q1 | Problem 1]],[[ QE637_sol2013_Q2 |2]]</font>
  
 
----
 
----
Line 11: Line 15:
  
 
a)  
 
a)  
 +
 
<math>
 
<math>
\[{{P}_{0}}({{e}^{j\omega }})=\sum\limits_{n=-\infty }^{\infty }{{{p}_{0}}(n){{e}^{-jn\omega }}}=\sum\limits_{n=-\infty }^{\infty }{\left( \sum\limits_{m=-\infty }^{\infty }{x(m,n)} \right){{e}^{-jn\omega }}}=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-j(m0+n\omega )}}=X({{e}^{j0}},{{e}^{j\omega }})}
+
{{P}_{0}}({{e}^{j\omega }})=\sum\limits_{n=-\infty }^{\infty }{{{p}_{0}}(n){{e}^{-jn\omega }}}=\sum\limits_{n=-\infty }^{\infty }{\left( \sum\limits_{m=-\infty }^{\infty }{x(m,n)} \right){{e}^{-jn\omega }}}=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-j(m0+n\omega )}}=X({{e}^{j0}},{{e}^{j\omega }})}
</math><br>  
+
</math>
  
and
+
b)
  
<span class="texhtml"><math>p_0(e^{jw}) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty}  
+
<math>
x(m,n)e^{-jnw}</math>,&nbsp;</span>  
+
{{P}_{1}}({{e}^{j\omega }})=\sum\limits_{m=-\infty }^{\infty }{{{p}_{1}}(m){{e}^{-jm\omega }}}=\sum\limits_{m=-\infty }^{\infty }{\left( \sum\limits_{n=-\infty }^{\infty }{x(m,n)} \right){{e}^{-jm\omega }}}=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-j(m\omega +n0)}}=X({{e}^{j\omega }},{{e}^{j0}})}
 +
</math>
  
we have:
+
c)
  
<math> p_0(e^{jw}) = X(e^{j\mu}, e^{jw})\vert_{\mu=0} </math>
+
<math>
 
+
\sum\limits_{n=-\infty }^{\infty }{{{p}_{0}}(n)}=\sum\limits_{n=-\infty }^{\infty }{\left( \sum\limits_{m=-\infty }^{\infty }{x(m,n)} \right)}=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-j(m0+n0)}}=X({{e}^{j0}},{{e}^{j0}})}
b) Similarly to a), we have:
+
</math>  
  
<math> p_1(e^{jw}) = X(e^{jw}, e^{j\nu})\vert_{\nu=0} </math>
+
d)  
  
<span style="color:green"> The solution used <math> v </math> and <math>\mu</math> to represent frequency axis. It used <math> w</math> to subuslitude  both <math> v </math> and <math>\mu</math> which is confusing. The solution should stated let <math> w=v </math> and <math> w=\mu </math> at (a) and (b). </span><br>
+
No, they don’t. From part (a) and (b), we know that <math>{{P}_{0}}({{e}^{jw}})</math> and  <math>{{P}_{1}}({{e}^{jw}})</math> represent the horizontal and vertical axes of the 2D DSFT <math>X({{e}^{j\mu }},{{e}^{j\upsilon }})</math>, which is not enough for reconstruction of x(m, n).
c) <br> <math> \sum_{n=-\infty}^{\infty} p_0(n) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} x(m,n) = X(e^{j\mu}, e^{j\nu}) |_{\mu=0, \nu=0} </math>  
+
which is the DC component of the image.  
+
  
d) No, it can't provide sufficient information. From the expression in a) and b), we see that <math>p_0(e^{jw}) </math> and <math> p_1(e^{jw}) </math> are only slices of the DSFT. The information when <math>\mu</math> and <math>\nu</math> are not zeros is lost. <br>
+
For example,   <math>{{x}_{1}}(m,n)=\left( \begin{matrix}
A simple example would be as follows.<br>
+
  1 & 3  \\
Let <br> <math>
+
  2 & 4 \\
x(m,n) =  
+
\end{matrix} \right),_{{}}^{{}} and\ {{x}_{2}}(m,n)=\left( \begin{matrix}
\left[ {\begin{array}{*{20}{c}}
+
  0 & 4 \\
1 ~ 2 \\
+
  3 & 3  \\
3 ~ 4\\
+
\end{matrix} \right)</math>
\end{array}} \right] </math>, so<br> <math> p_0(n) =[4~6], p_1(m) =  [3 ~7]^T </math>.
+
have the same <math>{{p}_{0}}(n)=\left[ \begin{matrix}
<br>
+
  3 & 7  \\
With the above the information of the projection, the original form of the 2D signal cannot be determined. For example, <math>
+
\end{matrix} \right]\ and\ {{p}_{1}}(m)=\left[ \begin{matrix}
x(m,n) =  
+
  4  \\
\left[ {\begin{array}{*{20}{c}}
+
  6  \\
2 ~ 1 \\
+
\end{matrix} \right]</math>. So, x(m,n) can’t be reconstructed from <math>{{p}_{0}}(n)\ and\ {{p}_{1}}(m)</math>.
2 ~ 5\\
+
\end{array}} \right] </math> gives the same projection. '''
+
  
 
== Solution 2:  ==
 
== Solution 2:  ==
  
a) From the question,&nbsp;
+
a)  
  
<math>P_0(e^{j\mu}) = \sum_{n=-\infty}^{\infty}p_0(n)e^{-jn\mu} = \sum_{n=-\infty}^{\infty} \sum_{m=-\infty}^{\infty}x(m,n) e^{-jn\mu}\cdot1
+
<math>
= \sum_{n=-\infty}^{\infty} \sum_{m=-\infty}^{\infty}x(m,n) e^{-jn\mu}e^{-jm\cdot0} = X(e^{j\mu},e^{j\cdot0})</math>  
+
{{P}_{0}}({{e}^{j\omega }})=\sum\limits_{n=-\infty }^{\infty }{\sum\limits_{m=-\infty }^{\infty }{x(m,n)} {{e}^{-jn\omega }}}=X({{e}^{j0}},{{e}^{j\omega }})
 +
</math>
  
Therefore,&nbsp;
+
<span style="color:green"> The answer is correct, but multiple steps are skipped in this solution, which are necessary for clarity. (See Solution 1)  </span>
  
<math>P_0(e^{j\mu}) = X(e^{j\mu},e^{j\nu})\vert_{\nu = 0}</math><br>
+
b)  
  
b) Similar to question a),&nbsp;
+
<math>
 +
{{P}_{1}}({{e}^{j\omega }})=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-jm\omega }}}=X({{e}^{j\omega }},{{e}^{j0}})
 +
</math>
  
<math>P_1(e^{j\nu}) = \sum_{m=-\infty}^{\infty}p_1(m)e^{-jm\mu} = \sum_{n=-\infty}^{\infty} \sum_{m=-\infty}^{\infty}x(m,n) e^{-jm\nu}\cdot1
+
<span style="color:green"> The answer is correct, but multiple steps are skipped in this solution, which are necessary for clarity. (See Solution 1) </span>
= \sum_{n=-\infty}^{\infty} \sum_{m=-\infty}^{\infty}x(m,n) e^{-jn\cdot0}e^{-jm\nu} = X(e^{j\cdot0},e^{j\nu})</math>  
+
  
Therefore,
+
c)
  
<math>P_0(e^{j\mu}) = X(e^{j\mu},e^{j\nu})\vert_{\mu = 0}</math><br>  
+
<math>
 +
\sum\limits_{n=-\infty }^{\infty }{{{p}_{0}}(n)}=\sum\limits_{n=-\infty }^{\infty }{\sum\limits_{m=-\infty }^{\infty }{x(m,n)}=X({{e}^{j0}},{{e}^{j0}})}
 +
</math>  
  
<span style="color:green"> To be consistent with the problem statement, frequency notation<math>\mu</math> corresponds to the spatial notation <math>m </math> and is the first parameter. As a result, the solution of the (a) and (b) can be switched. </span>
+
<span style="color:green"> The answer is correct, but multiple steps are skipped in this solution, which are necessary for clarity. (See Solution 1) </span>
  
 +
d)
  
c)  
+
They do not; <math>{{p}_{0}}(n)\ and\ {{p}_{1}}(m)</math> are projections at two angles, and do not contain enough information to reconstruct x(m,n).
 +
[[File:sol2_2013_1d_1.jpg|thumbnail|center]]
 +
<math>
 +
\begin{align}
 +
  & X({{e}^{j\mu }},{{e}^{j\upsilon }})=\sum\limits_{m=-\infty }^{\infty }{\left[ \sum\limits_{n=-\infty }^{\infty }{x(m,n)} \right]}{{e}^{-jm\mu }}{{e}^{-jn\upsilon }} \\
 +
& X({{e}^{j\mu }},{{e}^{j\upsilon }})\ne \sum\limits_{m=-\infty }^{\infty }{{{p}_{1}}(m)}{{e}^{-jm\mu }}{{e}^{-jn\upsilon }}\ne {{P}_{1}}({{e}^{j\mu }}){{e}^{-jn\upsilon }} \\
 +
& \Rightarrow Can't\  do\  it!
 +
\end{align}</math> 
  
<math>\sum_{n = -\infty}^{\infty}p_0(n) = \sum_{n = -\infty}^{\infty} \sum_{m = -\infty}^{\infty} x(m,n)
 
=\sum_{n = -\infty}^{\infty} \sum_{m = -\infty}^{\infty} x(m,n) e^{-jn\cdot0}e^{-jm\cdot0} = X(e^{-jn\cdot0},e^{-jm\cdot0}) = X(e^{j\mu},e^{j\nu})\vert_{\mu = 0, \nu = 0}</math>
 
  
d)No. ''P''<sub>''0 &nbsp;''</sub>''only&nbsp;''represents the&nbsp;<span class="texhtml">μ</span>&nbsp;axis on <span class="texhtml">''X''(''e''<sup>''j''μ</sup>,''e''<sup>''j''ν</sup>)</span>. ''P<sub>1</sub>''&nbsp;only represents the <span class="texhtml">ν</span>&nbsp;axis on <span class="texhtml">''X''(''e''<sup>''j''μ</sup>,''e''<sup>''j''ν</sup>)</span>. It is not enough to represent&nbsp;<span class="texhtml">''X''(''e''<sup>''j''μ</sup>,''e''<sup>''j''ν</sup>)</span>.  
+
- To form reconstruction, need projections along many angles.
  
<span style="color:green"> Similarly to the above comment, <math>P_0(e^{jw}) </math>is the slice along <math>\nu </math> axis. </span>
+
- Could reconstruct a very simple object, like triangle.
 +
[[File:sol2_2013_1d_2.jpg|thumbnail|center]]
  
For example, assume two different array x''<sub>1</sub>'' and x''<sub>2</sub>''.  
+
<span style="color:green"> In the first figure, the projection of x(m,n) along the vertical axis is <math>{{p}_{1}}(m)\</math>, not <math>\ {{p}_{0}}(m)</math>.</span>
  
<math>x_1 = \left [
+
<span style="color:green"> In the second line of equations, <math>=</math> must be used instead of <math>\ne</math>. </span>
    \begin{array}{cc}
+
    3 & 4 \\
+
    5 & 6
+
    \end{array}
+
    \right ]</math>&nbsp;and&nbsp;<math>x_2 = \left [
+
    \begin{array}{cc}
+
    4 & 3 \\
+
    4 & 7
+
    \end{array}
+
    \right ]</math>&nbsp;have the same&nbsp;<span class="texhtml">''p''<sub>0&nbsp;</sub>and''&nbsp;p''<sub>1</sub>'''<sub>.&nbsp;</sub>'''</span>  
+
  
<span class="texhtml">'''<sub></sub>'''</span>Therefore, ''P''<sub>''0''</sub> and ''P''<sub>''1''</sub> will be the same for ''X<sub>0</sub>'' and ''X<sub>1</sub>''. We will not be able to recover x<sub><span style="font-size: 11px;">''0''</span></sub>&nbsp;and x<sub><span style="font-size: 11px;">''1''</span></sub>&nbsp;based on ''P''<sub>''0''</sub> and ''P''<sub>''1''</sub>.&nbsp;
+
<span style="color:green"> Also, the question asks for a counter example if the answer is no! </span>
 
+
<br>
+
 
+
<span class="texhtml"><sub></sub></span>  
+
  
 
----
 
----
Line 104: Line 103:
 
=== Related Problem  ===
 
=== Related Problem  ===
  
1.Let <span class="texhtml">''g''(''x'',''y'') = ''s''''i''''n''''c'''''<b>(</b>'''''x'' / 2,''y'' / 2)'''</span>''''', and let &lt;span class="texhtml" /&gt;''s''(''m'',''n'') = ''g''(''''''<i>T</i>,''n''''T'''''<b>) where T = 1.<br> </b>  
+
Consider the 2D discrete space signal&nbsp;<span class="texhtml">''x''(''m'',''n'') with the DSFT of&nbsp;<span class="texhtml">''X''(''e''<sup>''j''μ</sup>,''e''<sup>''j''ν</sup>) given by&nbsp;</span></span>
 +
 
 +
<center>
 +
<math>X(e^{j\mu},e^{j\nu}) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty}
 +
x(m,n)e^{-j(m\mu+n\nu)}</math>  
 +
</center>
 +
 
 +
Then define
 +
<center>
 +
<math>p_{0}(n) = \sum_{m=-\infty}^{\infty}x(m,n)</math><br>
 +
 
 +
<math>p_{1}(m) = \sum_{n=-\infty}^{\infty}x(m,n)</math>
 +
</center>
 +
 
 +
with corresponding DTFT given by&nbsp;
 +
<center>
 +
<math>P_{0}(e^{j\omega}) = \sum_{n=-\infty}^{\infty} p_{0}(n)e^{-jn\omega}</math><br>
 +
 
 +
<math>P_{1}(e^{j\omega}) = \sum_{m=-\infty}^{\infty} p_{0}(m)e^{-jm\omega}</math><br>
 +
</center>
  
a) Calculate <span class="texhtml">''G''(μ,ν)</span> the CSFT of <span class="texhtml">''g''(''x'',''y'')</span>. <br> b) Calculate <span class="texhtml">''S''(''e''<sup>''j''μ</sup>,''e''<sup>''j''ν</sup>)</span> the DSFT of <span class="texhtml">''s''(''m'',''n'')</span>. <br>
+
a) Derive an expression for&nbsp;<span class="texhtml">''P''<sub>0</sub>(''e''<sup>''j''ω</sup>)</span>&nbsp;in terms of&nbsp;<span class="texhtml">''X''(''e''<sup>''j''μ</sup>,''w''<sup>''j''ν</sup>)</span>.  
  
2. Assume that we know (or can measure) the function
+
b) Derive an expression&nbsp;<span class="texhtml">''P''<sub>0</sub>(''e''<sup>''j''ω</sup>)</span>&nbsp;in terms of&nbsp;<span class="texhtml">''X''(''e''<sup>''j''μ</sup>,''e''<sup>''j''ν</sup>)</span>.
  
<math>p(x) = \int_{-\infty}^{\infty}f(x,y)dy</math>  
+
c) Find a function x(m,n) that is not zero everywhere such that <math>{{p}_{0}}(n)={{p}_{1}}(m)=0</math> for all m and n.
  
Using the definitions of the Fourier transform, derive an expressoin for&nbsp;<span class="texhtml">''F''(''u'',0)</span>&nbsp;in terms of the function&nbsp;<span class="texhtml">''p''(''x'')</span>.  
+
d) Do the function&nbsp;<span class="texhtml">''p''<sub>0</sub>(''n'')</span>&nbsp;and&nbsp;<span class="texhtml">''p''<sub>1</sub>(''m'')</span>&nbsp;together contain sufficient information to uniquely reconstruct the function&nbsp;<span class="texhtml">''x''(''m'',''n'')</span>? Justify your answer.
  
(Refer to ECE637 2008 Exam1 Problem2.)  
+
(Refer to <u>[https://engineering.purdue.edu/~bouman/ece637/previous/ece637S2015/exams/exam1/exam.pdf ECE 637 Spring 2015 Exam 1 Problem 2].</u>)  
  
 
----
 
----

Latest revision as of 20:03, 2 May 2017


ECE Ph.D. Qualifying Exam

Communication Networks Signal and Image processing (CS)

Question 5, August 2013(Published on May 2017)

Problem 1,2


Solution 1:

a)

$ {{P}_{0}}({{e}^{j\omega }})=\sum\limits_{n=-\infty }^{\infty }{{{p}_{0}}(n){{e}^{-jn\omega }}}=\sum\limits_{n=-\infty }^{\infty }{\left( \sum\limits_{m=-\infty }^{\infty }{x(m,n)} \right){{e}^{-jn\omega }}}=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-j(m0+n\omega )}}=X({{e}^{j0}},{{e}^{j\omega }})} $

b)

$ {{P}_{1}}({{e}^{j\omega }})=\sum\limits_{m=-\infty }^{\infty }{{{p}_{1}}(m){{e}^{-jm\omega }}}=\sum\limits_{m=-\infty }^{\infty }{\left( \sum\limits_{n=-\infty }^{\infty }{x(m,n)} \right){{e}^{-jm\omega }}}=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-j(m\omega +n0)}}=X({{e}^{j\omega }},{{e}^{j0}})} $

c)

$ \sum\limits_{n=-\infty }^{\infty }{{{p}_{0}}(n)}=\sum\limits_{n=-\infty }^{\infty }{\left( \sum\limits_{m=-\infty }^{\infty }{x(m,n)} \right)}=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-j(m0+n0)}}=X({{e}^{j0}},{{e}^{j0}})} $

d)

No, they don’t. From part (a) and (b), we know that $ {{P}_{0}}({{e}^{jw}}) $ and $ {{P}_{1}}({{e}^{jw}}) $ represent the horizontal and vertical axes of the 2D DSFT $ X({{e}^{j\mu }},{{e}^{j\upsilon }}) $, which is not enough for reconstruction of x(m, n).

For example, $ {{x}_{1}}(m,n)=\left( \begin{matrix} 1 & 3 \\ 2 & 4 \\ \end{matrix} \right),_{{}}^{{}} and\ {{x}_{2}}(m,n)=\left( \begin{matrix} 0 & 4 \\ 3 & 3 \\ \end{matrix} \right) $ have the same $ {{p}_{0}}(n)=\left[ \begin{matrix} 3 & 7 \\ \end{matrix} \right]\ and\ {{p}_{1}}(m)=\left[ \begin{matrix} 4 \\ 6 \\ \end{matrix} \right] $. So, x(m,n) can’t be reconstructed from $ {{p}_{0}}(n)\ and\ {{p}_{1}}(m) $.

Solution 2:

a)

$ {{P}_{0}}({{e}^{j\omega }})=\sum\limits_{n=-\infty }^{\infty }{\sum\limits_{m=-\infty }^{\infty }{x(m,n)} {{e}^{-jn\omega }}}=X({{e}^{j0}},{{e}^{j\omega }}) $

The answer is correct, but multiple steps are skipped in this solution, which are necessary for clarity. (See Solution 1)

b)

$ {{P}_{1}}({{e}^{j\omega }})=\sum\limits_{m=-\infty }^{\infty }{\sum\limits_{n=-\infty }^{\infty }{x(m,n)}{{e}^{-jm\omega }}}=X({{e}^{j\omega }},{{e}^{j0}}) $

The answer is correct, but multiple steps are skipped in this solution, which are necessary for clarity. (See Solution 1)

c)

$ \sum\limits_{n=-\infty }^{\infty }{{{p}_{0}}(n)}=\sum\limits_{n=-\infty }^{\infty }{\sum\limits_{m=-\infty }^{\infty }{x(m,n)}=X({{e}^{j0}},{{e}^{j0}})} $

The answer is correct, but multiple steps are skipped in this solution, which are necessary for clarity. (See Solution 1)

d)

They do not; $ {{p}_{0}}(n)\ and\ {{p}_{1}}(m) $ are projections at two angles, and do not contain enough information to reconstruct x(m,n).

Sol2 2013 1d 1.jpg

$ \begin{align} & X({{e}^{j\mu }},{{e}^{j\upsilon }})=\sum\limits_{m=-\infty }^{\infty }{\left[ \sum\limits_{n=-\infty }^{\infty }{x(m,n)} \right]}{{e}^{-jm\mu }}{{e}^{-jn\upsilon }} \\ & X({{e}^{j\mu }},{{e}^{j\upsilon }})\ne \sum\limits_{m=-\infty }^{\infty }{{{p}_{1}}(m)}{{e}^{-jm\mu }}{{e}^{-jn\upsilon }}\ne {{P}_{1}}({{e}^{j\mu }}){{e}^{-jn\upsilon }} \\ & \Rightarrow Can't\ do\ it! \end{align} $


- To form reconstruction, need projections along many angles.

- Could reconstruct a very simple object, like triangle.

Sol2 2013 1d 2.jpg

In the first figure, the projection of x(m,n) along the vertical axis is $ {{p}_{1}}(m)\ $, not $ \ {{p}_{0}}(m) $.

In the second line of equations, $ = $ must be used instead of $ \ne $.

Also, the question asks for a counter example if the answer is no!


Related Problem

Consider the 2D discrete space signal x(m,n) with the DSFT of X(ejμ,ejν) given by 

$ X(e^{j\mu},e^{j\nu}) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} x(m,n)e^{-j(m\mu+n\nu)} $

Then define

$ p_{0}(n) = \sum_{m=-\infty}^{\infty}x(m,n) $

$ p_{1}(m) = \sum_{n=-\infty}^{\infty}x(m,n) $

with corresponding DTFT given by 

$ P_{0}(e^{j\omega}) = \sum_{n=-\infty}^{\infty} p_{0}(n)e^{-jn\omega} $

$ P_{1}(e^{j\omega}) = \sum_{m=-\infty}^{\infty} p_{0}(m)e^{-jm\omega} $

a) Derive an expression for P0(ejω) in terms of X(ejμ,wjν). 

b) Derive an expression P0(ejω) in terms of X(ejμ,ejν).

c) Find a function x(m,n) that is not zero everywhere such that $ {{p}_{0}}(n)={{p}_{1}}(m)=0 $ for all m and n.

d) Do the function p0(n) and p1(m) together contain sufficient information to uniquely reconstruct the function x(m,n)? Justify your answer.

(Refer to ECE 637 Spring 2015 Exam 1 Problem 2.)


Back to ECE QE page:

Alumni Liaison

Followed her dream after having raised her family.

Ruth Enoch, PhD Mathematics