# fft

Fast Fourier transform

## Description

computes
the discrete
Fourier transform (DFT) of `Y`

= fft(`X`

)`X`

using a fast
Fourier transform (FFT) algorithm.

If

`X`

is a vector, then`fft(X)`

returns the Fourier transform of the vector.If

`X`

is a matrix, then`fft(X)`

treats the columns of`X`

as vectors and returns the Fourier transform of each column.If

`X`

is a multidimensional array, then`fft(X)`

treats the values along the first array dimension whose size does not equal 1 as vectors and returns the Fourier transform of each vector.

returns
the `Y`

= fft(`X`

,`n`

)`n`

-point DFT. If no value is specified, `Y`

is
the same size as `X`

.

If

`X`

is a vector and the length of`X`

is less than`n`

, then`X`

is padded with trailing zeros to length`n`

.If

`X`

is a vector and the length of`X`

is greater than`n`

, then`X`

is truncated to length`n`

.If

`X`

is a matrix, then each column is treated as in the vector case.If

`X`

is a multidimensional array, then the first array dimension whose size does not equal 1 is treated as in the vector case.

## Examples

### Noisy Signal

Use Fourier transforms to find the frequency components of a signal buried in noise.

Specify the parameters of a signal with a sampling frequency of 1 kHz and a signal duration of 1.5 seconds.

Fs = 1000; % Sampling frequency T = 1/Fs; % Sampling period L = 1500; % Length of signal t = (0:L-1)*T; % Time vector

Form a signal containing a 50 Hz sinusoid of amplitude 0.7 and a 120 Hz sinusoid of amplitude 1.

S = 0.7*sin(2*pi*50*t) + sin(2*pi*120*t);

Corrupt the signal with zero-mean white noise with a variance of 4.

X = S + 2*randn(size(t));

Plot the noisy signal in the time domain. It is difficult to identify the frequency components by looking at the signal `X(t)`

.

plot(1000*t(1:50),X(1:50)) title("Signal Corrupted with Zero-Mean Random Noise") xlabel("t (milliseconds)") ylabel("X(t)")

Compute the Fourier transform of the signal.

Y = fft(X);

Compute the two-sided spectrum `P2`

. Then compute the single-sided spectrum `P1`

based on `P2`

and the even-valued signal length `L`

.

P2 = abs(Y/L); P1 = P2(1:L/2+1); P1(2:end-1) = 2*P1(2:end-1);

Define the frequency domain `f`

and plot the single-sided amplitude spectrum `P1`

. The amplitudes are not exactly at 0.7 and 1, as expected, because of the added noise. On average, longer signals produce better frequency approximations.

f = Fs*(0:(L/2))/L; plot(f,P1) title("Single-Sided Amplitude Spectrum of X(t)") xlabel("f (Hz)") ylabel("|P1(f)|")

Now, take the Fourier transform of the original, uncorrupted signal and retrieve the exact amplitudes, 0.7 and 1.0.

Y = fft(S); P2 = abs(Y/L); P1 = P2(1:L/2+1); P1(2:end-1) = 2*P1(2:end-1); plot(f,P1) title("Single-Sided Amplitude Spectrum of S(t)") xlabel("f (Hz)") ylabel("|P1(f)|")

### Gaussian Pulse

Convert a Gaussian pulse from the time domain to the frequency domain.

Specify the parameters of a signal with a sampling frequency of 44.1 kHz and a signal duration of 1 ms. Create a Gaussian pulse with a standard deviation of 0.1 ms.

Fs = 44100; % Sampling frequency T = 1/Fs; % Sampling period t = -0.5:T:0.5; % Time vector L = length(t); % Signal length X = 1/(0.4*sqrt(2*pi))*(exp(-t.^2/(2*(0.1*1e-3)^2)));

Plot the pulse in the time domain.

plot(t,X) title("Gaussian Pulse in Time Domain") xlabel("Time (t)") ylabel("X(t)") axis([-1e-3 1e-3 0 1.1])

The execution time of `fft`

depends on the length of the transform. Transform lengths that have only small prime factors result in significantly faster execution time than those that have large prime factors.

In this example, the signal length `L`

is 44,101, which is a very large prime number. To improve the performance of `fft`

, identify an input length that is the next power of 2 from the original signal length. Calling `fft`

with this input length pads the pulse `X`

with trailing zeros to the specified transform length.

n = 2^nextpow2(L);

Convert the Gaussian pulse to the frequency domain.

Y = fft(X,n);

Define the frequency domain and plot the unique frequencies.

f = Fs*(0:(n/2))/n; P = abs(Y/n).^2; plot(f,P(1:n/2+1)) title("Gaussian Pulse in Frequency Domain") xlabel("f (Hz)") ylabel("|P(f)|^2")

### Cosine Waves

Compare cosine waves in the time domain and the frequency domain.

Specify the parameters of a signal with a sampling frequency of 1 kHz and a signal duration of 1 second.

Fs = 1000; % Sampling frequency T = 1/Fs; % Sampling period L = 1000; % Length of signal t = (0:L-1)*T; % Time vector

Create a matrix where each row represents a cosine wave with scaled frequency. The result, `X`

, is a 3-by-1000 matrix. The first row has a wave frequency of 50, the second row has a wave frequency of 150, and the third row has a wave frequency of 300.

x1 = cos(2*pi*50*t); % First row wave x2 = cos(2*pi*150*t); % Second row wave x3 = cos(2*pi*300*t); % Third row wave X = [x1; x2; x3];

Plot the first 100 entries from each row of `X`

in a single figure in order and compare their frequencies.

for i = 1:3 subplot(3,1,i) plot(t(1:100),X(i,1:100)) title("Row " + num2str(i) + " in the Time Domain") end

Specify the `dim`

argument to use `fft`

along the rows of `X`

, that is, for each signal.

dim = 2;

Compute the Fourier transform of the signals.

Y = fft(X,L,dim);

Calculate the double-sided spectrum and single-sided spectrum of each signal.

P2 = abs(Y/L); P1 = P2(:,1:L/2+1); P1(:,2:end-1) = 2*P1(:,2:end-1);

In the frequency domain, plot the single-sided amplitude spectrum for each row in a single figure.

for i=1:3 subplot(3,1,i) plot(0:(Fs/L):(Fs/2-Fs/L),P1(i,1:L/2)) title("Row " + num2str(i) + " in the Frequency Domain") end

### Phase of Sinusoids

Create a signal that consists of two sinusoids of frequencies 15 Hz and 40 Hz. The first sinusoid is a cosine wave with phase $-\pi /4$, and the second is a cosine wave with phase $\pi /2$. Sample the signal at 100 Hz for 1 s.

Fs = 100; t = 0:1/Fs:1-1/Fs; x = cos(2*pi*15*t - pi/4) + cos(2*pi*40*t + pi/2);

Compute the Fourier transform of the signal. Plot the magnitude of the transform as a function of frequency.

y = fft(x); z = fftshift(y); ly = length(y); f = (-ly/2:ly/2-1)/ly*Fs; stem(f,abs(z)) title("Double-Sided Amplitude Spectrum of x(t)") xlabel("Frequency (Hz)") ylabel("|y|") grid

Compute the phase of the transform, removing small-magnitude transform values. Plot the phase as a function of frequency.

tol = 1e-6; z(abs(z) < tol) = 0; theta = angle(z); stem(f,theta/pi) title("Phase Spectrum of x(t)") xlabel("Frequency (Hz)") ylabel("Phase/\pi") grid

### Interpolation of FFT

Interpolate the Fourier transform of a signal by padding with zeros.

Specify the parameters of a signal with a sampling frequency of 80 Hz and a signal duration of 0.8 s.

Fs = 80; T = 1/Fs; L = 65; t = (0:L-1)*T;

Create a superposition of a 2 Hz sinusoidal signal and its higher harmonics. The signal contains a 2 Hz cosine wave, a 4 Hz cosine wave, and a 6 Hz sine wave.

X = 3*cos(2*pi*2*t) + 2*cos(2*pi*4*t) + sin(2*pi*6*t);

Plot the signal in the time domain.

plot(t,X) title("Signal superposition in time domain") xlabel("t (ms)") ylabel("X(t)")

Compute the Fourier transform of the signal.

Y = fft(X);

Compute the single-sided amplitude spectrum of the signal.

f = Fs*(0:(L-1)/2)/L; P2 = abs(Y/L); P1 = P2(1:(L+1)/2); P1(2:end) = 2*P1(2:end);

In the frequency domain, plot the single-sided spectrum. Because the time sampling of the signal is quite short, the frequency resolution of the Fourier transform is not precise enough to show the peak frequency near 4 Hz.

plot(f,P1,"-o") title("Single-Sided Spectrum of Original Signal") xlabel("f (Hz)") ylabel("|P1(f)|")

To better assess the peak frequencies, you can increase the length of the analysis window by padding the original signal with zeros. This method automatically interpolates the Fourier transform of the signal with a more precise frequency resolution.

Identify a new input length that is the next power of 2 from the original signal length. Pad the signal `X`

with trailing zeros to extend its length. Compute the Fourier transform of the zero-padded signal.

n = 2^nextpow2(L); Y = fft(X,n);

Compute the single-sided amplitude spectrum of the padded signal. Because the signal length `n`

increased from 65 to 128, the frequency resolution becomes `Fs/n`

, which is 0.625 Hz.

f = Fs*(0:(n/2))/n; P2 = abs(Y/L); P1 = P2(1:n/2+1); P1(2:end-1) = 2*P1(2:end-1);

Plot the single-sided spectrum of the padded signal. This new spectrum shows the peak frequencies near 2 Hz, 4 Hz, and 6 Hz within the frequency resolution of 0.625 Hz.

plot(f,P1,"-o") title("Single-Sided Spectrum of Padded Signal") xlabel("f (Hz)") ylabel("|P1(f)|")

## Input Arguments

`X`

— Input array

vector | matrix | multidimensional array

Input array, specified as a vector, matrix, or multidimensional array.

If `X`

is an empty 0-by-0 matrix, then `fft(X)`

returns
an empty 0-by-0 matrix.

**Data Types: **`double`

| `single`

| `int8`

| `int16`

| `int32`

| `uint8`

| `uint16`

| `uint32`

| `logical`

**Complex Number Support: **Yes

`n`

— Transform length

`[]`

(default) | nonnegative integer scalar

Transform length, specified as `[]`

or a nonnegative integer scalar.
Specifying a positive integer scalar for the transform length can improve
the performance of `fft`

. The length is typically specified
as a power of 2 or a value that can be factored into a product of small
prime numbers (prime factors not greater than 7). If `n`

is
less than the length of the signal, then `fft`

ignores the
remaining signal values past the `n`

th entry and returns
the truncated result. If `n`

is `0`

, then
`fft`

returns an empty matrix.

**Example: **`n = 2^nextpow2(size(X,1))`

**Data Types: **`double`

| `single`

| `int8`

| `int16`

| `int32`

| `uint8`

| `uint16`

| `uint32`

| `logical`

`dim`

— Dimension to operate along

positive integer scalar

Dimension to operate along, specified as a positive integer scalar. If you do not specify the dimension, then the default is the first array dimension of size greater than 1.

`fft(X,[],1)`

operates along the columns of`X`

and returns the Fourier transform of each column.`fft(X,[],2)`

operates along the rows of`X`

and returns the Fourier transform of each row.

If `dim`

is greater than `ndims(X)`

,
then `fft(X,[],dim)`

returns `X`

.
When `n`

is specified, `fft(X,n,dim)`

pads
or truncates `X`

to length `n`

along
dimension `dim`

.

**Data Types: **`double`

| `single`

| `int8`

| `int16`

| `int32`

| `uint8`

| `uint16`

| `uint32`

| `logical`

## Output Arguments

`Y`

— Frequency domain representation

vector | matrix | multidimensional array

Frequency domain representation returned as a vector, matrix, or multidimensional array.

If `X`

is of type `single`

,
then `fft`

natively computes in single precision,
and `Y`

is also of type `single`

.
Otherwise, `Y`

is returned as type `double`

.

The size of `Y`

is as follows:

For

`Y = fft(X)`

or`Y = fft(X,[],dim)`

, the size of`Y`

is equal to the size of`X`

.For

`Y = fft(X,n,dim)`

, the value of`size(Y,dim)`

is equal to`n`

, while the size of all other dimensions remains as in`X`

.

If `X`

is real, then `Y`

is
conjugate symmetric, and the number of unique points in `Y`

is `ceil((n+1)/2)`

.

**Data Types: **`double`

| `single`

## More About

### Discrete Fourier Transform of Vector

`Y = fft(X)`

and ```
X
= ifft(Y)
```

implement the Fourier transform and inverse Fourier
transform, respectively. For `X`

and `Y`

of
length `n`

, these transforms are defined as follows:

$$\begin{array}{l}Y(k)={\displaystyle \sum _{j=1}^{n}X}(j)\text{\hspace{0.17em}}{W}_{n}^{(j-1)\text{}(k-1)}\\ X(j)=\frac{1}{n}{\displaystyle \sum _{k=1}^{n}Y}(k)\text{\hspace{0.17em}}{W}_{n}{}^{-(j-1)\text{}(k-1)},\end{array}$$

where

$${W}_{n}={e}^{(-2\pi i)/n}$$

is one of *n* roots
of unity.

## Tips

The execution time of

`fft`

depends on the length of the transform. Transform lengths that have only small prime factors (not greater than 7) result in significantly faster execution time than those that are prime or have large prime factors.For most values of

`n`

, real-input DFTs require roughly half the computation time of complex-input DFTs. However, when`n`

has large prime factors, there is little or no speed difference.You can potentially increase the speed of

`fft`

using the utility function`fftw`

. This function controls the optimization of the algorithm used to compute an FFT of a particular size and dimension.

## Algorithms

The FFT functions (`fft`

, `fft2`

, `fftn`

, `ifft`

, `ifft2`

, `ifftn`

)
are based on a library called FFTW [1] [2].

## References

[1] FFTW (https://www.fftw.org)

[2] Frigo, M., and S. G. Johnson. “FFTW:
An Adaptive Software Architecture for the FFT.” *Proceedings
of the International Conference on Acoustics, Speech, and Signal
Processing*. Vol. 3, 1998, pp. 1381-1384.

## Extended Capabilities

### C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

For limitations related to variable-size data, see Variable-Sizing Restrictions for Code Generation of Toolbox Functions (MATLAB Coder).

For MEX output, MATLAB

^{®}Coder™ uses the library that MATLAB uses for FFT algorithms. For standalone C/C++ code, by default, the code generator produces code for FFT algorithms instead of producing FFT library calls. To generate calls to a specific installed FFTW library, provide an FFT library callback class. For more information about an FFT library callback class, see`coder.fftw.StandaloneFFTW3Interface`

(MATLAB Coder).For simulation of a MATLAB Function block, the simulation software uses the library that MATLAB uses for FFT algorithms. For C/C++ code generation, by default, the code generator produces code for FFT algorithms instead of producing FFT library calls. To generate calls to a specific installed FFTW library, provide an FFT library callback class. For more information about an FFT library callback class, see

`coder.fftw.StandaloneFFTW3Interface`

(MATLAB Coder).Using the Code Replacement Library (CRL), you can generate optimized code that runs on ARM

^{®}Cortex^{®}-A processors with Neon extension. To generate this optimized code, you must install the Embedded Coder^{®}Support Package for ARM Cortex-A Processors (Embedded Coder Support Package for ARM Cortex-A Processors). The generated code for ARM Cortex-A uses the Ne10 library. For more information, see Ne10 Conditions for MATLAB Functions to Support ARM Cortex-A Processors (Embedded Coder Support Package for ARM Cortex-A Processors).Using the Code Replacement Library (CRL), you can generate optimized code that runs on ARM Cortex-M processors. To generate this optimized code, you must install the Embedded Coder Support Package for ARM Cortex-M Processors (Embedded Coder Support Package for ARM Cortex-M Processors). The generated code for ARM Cortex-M uses the CMSIS library. For more information, see CMSIS Conditions for MATLAB Functions to Support ARM Cortex-M Processors (Embedded Coder Support Package for ARM Cortex-M Processors).

### GPU Code Generation

Generate CUDA® code for NVIDIA® GPUs using GPU Coder™.

### Thread-Based Environment

Run code in the background using MATLAB® `backgroundPool`

or accelerate code with Parallel Computing Toolbox™ `ThreadPool`

.

This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.

### GPU Arrays

Accelerate code by running on a graphics processing unit (GPU) using Parallel Computing Toolbox™.

Usage notes and limitations:

The output

`Y`

is always complex even if all the imaginary parts are zero.

For more information, see Run MATLAB Functions on a GPU (Parallel Computing Toolbox).

### Distributed Arrays

Partition large arrays across the combined memory of your cluster using Parallel Computing Toolbox™.

Usage notes and limitations:

For distributed arrays, instead of using a parallel FFT algorithm,

`fft`

gathers vectors on a single worker to perform prime length FFTs. For large prime-length vector FFTs, out-of-memory errors can result.

For more information, see Run MATLAB Functions with Distributed Arrays (Parallel Computing Toolbox).

## Version History

**Introduced before R2006a**

## Open Example

You have a modified version of this example. Do you want to open this example with your edits?

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

# Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)