
Recall the DTFT equations:

\begin{nicebox}
\begin{align*}
x(n) &= \frac{1}{2\pi} \int_{\langle 2\pi\rangle } X(\omega)e^{i\omega n}d\omega \quad &\mbox{(synthesis equation)} \\
X(\omega) &= \sum \limits_{n=-\infty}^{\infty}x(n)e^{-i\omega n} \quad &\mbox{(analysis equation)}
\end{align*}
\end{nicebox}

\begin{example}
1) Find the DTFT for the signal $x(n) = 1 $ $ \forall n$

\begin{align*}
x(n) &= \frac{1}{2\pi} \int_{\langle 2\pi\rangle } X(\omega)e^{i\omega n}d\omega  \\
1 &= \frac{1}{2\pi} \int_{\langle 2\pi\rangle } X(\omega)e^{i\omega n}d\omega  \\
e^{i\omega 0} &= \frac{1}{2\pi} \int_{\langle 2\pi\rangle } X(\omega)e^{i\omega n}d\omega  \\
e^{i\omega 0} &= \frac{1}{2\pi} \int_{\langle 2\pi\rangle } A\delta(\omega)e^{i\omega n}d\omega  \\
e^{i\omega 0} &= \frac{1}{2\pi} Ae^{i\omega 0} \\
1 &= \frac{1}{2\pi} A \\
A &= 2\pi \\
\end{align*}

Hence, $X(\omega) = 2\pi\delta(\omega)$ for $\abs{\omega} \lt \pi$, or $X(\omega) = 2\pi\sum\limits_{k\in\Z}\delta(w-2\pi k)$. Lets take this a little further, utilizing the analysis equation:

\begin{align*}
X(\omega) &= \sum \limits_{n=-\infty}^{\infty}x(n)e^{-i\omega n} \\
X(\omega) &= \sum \limits_{n=-\infty}^{\infty}e^{-i\omega n} \quad \mbox{let }x(n) = 1 \\
X(\omega) &= \sum \limits_{n=-\infty}^{\infty}e^{-i\omega n} = 2\pi\sum\limits_{k\in\Z}\delta(w-2\pi k) \\
\end{align*}

Hence we have the relation known as \emph{Poisson's Identity}:

$$
\sum \limits_{n\in\Z}e^{-i\omega n} = 2\pi\sum\limits_{k\in\Z}\delta(w-2\pi k) \\
$$

Notice that the left side is a continuous function where the right side is of discrete dirac deltas. Hence, the equality is not pointwise, but more that both representations treat other functions the same way when they come into contact. This relationship is not consistent with our intuition and therefore must be derived.

\end{example}

\begin{example}

2) Find the DTFT of the signal $x(n)=\sin(2\pi n/3)$.

\begin{align*}
x(n) &= \sin(2\pi n/3) \\
x(n) &= \frac{1}{2i}e^{i2\pi n/3} - \frac{1}{2i}e^{-i2\pi n/3} \\
\ftrans{x(n)} &= \ftrans{\frac{1}{2i}e^{i2\pi n/3}} - \ftrans{\frac{1}{2i}e^{-i2\pi n/3}} \\
\end{align*}

Now since the DTFT in linear, we can look at these individually. Consider an arbitrary complex exponential:

\begin{align*}f(n) &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle }F(\omega)e^{i\omega n}d\omega \\
Re^{i\omega_0 n} &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle }A\delta(\omega - \omega_0)e^{i\omega n}d\omega \\
Re^{i\omega_0 n} &= \frac{1}{2\pi}Ae^{i\omega_0 n} \\
R &= \frac{1}{2\pi}A \\
A &= 2\pi R \\
\end{align*}

This shows that $F(\omega) = 2\pi R \delta(\omega - \omega_0)$:

\begin{nicebox}
$$
Re^{i\omega} \ftp 2\pi R \delta(\omega - \omega_0)
$$
\end{nicebox}

So in our case we can use the derived formula to find the coefficients:
\begin{align*}
\ftrans{x(n)} &= \ftrans{\frac{1}{2i}e^{i2\pi n/3}} - \ftrans{\frac{1}{2i}e^{-i2\pi n/3}} \\
X(\omega) &= \frac{\pi}{i}\delta(\omega - 2\pi n/3) - \frac{\pi}{i}\delta(\omega + 2\pi n/3) \\
\end{align*}

Remember that we have to restrict our domain of $\omega$ to $\abs{\omega} \lt \pi$ for the equation to hold.

\end{example}

DTFT of Complex Exponentials

We know the following pairs:
\begin{align*}
x(n) &\ftp X(\omega) \\
y(n) &\ftp Y(\omega)
\end{align*}

What is the transform of $x(n)y(n)$? It may seem that multiplication in the time domain corresponds to convolution in the frequency domain, but there are issues with the $2\pi$ periodicity of the frequency response. So we do not use ordinary convolution.

\begin{align*}
\mbox{let } q(n) = x(n)y(n) \\
Q(\omega) &= \sum \limits_{n\in\Z}x(n)y(n)e^{-i\omega n} \\
Q(\omega) &= \sum \limits_{n\in\Z}\lr{\frac{1}{2\pi}\int_{\langle 2\pi\rangle}X(\lambda)e^{i\lambda n}d\lambda}y(n)e^{-i\omega n} \\
Q(\omega) &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) \lr{\sum \limits_{n\in\Z}y(n)e^{i\lambda n}e^{-i\omega n}}d\lambda \\
Q(\omega) &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) \lr{\sum \limits_{n\in\Z}y(n) e^{-i(\omega-\lambda) n}} d\lambda \\
Q(\omega) &= \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) Y(\omega - \lambda) d\lambda \\
\end{align*}

Thus, the fourier transform pair is:

\begin{nicebox}
$$
x(n)y(n) \ftp \frac{1}{2\pi}\int_{\langle 2\pi\rangle} X(\lambda) Y(\omega - \lambda) d\lambda 
$$
\end{nicebox}

So we can define this result as \emph{circular convolution}:

\begin{nicebox}
$$
(X \circconv Y)(\omega) = \int_{\langle 2\pi\rangle} X(\lambda) Y(\omega - \lambda) d\lambda 
$$
\end{nicebox}

Do not confuse this with regular convolution: 
\begin{nicebox}
$$
(X * Y)(\omega) = \int_{\R} X(\lambda) Y(\omega - \lambda) d\lambda 
$$
\end{nicebox}

We use ordinary convolution with non-periodic functions and circular convolution with periodic functions. How can we solve a circular convolution?

\begin{enumerate}
\item Keep on function as it is.
\item Restrict the other function to one period
\item Perform a normal convolution
\item Divide by $2\pi$ (if necessary as in above example)
\end{enumerate}

\begin{example}

1) Consider the two following $2\pi$-periodic frequency responses:

% \img{images/boxes/circularconv/a/boxes.ps}
% \img{images/boxes/circularconv/b/boxes.ps}


How would we perform a circular convolution? Limit $Y(\lambda)$ to one period and then perform a single convolution.

% \img{images/boxes/circularconv/b/oneperiod/boxes.ps}

\end{example}

\begin{example}

2) Lets look at an example of DT amplitude modulation. This system takes in $x(n)$ and multiplies it by $y(t)$:

% \img{images/modulators/dtampmod/am.ps}

\begin{center}
\begin{pspicture}(-3,-3)(3,3)

% in from x
\rput(-3.2,0){$x(n)$}
\psline[linewidth=1.25 pt, arrowscale=1.1]{->}(-2.7,0)(-0.25,0)
% out to y
\rput(4.25,0){$q(n)=x(n)y(n)$}
\psline[linewidth=1.25 pt, arrowscale=1.1]{->}(0.25,0)(2.7,0)
% up arrow
\rput(0,-2){$y(n)=e^{i\omega_0 n}$}
\psline[linewidth=1.25 pt, arrowscale=1.1]{->}(0,-1.65)(0,-0.25)

% multiplier
\pscircle(0,0){0.25}
\psline(-0.175,0.175)(0.175,-0.175)
\psline(0.175,0.175)(-0.175,-0.175)

% box
\pspolygon(-1.5,-2.65)(-1.5,1)(1.5,1)(1.5,-2.65)

\end{pspicture}
\end{center}

$y(n) = e^{i\omega_0 n}$, and $x(n)$ is defined by its frequency response, $X(\lambda)$, which is shown below:

% \img{images/boxes/circularconv/a/simple/boxes.ps}

$Y(\lambda)$ can be shown to be an infinite impulse train, such that when limited for our circular convolution method, we have a single dirac delta:

% \img{images/pulsetrains/diracs/freq/yomega.ps}
% \img{images/pulsetrains/diracs/freq/limited.ps}

Now we perform regular convolution. Any time we convolve a signal with a single dirac at a particular frequency, we simple shift the signal such that it is centered at that frequency:

% \img{images/boxes/circularconv/a/convolved/boxes.ps}

This is equal to $\frac{1}{2\pi}\int_{\langle 2\pi\rangle}x(\lambda)Y(\omega - \lambda)d\lambda = \lr{X \circconv Y }\lr{\omega}$.

\end{example}

Circular Convolution

We define the continuous-time fourier transform pair as:

\begin{nicebox}
\begin{align*}
x(t) &= \frac{1}{2\pi}\int_{-\infty}^{\infty}X(\omega)e^{i\omega t}d\omega \quad &\mbox{(synthesis equation)} \\
X(\omega) &= \int_{-\infty}^{\infty}x(t)e^{-i\omega t}dt \quad &\mbox{(analysis equation)}
\end{align*}
\end{nicebox}

Neither $x(t)$ or $X(\omega)$ has to be periodic.

\begin{example}

1) If $x(t) = \begin{cases} B & t<\abs{A} \\ 0 & \mbox{otherwise} \\ \end{cases}$, what is $\ftrans{x(t)}$?

\begin{align*}
X(\omega) &= \int_{-\infty}^{\infty} x(t) e^{-i\omega t}dt \\
X(\omega) &= B\int_{-A}^{A} e^{-i\omega t}dt \\
X(\omega) &= B\left. \frac{e^{-i\omega t}}{-i\omega} \right|_{-A}^{A} \\
X(\omega) &= B\frac{e^{i\omega A} - e^{-i\omega A}}{i\omega} \\
X(\omega) &= \frac{2B\sin(\omega A)}{\omega} \\
\end{align*}

Note that $\lim_{\omega \to 0} \frac{2B\sin(\omega A)}{\omega} = \lim_{\omega \to 0} \frac{2AB\cos(\omega A)}{1} = 2AB$ by L'Hopital's Rule.

%\img{images/sinc/timedomain/new.ps}

Also note that $\lim_{A \to \infty} X(\omega) = \delta(\omega)$.

\end{example}


\begin{example}

2) If $x$ is $p$-periodic, then
\begin{align*}
x(t) &= \sum_{k\in\Z}X_ke^{ik\omega_0 t} \\
e^{i\omega_0 t} &\ftp 2\pi \delta(\omega - \omega_0)
\end{align*}

We can find $X(\omega)$:

\begin{align*}
X(\omega) &= \int_{-\infty}^{\infty} x(t) e^{-i\omega t}dt \\
X(\omega) &= \int_{-\infty}^{\infty} \lr{\sum_{k\in\Z}X_ke^{ik\omega_0 t}}  e^{-i\omega t}dt \\
X(\omega) &= \sum_{k\in\Z} X_k \int_{-\infty}^{\infty} e^{ik\omega_0 t}  e^{-i\omega t}dt \\
X(\omega) &= \sum_{k\in\Z} X_k \ftrans{ e^{ik\omega_0 t} } \\
X(\omega) &= \sum_{k\in\Z} X_k 2\pi\delta(\omega - k\omega_0) \\
\end{align*}

This tells us that we have an amount $X_k$ of frequency $k\omega_0$:
$$
X(\omega) = \sum_{k\in\Z} X_k 2\pi\delta(\omega - k\omega_0) 
$$

\end{example}

5 Week 5