Documentation

This is machine translation

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

FFT

Fast Fourier transform (FFT) of input

Library

Transforms

`dspxfrm3`

Description

The FFT block computes the fast Fourier transform (FFT) across the first dimension of an N-D input array, u. For user-specified FFT lengths, not equal to P, zero padding or truncating, or modulo-length data wrapping occurs before the FFT operation.

`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`

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 modulo-M 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.

The kth entry of the lth output channel, y(k, l), equals the kth point of the M-point discrete Fourier transform (DFT) of the lth input channel:

`$y\left(k,l\right)=\sum _{p=1}^{P}u\left(p,l\right){e}^{-j2\pi \left(p-1\right)\left(k-1\right)/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$`

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 Radix-2 algorithms. You can select `Auto` to allow the block to choose the implementation.

FFTW Implementation

The FFTW implementation provides an optimized FFT calculation including support for power-of-two and non-power-of-two transform lengths in both simulation and code generation. Generated code using the FFTW implementation will be restricted to those computers which are capable of running MATLAB®. The input data type must be floating-point.

The Radix-2 implementation supports bit-reversed processing, fixed or floating-point data, and allows the block to provide portable C-code generation using the Simulink® Coder™. The dimension M of the M-by-N 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 Radix-2 selected, the block implements one or more of the following algorithms:

• Butterfly operation

• Double-signal algorithm

• Half-length algorithm

Radix-2 Algorithms for Real and Complex Signals

Complexity of InputOutput OrderingAlgorithms Used for FFT Computation

Complex

Linear

Complex

Bit-reversed

Real

Linear

Bit-reversed operation and radix-2 DIT in conjunction with the half-length and double-signal algorithms

Real

Bit-reversed

Radix-2 DIF in conjunction with the half-length and double-signal algorithms

The efficiency of the FFT algorithm can be enhanced for real input signals by forming complex-valued sequences from the real-valued sequences prior to the computation of the DFT. When there are 2N+1 real input channels, the FFT block forms these complex-valued sequences by applying the double-signal algorithm to the first 2N input channels, and the half-length algorithm to the last odd-numbered channel.

For real input signals with fixed-point data types, it is possible to see different numerical results in the output of the last odd numbered channel, even when all input channels are identical. This numerical difference results from differences in the double-signal algorithm and the half-length algorithm.

You can eliminate this numerical difference in two ways:

• Using full precision arithmetic for fixed-point input signals

• Changing the input data type to floating point

For more information on the double-signal and half-length algorithms, see [2]. “Efficient Computation of the DFT of Two Real Sequences” on page 475 describes the double signal algorithm. “Efficient Computation of the DFT of a 2N-Point Real Sequence” on page 476 describes the half-length algorithm.

Radix-2 Optimization for the Table of Trigonometric Values

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 ,K-1$. The block stores these values in a table and retrieves them during simulation. The number of table entries for fixed-point and floating-point is summarized in the following table:

Number of Table Entries for N-Point FFT

floating-point

3 N/4

fixed-point

N

Fixed-Point Data Types

The following diagrams show the data types used in the FFT block for fixed-point 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 decimation-in-time FFT and after each butterfly stage in a decimation-in-frequency 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.

Parameters

Main Tab

FFT implementation

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 `Radix-2` for bit-reversed processing, fixed or floating-point data, or for portable C-code generation using the Simulink Coder. The dimension M of the M-by-N 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. See Radix-2 Implementation.

Set this parameter to `Auto` to let the block choose the FFT implementation. For non-power-of-two transform lengths, the block restricts generated code to MATLAB host computers.

Output in bit-reversed order

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 bit-reversed 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.

Linearly ordering the output requires extra data sorting manipulation, so in some situations it might be better to output in bit-reversed order.

Note

The FFT block calculates its output in bit-reversed order. Linearly ordering the FFT block output requires an extra bit-reversal operation. Thus, in many situations, you can increase the speed of the FFT block by selecting the Output in bit-reversed order check box.

For more information ordering of the output, see Linear and Bit-Reversed Output Order.

Divide output by FFT length

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 fixed-point data types.

Inherit FFT length from input dimensions

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. When you do not select this check box, the FFT length parameter becomes available to specify the length.

FFT length

Specify FFT length. This parameter becomes available only when you do not select the Inherit FFT length from input dimensions parameter.

When you set the FFT implementation parameter to `Radix-2`, or when you check the Output in bit-reversed order check box, this value must be a power of two.

Wrap input data when FFT length is shorter than input length

Choose to wrap or truncate the input, depending on the FFT length. If this parameter is checked, modulo-length data wrapping occurs before the FFT operation, given FFT length is shorter than the input length. If this property is unchecked, truncation of the input data to the FFT length occurs before the FFT operation. The default is checked.

Data Types Tab

Rounding mode

Select the rounding mode for fixed-point operations. The sine table values do not obey this parameter; instead, they always round to `Nearest`.

Saturate on integer overflow

When you select this parameter, the block saturates the result of its fixed-point operation. When you clear this parameter, the block wraps the result of its fixed-point operation. For details on `saturate` and `wrap`, see overflow mode for fixed-point operations.

Note

The Rounding mode and Saturate on integer overflow parameters have 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 full-precision mode.

Sine table data type

Choose how you 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)`

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`.

Click the button to display the Data Type Assistant, which helps you set the Sine table data type parameter.

Product output data type

Specify the product output data type. See Fixed-Point 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 button to display the Data Type Assistant, which helps you set the Product output data type parameter.

Accumulator data type

Specify the accumulator data type. See Fixed-Point 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 button to display the Data Type Assistant, which helps you set the Accumulator data type parameter.

Output data type

Specify the output data type. See Fixed-Point 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}+floor\left({\mathrm{log}}_{2}\left(FFTlength-1\right)\right)+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 button to display the Data Type Assistant, which helps you set the Output data type parameter.

Output Minimum

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 Signal Ranges (Simulink))

• Automatic scaling of fixed-point data types

Output Maximum

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 Signal Ranges (Simulink))

• Automatic scaling of fixed-point data types

Lock data type settings against changes by the fixed-point tools

Select this parameter to prevent the fixed-point tools from overriding the data types you specify on the block mask.

Examples

See the section on Transform Time-Domain Data into Frequency Domain in the DSP System Toolbox™ User's Guide.

Supported Data Types

PortSupported Data Types

Input

• Double-precision floating point

• Single-precision floating point

• Fixed point

• 8-, 16-, and 32-bit signed integers

• 8-, 16-, and 32-bit unsigned integers

Output

• Double-precision floating point

• Single-precision floating point

• Fixed point (signed only)

• 8-, 16-, and 32-bit signed integers

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.

[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. 1381-1384.