DSP Builder for Intel® FPGAs (Advanced Blockset): Handbook

ID 683337
Date 5/27/2022

A newer version of this document is available. Customers should click here to go to the newest version.

Document Table of Contents

15.3.1. About Pruning and Twiddle for FFT Blocks

DSP Builder allows you to specify: the type of the data values before each twiddle multiplication; the type of the twiddle constants; the type of the data values after each twiddle multiplication.

For example:


Figure 98. Pruning and Twiddle for FFT Blocks

An FFT with 2N points has N radix-2 stages and (conceptually) N–1 twiddle multipliers. In practice, DSP Builder optimizes away many of the twiddle multipliers. However, they still need entries in the twiddle specification.

The twiddle and pruning specification for this FFT consists of a (N–1)x3 array (N–1 rows with 3 entries in each row) of strings which specify these types. DSP Builder uses strings because Simulink does not pass raw types into the Simulink GUI.

DSP Builder provides three utility functions to generate twiddle and pruning specifications, each of which implements a different pruning strategy:

  • dspba.fft.full_wordgrowth(complexFFT,radix2,N,input_type,twiddle_type)
  • dspba.fft.mild_pruning(complexFFT,radix2,N,input_type,twiddle_type)
  • dspba.fft.prune_to_width(maxWidth,complexFFT,radix2,N,input_type,twiddle_type)

In addition, DSP Builder provides a fourth function for floating-point FFTs (where no pruning is required)

  • dspba.fft.all_float(N, float_type)

This function generates a pruning specification where the input, twiddle and output types are all float_type.

The legacy FFT interfaces use dspba.fft.full_wordgrowth() pruning strategy. It grows the datapath by one bit for each radix–2 FFT stage.

The dspba.fft.mild_pruning() grows the datapath by one bit for each two radix-2 FFT stages.

The dspba.fft.prune_to_width(maxWidth) grows the datapath by one bit for each radix–2 FFT stage up to the specified maximum width. At that point, it applies drastic pruning to ensure that the data input to the twiddle multiplier is never more than maxWidth bits wide.

Intel provides these built-in strategies only for your convenience. If you need a different pruning strategy, you can define and use your own pruning function (or just construct the pruning or twiddle array manually).

Each of these utility functions generate an array in the appropriate format (N–1 rows, each containing three entries).

In each case:

  • complexFFT is a Boolean number (usually true) that indicates whether the FFT's input is complex.
  • radix2 is a Boolean number (usually false) that indicates whether the FFT can have two consecutive twiddle stages.
  • N is an integer indicating the number of radix-2 stages in the FFT. For example, 10 for a 1,024-point FFT.
  • input_type is the type of the input signal.
  • twiddle_type is the type of the twiddle constants.