The DFT provides us with a frequency-domain representation of signals that contain a finite amount of data; periodic signals, which are also uniquely described by a finite number of data samples, use a formally identical frequency representation (which, solely for clarity, we label DFS). In both cases, the transform is a simple change of basis in $\mathbb{C}^N$ and, as such, it can be described algorithmically as a matrix-vector multiplication involving a finite number of operations.
We now consider the problem of obtaining a frequency-domain representation for aperiodic, infinite-length sequences. Such signals are an idealized mathematical concept, of course, but they are indispensable in order to obtain fundamental results in signal processing that hold for \textit{any} finite-length, finite-support or periodic signal. We can always think of an infinite-length sequence as the limit of a finite-length signal whose length grows to infinity; or, alternatively, as the limit of a periodic signal whose period grows unbounded. It is therefore reasonable to expect that the frequency representation of infinite-length signals should be consistent with the limit of a DFT or DFS, and that it should retain its intuitive interpretation as a change of basis in an appropriate vector space. Indeed, we will see that this is the case although, when we move from finite to infinite-length signals, something ``breaks down'' in the formalism and we won't be able to obtain a Fourier transform operator that acts as an isomorphism on the underlying signal space. In other words, given a signal in $\ell_2(\mathbb{Z})$, its Fourier transform will not be itself an element of $\ell_2(\mathbb{Z})$. Although the exact reasons for this are quite technical and beyond the scope of this book, we will try to provide some intuition in Section~\ref{sec:fa:dtftlimit}.
The frequency-domain representation for infinite-length, discrete-time signals is called the Discrete-Time Fourier Transform (DTFT). We will first introduce the transform as a formal operator and then show its ``operational'' equivalence to a change of basis in a suitable vector space.
\subsection{Formal Definition}
The Discrete-Time Fourier Transform of a sequence $\mathbf{x}$ is defined as\index{DTFT|mie}
Formally, the DTFT is an operator that maps discrete-time sequences to a complex-valued functions of the frequency variable $\omega\in\mathbb{R}$. Since the argument $\omega$ only appears as the phase of a complex exponential in the integral, the resulting function is always $2\pi$-periodic. As we already mentioned in Section~\ref{sec:intro:notation}, the somewhat odd notation $X(e^{j\omega})$ is rather standard in the signal processing literature and offers several advantages:
\begin{itemize}
\item it stresses the periodic nature of the transform since, independently of the actual expression for $X$, $X(e^{j(\omega+2\pi)})= X(e^{j\omega})$;
\item regardless of context, it immediately identifies the expression as a DTFT;
\item it provides a convenient notational framework which unifies the Fourier transform and the $z$-transform, as we will see in Chapter~\ref{ch:zt}.
\end{itemize}
The DTFT, when it exists, can be inverted via the integration
\begin{equation}\label{eq:fa:DTFTrec}
x[n] = \frac{1}{2\pi}\int_{-\pi}^{\pi} X (e^{j\omega}) \,e^{j\omega n} d\omega;
\end{equation}
this can be easily verified by substituting~(\ref{eq:fa:DTFTsyn}) into~\ref{eq:fa:DTFTrec}) and recalling that
In fact, due to the $2\pi$-periodicity of the DTFT, the integral in~(\ref{eq:fa:DTFTrec}) can be computed over \emph{any}$2\pi$-wide interval on the real line; by convention, though, the DTFT is generally represented over the $[-\pi, \pi]$ interval. For the DTFT to exist, the sum in~(\ref{eq:fa:DTFTsyn}) must converge: if we define the partial sum
existence of the DTFT is equivalent to the convergence of $\lim_{M \rightarrow\infty} X_M(e^{j\omega})$. Convergence is very easy to prove for \emph{absolutely summable} sequences, that is for sequences satisfying
For this class of sequences it can also be proved that the convergence of $X_M(e^{j\omega})$ to $X(e^{j\omega})$ is uniform and that $X(e^{j\omega})$ is continuous. While absolute summability is a sufficient condition for the existence of the DTFT, it can be shown that the sum in~(\ref{eq:fa:DTFTpartial}) is convergent also for all \emph{square-summable} sequences, i.e. for sequences whose energy is finite, that is, for all sequences in $\ell_2(\mathbb{Z})$. In the case of square summability only, however, the convergence of~(\ref{eq:fa:DTFTpartial}) is no longer uniform but takes place only in the mean-square sense, i.e.{}
This type of convergence implies that, while the total energy of the difference between functions goes to zero, the functions may differ in value over a countable set of points.\footnote{
A particular manifestation of this behavior is called the \emph{Gibbs phenomenon}, which has important consequences in the problem of filter design, as we will study in Chapter~\ref{ch:fd}.}
Furthermore, in the case of square-summable sequences, $X(e^{j\omega})$ is no longer guaranteed to be
continuous.
As an example, consider the sequence:
\begin{equation}\label{DTFTexeq}
x[n] = \left\{\!\begin{array}{ll}
1 &\mbox{ for } -N \leq n \leq N \\
0 &\mbox{ otherwise}
\end{array}
\right.
\end{equation}
Its DTFT can be computed as the sum\footnote{Remember that
By defining $\Delta=(2\pi/N)$, we can rewrite the above expression as
\begin{equation}
\tilde{x}[n] = \frac{1}{2\pi}\sum_{k = 0}^{N-1}
X(e^{j(k\Delta)}) \, e^{j(k\Delta) n}\,\Delta
\end{equation}
and the summation is easily recognized as the Riemann sum with step~$\Delta$ approximating the integral of $f(\omega)= X(e^{j\omega})e^{j\omega n}$ between $0$ and $2\pi$. As $N$ goes to infinity (and therefore $\tilde{x}[n]\rightarrow x[n]$), we can therefore write