At the beginning of the 19th century, French polymath Jean-Baptiste Joseph Fourier turned his attention to the way in which heat propagates inside a solid object. In the resulting memoir he introduced an analytical tool that was destined to become so successful, both in mathematics and in applied engineering, as to acquire the eponymous name of \textit{Fourier Transform}. Fourier's intuition was that many functions (and, remarkably, even discontinuous functions) could be represented as linear combinations of simple, harmonically-related sinusoidal components.
The systematization of the mathematical aspects of Fourier's theory took over a century to complete, and produced a remarkable body of work collectively known under the name of Harmonic Analysis. At the same time, the practical applicability of the Fourier transform gained immediate recognition across all scientific domains --- the sole drawback being the need to carry out cumbersome numerical calculation in order to work out the necessary coefficients. It is no surprise, then, that Fourier analysis enjoyed a renewed, explosive success as soon as electronic computation became a commodity: the well-known Fast Fourier Transform algorithm (interestingly, originally sketched by Gauss in~1805) is arguably the fundamental ingredient at the heart of today's personal communication devices.
To understand why Fourier Analysis plays such a central role in so many disciplines, and in signal processing in particular, let's consider the physical processes behind most of the interesting phenomena that we want to model or describe. Signals are time-varying quantities: you can imagine, for instance, the voltage level at the output of a microphone or the measured level of the tide at a particular location; in all cases, the variation of a signal over time implies that a transfer of energy is taking place somewhere. Now, a time-varying value which only increases monotonically over time is clearly a physical impossibility in the long run: fuses will blow, wires will melt and engines will explode. Oscillations, on the other hand, are nature's (and man's) way of keeping things in motion indefinitely without incurring a meltdown; from Maxwell's wave equation to the mechanics of the vocal cords, from the motion of an engine to the ebb and flow of the tide, oscillatory behavior is always the recurring theme. Sinusoidal oscillations are the purest form of such a constrained motion and, in a nutshell, Fourier's lasting contribution was to show that one could express any reasonably well-behaved phenomenon as the combined output of a number of sinusoidal ``generators''.
In this chapter we will describe some key properties and results of Fourier analysis as applied to discrete-time signals. We have already mentioned in the previous chapter that, by using a vector space framework for signal processing, the Fourier transform can be described as a change of basis. This guiding principle will prove extremely useful as we navigate the subtle differences that exists between the different flavors of the transform and as we interpret their properties.
%Sinusoids have another remarkable property which justifies their ubiquitous presence. Indeed, \emph{any linear time-invariant transformation of a sinusoid is a sinusoid at the same frequency}: we express this by saying that sinusoidal oscillations are eigenfunctions of linear time-invariant systems. This is a formidable tool for the analysis and design of signal processing structures, as we will see in much detail in the context of discrete-time filters.
\section{Chapter Outline}
The Fourier transform of a signal is an alternative representation of the data in the signal. While a signal lives in the \emph{time domain}\index{time domain},\footnote{\emph{Discrete}-time, of course.} its Fourier representation lives in the \emph{frequency domain}\index{frequency domain}. We can move back and forth at will from one domain to the other using the direct and inverse Fourier operators, since these operators are invertible.
In this chapter we describe three types of Fourier transform which apply to the three main classes of signals that we have seen so far:
\begin{itemize}
\item the Discrete Fourier Transform (DFT), which maps length-$N$ signals into a set of $N$ discrete frequency components; the transform is a change of basis in the underlying vector space $\mathbb{C}^N$.
\item the Discrete Fourier Series (DFS), which maps $N$-periodic sequences into a set of $N$ discrete frequency components; this also is a change of basis in $\mathbb{C}^N$.
\item the Discrete-Time Fourier Transform (DTFT), which maps infinite sequences into the space of $2\pi$-periodic function of a real-valued argument; this transform can be interpreted as a ``formal'' change of basis in $L_2(\mathbb{Z})$, as we will see in detail.
\end{itemize}
The frequency representation of a signal (given by a set of coefficients in the case of the DFT and DFS and by a frequency distribution in the case of the DTFT) is called the \emph{spectrum}.
\section{Digital vs ``Real-World'' Frequency}
\section{The Complex Exponential}
\label{sec:fa:cexp}
Regardless of the underlying signal space, the Fourier transform decomposes a discrete-time signal into a superposition of suitably scaled discrete-time oscillatory components. We will express the prototypical oscillation (i.e., the basic ingredient of all transforms) as a \textit{discrete-time complex exponential}, namely a sequence of the form\index{complex exponential}
\begin{equation}
x[n] = A\,e^{j(\omega n + \phi)}%= A \bigl[ \cos(\omega n + \phi) + j\sin(\omega n + \phi) \bigr]
\end{equation}
where $A \in\mathbb{R}$ is the amplitude, $\phi$ is the phase offset (in radians) and $\omega\in\mathbb{R}$ is the oscillation's frequency, also expressed in radians. Note that, although it is convenient to think of the index $n$ as a measure of ``time'', such time is a-dimensional and therefore the units for the frequency are simply radians (and not, say, radians per second).
As we have already explored in Section~\ref{sec:dt:frequency}, using simple algebra, we can easily see that
\begin{equation}
x[n+1] = x[n]\,e^{j\omega};
\end{equation}
that is, we can imagine the sequence $x[n]$ as the sequential output of a ``complex exponential generating machine'' that, at each step, takes the previous sample and multiplies it by $e^{j\omega}$, a pure phase factor\footnote{A phase factor is a complex number whose magnitude is equal to one. As such, it lives on the unit circle and it can be uniquely identified by its phase only.}. Recall now that, given a point $z$ on the complex plane, the position of $ze^{j\theta}$ can be found by rotating $z$ around the origin by an angle $\theta$ as shown in Figure~\ref{fig:fa:rotation}; the rotation is counterclockwise if $\theta$ is positive and clockwise if $\theta$ is negative. With this, $x[n]$ can be plotted on the complex plane as a series of point on a circle of radius $|A|$ centered on the origin; each point is at an angular distance of $\omega$ from the previous one. Two examples of complex exponential sequences are shown for a few values of $n$ in Figure~\ref{fig:fa:cexp_pn}, using positive and negative frequencies and different phase offsets. As you can see, the complex exponential perfectly captures the concept of a point rotating in circles, i.e. the most fundamental type of oscillatory movement.
\caption{Complex exponential sequences on the complex plane: \\ (a) $x[n]= e^{j\omega n}$ with $\omega=2\pi/10$ (positive frequency); \\ (b) $x[n]= e^{j\omega n +\theta}$ with $\omega=-2\pi/20$ and $\theta=2\pi/40$ (negative frequency).}\label{fig:fa:cexp_pn}
The choice of a complex-valued signal as the prototypical oscillation may appear needlessly esoteric at first and, in fact, if we only consider real-valued signals we could derive the Fourier transform using only standard, real-valued trigonometric functions. There are however some major advantages in using complex exponentials:
\itempar{The math is simpler:} simply put, by using complex exponentials, trigonometry boils down to algebra. For instance, how many times have you struggled with the correct angle-sum formula? You remember that $\cos(\alpha+\beta)$ will be equal to a sum of products of sines and cosines but in what order and with what sign? Using complex algebra, however,
No need to remember formulas means fewer chances of making mistakes.
\itempar{The notation is more compact:} the prototypical oscillation is described by a rotating point, whose position has two degrees of freedom. To encode those, either we provide the real-valued vertical and horizontal coordinates of the point on a Cartesian plane (using a cosine and a sine); or we interpret the point's position as a point on the complex plane (using a complex exponential). While the two representations are equivalent, the latter is obviously more compact and, to see how cumbersome the notation becomes if we insist on using only real-valued quantities, please refer to Appendix~A, where some real-valued transforms are worked out.
The same holds for the \textit{values} of the Fourier transform; we will soon see that each Fourier coefficient encodes ``how much'' an oscillation of appropriate frequency contributes to the signal. While it may seem disorienting at first to have a complex-valued transform of a real-valued signal, note that each oscillatory contribution will be scaled in amplitude and offset in phase. Again, these two degrees of freedom can be conveniently packaged into a complex-valued Fourier coefficient!
\itempar{In the digital world, signals can be complex:} indeed, why not? Digital signals are just sequences of numbers that will be processed by general-purpose computational units, and therefore these sequences can certainly be complex-valued. While the interfaces to and from the physical world will necessarily handle real values only, \textit{internally} a DSP system will often be easier to design if complex-valued operations are allowed; this is particularly true in the case of communication systems. By starting off with complex exponentials as the prototypical oscillation, we are already equipped with a more versatile tool for frequency analysis.
\caption{Same point, many aliases: (a) adding multiples of $2\pi$ to a pure phase term does not change its position; (b) a positive (counterclockwise) displacement by $\theta$ is equivalent to a negative (clockwise) displacement by ($2\pi-\theta)$}\label{fig:fa:point_alias}
In discrete time, things are a bit different with respect to the properties of classic sinusoidal functions of a real variable. First of all, perhaps surprisingly, not all complex exponential sequences are periodic in $n$. Without loss of generality, consider a sequence with zero phase offset $x[n]= e^{j\omega n}$; for $x[n]$ to be periodic, there must exist an integer $N$ so that
\[
x[n]= x[n + N], \quad\forall n\in\mathbb{Z}.
\]
The above expression is equivalent to $e^{j\omega N} =1$, that is, there must exist an integer $M$ such that
\[
\omega N =2\pi\, M.
\]
Periodicity therefore requires the frequency to be of the form
or, in other words, in discrete time the only periodic oscillations are those \textit{whose frequency is a rational multiple of $2\pi$}.
Incidentally, \marginpar{LATER} note that the energy of the infinite-length signal $x[n]= A\,e^{j(\omega n +\phi)}$ is infinite while the power is equal to $|A|^2$ irrespective of frequency and phase.
Another peculiarity of discrete-time oscillations is that there is a limit on ``how fast'' we can go. To understand why, let's start by recalling that a pure phase term is always $2\pi$-periodic, in the sense that
This inherent phase ambiguity is called aliasing and stems from the simple fact that a point on the unit circle has an infinite number of possible ``names'', as shown in Figure~\ref{fig:fa:point_alias}-(a) --- etymologically, ``alias'' is Latin for ``otherwise''. Applied to discrete-time complex exponential sequences, this clearly implies an upper limit on the rotational speed of a point around the unit circle, since adding multiples of $2\pi$ to the value of the frequency will not change the values of the samples:
consequently, we can limit the range of distinct angular speeds to a representative interval of size $2\pi$. To choose the most suitable interval, consider what happens if we gradually increase the frequency of a discrete-time complex exponential starting from zero:
\begin{itemize}
\item for $0\leq\omega < \pi$ we have a counterclockwise motion with increasing angular speed, i.e., we cover the full circle in fewer and fewer steps.
\item for $\omega=\pi$ we have the maximum possible forward speed of a discrete-time complex exponential; this corresponds to a sequence whose values are alternating between $+1$ and $-1$, which represents the maximum displacement attainable by successive points on the unit circle (antipodal points); we cover the full circle in 2 steps.
\item for $\pi < \omega < 2\pi$ at each step the point on the unit circle moves by more than $\pi$, as shown in Figure~\ref{fig:fa:cexp_alias}. Such a large counterclockwise motion is more ``economically'' explained by a \textit{clockwise} motion by an angle $2\pi-\omega < \pi$, i.e., the motion is better described by a \textit{negative} frequency whose magnitude is less than $\pi$.
\item for $\omega\geq2\pi$ we can subtract a suitable multiple of $2\pi$ to $\omega$ until we fall into one of the three preceding cases.
\end{itemize}
The reference interval of choice for angular frequencies is therefore $[-\pi, \pi]$.
Note that, as we increase $\omega$ beyond $\pi$, we obtain a perceived reversal of direction and a \textit{decreasing} angular speed. This aliasing phenomenon is well known in cinematography where it is called the \textit{wagonwheel effect}; you can experience it in full by watching an old western movie: if a stagecoach enters the scene, you will see that its multi-spoked wheels seem to spin alternately backwards and forward as the speed of the vehicle changes. For a more detailed discussion of this optical illusion, see Appendix~B.
\caption{Complex-exponential sequence at angular speed $\omega=2\pi-\theta$, with $\theta$ small: (a) at each step, the point's displacement is larger than $\pi$; (b) the movement is more ``economical'' if one assumes a negative frequency $\omega' =-\theta$.}\label{fig:fa:cexp_alias}