\chapter{Discrete-time Fourier transforms} We now shift our focus to possible non-periodic complex sequences. We will again find an appropriate sequence space to work in and proceed as such. Like with complex and real functions, we seek a Fourier integral form for our sequence, since a sum will not suffice (since every term would be periodic); this means we need to find an appropriate 'Fourier kernel' for the sequence, which will be a complex function. Because of this, we will have to consider 2 different spaces; an $\ell^2$ space for the sequence itself and $L^2$ for the kernel (the DTFT). We'll need to pay attention to convergence related matters given that we are working in 2 infinite spaces. Before we start doing this, it is worth discussing a seriously cool theorem. \section{Sampling theorem} As it turns out, a result called \emph{the sampling theorem} gives a condition and formula where a discretization of $f$ can be used to \emph{recover the function $f$ entirely}. As powerful tas this is, the sampling theorem requires the disposal of all infinite terms of the discretization, which means that a numerical method based on the sampling theorem can, at best, arbitrarily approach the original function. Futhermore, the sampling theorem only applies to a special (yet still rich) class of functions, and only if the frequency of ones discretization is 'sufficiently high' (this condition will be explored further). We will now cover the sampling theorem; a result that can potentially sidestep the need to resort to the DFT. 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{ \sin (\pi (\omega_s t -n) )}{\pi (\omega_s t -n)},\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{DTFT} \begin{example}[$\ell^2 (\mathbb{Z})$] The complex sequences over $\mathbb{Z}$ such that $\sum_{n \in \mathbb{Z}} |x[n]|^2$ converges form a linear space under the standard notion of adding and scaling sequences. This space is known as $\ell^2 (\mathbb{Z})$ This is an infinite Hilbert space that we consider with inner product defined as such. $\langle x , y \rangle = \sum_{k \in \mathbb{Z}} x^{*}[k] y[k]$ $\|x\|_2 = \sqrt{\sum_{n \in \mathbb{Z}} |x[n]|^2} $ \end{example} Like the Fourier integral for complex functions, we will also consider an Fourier integral representation for these sequences, and find what kernel of this integral transform returns the sequence back. Fortunately and unlike Fourier analysis of general functions, the kernel can be represented as a sum rather than an integral too. \[f[n] = \int^{\pi}_{-\pi} F(\xi ) e^{i \xi n } d\xi\] \begin{definition}[DTFT] \[F(\xi ) = \sum_{n \in \mathbb{Z}} f[n] e^{-i \xi n}\] \end{definition} \begin{theorem}[DTFT inversion theorem] \[f[n] = \frac{1}{2\pi} \int^{\pi}_{-\pi} F(\xi ) e^{i \xi n } d\xi\] \end{theorem} Like the Fourier transform, the DTFT has some of its transforms as distributions rather than classical functions. DTFT is $2\pi$-periodic DTFT is linear time reversal conjugation time shift modulation symmetric sequence iff symmetric DTFT real sequence iff hermitian symmetric DTFT \section{$z$-transform} The Z-transform generalizes the DFT Bilateral Z-transform \[\mathcal{Z}\{f\}(z)= \sum_{n \in \mathbb{Z}} f[n]z^{-n}\] Unilateral Z-transform \[\mathcal{Z}_{+}\{f\}(z)= \sum_{n \in \mathbb{N}} f[n]z^{-n}\] \[0 \in \mathbb{N}\] The unilateral Z-transform is useful for studying 'causal' sequences (sequences that are zero until a certain term). The unilateral Z-transform is similar to a power series, and is indeed one when we let $z=\frac{1}{w}$. Under this substution, if this series has a ROC $\frac{1}{R_1}$ so$|\frac{1}{z}| < \frac{1}{R_1}$ then we have $|z| > R_1$. The bilateral minus the unilateral is a power series with no constant term, hence denote its radius of convergence $R_2$ so $|z|< R_2$. Therefore, the $R_1 < |z| < R_2$ \[\mathcal{Z}\{f+g\}(z)= \mathcal{Z}\{f\}(z) + \mathcal{Z}\{g\}(z) \] \[\mathcal{Z}\{f[-n]\}(z)= \mathcal{Z}\{f\}(\frac{1}{z}) \] \[\mathcal{Z}\{f^{*}\}(z)= [ \mathcal{Z}\{f\}(z) ]^{*} \] \[\mathcal{Z}\{f[n-l]\}(z)= z^{-l} \mathcal{Z}\{f\}(z) \] \[\mathcal{Z}\{a^n f[n]\}(z)= \mathcal{Z}\{f\}(\frac{a}{z}) \] \[\mathcal{Z}\{n f[n]\}(z)= -z \mathcal{Z}'\{f\}(\frac{a}{z}) \] Convolution theorem (Z-transform) \[\mathcal{Z}\{f\}(z)\mathcal{Z}\{g\}(z) = \mathcal{Z}(f * g)(z) \] \subsection{Inverse $z$-transform} Complex analysis lights the way for a inverse transform. \[\mathcal{Z}^{-1}\{f\}[n] = \frac{1}{2\pi i}\oint_{\gamma} f(z)z^{n-1} dz\] where $\gamma$ is a countour around the ROC.