FFT

Fast Fourier Transform (FFT) of the input signal.

fft

Description

The FFT block computes the Fast Fourier Transform (FFT) on the first dimension of a multidimensional input array, .

The block uses one of two possible implementations of the FFT. You can choose the implementation based on the FFTW library or the implementation based on the Radix-2 algorithm.

When the input signal length, , is greater than the FFT length, , you may observe an increase in the amplitude of the output signal. This is because the FFT block uses length modulo data reset , to preserve all available input samples.

To avoid this amplitude increase, you can truncate the input sample length to the FFT length . To do this, place the Pad block before the FFT block in the model.

Ports

Input

Port_1 - input signal
vector | matrix| multidimensional array

Input signal for FFT calculation as vector, matrix or multidimensional array.

The block calculates the FFT by the first dimension of the multidimensional input signal.

Data types: Float16, Float32, Float64, Int8, Int16, Int32, Int64, UInt8, UInt16, UInt32, UInt64.

Support for complex numbers: Yes

Output

Port_1 - FFT of the input signal
vector | matrix| multidimensional array

Output signal returned as a vector, matrix or multidimensional array.

FFT calculated from the first dimension of a multidimensional input array.

The -th entry of the -th output channel, , is equal to the -th point of the -point discrete Fourier transform (DFT) of the -th input channel:

Data types: Float16, Float32, Float64, Int8, Int16, Int32, Int64, UInt8, UInt16, UInt32, UInt64.

Support for complex numbers: Yes

Parameters

Main

FFT implementation - FFT implementation
Radix-2 (by default) | FFTW

FFT implementation:

FFTW - support input signal of arbitrary length.
Radix-2 - implementation of bitwise processing of floating point data. The dimensionality of the input matrix with the size to must be equal to the power of two. To work with other input data dimensions, use the block Pad, to flatten or truncate these dimensions to powers of two, or if possible, choose the FFTW implementation.

Output in bit-reversed order - output in bit-reversed order
off (by default) | on

Specifies the order of the output channel elements relative to the order of the input channel elements. When checked, the output channel elements are displayed in bit-reversed order relative to the input sequence order. When unchecked, the output channel elements are displayed in linear order relative to the input sequence order.

The FFT block computes its output in bit-reverse order. The linear ordering of the FFT block’s output requires an additional bit-reverse operation. In many situations, you can increase the speed of the FFT block by checking the Output in bit-reversed order checkbox.

Dependencies

To use this parameter, set the FFT implementation parameter to Radix-2.

Divide output by FFT length - divide output by FFT length
off (by default) | on.

When this option is selected, the block divides the FFT output by FFT length. This option is useful when you want the FFT output to remain in the same amplitude range as the input.

Inherit FFT length from input dimensions - inherit FFT length from input dimensions
enabled (by default) | disabled

Select to inherit FFT length from input dimensions. When this checkbox is selected, the input length must be equal to a power of two.

Dependencies

If this checkbox is not selected, the FFT length parameter becomes available for specifying the length.

FFT length - FFT length
64 (by default) | ` integer`.

Specify the FFT length as an integer, which is a power of two.

If the FFT implementation parameter is set to Radix-2 or the Output in bit-reversed order checkbox is selected, this value must be equal to the power of two.

Dependencies

To use this parameter, uncheck Inherit FFT length from input dimensions.

Wrap input data when FFT length is shorter than input length - collapse or truncate input data
On (By default) | Off

Selects whether to convolve or truncate the input data depending on the FFT length. If selected, modulo convolution is performed before the FFT operation when the FFT length is less than the input length. If unchecked, the input data is truncated to the FFT length before the FFT operation.

Dependencies

To use this option, clear the Inherit FFT length from input dimensions checkbox.

Algorithms

FFTW implementation

The FFTW implementation provides an optimised FFT calculation, including support for transform lengths equal to and not equal to powers of two, as in simulation. The input data type must be floating point.

Radix-2 implementation

The Radix-2 implementation supports bit-reverse processing and allows the block to perform C code generation. The dimensionality of an input matrix of size M by N must be of degree two. To work with other input dimensions, use the Pad block to augment or truncate these dimensions to powers of two.

When Radix-2 is selected, the block implements one or more of the following algorithms:

Butterfly operation
Double signal algorithm
Half length algorithm
Radix-2’s time-invariant thinning (DIT) algorithm
Radix-2 Frequency (DIF) Thinning Algorithm

Radix-2 algorithms for real and complex signals

Complexity of input data	Order of output data	Algorithms used for FFT calculation
Complex	Linear	Bit-reversal operation and Radix-2 DIT algorithm
Complex	Bit-reversal	Radix-2 DIF
Real	Linear	Bit-reverse operation and Radix-2 DIT combined with half-length and double-signal algorithms
Real	Bit-reverse	Radix-2 DIF combined with half-length and double-signal algorithms

Complexity of input data

Order of output data

Algorithms used for FFT calculation

Complex

Linear

Bit-reversal operation and Radix-2 DIT algorithm

Complex

Bit-reversal

Radix-2 DIF

Real

Linear

Bit-reverse operation and Radix-2 DIT combined with half-length and double-signal algorithms

Real

Bit-reverse

Radix-2 DIF combined with half-length and double-signal algorithms

The efficiency of the FFT algorithm can be improved for real input signals by forming complex sequences from the real sequences before computing the DIF. If there are real input channels, the FFT unit generates these complex sequences by applying the double signal algorithm to the first input channels and the half length algorithm to the last odd channel.

Optimising Radix-2 for a table of trigonometric values

In some situations, the Radix-2 block algorithm calculates all possible trigonometric values of the twiddle factor.

where

- is the larger of the two values: or ,
.

The block stores these values in a table and retrieves them during the simulation. The number of entries in the table for the floating point is shown in the following table:

Number of entries in the table for N-point FFT
floating point

Number of entries in the table for N-point FFT

floating point

Bibliography

Orfanidis, S. J. Introduction to Signal Processing. Upper Saddle River, NJ: Prentice Hall, 1996, p. 497.
Proakis, John G. and Dimitris G. Manolakis. Digital Signal Processing, 3rd ed. Upper Saddle River, NJ: Prentice Hall, 1996.
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.