Signal Processing Blockset™

FFT - Compute fast Fourier transform (FFT) of input

Library

Transforms

dspxfrm3

Description

The FFT block computes the fast Fourier transform (FFT) of each channel of a P-by-N or length-P input, u. When the Inherit FFT length from input dimensions check box is selected, the input length P must be an integer power of two, and the FFT length M is equal to P. When the check box is not selected, P can be any length, and the value of the FFT length parameter must be a positive integer power of two. For user-specified FFT lengths, when M is not equal to P, zero padding or modulo-M data wrapping happens before the FFT operation, as per Orfanidis [1]:

y = fft(u,M)		% P ≤ M

y(:,l) = fft(datawrap(u(:,l),M))		% P > M; l = 1,...,N

To get zero padding or truncation rather than zero padding or wrapping, use a Pad block before the FFT block in your model to obtain a power-of-two input length.

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.

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 inputs to the FFT block. They can be real- or complex-valued, and they must be in linear order.

• The dimension along which the block computes the DFT.

• The corresponding block output characteristics. The output port rate must equal the input port rate.

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. Only Table lookup mode is supported for fixed-point signals.

Optimizing the Table of Trigonometric Values

When you set the Twiddle factor computation parameter to Table lookup, you also need to 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.

Ordering Output Column Entries

You can set the Output in bit-reversed order parameter to specify the ordering of the column elements of the block output. If you select the Output in bit-reversed order check box, the output is in bit-reversed order. If you clear the Output in bit-reversed order check box, the output is in linear order.

Note   Linearly ordering the FFT block output requires a butterfly operation. Therefore, it might be better to output in bit-reversed order in some situations.

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

Algorithms Used for FFT Computation

Depending on whether the block's input is 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 table:

• Butterfly operation

• Double-signal algorithm

• Half-length algorithm

• Radix-2 decimation-in-time (DIT) algorithm

• Radix-2 decimation-in-frequency (DIF) algorithm

For more information on the double-signal and half-length algorithms, see Proakis [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.

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 dialog 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, see Multiplication Data Types.

Dialog Box

The Main pane of the FFT block dialog appears as follows.

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 might be better to output in bit-reversed order.

Inherit FFT length from input dimensions

Select to inherit the FFT length from the input dimensions. When this parameter is selected, the input length P must be a power of two. When this parameter is not selected, the FFT length parameter is available.

FFT length

Specify a power-of-two FFT length. This parameter is only available when the Inherit FFT length from input dimensions parameter is not selected.

The Fixed-point pane of the FFT block dialog appears as follows.

Rounding mode

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

Overflow mode

Select the overflow mode for fixed-point operations. The sine table values do not obey this parameter; they are always saturated.

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

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

Sine table

Choose how you specify the word length of the values of the sine table. The fraction length of the sine table values is always equal to the word length minus one:

• When you select Same word length as input, the word length of the sine table values match that of the input to the block.

• When you select Specify word length, you can enter the word length of the sine table values, in bits.

The sine table values do not obey the Rounding mode and Overflow mode parameters; they are always saturated and rounded to Nearest.

Product output

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

• When you select Inherit via internal rule, the product output word length and fraction length are calculated automatically. For information about how the product output word and fraction lengths are calculated when an internal rule is used, see Inherit via Internal Rule.

• When you select Same as input, these characteristics match those of the input to the block.

• When you select Binary point scaling, you can enter the word length and the fraction length of the product output, in bits.

• When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the product output. This block requires power-of-two slope and a bias of zero.

Accumulator

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

• When you select Inherit via internal rule, the accumulator word length and fraction length are calculated automatically. For information about how the accumulator word and fraction lengths are calculated when an internal rule is used, see Inherit via Internal Rule.

• When you select Same as product output, these characteristics match those of the product output.

• When you select Same as input, these characteristics match those of the input to the block.

• When you select Binary point scaling, you can enter the word length and the fraction length of the accumulator, in bits.

• When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the accumulator. This block requires power-of-two slope and a bias of zero.

Output

Choose how you specify the output word length and fraction length:

• When you select Inherit via internal rule, the output word length and fraction length are calculated automatically. The internal rule first calculates an ideal output word length and fraction length using the following equations:

  

  

  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.

• When you select Same as input, these characteristics match those of the input to the block.

• When you select Binary point scaling, you can enter the word length and the fraction length of the output, in bits.

• When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the output. This block requires power-of-two slope and a bias of zero.

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.

Supported Data Types

See Also

Fast Block LMS Filter

Filter Realization Wizard