(26 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 10: Line 14:
 
== Solution 1:  ==
 
== Solution 1:  ==
  
a) <math>
+
a)  
 +
 
 +
<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>
 +
 
 +
b)
  
b) <math>
+
<math>
 
{{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}})}
 
{{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>
 
</math>
  
<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>
+
c)  
  
c) <br> <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}})}
+
\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}})}
 
</math>  
 
</math>  
  
d) 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).
+
d)  
 +
 
 +
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).
 +
 
 
For example,  <math>{{x}_{1}}(m,n)=\left( \begin{matrix}
 
For example,  <math>{{x}_{1}}(m,n)=\left( \begin{matrix}
 
   1 & 3  \\
 
   1 & 3  \\
 
   2 & 4  \\
 
   2 & 4  \\
\end{matrix} \right),_{{}}^{{}}and_{{}}^{{}}{{x}_{2}}(m,n)=\left( \begin{matrix}
+
\end{matrix} \right),_{{}}^{{}} and\ {{x}_{2}}(m,n)=\left( \begin{matrix}
 
   0 & 4  \\
 
   0 & 4  \\
 
   3 & 3  \\
 
   3 & 3  \\
Line 34: Line 45:
 
have the same <math>{{p}_{0}}(n)=\left[ \begin{matrix}
 
have the same <math>{{p}_{0}}(n)=\left[ \begin{matrix}
 
   3 & 7  \\
 
   3 & 7  \\
\end{matrix} \right]_{{}}^{{}}and_{{}}^{{}}{{p}_{1}}(m)=\left[ \begin{matrix}
+
\end{matrix} \right]\ and\ {{p}_{1}}(m)=\left[ \begin{matrix}
 
   4  \\
 
   4  \\
 
   6  \\
 
   6  \\
\end{matrix} \right]</math>. So, x(m,n) can’t be reconstructed from <math>{{p}_{0}}(n)=\left[ \begin{matrix}
+
\end{matrix} \right]</math>. So, x(m,n) can’t be reconstructed from <math>{{p}_{0}}(n)\ and\ {{p}_{1}}(m)</math>.
  3 & 7  \\
+
\end{matrix} \right]_{{}}^{{}}and_{{}}^{{}}{{p}_{1}}(m)=\left[ \begin{matrix}
+
  4  \\
+
  6  \\
+
\end{matrix} \right]</math>.
+
  
 
== Solution 2:  ==
 
== Solution 2:  ==
  
a) <math>
+
a)  
 +
 
 +
<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 }})
 
{{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><br>
 
 
b) <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>
  
 +
<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>
  
 +
b)
  
<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>
+
<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>
  
 +
<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>
  
 
c)  
 
c)  
  
c) <br> <math>
+
<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}})
+
\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>
+
</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>.
+
<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>
  
<span style="color:green"> Similarly to the above comment, <math>P_0(e^{jw}) </math>is the slice along <math>\nu </math> axis. </span>
+
d)
  
For example, assume two different array x''<sub>1</sub>'' and x''<sub>2</sub>''.
+
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>x_1 = \left [
 
    \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;
+
- To form reconstruction, need projections along many angles.
  
<br>
+
- Could reconstruct a very simple object, like triangle.
 +
[[File:sol2_2013_1d_2.jpg|thumbnail|center]]
  
<span class="texhtml"><sub></sub></span>  
+
<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>
 +
 
 +
<span style="color:green"> In the second line of equations, <math>=</math> must be used instead of <math>\ne</math>. </span>
 +
 
 +
<span style="color:green"> Also, the question asks for a counter example if the answer is no! </span>
  
 
----
 
----
Line 93: 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 21: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

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

Dr. Paul Garrett