FFT
Fast Fourier transform (FFT) of input
Libraries:
DSP System Toolbox /
Transforms
Description
The FFT block computes the fast Fourier transform (FFT) across the first
dimension of an ND input array, u. The block
uses one of two possible FFT implementations. You can select an implementation based on
the FFTW library or an implementation based on a collection of Radix2 algorithms. To
allow the block to choose the implementation, you can select
Auto
. For more information about the FFT implementations,
see Algorithms.
For userspecified FFT lengths not equal to P, zero padding or truncating, or modulolength data wrapping occurs before the FFT operation. For an FFT with P ≤ M:
y = fft(u,M) % P ≤ M
Wrapping:
y(:,L) = fft(datawrap(u(:,L),M)) % P > M; L = 1,...,N
Truncating:
y (:,L) = fft(u,M) % P > M; L = 1,...,N
Tip
When the input length, P, is greater than the FFT length, M, you may see magnitude increases in your FFT output. These magnitude increases occur because the FFT block uses moduloM data wrapping to preserve all available input samples.
To avoid such magnitude increases, you can truncate the length of your input sample, P, to the FFT length, M. To do so, place a Pad block before the FFT block in your model.
Examples
Ports
Input
Port_1 — Input signal
vector  matrix  ND array
Input signal for computing the FFT. The block computes the FFT along the first dimension of the ND input signal.
For more information on how the block computes the FFT, see Description and Algorithms.
Data Types: single
 double
 int8
 int16
 int32
 int64
 uint8
 uint16
 uint32
 uint64
 fixed point
Complex Number Support: Yes
Output
Port_1 — FFT of input
vector  matrix  ND array
The FFT, computed across the first dimension of an ND input array. When the output of the block has an integer or fixedpoint data type, it is always signed.
The kth entry of the Lth output channel, y(k,L), equals the kth point of the Mpoint discrete Fourier transform (DFT) of the Lth input channel:
$$y(k,L)={\displaystyle \sum _{p=1}^{P}u(p,L){e}^{j2\pi (p1)(k1)/M}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}k=1,\dots ,M$$
For more information on how the block computes the FFT, see Description and Algorithms.
Data Types: single
 double
 int8
 int16
 int32
 fixed point
Complex Number Support: Yes
Parameters
Main
FFT implementation — FFT implementation
Auto
(default)  Radix2
 FFTW
Set this parameter to FFTW
to support an arbitrary length
input signal. The block restricts generated code with FFTW
implementation to host computers capable of running MATLAB^{®}.
Set this parameter to Radix2
for bitreversed processing,
fixed or floatingpoint data, or portable Ccode generation using the
Simulink^{®}
Coder™. The dimension M of the
MbyN input matrix, must be a
power of two. To work with other input sizes, use the Pad block to pad or truncate
these dimensions to powers of two, or if possible choose the FFTW
implementation. For more information about the algorithms used by the
Radix2
mode, see Radix2 Implementation.
Set this parameter to Auto
to let the block choose the FFT
implementation. For floatingpoint inputs with nonpoweroftwo
transform lengths, the FFTW algorithm is automatically chosen. Otherwise
a Radix2 algorithm is automatically chosen. For nonpoweroftwo
transform lengths, the block restricts generated code to MATLAB host computers.
Output in bitreversed order — Output in bitreversed order
off
(default)  on
Designate the order of the output channel elements relative to the ordering of the input elements. When you select this check box, the output channel elements appear in bitreversed order relative to the input ordering. If you clear this check box, the output channel elements appear in linear order relative to the input ordering.
Note
The FFT block calculates its output in bitreversed order. Linearly ordering the FFT block output requires an extra bitreversal operation. In many situations, you can increase the speed of the FFT block by selecting the Output in bitreversed order check box.
For more information ordering of the output, see Linear and BitReversed Output Order.
Dependencies
To enable this parameter, set FFT
implementation to Auto
or
Radix2
.
Divide output by FFT length — Divide output by FFT length
off
(default)  on
When you select this parameter, the block divides the output of the FFT by the FFT length. This option is useful when you want the output of the FFT to stay in the same amplitude range as its input. This is particularly useful when working with fixedpoint data types.
Inherit FFT length from input dimensions — Inherit FFT length from input dimensions
on
(default)  off
Select to inherit the FFT length from the input dimensions. When you select this check box, the input length must be a power of two.
Dependencies
When you do not select this check box, the FFT length parameter becomes available to specify the length.
FFT length — FFT length
64
(default)  integer
Specify FFT length as an integer greater than or equal to two.
When you set the FFT implementation parameter to
Radix2
, or when you check the Output
in bitreversed order check box, this value must be a
power of two.
Dependencies
To enable this parameter, clear the Inherit FFT length from input dimensions check box.
Wrap input data when FFT length is shorter than input length — Wrap or truncate input
on
(default)  off
Choose to wrap or truncate the input, depending on the FFT length. If you select this parameter, modulolength data wrapping occurs before the FFT operation when the FFT length is shorter than the input length. If you clear this check box, truncation of the input data to the FFT length occurs before the FFT operation.
Dependencies
To enable this parameter, clear the Inherit FFT length from input dimensions check box.
Data Types
Rounding mode — Rounding method
Floor
(default)  Ceiling
 Convergent
 Nearest
 Round
 Simplest
 Zero
Select the rounding mode for fixedpoint operations.
Limitations
The sine table values do not obey this parameter; instead, they
always round to Nearest
.
The Rounding mode parameter has no effect on numeric results when all these conditions are met:
Product output data type is
Inherit: Inherit via internal rule
.Accumulator data type is
Inherit: Inherit via internal rule
.
With these data type settings, the block operates in fullprecision mode.
Saturate on integer overflow — Saturate on integer overflow
off
(default)  on
When you select this parameter, the block saturates the result of its
fixedpoint operation. When you clear this parameter, the block wraps
the result of its fixedpoint operation. For details on
saturate
and wrap
, see overflow
mode for fixedpoint operations.
Limitations
The Saturate on integer overflow parameter has no effect on numeric results when all these conditions are met:
Product output data type is
Inherit: Inherit via internal rule
.Accumulator data type is
Inherit: Inherit via internal rule
.
With these data type settings, the block operates in fullprecision mode.
Sine table — Data type of sine table values
Inherit: Same word length as
input
(default)  fixdt(1,16)
Choose how to specify the word length of the values of the sine table. The fraction length of the sine table values always equals the word length minus one. You can set this parameter to:
A rule that inherits a data type, for example,
Inherit: Same word length as input
An expression that evaluates to a valid data type, for example,
fixdt(1,16)
Click the Show data type assistant button to display the Data Type Assistant, which helps you set the Sine table parameter.
See Specify Data Types Using Data Type Assistant (Simulink) for more information.
Limitations
The sine table values do not obey the Rounding
mode and Saturate on integer
overflow parameters; instead, they are always
saturated and rounded to Nearest
.
Product output — Product output data type
Inherit: Inherit via internal
rule
(default)  Inherit: Same as input
 fixdt(1,16,0)
Specify the product output data type. See FixedPoint Data Types and Multiplication Data Types for illustrations depicting the use of the product output data type in this block. You can set this parameter to:
A rule that inherits a data type, for example,
Inherit: Inherit via internal rule
. For more information on this rule, see Inherit via Internal Rule.An expression that evaluates to a valid data type, for example,
fixdt(1,16,0)
Click the Show data type assistant button to display the Data Type Assistant, which helps you set the Product output parameter.
See Specify Data Types Using Data Type Assistant (Simulink) for more information.
Accumulator — Accumulator data type
Inherit: Inherit via internal
rule
(default)  Inherit: Same as input
 Inherit: Same as product output
 fixdt(1,16,0)
Specify the accumulator data type. See FixedPoint Data Types for illustrations depicting the use of the accumulator data type in this block. You can set this parameter to:
A rule that inherits a data type, for example,
Inherit: Inherit via internal rule
. For more information on this rule, see Inherit via Internal Rule.An expression that evaluates to a valid data type, for example,
fixdt(1,16,0)
Click the Show data type assistant button to display the Data Type Assistant, which helps you set the Accumulator parameter.
See Specify Data Types Using Data Type Assistant (Simulink) for more information.
Output — Output data type
Inherit: Inherit via internal
rule
(default)  Inherit: Same as input
 fixdt(1,16,0)
Specify the output data type. See FixedPoint Data Types for illustrations depicting the use of the output data type in this block. You can set this parameter to:
A rule that inherits a data type, for example,
Inherit: Inherit via internal rule
.When you select
Inherit: Inherit via internal rule
, the block calculates the output word length and fraction length automatically. The equations that the block uses to calculate the ideal output word length and fraction length depend on the setting of the Divide output by FFT length check box.When you select the Divide output by FFT length check box, the ideal output word and fraction lengths are the same as the input word and fraction lengths.
When you clear the Divide output by FFT length check box, the block computes the ideal output word and fraction lengths according to the following equations:
$$W{L}_{idealoutput}=W{L}_{input}+\text{floor}({\mathrm{log}}_{2}(FFTlength1))+1$$
$$F{L}_{idealoutput}=F{L}_{input}$$
Using these ideal results, the internal rule then selects word lengths and fraction lengths that are appropriate for your hardware. For more information, see Inherit via Internal Rule.
An expression that evaluates to a valid data type, for example,
fixdt(1,16,0)
Click the Show data type assistant button to display the Data Type Assistant, which helps you set the Output parameter.
See Control Data Types of Signals (Simulink) for more information.
Output Minimum — Minimum value block should output
[]
(default)  scalar
Specify the minimum value that the block should output. The default
value is []
(unspecified). Simulink software uses this value to perform:
Simulation range checking (see Specify Signal Ranges (Simulink))
Automatic scaling of fixedpoint data types
Output Maximum — Maximum value block should output
[]
(default)  scalar
Specify the maximum value that the block should output. The default
value is []
(unspecified). Simulink software uses this value to perform:
Simulation range checking (see Specify Signal Ranges (Simulink))
Automatic scaling of fixedpoint data types
Lock data type settings against changes by the fixedpoint tools — Prevent fixedpoint tools from overriding data types
off
(default)  on
Select this parameter to prevent the fixedpoint tools from overriding the data types you specify in the block dialog box.
Block Characteristics
Data Types 

Direct Feedthrough 

Multidimensional Signals 

VariableSize Signals 

ZeroCrossing Detection 

^{a} 
More About
FixedPoint Data Types
The following diagrams show the data types used in the FFT block for fixedpoint signals. You can set the Sine table, Accumulator, Product output, and Output data types displayed in the diagrams in the FFT dialog box as discussed in Parameters.
Inputs to the FFT block are first cast to the output data type and stored in the output buffer. Each butterfly stage then processes signals in the accumulator data type, with the final output of the butterfly being cast back into the output data type. The block multiplies in a twiddle factor before each butterfly stage in a decimationintime FFT and after each butterfly stage in a decimationinfrequency FFT.
The output of the multiplier appears in the accumulator data type because both of the inputs to the multiplier are complex. For details on the complex multiplication performed, see Multiplication Data Types.
Note
When the block input is fixed point, all internal data types are signed fixed point.
Algorithms
FFTW Implementation
The FFTW implementation provides an optimized FFT calculation including support for poweroftwo and nonpoweroftwo transform lengths in both simulation and code generation. Generated code using the FFTW implementation can only run on computers capable of running MATLAB. The input data type must be floatingpoint.
Radix2 Implementation
The Radix2 implementation supports bitreversed processing, fixed or floatingpoint data, and allows the block to provide portable Ccode generation using the Simulink Coder. The dimension M of the MbyN input matrix must be a power of two. To work with other input sizes, use the Pad block to pad or truncate these dimensions to powers of two, or if possible choose the FFTW implementation.
With Radix2 selected, the block implements one or more of the following algorithms:
Butterfly operation
Doublesignal algorithm
Halflength algorithm
Radix2 decimationintime (DIT) algorithm
Radix2 decimationinfrequency (DIF) algorithm
Complexity of Input  Output Ordering  Algorithms Used for FFT Computation 

Complex  Linear  Bitreversed operation and radix2 DIT 
Complex  Bitreversed  Radix2 DIF 
Real  Linear  Bitreversed operation and radix2 DIT in conjunction with the halflength and doublesignal algorithms 
Real  Bitreversed  Radix2 DIF in conjunction with the halflength and doublesignal algorithms 
The efficiency of the FFT algorithm can be enhanced for real input signals by forming complexvalued sequences from the realvalued sequences prior to the computation of the DFT. When there are 2N+1 real input channels, the FFT block forms these complexvalued sequences by applying the doublesignal algorithm to the first 2N input channels, and the halflength algorithm to the last oddnumbered channel.
For real input signals with fixedpoint data types, different numerical results might appear in the output of the last oddnumbered channel, even when all input channels are identical. This numerical difference results from differences in the doublesignal algorithm and the halflength algorithm.
You can eliminate this numerical difference in two ways:
Using full precision arithmetic for fixedpoint input signals
Changing the input data type to floating point
For more information on the doublesignal algorithm, see [2], “Efficient Computation of the DFT of Two Real Sequences” on page 475. For more information on the halflength algorithm, see [2], “Efficient Computation of the DFT of a 2NPoint Real Sequence” on page 476.
In certain situations, the block’s Radix–2 algorithm computes all the possible trigonometric values of the twiddle factor
$${e}^{j\frac{2\pi k}{K}}$$
where K is the greater value of either M or N and $$k=0,\cdots ,K1$$. The block stores these values in a table and retrieves them during simulation. The number of table entries for fixedpoint and floatingpoint is summarized in the following table:
Number of Table Entries for NPoint FFT  

floatingpoint  3N/4 
fixedpoint  N 
References
[1] Orfanidis, S. J. Introduction to Signal Processing. Upper Saddle River, NJ: Prentice Hall, 1996, p. 497.
[2] Proakis, John G. and Dimitris G. Manolakis. Digital Signal Processing, 3rd ed. Upper Saddle River, NJ: Prentice Hall, 1996.
[3] FFTW (https://www.fftw.org
)
[4] 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. 13811384.
Extended Capabilities
C/C++ Code Generation
Generate C and C++ code using Simulink® Coder™.
Usage notes and limitations:
When the following conditions apply, the executable generated from this block relies on prebuilt dynamic library files (
.dll
files) included with MATLAB:FFT implementation is set to
FFTW
.Inherit FFT length from input dimensions is cleared, and FFT length is set to a value that is not a power of two.
Use the
packNGo
function to package the code generated from this block and all the relevant files in a compressed zip file. Using this zip file, you can relocate, unpack, and rebuild your project in another development environment where MATLAB is not installed. For more details, see How To Run a Generated Executable Outside MATLAB.When the FFT length is a power of two, you can generate standalone C and C++ code from this block.
FixedPoint Conversion
Design and simulate fixedpoint systems using FixedPoint Designer™.
Version History
Introduced before R2006a
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)