fft

Fast Fourier transform.

Library

EngeeDSP

Syntax

Function call

Y = fft(X) — calculates the Discrete Fourier transform (DFT) for the argument X using the Fast Fourier Transform (FFT) algorithm. Argument Y has the same size as X.
- If X — vector, then fft(X) returns the Fourier transform for this vector.
- If X — the matrix, then fft(X) examines the columns of the argument X as vectors, and returns the Fourier transform for each column.
- If X — a multidimensional array, then fft(X) considers values based on the first dimension of the array, the size of which is not equal to 1, as vectors, and returns the Fourier transform for each vector.

Y = fft(X,n) — returns n-point DFT.
- If X — vector and length X less n Then X padded with zeros up to the length n.
- If X — vector and length X more n Then X truncated to length n.
- If X — a matrix, then each column is treated as a vector.
- If X — multidimensional array, the first dimension of the array, the size of which is not equal to 1, is processed as a vector.

Y = fft(X,n,dim) — returns the Fourier transform in dimension dim. For example, if X — the matrix, then fft(X,n,2) returns n-point Fourier transform for each row.

Arguments

Input arguments

# X — input array

+ vector | the matrix | multidimensional array

Details

An input array specified as a vector, matrix, or multidimensional array.

If X — an empty matrix of size 0 on 0 Then fft(X) returns an empty matrix of size 0 on 0.

Data types	`Float64`, `Float32`, `Int8`, `Int16`, `Int32`, `UInt8`, `UInt16`, `UInt32`, `Bool`
Support for complex numbers	Yes

# n is the length of the conversion

+ [] (default) | a non-negative integer scalar

Details

The length of the transformation, set as [] or a non-negative integer scalar. Specifying a positive integer for the conversion length can improve the performance of the function. fft. The length is usually specified as a power of two or a value that can be factorized (with prime factors of no more than 7). If n less than the length of the signal, the function fft ignores the remaining signal values after n-th element and returns a truncated result. If n equally 0, function fft returns an empty matrix.

Data types

Float64, Float32, Int8, Int16, Int32, UInt8, UInt16, UInt32, Bool

# dim — the measurement for which the operation is performed

+ positive integer scalar

Details

The dimension that the operation is performed on is set as a positive integer. If no dimension is specified, the first dimension of the array is used by default, the size of which is not equal to 1.

fft(X,[],1) performs an operation on the columns of an array X and returns the Fourier transform for each column.
fft(X,[],2) performs an operation on the rows of an array X and returns the Fourier transform for each row.

If dim more ndims(X) Then fft(X,[],dim) returns X. If specified n, fft(X,n,dim) complements or truncates X up to length n by measurement dim.

Data types

Float64, Float32, Int8, Int16, Int32, UInt8, UInt16, UInt32, Bool

Output arguments

# Y is a representation in the frequency domain

+ vector | the matrix | multidimensional array

Details

The representation in the frequency domain is returned as a vector, matrix, or multidimensional array.

If the argument is X has a type Float32, then the function fft it is calculated with single precision, and Y It also has a type Float32. Otherwise, Y returned as a type Float64.

Size of the argument Y It is defined as follows:

For Y = fft(X) or Y = fft(X,[],dim) size Y is equal to the size of X.
For Y = fft(X,n,dim) meaning size(Y,dim) equally n, while the size of all other dimensions remains the same as that of X.

If X is a real number, then Y is conjugate symmetric, and the number of unique points in Y equally ceil((n+1)/2).

Data types

Float64, Float32

Additional Info

Discrete Fourier transform

Y = fft(X) and X = ifft(Y) implement the Fourier transform and the inverse Fourier transform, respectively. For X and Y lengths n these transformations are defined as follows:

where — one of the roots of one.

Recommendations

Lead time fft depends on the length of the conversion. Transformation lengths having only small prime factors (no more than 7) provide significantly faster execution time than those that are simple numbers with large prime factors.
For most values n DFTs with real input data require about half as much computing time as DFTs with complex input data. However, with large prime factors n There is little or no difference in speed.
You can potentially increase the speed fft using the utility fftw. This function controls the optimization of the algorithm used to calculate the FFT of a given size and dimension.

Algorithms

FFT functions (fft, fft2, ifft, ifft2) are based on the FFTW library [1] [2].

List of literature

FFTW (https://www.fftw.org)
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.