Week 13

\begin{claim}
if a signal is real-valued, then its fourier transform is conjugate symmetric. In other words, 

$$ x(n) \in \R \mbox{ } \forall n \Rightarrow X(\omega) = X^*(\omega) $$

\end{claim}

\begin{proof}
We can use the definition of the fourier transform of a signal $x(n)$:
\begin{align*}
X(\omega) &= \sum \limits_{n=-\infty}^{\infty} x(n) e^{-i\omega n} \\
X(-\omega) &= \sum \limits_{n=-\infty}^{\infty} x(n) e^{i\omega n} \\
X^*(-\omega) &= \sum \limits_{n=-\infty}^{\infty} x^*(n) e^{-i\omega n} \\
X^*(-\omega) &= \sum \limits_{n=-\infty}^{\infty} x(n) e^{-i\omega n} \quad \mbox{since $x(n)$ is real} \\
X^*(-\omega) &= X(\omega) \\
\end{align*}

Here is a more simplistic proof that uses the fact that $\ftrans{x^*(n)} = X^*(-\omega)$:

\begin{align*}
x(n) &\ftp X(\omega) \\
x^*(n) &\ftp X^*(\omega) \\
x(n) &\ftp X^*(\omega) \\
\end{align*}

\end{proof}

This implies that the frequency response is equal to its conjugate (for real-valued signals $x(n)$):

\begin{nicebox}
$$x \in \left[ \Z \to \R \right]$$ 
$$\Rightarrow  $$
$$X(\omega) = X^*(\omega)$$
\end{nicebox}

Conjugate Symmetry

\begin{claim}
If $x(n)$ is a real-valued signal of an even function, then its fourier transform is even and real-valued. In other words, 

\begin{nicebox}
$$x \in \left[ \Z \to \R \right]  \mbox{ AND } x(n) = x(-n) \mbox{ } \forall n$$
$$\Rightarrow$$
$$X(-\omega) = X(\omega) \mbox{ AND } X \in \left[ \R \to \R \right]$$
\end{nicebox}

\end{claim}

To show that the frequency response is odd, we show that $X(\omega) = X(-\omega)$. To show that the frequency response is real-valued, we need to show that the conjugate of the frequency response is equal to the frequency response, namely $X(\omega) = X^*(\omega)$

\begin{proof}

First show that the frequency response is even by noting some properties of the DTFT:
\begin{align*}
x(n) &\ftp X(\omega) \\
x(-n) &\ftp X(-\omega) \\
\end{align*}

Putting it all together,

\begin{align*}
x(n) &= x(-n) \\
\ftrans{x(n)} &= \ftrans{x(-n)} \\
X(\omega) &= X(-\omega)
\end{align*}

Now to show that the frequency response is real, we simply note that $X(\omega) = X^*(-\omega)$ because $x$ is real-valued, then 
\begin{align*}
X(-\omega) &= X(\omega) = X^*(-\omega) = X^*(\omega) \\
X(\omega) &= X^*(\omega) \\
\Rightarrow X(\omega) &\in \R \mbox{ } \forall \omega
\end{align*}

\end{proof}

Now we make make the general claim that the fourier transform of a real-valued even signal is equal to the real part of the signal's frequency response:

\begin{align*}
\ftrans{\frac{x(n) + x(-n)}{2}} &= \Real{\frac{X(\omega)+X(-\omega)}{2}} \\
\ftrans{x_e(n)} &= \Real{\frac{1}{2}X(\omega)+\frac{1}{2}X(-\omega)} \\
\ftrans{x_e(n)} &= \Real{\frac{1}{2}X(\omega)+\frac{1}{2}X(\omega)} \quad \mbox{since } X(\omega) = X(-\omega) \\
\ftrans{x_e(n)} &= \Real{X(\omega)} \\
\end{align*}

\begin{nicebox}
$$x \in \left[ \Z \to \R \right] $$
$$\Rightarrow$$
$$x_e(n) \ftp \Real{X(\omega)} $$
\end{nicebox}


Signals of Even Functions

\begin{claim}

If $x(n)$ is a real-valued signal of an odd function, then its fourier transform is odd and imaginary. In other words, 

\begin{nicebox}
$$x \in \left[ \Z \to \R \right] \mbox{ AND } x(n) = -x(-n) \mbox{ } \forall n$$
$$\Rightarrow$$
$$-X(-\omega) = X(\omega) \mbox{ AND } X \in \left[\R \to i\cdot\R \right]$$
\end{nicebox}

\end{claim}


To show that the frequency response is odd, we need to show $X(\omega) = -X(-\omega)$. To show that the frequency response is purely imaginary, we need to show that the frequency response is equal to the negative of the conjugate of the frequency response, namely $X(\omega) = -X^*(\omega)$.


\begin{proof}

First show that the frequency response is odd by noting some properties of the DTFT:
\begin{align*}
x(n) &\ftp X(\omega) \\
x(-n) &\ftp X(-\omega) \\
-x(-n) &\ftp -X(-\omega) \\
\end{align*}

Putting it all together,

\begin{align*}
x(n) &= -x(-n) \\
\ftrans{x(n)} &= \ftrans{-x(-n)} \\
X(\omega) &= -X(-\omega)
\end{align*}

Now we can use conjugate symmetry to show that the frequency response is imaginary. This means that if $x$ is real-valued, then $X(\omega) = X^*(\omega)$. 

\begin{align*}
X(\omega) &= -X(-\omega) \quad \mbox{since $X$ is odd}\\
X(\omega) &= X^*(-\omega) \quad \mbox{since $x$ is real}\\
X^*(-\omega) &= -X(-\omega) \\
X^*(\omega) &= -X(\omega) \\
\end{align*}

\end{proof}

Here is a more rigorous proof:

\begin{proof}

To show that the frequency response is odd:

\begin{align*}
X(\omega) &= \sum \limits_{n=-\infty}^{\infty}x(n)e^{-i\omega n} \\
X(\omega) &= \sum \limits_{m=-\infty}^{\infty}x(-m)e^{i\omega m} \quad \mbox{let }m=-n \\
X(\omega) &= -\sum \limits_{m=-\infty}^{\infty}x(m)e^{i\omega m} \quad \mbox{since $x$ is odd} \\
X(\omega) &= -X(-\omega) \\
\end{align*}

To show that the frequency response is purely imaginary:

\begin{align*}
X(\omega) &= \sum \limits_{n=-\infty}^{\infty}x(n)e^{-i\omega n} \\
X(\omega) &= \sum \limits_{m=-\infty}^{\infty}x(-m)e^{i\omega m} \quad \mbox{let }m=-n \\
X^*(\omega) &= \sum \limits_{m=-\infty}^{\infty}x^*(-m)e^{-i\omega m} \\
X^*(\omega) &= \sum \limits_{m=-\infty}^{\infty}x(-m)e^{-i\omega m} \quad \mbox{since $x$ is real-valued}\\
X^*(\omega) &= -\sum \limits_{m=-\infty}^{\infty}x(m)e^{-i\omega m} \quad \mbox{since $x$ is odd}\\
X^*(\omega) &= -X(\omega)\\
\end{align*}

Since the frequency response is equal to the negative of its conjugate, it is purely imaginary. 

\end{proof}


Now we make make the general claim that the fourier transform of a real-valued odd signal is equal to the product of $i$ and the imaginary part of the signal's frequency response:

\begin{align*}
\ftrans{\frac{x(n) - x(-n)}{2}} &= i\Imag{\frac{X(\omega)-X(-\omega)}{2}} \\
\ftrans{x_o(n)} &= i\Imag{\frac{1}{2}X(\omega)-\frac{1}{2}X(-\omega)} \\
\ftrans{x_o(n)} &= i\Imag{\frac{1}{2}X(\omega)+\frac{1}{2}X(\omega)} \quad \mbox{since } X(\omega) = -X(-\omega) \\
\ftrans{x_o(n)} &= i\Imag{X(\omega)} \\
\end{align*}


\begin{nicebox}
$$x \in \left[ \Z \to \R \right]$$
$$\Rightarrow$$
$$x_o(n) \ftp i\Imag{X(\omega)} $$
\end{nicebox}


Signals of Odd Functions

\begin{example}

Given $x_e(n) = \frac{1}{2}\lr{x(n) + x(-n)}$, prove that $\Real{X(\omega)} = \frac{1}{2}\lr{X(\omega) + X^*(\omega)}$.


\begin{align*}
x(n) &\ftp X(\omega) \\
\frac{1}{2}x(n) &\ftp \frac{1}{2}X(\omega) \\
\frac{1}{2}x(-n) &\ftp \frac{1}{2}X(-\omega) \\
\end{align*}

We showed that if a signal is even, then its fourier transform is also even and purely real. This implies that the inverse fourier transform of the real part a frequency response is the even part of the signal. In other words,

\begin{align*}
\iftrans{\Real{X(\omega)}} &= x_e(n) \\
\Real{X(\omega)} &= \ftrans{x_e(n)} \\
\end{align*}


Also note that if $x$ is real, then we can use the conjugate symmetric property, $X(\omega) = X^*(-\omega)$. 
\begin{align*}
x_e &= \frac{1}{2}\lr{x(n) + x(-n)} \\
\ftrans{x_e} &= \ftrans{\frac{1}{2}\lr{x(n) + x(-n)}} \\
\ftrans{x_e} &= \frac{1}{2}\ftrans{x(n)} + \frac{1}{2}\ftrans{x(-n)} \\
\ftrans{x_e} &= \frac{1}{2}X(\omega) + \frac{1}{2}X(-\omega) \\
\ftrans{x_e} &= \frac{1}{2}X(\omega) + \frac{1}{2}X^*(\omega) \\
\end{align*}

\end{example}


\begin{example}
Given $x_o(n) = \frac{1}{2}\lr{x(n) - x(-n)}$, prove that $\Imag{X(\omega)} = \frac{1}{2}\lr{X(\omega) - X^*(\omega)}$.


\begin{align*}
x(n) &\ftp X(\omega) \\
\frac{1}{2}x(n) &\ftp \frac{1}{2}X(\omega) \\
\frac{1}{2}x(-n) &\ftp \frac{1}{2}X(-\omega) \\
\end{align*}

We showed that if a signal is odd, then its fourier transform is also odd and purely imaginary. This implies that the inverse fourier transform of the product of $i$ and the imaginary part a frequency response is the odd part of the signal. In other words,

\begin{align*}
\iftrans{i\Imag{X(\omega)}} &= x_o(n) \\
i\Imag{X(\omega)} &= \ftrans{x_o(n)} \\
\end{align*}


Also note that if $x$ is real, then we can use the conjugate symmetric property, $X(\omega) = X^*(-\omega)$. 
\begin{align*}
x_o &= \frac{1}{2}\lr{x(n) - x(-n)} \\
\ftrans{x_o} &= \ftrans{\frac{1}{2}\lr{x(n) - x(-n)}} \\
\ftrans{x_o} &= \frac{1}{2}\ftrans{x(n)} - \frac{1}{2}\ftrans{x(-n)} \\
\ftrans{x_o} &= \frac{1}{2}X(\omega) - \frac{1}{2}X(-\omega) \\
\ftrans{x_o} &= \frac{1}{2}X(\omega) - \frac{1}{2}X^*(\omega) \\
\end{align*}

\end{example}

\begin{example}
For a signal $x(n) \in \R $ $ \forall n$, given the following facts, determine $x(n)$.
\begin{align*}
(1)& \quad x(n) = 0 \quad \forall n \gt 0 \\
(2)& \quad x(0) \gt 0 \\
(3)& \quad \Imag{X(\omega)} = \sin(\omega) - \sin(2\omega)\\
(4)& \quad \frac{1}{2\pi} \int_{-\pi}^{\pi}\abs{X(\omega)}^2d\omega=3 \\
\end{align*}

Note that Parseval's Relation for Aperiodic signals is:
$$ \sum \limits_{n\in\Z}\abs{x(n)}^2 = \frac{1}{2\pi} \int_{-\pi}^{\pi}\abs{X(\omega)}^2d\omega$$

Start with the third fact:
\begin{align*}
\Imag{X(\omega)} &= \sin(\omega) - \sin(2\omega) \\
i\Imag{X(\omega)} &= i\lr{\sin(\omega) - \sin(2\omega)} \\
\ftrans{x_o(n)} &= i\lr{\sin(\omega) - \sin(2\omega)} \\
\ftrans{x_o(n)} &= i\lr{\frac{1}{2i}e^{i\omega}-\frac{1}{2i}e^{-i\omega}-\frac{1}{2i}e^{i2\omega}+\frac{1}{2i}e^{-i2\omega}} \\
\ftrans{\frac{x(n)-x(-n)}{2}} &= i\lr{\frac{1}{2i}e^{i\omega}-\frac{1}{2i}e^{-i\omega}-\frac{1}{2i}e^{i2\omega}+\frac{1}{2i}e^{-i2\omega}} \\
\frac{1}{2}\ftrans{x(n)} - \frac{1}{2}\ftrans{x(-n)}&= \frac{1}{2}\lr{e^{i\omega}-e^{-i\omega}-e^{i2\omega}+e^{-i2\omega}} \\
\ftrans{x(n)} - \ftrans{x(-n)}&= \lr{e^{i\omega}-e^{-i\omega}-e^{i2\omega}+e^{-i2\omega}} \\
\end{align*}

How can we eliminate the $x(-n)$? Lets consider $\forall n \lt 0$, so $x(-n) = 0$:

\begin{align*}
\ftrans{x(n)} - \ftrans{x(-n)}&= \lr{e^{i\omega}-e^{-i\omega}-e^{i2\omega}+e^{-i2\omega}} \\
\ftrans{x(n)} &= \lr{e^{i\omega}-e^{-i\omega}-e^{i2\omega}+e^{-i2\omega}} \\
x(n) &= \iftrans{e^{i\omega}-e^{-i\omega}-e^{i2\omega}+e^{-i2\omega}} \\
x(n) &= \delta(n+1)-\delta(n-1)-\delta(n+2)+\delta(n-2) \\
\end{align*}

But notice that $\delta(n-1)$ and $\delta(n-2)$ are out of range. This is because $\delta(n-1)$ doesn't make sense $\forall n \lt 0$ since $n$ here must be 1 for $\delta(n-1$ to equal 1. The same is true for $\delta(n-2)$ since 2 is not in the domain. Now we can continue by taking those terms out of the equation:
\begin{align*}
x(n) &= \delta(n+1)-\delta(n-1)-\delta(n+2)+\delta(n-2) \\
x(n) &= \delta(n+1)-\delta(n+2) \\
\end{align*}

Now we can use the fourth fact, $\frac{1}{2\pi} \int_{-\pi}^{\pi}\abs{X(\omega)}^2d\omega=3$, in combination with Parseval's relation. 

\begin{align*}
\frac{1}{2\pi} \int_{-\pi}^{\pi}\abs{X(\omega)}^2d\omega &= 3 \\
\sum \limits_{n\in\Z}\abs{x(n)}^2 &= 3 \\
\sum \limits_{n=-\infty}^{0}\abs{x(n)}^2 &= 3 \\
\sum \limits_{n=-\infty}^{-1}\abs{x(n)}^2 + \abs{x(0)}^2 &= 3 \\
\abs{x(-2)}^2 + \abs{x(-1)}^2 + \abs{x(0)}^2 &= 3 \\
2 + \abs{x(0)}^2 &= 3 \\
\abs{x(0)}^2 &= 1 \\
x(0) &= 1 \quad \mbox{because of (2)}\\
\end{align*}

We know that this implies $\delta(n)$ since we have 1 at 0. Therefore our signal is $x(n) = \delta(n) + \delta(n+1)-\delta(n+2)$.

\end{example}


13.3 Discussion