Sunday, July 10, 2011

Fourier Integral and Periodic Functions

Consider a function $f(t)$, sufficiently well-behaved such that

\begin{align}
f(t) = &\int_{-\infty}^{\infty} {F(\omega) e^{i \omega t} d{\omega }}\\
F(\omega) = \frac 1 {2 \pi} &\int_{-\infty}^{\infty}{f(t) e^{-i \omega t} dt} 
\end{align}

Periodic Function


What does the transform $F(\omega)$ look like for a periodic function?  Let $f(t)$ be periodic: $f(t)$ = $ \sum_n {f_0(t-nT) } $  where $f_0$ is a time-limited function defined over the interval $[0, T]$.

Compute $F(\omega)$:

\begin{align}

F(\omega) &= \frac 1 {2 \pi} \int_{-\infty}^{\infty}{ \sum_{n=-\infty}^{\infty} f_0(t-nT) e^{-i \omega t} {dt} }\\

 &= \sum_{n=-\infty}^{\infty} \frac 1 {2 \pi} \int_{-\infty}^{\infty}{  f_0(t-nT) e^{-i \omega t} {dt} } \\

 &= \sum_{n=-\infty}^{\infty} \frac 1 {2 \pi} \int_{-\infty}^{\infty}{  f_0(t) e^{-i \omega t}e^{-i \omega nT} {dt}} \\

 &= \bbox[ border:2px solid yellow ]{\left( \sum_{n=-\infty}^{\infty} e^{-i \omega nT} \right)}  \bbox[ border:2px solid cyan]{\left(   \frac 1 {2 \pi} \int_0^T{  f_0(t) e^{-i \omega t}{dt} } \right)}

\end{align}


The yellow box is  ${\Omega} \sum_{n=-\infty}^{\infty} \delta (\omega-n \Omega)$, where $\Omega = \frac {2 \pi} T$

So we end up with
\begin{align*}
F(\omega) &= \Omega \sum_{n=-\infty}^{\infty} \delta (\omega-n \Omega)  F_0(\omega) \\
&= \Omega \sum_{n=-\infty}^{\infty} \delta (\omega-n \Omega)  F_0(n \Omega)
\end{align*}

$F(\omega)$ is just a sampled version of the transform of $f_0(t)$.

Sampled Function


Working the other way now, let's transform a sampled function.

Let $F$ be the transform of $f$:

$$
F(k) =   \frac 1 {2 \pi} \int_{-\infty}^{\infty}{f(x) e^{-i k x} dx}
$$
$f(x)$ is a sampled version of $g(x)$: 
$$
f(x) = \sum_{n=-\infty}^{\infty} \delta(x - nL) g(x)
$$

The result is immediate:
$$
F(k) =  \frac 1 {2 \pi} \int_{-\infty}^{\infty}{  \left(  \sum_{n=-\infty}^{\infty} \delta(x - nL) \right) g(x)  e^{-i k x} dx}
$$

This looks like a transform of a product, which resolves to a convolution product of the individual transforms. Since $\sum_{n=-\infty}^{\infty} \delta(x - nL) \iff   \bbox[ border:2px solid yellow ]{\frac {\Omega} {2 \pi}  \sum_ {n=-\infty}^{\infty}\delta(k - n\Omega)}$, we can write

\begin{align}
F(k)  &=  \int_{-\infty}^{\infty} {  \left(  \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty} \delta(k - k^{'} - n\Omega) \right) G(k^{'})  dk^{'} } \label{ISI} \\
&=  \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty}  G(k - n \Omega)
\end{align}

This is a set of shifted copies of the transform of $g$, which might be a mess unless $g$ is zero outside the interval controlled by the sample rate $\Omega$.  Although, we will return to this later with an interesting example of when the overlap works out nicely.

Periodic, Sampled Function


Finally, let's work out the transform of a periodic, sampled function.

\begin{align}
F(\omega) &= \frac {1}{2 \pi} \int f(t) e^{-i \omega t} {dt} \\
&=\frac {1}{2 \pi} \int \sum_{m=-\infty}^{\infty} \sum_{n=0}^{L-1} d_n \delta(t-mP-nT) e^{-i \omega t} {dt}\\
&=\frac {1}{2 \pi}\sum_m \sum_{n=0}^{L-1} d_n e^{-i \omega m P} e^{-i \omega n T}\\
&=\frac {1}{2 \pi}\bbox[ border:2px solid yellow ]{\sum_m e^{-i \omega m P}} \sum_{n=0}^{L-1} d_n e^{-i \omega n T} \\
&= \frac {1}{P}\sum_m \delta(\omega - \frac {m 2 \pi}{P}) \sum_{n=0}^{L-1} d_n e^{-i \omega n T} \\
&= \sum_m \delta(\omega - \frac {m 2 \pi}{P}) \frac {1}{P} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m n  \frac {T}{P} } \\
&= \sum_m \delta(\omega -  m \Omega) \frac {\Omega}{2 \pi} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m \frac {n} L }  \\
&= \sum_m \delta(\omega -  m \Omega)  c_m
\end{align}

We used $\Omega P = 2 \pi$ and $P \equiv T L$, and defined

\begin{align*}
c_m &= \frac {\Omega}{2 \pi} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m \frac {n} L } \\
&= \left({1 \over T}\right)  \left({1 \over L} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m \frac {n} L }\right)
\end{align*}

In general, the transform of a periodic function is discrete, the transform of a discrete function is periodic, and the transform of a periodic and discrete function is periodic and discrete.

The Nysquist Criterion for Avoiding ISI


Returning to equation \eqref{ISI}, consider the following system

$$ y(t) = \sum_n c_n h(t-nT)   $$

Sampled at intervals $t-kT=0$, this looks like

\begin{align*}
y(kT) &= \sum_n c_n h(kT-nT) \\
\hat y(k) &= \sum_n c_n  \hat h(k-n)
\end{align*}

We would like to investigate the situation where $\hat y(k)$ is just $c_k$.  That is, $\hat h(k)$ are all zero with one exception: $\hat h(k) = \delta_k$.  So let's look at the Fourier analysis of a discrete version of $h(t)$:

\begin{align*}

\sum_{n=-\infty}^{\infty} \delta(t - nT) h(t) &= \int \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty}  H(\omega - n \Omega) e^{i \omega t} {d\omega} \\

\delta(t) &=  \int \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty}  H(\omega - n \Omega) e^{i \omega t} {d\omega}

\end{align*}

So we must have
$$
\Omega \sum_{n=-\infty}^{\infty}  H(\omega - n \Omega) = 1
$$

In the study of communication in bandlimited channels, this is known as the Nyquist Criterion for the elimination of inter-symbol interference.