This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.

Fourier Transforms

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

Discrete Fourier Transform

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 $x$ that has $n$ uniformly sampled points, the following formula defines the discrete Fourier transform (DFT) of $x$:

$$y_{k+1} = \sum_{j=0}^{n-1}\omega^{jk}x_{j+1}$$

$i$ is the imaginary unit, $\omega = e^{-2\pi i/n}$ is one of $n$ complex roots of unity, and $j$ and $k$ are indices that run from $0$ to $n-1$. The indices for $x$ and $y$ 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 $y$ with $n$ data points is defined as the following:

$$x_{j+1} = \frac{1}{n}\sum_{k=0}^{n-1}\omega^{-jk}y_{k+1}$$

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 $y$, on the order of $n^2$ floating-point operations are required. This is not computationally optimal, and the DFT is commonly computed with a faster algorithm.

Fast Fourier Transform

The fast Fourier transform (FFT) is a computationally efficient implementation of the DFT. While a one-dimensional DFT requires on the order of $n^2$ floating-point operations for a vector of $n$ data points, the FFT requires on the order of $n\log{n}$ operations, a significant reduction in computational complexity. There are many specialized implementations of the FFT algorithm, such as ones that gain efficiency when $n$ 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.

Basic Fourier Analysis

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.


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.



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

x2 = ifft(y);