DSP Blockset

FFT

Compute the FFT of the input

Library

Transforms

Description

The FFT block computes the fast Fourier transform (FFT) of each channel of an M-by-N or length-M input, u, where M must be a power of two. To work with other input sizes, use the Zero Pad block to pad or truncate the length-M dimension to a power-of-two length.

The output of the FFT block is equivalent to the MATLAB fft function:

• y = fft(u,M)         % Equivalent MATLAB code
  

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

This block supports real and complex floating-point and fixed-point inputs.

Sections of This Reference Page

For information on block output characteristics and how to configure the block computation methods, see other sections of this reference page:

• Input and Output Characteristics
• Selecting the Twiddle Factor Computation Method
• Optimizing the Table of Trigonometric Values
• Ordering Output Column Entries
• Algorithms Used for FFT Computation
• Examples
• Dialog Box
• Supported Data Types
• See Also

Input and Output Characteristics

The following table describes valid inputs to the FFT block, their corresponding outputs, and the dimension along which the block computes the DFT.

Valid Block Inputs Real- or complex-valued Must be in linear order M must be a power of two	Dimension Along Which Block Computes DFT	Corresponding Block Output Characteristics Output port rate = input port rate
Frame-based M-by-N matrix	Column	Sample based Complex valued Same dimensions as input Each column (each row for sample-based row inputs) contains the M-point DFT of the corresponding input channel in linear or bit-reversed order.
Sample-based M-by-N matrix,	Column
Sample-based 1-by-M row vector	Row
Unoriented length-M 1-D vector	Vector	Unoriented, length-M, complex-valued 1-D vector containing M-point DFT of input in linear or bit-reversed order

The following diagram shows the effects of the input size, dimension, and frame status on the output of the FFT block (see also fft_ins_outs.mdl).

Selecting the Twiddle Factor Computation Method

The Twiddle factor computation parameter determines how the block computes the necessary sine and cosine terms to calculate the term , shown in the first equation of this block reference page. This parameter has two settings, each with its advantages and disadvantages, as described in the following table. Note that only Table lookup mode is supported for fixed-point signals.

Twiddle Factor Computation Parameter Setting	Sine and Cosine Computation Method	Effect on Block Performance
Table lookup	The block computes and stores the trigonometric values before the simulation starts, and retrieves them during the simulation. When you generate code from the block, the processor running the generated code stores the trigonometric values computed by the block, and retrieves the values during code execution.	The block usually runs much more quickly, but requires extra memory for storing the precomputed trigonometric values. You can optimize the table for memory consumption or speed, as described in Optimizing the Table of Trigonometric Values below.
Trigonometric fcn	The block computes sine and cosine values during the simulation. When you generate code from the block, the processor running the generated code computes the sine and cosine values while the code runs.	The block usually runs more slowly, but does not need extra data memory. For code generation, the block requires a support library to emulate the trigonometric functions, increasing the size of the generated code.

Optimizing the Table of Trigonometric Values

When you set the Twiddle factor computation parameter to Table lookup, you need to also set the Optimize table for parameter. This parameter optimizes the table of trigonometric values for speed or memory by varying the number of table entries as summarized in the following table.

Optimize Table for Parameter Setting	Number of Table Entries for N-Point FFT	Memory Required for Single-Precision 512-Point FFT
Speed	3N/4 -- floating point N -- fixed point	1536 bytes
Memory	N/4 + 1 -- floating point Not supported for fixed point	516 bytes

Ordering Output Column Entries

You can set the Output in bit-reversed order parameter to specify the ordering of the column elements of the output as either linear or bit-reversed.

Two numbers are bit-reversed values of each other when the binary representation of one is the mirror image of the binary representation of the other. For example, in a three-bit system, one and four are bit-reversed values of each other, since the three-bit binary representation of one, 001, is the mirror image of the three-bit binary representation of four, 100.

In the diagram below, the sequence 0, 1, 2, 3, 4, 5, 6, 7 is in linear order. To put the sequence in bit-reversed order, replace each element in the linearly ordered sequence with its bit-reversed counterpart. You can do this by translating the sequence into its binary representation with the minimum number of bits, then finding the mirror image of each binary entry, and finally translating the sequence back to its decimal representation. The resulting sequence is the original linearly ordered sequence in bit-reversed order.

Set the Output in bit-reversed order parameter as follows to indicate the ordering of the output's column elements.

Parameter Setting	Ordering of Output Channel Elements	Output Column Entries
	Linear order	kth column element is the DFT of the corresponding input column at the kth frequency.
	Bit-reversed order	kth column element is the DFT of the corresponding input column at the rth frequency, where r is the bit reversed value of k.

Note    Linearly ordering the output requires extra data sorting manipulation, so in some situations it may be better to output in bit-reversed order as illustrated in the example, The Use of Bit-Reversed Outputs.

The next diagram illustrates the difference between linear and bit-reversed outputs. Note that output values in linear and bit-reversed order are the same; only the order in which they appear in the columns differs.

Algorithms Used for FFT Computation

Depending on whether the block input is floating-point or fixed-point, real- or complex-valued, and whether you want the output in linear or bit-reversed order, the block uses one or more of the following algorithms as summarized in the following tables:

• Radix-2 decimation-in-time (DIT) algorithm
• Radix-2 decimation-in-frequency (DIF) algorithm
• Half-length algorithm
• Double-signal algorithm

For floating-point signals:

Complexity of Input	Output Ordering	Algorithms Used for FFT Computation
Complex	Linear or bit-reversed	Radix-2 DIT
Real	Linear	Radix-2 DIT in conjunction with the half-length and double-signal algorithms when possible
Real	Bit-reversed	Radix-2 DIF in conjunction with the half-length and double-signal algorithms when possible

For fixed-point signals:

Complexity of Input	Output Ordering	Algorithms Used for FFT Computation
Real or complex	Linear	Radix-2 DIT
Real or complex	Bit-reversed	Radix-2 DIF

Fixed-Point Data Types

The diagrams below show the data types used within 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 block mask as discussed in Dialog Box.

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. A twiddle factor is multiplied in 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 is in the accumulator data type since both of the inputs to the multiplier are complex. For details on the complex multiplication performed, refer to Multiplication Data Types.

Examples

The Use of Bit-Reversed Outputs

The FFT block runs more quickly when it outputs in bit-reversed order. You can often use an output in bit-reversed order when your model also uses the IFFT block, which allows you to indicate whether its input is in bit-reversed or linear order.

For instance, set the FFT block to output in bit-reversed order when you want to filter or convolve signals by taking the FFT of time domain data, multiplying frequency-domain data, and inputting the product to an IFFT block that is configured to accept input in bit-reversed order.

The following model shows the implementation of the Overlap-Save FFT Filter block. The implementation uses the FFT block in conjunction with an IFFT block, so the FFT block is set to output in bit-reversed order, and the IFFT block is set to accept inputs in bit-reversed order. Note that the implementation uses the bitrevorder function to put the vector H into bit-reversed order before multiplying it with the bit-reversed FFT outputs:

1. To open the demo model, type the following command at the MATLAB command line.

•     olapfilt
  

2. To see the implementation of the Overlap-Save FFT Filter block, right-click on the Overlap-Save FFT Filter block, and select Look under mask.
3. Look under the mask of the Overlap-Add FFT Filter block as well, which also uses an FFT block that outputs in bit-reversed order.

   

Dialog Box

Twiddle factor computation

Specify the computation method of the term , shown in the first equation of this block reference page. In Table lookup mode, the block computes and stores the sine and cosine values before the simulation starts. In Trigonometric fcn mode, the block computes the sine and cosine values during the simulation. See Selecting the Twiddle Factor Computation Method.

This parameter must be set to Table lookup for fixed-point signals.

Optimize table for

Select the optimization of the table of sine and cosine values for Speed or Memory. This parameter is only available when the Twiddle factor computation parameter is set to Table lookup. See Selecting the Twiddle Factor Computation Method.

This parameter must be set to Speed for fixed-point signals.

Output in bit-reversed order

Designate the order of the output channel elements relative to the ordering of the input elements. When selected, the output channel elements are in bit-reversed order relative to the input ordering. Otherwise, the output column elements are linearly ordered relative to the input ordering.

Linearly ordering the output requires extra data sorting manipulation, so in some situations it may be better to output in bit-reversed order as illustrated in the example, The Use of Bit-Reversed Outputs.

Show additional parameters

If selected, additional parameters specific to implementation of the block become visible as shown.

Skip divide-by-2 on butterfly outputs for fixed-point signals

When this parameter is selected, no scaling occurs. When this parameter is not selected, the output of each butterfly of the FFT is divided by two for fixed-point signals.

Allow overrides from DSP Fixed-Point Attributes blocks

If you select this parameter, fixed-point data types for this block may be set by DSP Fixed-Point Attributes blocks in your model. If this parameter is unselected, the data types are always set by the parameters in the block mask.

Fixed-point sine table attributes

Choose how you will specify the word length and fraction length of the values of the sine table. If you select Same as input, the word and fraction lengths of the sine table values are the same as those of the input of the block. If you select Same as output, they are the same as those of the output of the block. If you select User-defined, the Fixed-point sine table word length and Fixed-point sine table fraction length parameters become visible.

The sine table values do not obey the Round integer calculations toward and Saturate on integer overflow parameters; they are always saturated and rounded to Nearest.

Fixed-point sine table word length

Specify the word length, in bits, of the sine table values. This parameter is only visible if User-defined is specified for the Fixed-point sine table attributes parameter.

Fixed-point sine table fraction length

Specify the fraction length, in bits, of the sine table values. This parameter is only visible if User-defined is specified for the Fixed-point sine table attributes parameter.

Fixed-point output attributes

Choose how you will specify the output word length and fraction length. If you select Same as input, these characteristics will match those of the input to the block. If you select User-defined, the Output word length and Output fraction length parameters become visible.

Output word length

Specify the word length, in bits, of the output. This parameter is only visible if User-defined is specified for the Fixed-point output attributes parameter.

Output fraction length

Specify the fraction length, in bits, of the output. This parameter is only visible if User-defined is specified for the Fixed-point output attributes parameter.

Fixed-point accumulator attributes

Use this parameter to specify how you would like to designate the accumulator word and fraction lengths. Refer to Fixed-Point Data Types and Multiplication Data Types for illustrations depicting the use of the accumulator data type in this block.

If you select Same as input, the accumulator word and fraction lengths are the same as those of the input to the block. If you select Same as output, they are the same as those of the output of the block. If you select User-defined, the Accumulator word length and Accumulator fraction length parameters become visible.

Accumulator word length

Specify the word length, in bits, of the accumulator. This parameter is only visible when User-defined is specified for the Fixed-point accumulator attributes parameter.

Accumulator fraction length

Specify the fraction length, in bits, of the accumulator. This parameter is only visible when User-defined is specified for the Fixed-point accumulator attributes parameter.

Fixed-point product output attributes

Use this parameter to specify how you would like to designate the product output word and fraction lengths. Refer to Fixed-Point Data Types and Multiplication Data Types for illustrations depicting the use of the product output data type in this block.

If you select Same as input, Same as output, or Same as accumulator, the product output word and fraction lengths are the same as those of the input, output, or accumulator of the block, respectively. If you select User-defined, the Product output word length and Product output fraction length parameters become visible.

Product output word length

Specify the word length, in bits, of the product output. This parameter is only visible when User-defined is specified for the Fixed-point product output attributes parameter.

Product output fraction length

Specify the fraction length, in bits, of the product output. This parameter is only visible when User-defined is specified for the Fixed-point product output attributes parameter.

Round integer calculations toward

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

Saturate on integer overflow

If selected, overflows saturate. The sine table values do not obey this parameter; they are always saturated.

Supported Data Types

• Double-precision floating point
• Single-precision floating point
• Fixed point
• 8-, 16-, and 32-bit signed integers

To learn how to convert your data types to the above data types in MATLAB and Simulink, see Supported Data Types and How to Convert to Them.

See Also

Complex Cepstrum	DSP Blockset
DCT	DSP Blockset
IFFT	DSP Blockset
Pad	DSP Blockset
Zero Pad	DSP Blockset
bitrevorder	Signal Processing Toolbox
fft	Signal Processing Toolbox
ifft	Signal Processing Toolbox

Fast Block LMS Filter

Filter Realization Wizard