Returning to Fourier analysis

Now consider the bottom part of Figure 11.12. The operation of a linear filter is easy to understand and compute in the frequency domain. This is the function obtained by performing the Fourier transform on the signal, which provides an amplitude for every combination of frequency and phase. This transform was briefly introduced in Section 11.1 and illustrated in Figure 11.3. Formally, it is defined for discrete-time systems as

$\displaystyle X(f) = \sum_{k = -\infty}^{\infty} x[k] e^{-i 2\pi f k} ,$ (11.6)

in which $ X(f)$ is the resulting spectral distribution, which is a function of the frequency $ f$. The exponent involves $ i = \sqrt{-1}$ and is related to sinusoids through Euler's formula:

$\displaystyle e^{-i 2\pi f k} = \cos(-2\pi f k) + i \sin(-2\pi f k) .$ (11.7)

Unit complex numbers are used as an algebraic trick to represent the phase. The inverse Fourier transform is similar in form and converts the spectral distribution back into the time domain. These calculations are quickly performed in practice by using the Fast Fourier Transform (FFT) [11,189].

Steven M LaValle 2016-12-31