The consequences of $\omega=\pi$ being the ``fastest'' digital frequency can be readily appreciated when watching an old movie, and in particular a good old western. Consider the classic scene of a stagecoach leaving town: as the wagon starts moving, we see the spokes of its wheels beginning to turn forward; but, as the coach gains speed, the spokes appear to slow down, stop, and then start to turn backwards. The phenomenon is known as ``the wagonwheel effect'' and it is an instance of a digital angular frequency wrapping around its possible maximum value.
To better understand the phenomenon, remember that each frame in the film is an instantaneous snapshot of a rotating wheel. In stationary conditions (i.e., the wheel's motion is constant) if the angular speed of the wheel is $\omega_0$ radians per second, and if the frame rate of the movie is $F$ frames per second, the angular displacement between two successive frames is $\Delta=\omega_0/F$. If the wheel has $K$ spokes (and has perfect circular symmetry), two wheel positions $2\pi/K$ radians apart will be indistinguishable. That gives us a first upper limit on the maximum angular speed of
\[
\omega_1 < 2\pi\frac{F}{K} \quad\mbox{rad/sec}
\]
Things are however slightly more complicated because of the perceptual mechanisms of the human visual system. The illusion of movement in motion pictures relies on the brain's ability to ``fill in the gaps'' between successive static images, provided that the images come fast enough: anything below approximately~12 frames per second will not create the illusion of motion. The full mechanism at work is very complex but one of the underlying principles is that the brain will apply a ``plausibility test'' to the virtual motion and go with the most realistic hypothesis. When looking at a revolving spoked wheel, the brain will perceive a rotation in the direction that minimizes the apparent motion of the spokes between successive frames. So, for small angular displacements as in Figure~\ref{fig:fa:ww_forw} the motion will appear counterclockwise; for displacements larger than $\omega_1/2$, on the other hand, the motion will appear clockwise as in Figure~\ref{fig:fa:ww_back}. In both figures, the current position is drawn in black and previous position are drawn in progressively lighter shades of gray; the current position for the reference spoke is indicated by a dot. This observation gives us a second upper limit on the maximum angular speed for ``forward'' motion:
\[
\omega_1 < \pi\frac{F}{K} \quad\mbox{rad/sec}
\]
In practice things are actually even a bit more complicated still. For instance, when the angular speed is equal to $\omega_1$ above, the perceived image may be that of a stationary wheel with twice the number of spokes, i.e., the preferred interpretation on the part of the brain is to superimpose two successive frames into a slightly blurred but still image rather than postulating such a wide motion. The net effect is that, at speeds close to $\omega_1$, the wheel appears to have twice the number of spokes and therefore the maximum forward speed is $\omega_2=\omega_1/2$.
Finally, consider a ``real'' wheel with a diameter of $d$ meters. The linear speed of the wagon for an angular speed of $\omega_2$ is
\[
v =\frac{d}{2}\,\frac{\pi}{2}\,\frac{F}{K}
\]
For an 8-spoke wheel with a diameter of one meter in a movie shot at 24fps, the maximum forward velocity is reached when the wagon travels at approximately 8~Km/h. Since the apparent forward/backward switch in rotation takes place each time the angular velocity reaches a multiple of $\omega_2$, by the time the stagecoach reaches full speed the wagonwheel effect has happened several times.
\begin{example}[The DFT, its physical interpretation and Lod Kelvin's tide-predicting machine.]
\index{tide prediction|DFT}
An instructive way to explain the physical interpretation of the DFT is to start with the synthesis formula~(\ref{eq:fa:idft}). The expression tells us that we can build \textit{any} signal in $\mathbb{C}^N$ as a suitable combination of $N$ complex sinusoids with harmonically related frequencies; the magnitude and initial phase of each oscillation are given by the complex-valued Fourier coefficients. Consider a ``complex exponential generator'' as in Figure~\ref{fig:fa:gen}; the oscillator works at a frequency $(2\pi/N)k$ and it can be tuned in magnitude and phase. The DFT synthesis formula can be represented graphically as in Figure~\ref{fig:fa:idft}, that is, as a bank of $N$ oscillators working in parallel; to reproduce any signal $\mathbf{x}$ from its DFT $\mathbf{X}$:
\begin{itemize}
\item set the amplitude $A_k$ of the $k$-th generator to $\bigl|X[k]\bigr|$, i.e.\ to the magnitude of the $k$-th DFT coefficient;
\item set the phase $\phi_{k}$ of the $k$-th generator to $\measuredangle{X[k]}$, i.e.\ to the phase of the $k$-th DFT coefficient;
\item start all the generators at the same time and sum their outputs for $N$ cycles
\item divide the result by $N$.
\end{itemize}
This ``machine'' shows that each Fourier coefficient captures ``how much of'' and ``how in phase'' an oscillation at frequency $2\pi/k$ is contained in $\mathbf{x}$; this is consistent with the fact that each $X[k]$ is computed as the inner product between $\mathbf{x}$ and $\mathbf{w}_k$, and that the inner product is a measure of similarity.
consequently, the square magnitude of a DFT coefficient $|X[k]|^2$ is proportional, via to a scale factor $N$, to the energy of $\mathbf{x}$ at the frequency $(2\pi/N)k$: the magnitude of the DFT therefore shows how the global energy of the original signal is distributed in the frequency domain. The phase of each DFT coefficient specifies the initial phase of each oscillator in the reconstruction formula, i.e. the \emph{relative alignment} of each complex exponential at the onset of the signal. While this does not affect the energy distribution in frequency, it does have a significant impact on the \textit{shape} of the signal in the time domain as we will see in more detail shortly.
On a historical note, far from being a pure academic exercise, the synthesis of signals via a bank of oscillators is a topic that attracted great interest and efforts long before the advent of digital computers. Figure~\ref{fig:fa:tidemachine} shows a mechanical implementation of the inverse DFT as we just described; in this case the device was designed in order to anticipate the evolution of the sea tide. The original design of these tide prediction machines dates back to Lord Kelvin in the 1860s.
\begin{example}[The Fast Fourier Transform.] \index{FFT}
\label{sec:fa:fft}
When computing the numerical DFT of an $N$-point data vector, it is easy to see that the formula in~(\ref{eq:fa:dft}) requires about $N$ multiplications per DFT point, that is, a total of $N^2$ multiplications. A computational cost that is quadratic in the size of the input is usually bad news for practical applications but fortunately many algorithms have been developed over the years that significantly reduce this load so that, in general, a fast Fourier Transform implementation (FFT) requires on the order of $N\log N$ operations. For a data vector of, say, ten thousand samples (which represents less than a quarter of a second's worth of DVD-quality mono audio data), an FFT requires approximately forty thousand multiplications; compare this to the more than a hundred million operations required out by a naive DFT implementation: this is a cost reduction of \textit{four orders of magnitude} and these savings are what make Fourier analysis a practical rather than a theoretical tool in today's digital devices.
The idea behind all FFT algorithms is to decompose the full DFT computation into a series of smaller DFTs; if the cost of ``reassembling back the pieces'' is linear in $N$, then the total number of operations will be less than $N^2$. This \textit{divide et impera}\/\footnote{
``Divide and conquer,'' a staple strategy of Julius C\ae{}sar's...}
approach is in fact very general and represents the key ingredient of many other famous recursive algorithms, such as Quicksort or Mergesort. Assume we have a problem of size $N$, with $N$ even, whose solution requires approximately $N^2$ operations; if we split the problem into two subproblems of size $N/2$, requiring $(N/2)^2$ operations each, and if merging the results requires approximately $N$ operations, the total cost will be
\[
2(N/2)^2+ N = N^2/2+ N
\]
which is less than $N^2$ as soon as $N > 4$. Of course this subdivision can be repeated recursively $\log_2 N$ times, yielding a total cost for the solution of the problem proportional to $N\log_2 N$ operations.
\itempar{Decimation in time.} As a simple illustration of one of the most famous FFT implementations, consider a data size equal to a power of two: $N =2^L$. Split the input and the output of the DFT like so:
\begin{itemize}
\item split the input into even- and odd-indexed signals, of length $N/2$ each:
\begin{align*}
x_e[n] &= x[2n] & n = 0, 1, \ldots, N/2-1 \\
x_o[n] &= x[2n+1] & n = 0, 1, \ldots, N/2-1 \\
\end{align*}
\item split the output into two successive halves, of length $N/2$ each:
\begin{align*}
X_a[k] &= X[k] & k = 0, 1, \ldots, N/2-1 \\
X_b[k] &= X[k + N/2] & k = 0, 1, \ldots, N/2-1 \\
\end{align*}
\end{itemize}
We can now split the DFT sum into even and odd terms and write
where $\mathbf{X}_e$ and $\mathbf{X}_o$ are the two $(N/2)$-point DFTs of $\mathbf{x}_e$ and $\mathbf{x}_o$ respectively. So far, there are no computational savings since each term in the summation requires 3 multiplications for a total of $N(3N/2)\approx N^2$ operations. But now consider the inherent periodicity of the DFT coefficients, as shown in~\ref{sec:fa:dfs}; since $X_{e,o}[k+N/2]= X_{e,o}[k]$ we can compute the first and second halves of the \textit{full} DFT as:
In other words, once we have computed the first $N/2$ DFT coefficients, the second half is obtained without any additional multiplication but only via a change of sign. The computational cost can be broken down like so:
\begin{enumerate}
\item zero multiplications for the splitting of the input sequence
\item$2(N/2)^2= N^2/2$ multiplications for the computation of $\mathbf{X}_e$ and $\mathbf{X}_o$
\item$N/2$ multiplications by a phase terms for $\mathbf{X}_o$
\item zero multiplications for the computation of $\mathbf{X}_a$ and $\mathbf{X}_b$
\end{enumerate}
for a total of $(N+1)(N/2)$ multiplication which is about half the cost of the initial problem. Of course, the splitting and merging can be performed recursively until the size of the smaller DFTs is two or four; as we have seen in Section~\ref{sec:fa:dft_matrix}, the DFT matrices of these sizes require no multiplications.