\chapter{Discrete Fourier transform}


$f : \mathbb{Z} \to \mathbb{R}$

We can 'discretize' real functions as sequences in this way: for a real function $f$, we can make a sequence that recognizes values $T$ away from eachother in the following way
\begin{definition}[$T$-discretization of $f$]
$f[n] = f(nT)$
frequency $\omega = \frac{1}{T}$
\end{definition}

dirac delta sequence
$\delta [n] = \delta_{0n}$

any real sequence is representable as such.
\[f[n] = \sum_{k \in \mathbb{Z}} f[k] \delta[n-k] \]

Discrete dirac comb
$\delta_N [n]$

any periodic real sequence is representable as such 
\[f[n] = \sum_{k =0}^{N-1} f[k] \delta_{N}[n-k] \]

heaviside step sequence
\[ \theta [n] = \begin{cases} 1 & n \geq 0 // 0 & n < 0 \end{cases} \]


\section{Poisson summation formula}

\begin{theorem}[Poisson summation formula]
Let $f \in \mathcal{S}$ be a Schwartz function, then the following holds.
\[\sum_{n \in \mathbb{Z}} f(x+nT) = \frac{1}{T} \sum_{n \in \mathbb{Z}} \mathcal{F}\{f\}(2 \pi \frac{n}{t})e^{2\pi i n \frac{x}{T}}\]
\end{theorem}






\section{Sampling theorem}

This section will discuss how we can use \emph{discrete convolutions} to transform a real sequence into a real function.

In numerical analysis, linear interpolation is a basic method to port a real sequence to a real function.

Let $q_T(t)$ be triangular pulse function; it is a linear interpolation of $\delta[n]$

let $f_r$ be a linear interpolation of $f$, then 
\[f_r (t) = \sum_{k \in \mathbb{Z}} f[k] q_T (t-kT) \]


This method of using $f[n]$ to reconstruct $f$ naturally induces considerable error in this interpolation. Even if the sequence has high frequency, there will always be this error.


There is a discrete convolution, however, that converges perfectly given a nice enough function and a frequency above a certain threshold. We will exlain which and why a certain class of functions satisfies this, and  how this 'magic frequency' comes into play.

We require the notion of a \emph{bandlimited function}

\begin{definition}[Bandlimited function]
\emph{band limited function} is a function $f$ with spectrum $\mathcal{F}\{f\}$ such that there is some $\xi'$ where $\mathcal{F}\{f\}(\xi) =0$ when $|\xi| > \xi'$
The double of the minimum such $\xi'$ for which the this holds is called the Nyquist frequency.
\end{definition}





For bandlimited functions, there is a convolution we can made. it naturally arises when considering an appropriate periodic extension of the Fourier transform then multiplying it by a rectangle pulse to make it bandlimited again. The trick is choosing an appropriate periodic extension, that is, one that ensures that the whole nonzero Fourier transform at least is included in the period, since this is when our 'periodic Fourier transform times rectangular pulse' will equate to the real Fourier transform. To do this, we require the half the sampling frequency of the period to be below the bandlimit, otherwise the construction we will use to make the Fourier transform periodic will include a messy superposition of the beginning and end of the spectrum.


\begin{theorem}[Sampling theorem]
Let $f$ be a bandlimited function with Nyquist frequency $2\xi'$, and let $f[n]$ be taken with sampling frequency $\omega_s > 2\xi'$, then the following holds.
\[f(x) = \sum_{n \in \mathbb{Z}} f[n] \frac{2 \sin (\frac{\omega_s (t-nT)}{2} )}{\omega_s (t-nT)},\forall x \in \mathbb{R}\]
\end{theorem}

The sketch is to consider a periodic extension of the Fourier transform at the bandlimit, apply the Poisson summation formula, return it to it's non-periodic form by multiplying by a rectangular pulse function, calculating the inverse Fourier transform of this function, and finally showing that this function equals the original function





\section{Discrete Fourier transform}


Arises by numerically evaluating the Fourier coefficient integral as a riemann sum partitioned into $N$ parts.

\begin{definition}[Discrete Fourier Transform (DFT)]
\[F[k] = \sum^{N-1}_{n=0} f[n] e^{-2\pi i n \frac{k}{N}}\]
$\frac{2\pi}{N}$ is the fundamental frequency
\end{definition}

\[f[-n] \iff F[k]\]
\[ f^{*}[n] \iff F^{*}[-k]) \]
\[f[n-l] \iff e^{-2\pi i n \frac{k}{N}}F[k] \]

\begin{theorem}[Fundamental theorem of discrete fourier transform]
Let $f : \mathbb{Z} \to \mathbb{R}$ be $N$-periodic sequence. Then
	\[ f[n] = \frac{1}{N} \sum^{N-1}_{k=0} F[k] e^{2\pi i n \frac{k}{N}}\]
\end{theorem}

The DFT is similar in many other ways to Fourier coefficients in the properties they follow.


cyclical convolution
\[(f * g) [n] \sum^{N-1}_{i=0} f[i]g[n-i] \]


\[(f * g) [n] \iff F[k]G[k] \]
\[f[n] g[n] \iff \frac{1}{N} (F*G)[k] \]


Parsval's theorem (DFT)
\[\sum^{N-1}_{n=0} f[n]g^{*}[n] =\frac{1}{N} \sum^{N-1}_{n=0} F[n]G^{*}[n] \]

\section{$z$-transform}
