This topic describes the discrete Fourier transform and its implementations, and introduces an example of basic Fourier analysis for signal processing applications.

The Fourier transform is a mathematical formula that relates a signal sampled in time or space to the same signal sampled in frequency. For a vector that has uniformly sampled points, the following formula defines the discrete Fourier transform (DFT) of :

is the imaginary unit, is one of complex roots of unity, and and are indices that run from to . The indices for and are shifted by 1 in this formula to reflect vector indices in MATLAB®.

The inverse Fourier transform converts a signal sampled in frequency back to a signal sampled in time or space. The inverse Fourier transform of a vector with data points is defined as the following:

In signal processing, the Fourier transform can reveal important characteristics of a signal, namely, its frequency components. Modern signal and image processing applications often need to handle signals with millions of discrete data points. To compute each element of , on the order of floating-point operations are required. This is not computationally optimal, and the DFT is commonly computed with a faster algorithm.

The fast Fourier transform (FFT) is a computationally efficient implementation of the DFT. While a one-dimensional DFT requires on the order of floating-point operations for a vector of data points, the FFT requires on the order of operations, a significant reduction in computational complexity. There are many specialized implementations of the FFT algorithm, such as ones that gain efficiency when is a power of 2.

In MATLAB®, the `fft`

and `ifft`

functions compute the 1-D fast Fourier transform and inverse transform, respectively. For two-dimensional data, you can compute the 2-D transform and inverse transform using `fft2`

and `ifft2`

. For higher dimensional arrays, use the `fftn`

and `ifftn`

functions. For any of these FFT implementations, you can also use the `fftw`

function, which optimizes speed based on a heuristic tuning algorithm. The `fftshift`

function shifts the output of a Fourier transform so that the zero-frequency component is in the center, and the `ifftshift`

function reverses this shift. Since the zero-frequency component is always the first element of the output, shifting it to the center can be useful for visualizing the spectrum.

This example uses the Fourier transform to identify component frequencies in a simple signal.

Create a time vector `t`

and a sinusoidal signal `x`

that is a function of `t`

.

t = 0:1/50:10-1/50; x = sin(2*pi*15*t) + sin(2*pi*20*t);

Plot the signal as a function of time.

plot(t,x)

Compute the Fourier transform of the signal, and then compute the magnitude `m`

and phase `p`

of the signal.

y = fft(x); m = abs(y); p = angle(y);

Compute the frequency vector associated with the signal `y`

, which is sampled in frequency space.

f = (0:length(y)-1)*50/length(y);

Plot the magnitude and phase of the signal as a function of frequency. The spikes in magnitude correspond to the signal's frequency components.

subplot(2,1,1) plot(f,m) title('Magnitude') subplot(2,1,2) plot(f,rad2deg(p)) title('Phase')

Compute and plot the inverse transform of , which reproduces the original data in up to round-off error.

figure x2 = ifft(y); plot(t,x2)