Homec4science
Diffusion epfl (master) Browse

R2653/writing/sp4comm.multipub/40-fourier/00-fa-intro.tex
949fe07cb507master

Last Change
Raw File

00-fa-intro.tex
View Options

\chapter{Fourier Analysis}
\label{ch:fourier}\label{ch:fa}
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 air pressure level produced by the singing voice, the electrical activity of a beating heart or the daily level of the tide in Venice; 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 whose trend is continually increasing over time is clearly a physical impossibility in the long run: either the system will reach a maximum level and stop, or something (such as a wire or a fuse somewhere) will overheat and break. Oscillations, on the other hand, are nature's (and man's) way of keeping things indefinitely in motion 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 the universally recurring theme for sustained activities. Sinusoidal oscillations are the purest form of such a constrained motion and, details aside, Fourier's lasting contribution was to show that one could express any reasonably well-behaved phenomenon as the combined output of a number of harmonically related sinusoidal sources.
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{Introduction}
A Fourier transform provides an alternative representation of the data contained in a signal. Whereas a signal lives in the \emph{time domain}\index{time domain}, 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.
The time domain version of a signal can be decomposed as the linear combination of atomic time units; in the frequency domain the atomic units are periodic oscillations. See figure
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[p]
%
\def\timeplot#1#2{
\begin{dspPlot}[width=2.5cm,height=1.3cm,xticks=1,yticks=1]{0,7}{0,1.2}
\dspSignal[linecolor=ColorDT2]{x #1 eq {1} {0} ifelse}
\dspText(3,1.4){$#2$}
\end{dspPlot}\hspace{-2em}}
\def\freqplot#1#2{
%
\begin{dspPlot}[width=2.5cm,height=1.3cm,xticks=none,yticks=1]{0,7}{-1.3,1.3}
\dspFunc[linewidth=0.3pt,linecolor=ColorDF!50]{x 360 8 div #1 mul mul cos}
\dspSignal[linecolor=ColorDF]{x 360 8 div #1 mul mul cos}
\dspText(3,1.8){$#2$}
\end{dspPlot}\hspace{-2em}}
%
\center\small
%
\begin{dspPlot}[width=\dspHalfWidth,height=\dspHalfHeight,xticks=1,yticks=5]{0,7}{0,6}
\dspTapsAt[linecolor=ColorDT]{0}{1 2 3 4 5 4 3 2}
\end{dspPlot}
\vspace{2em}
\begin{tabular}{cccc}
\timeplot{0}{1}
&
\timeplot{1}{2}
&
\timeplot{2}{3}
&
\timeplot{3}{4}
\\
\timeplot{4}{5}
&
\timeplot{5}{4}
&
\timeplot{6}{3}
&
\timeplot{7}{2}
\end{tabular}
\vspace{2em}
\begin{tabular}{cccc}
\freqplot{0}{3}
&
\freqplot{1}{-0.8536}
&
\freqplot{2}{0}
&
\freqplot{3}{-0.1464}
\\
\freqplot{4}{0}
&
\freqplot{5}{-0.1464}
&
\freqplot{6}{0}
&
\freqplot{7}{-0.8536}
\end{tabular}
\caption{Decomposition of a 8-point triangular signal (top panel) into atomic time units (middle panel) and atomic oscillatory units (bottom panel); the coefficient for each component is shown on top of the plot of each unit. Superimposed to each discrete-time oscillatory basis vector is .}\label{fig:fa:rotation}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In this chapter we will derive a Fourier representations for all three classes of discrete-time signals that we have seen so far:
\begin{itemize}
\item the \textbf{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 \textbf{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 \textbf{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 also be interpreted structurally as a change of basis, 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}. We have seen that in discrete time the ``time'' index $n$ in the expression $x[n]$ is in fact an a-dimensional quantity with no physical units of measure; similarly, in the Fourier representation of discrete-time signals, the frequency variable (usually denoted by the letter $\omega$) is also a-dimensional. We explain see in due course how, by assigning a physical time value to the space between samples in a signal, we can map the a-dimesional frequency to a physical value in Hertz.
\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. The prototypical oscillation of choice (that is, the basic ingredient of all transforms) is the \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).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\center\small
\begin{dspPZPlot}[width=6cm,circle=0,xticks=none,yticks=none]{1.5}
\dspCPCirclePoint[toorg=true]{1.1}{20}{$z$}
\dspCPCirclePoint[linecolor=red,toorg=true]{1.1}{60}{$z\,e^{j\theta}$}
\dspCPArc{1.1}{20}{60}{$\theta$}
\end{dspPZPlot}
\caption{Rotation of a point on the complex plane via multiplication by a phase factor $e^{j\theta}$.}\label{fig:fa:rotation}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\center\small
\begin{tabular}{cc}\hskip-8mm
\begin{dspPZPlot}[width=0.42\textwidth]{1.8}
\dspCPCircle[linewidth=0.5pt]{0,0}{1}
\dspCPCirclePoint[linecolor=ColorOne,toorg=true]{1}{0}{$x[0]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{36}{$x[1]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{72}{$x[2]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{108}{$x[3]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{144}{$x[4]$}
\dspCPArc{0.6}{0}{36}{$\omega$}
\psarc[linewidth=4pt,linecolor=lightgray]{->}(0,0){1.6\dspUnitX}{10}{120}
\uput[u](1.2,1.2){\normalsize $x[n]$}
\end{dspPZPlot}
&
\begin{dspPZPlot}[width=0.42\textwidth]{1.8}
\dspCPCircle[linewidth=0.5pt]{0,0}{1}
\dspCPCirclePoint[linecolor=ColorOne,toorg=true]{1}{-9}{$x[0]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-27}{$x[1]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-45}{$x[2]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-63}{$x[3]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-81}{$x[4]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-99}{$x[5]$}
\dspCPArcn{0.6}{351}{333}{$\omega$}
\psarc[linewidth=4pt,linecolor=lightgray]{<-}(0,0){1.6\dspUnitX}{-120}{-20}
\uput[d](1.2,-1.2){\normalsize $x[n]$}
\end{dspPZPlot}
\\ (a) & (b)
\end{tabular}
\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}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Why \textit{complex-valued} oscillations?}
The choice of a complex-valued signal as the prototypical oscillation may appear needlessly... \textit{complex} at first and, in fact, the Fourier transform of real-valued sequences could be derived entirely in the real-valued domain using only standard 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 complex 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,
\begin{align*}
\cos(\alpha + \beta) &= \Re\{e^{j\alpha}\,e^{j\beta}\} \\
&= \Re\{(\cos\alpha + j\sin\alpha)(\cos\beta + j\sin\beta)\} \\
&= \cos\alpha\cos\beta - \sin\alpha\sin\beta.
\end{align*}
No need to remember formulas means fewer chances of making mistakes.
\itempar{The notation is more compact:} the prototypical oscillation encodes the movement of a rotating point and its description always possesses two degrees of freedom, magnitude and phase. We can choose to encode this information using the real-valued vertical and horizontal coordinates of the point on a Cartesian plane (that is, using a cosine and a sine); or we can 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.
symmetry of mag\marginpar{TODO or LATER}
\subsection{Properties of complex oscillations}
\label{sec:fa:aliasing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\center\small
\begin{tabular}{cc}\hskip-8mm
\begin{dspPZPlot}[width=0.42\textwidth]{1.4}
\dspCPCircle[linewidth=0.5pt,linecolor=lightgray]{0,0}{1}
\dspCPCirclePoint[linecolor=ColorOne,toorg=true]{1}{30}{$e^{j\theta} = e^{j(\theta + 6\pi)}$}
\uput{0.49\dspUnitX}[15]{0}(0,0){$\theta$}
\dspCPArc{0.4}{0}{30}{}
\parametricplot[linecolor=ColorThree,linewidth=\dspTickLineWidth,arrows=->,plotpoints=500]%
{0}{1110}{t 360 div 0.05 mul 0.7 add dup t cos mul exch t sin mul}
\uput*{0.91\dspUnitX}[15]{0}(0,0){$\theta + 6\pi$}
\end{dspPZPlot}
&
\begin{dspPZPlot}[width=0.42\textwidth]{1.4}
\dspCPCircle[linewidth=0.5pt,linecolor=lightgray]{0,0}{1}
\dspCPCirclePoint[linecolor=ColorOne,toorg=true]{1}{30}{$e^{j\theta} = e^{j(\theta - 2\pi)}$}
\dspCPArc{0.4}{0}{30}{$\theta$}
\dspCPArcn[linecolor=ColorTwo]{0.6}{0}{-330}{}
\uput*{0.5\dspUnitX}[115]{0}(0,0){$-(2\pi -\theta)$}
\end{dspPZPlot}
\\ (a) & (b)
\end{tabular}
\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}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In discrete time, things are a bit different with respect to the properties of classic sinusoidal functions of a real variable.
\itempar{Periodicity.} 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
\begin{equation}
\omega = \frac{M}{N}\, 2\pi, \quad M,N \in \mathbb{Z}
\end{equation}
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.
\itempar{Aliasing.} 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
\[
e^{j\theta} = e^{j(\theta + 2k\pi)} \quad \forall k\in\mathbb{Z}.
\]
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:
\[
e^{j(\omega + 2k\pi)n} = e^{j\omega n}e^{j\,(kn)\,2\pi} = e^{j\omega n} \quad \forall k\in\mathbb{Z};
\]
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 \geq 2\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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\center\small
\begin{tabular}{cc}\hskip-8mm
\begin{dspPZPlot}[width=0.42\textwidth]{1.4}
\dspCPCircle[linewidth=0.5pt]{0,0}{1}
\dspCPCirclePoint[linecolor=ColorOne,toorg=true]{1}{0}{$x[0]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-18}{$x[1]$}
\dspCPArc{0.6}{0}{-18}{}
\uput*{0.5\dspUnitX}[115]{0}(0,0){$\omega$}
\end{dspPZPlot}
&
\begin{dspPZPlot}[width=0.42\textwidth]{1.4}
\dspCPCircle[linewidth=0.5pt]{0,0}{1}
\dspCPCirclePoint[linecolor=ColorOne,toorg=true]{1}{0}{$x[0]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-18}{$x[1]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-36}{$x[2]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-54}{$x[3]$}
\dspCPCirclePoint[linecolor=ColorOne]{1}{-72}{$x[4]$}
\dspCPArc{0.6}{-54}{-72}{}
\uput*{0.5\dspUnitX}[115]{0}(0,0){$\omega$}
\dspCPArcn[linewidth=3pt,linecolor=ColorThree]{0.8}{0}{-72}{}
\end{dspPZPlot}
\\ (a) & (b)
\end{tabular}
\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}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
c4science · Help