Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Digital Signal Processing: A User's Guide » Alternate FFT Structures

Navigation

Table of Contents

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

In these lenses

  • Lens for Engineering

    This module is included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.
 

Alternate FFT Structures

Module by: Douglas L. Jones. E-mail the author

Summary: FFT structures with different memory layout and interconnection patterns are occasionally useful for certain applications. These alternate structures include decimation-in-frequency FFTs with in-order outputs, decimation-in-time FFTs with in-order inputs, structures with both in-order inputs and outputs, and constant-geometry structures with the same connection pattern in every stage.

Bit-reversing the input in decimation-in-time (DIT) FFTs or the output in decimation-in-frequency (DIF) FFTs can sometimes be inconvenient or inefficient. For such situations, alternate FFT structures have been developed. Such structures involve the same mathematical computations as the standard algorithms, but alter the memory locations in which intermediate values are stored or the order of computation of the FFT butterflies.

The structure in Figure 1 computes a decimation-in-frequency FFT, but remaps the memory usage so that the input is bit-reversed, and the output is in-order as in the conventional decimation-in-time FFT. This alternate structure is still considered a DIF FFT because the twiddle factors are applied as in the DIF FFT. This structure is useful if for some reason the DIF butterfly is preferred but it is easier to bit-reverse the input.

Figure 1: Decimation-in-frequency radix-2 FFT with bit-reversed input. This is an in-place algorithm in which the same memory can be reused throughout the computation.
Figure 1 (image1.png)

There is a similar structure for the decimation-in-time FFT with in-order inputs and bit-reversed frequencies. This structure can be useful for fast convolution on machines that favor decimation-in-time algorithms because the filter can be stored in bit-reverse order, and then the inverse FFT returns an in-order result without ever bit-reversing any data. As discussed in Efficient FFT Programming Tricks, this may save several percent of the execution time.

The structure in Figure 2 implements a decimation-in-frequency FFT that has both input and output in order. It thus avoids the need for bit-reversing altogether. Unfortunately, it destroys the in-place structure somewhat, making an FFT program more complicated and requiring more memory; on most machines the resulting cost exceeds the benefits. This structure can be computed in place if two butterflies are computed simultaneously.

Figure 2: Decimation-in-frequency radix-2 FFT with in-order input and output. It can be computed in-place if two butterflies are computed simultaneously.
Figure 2 (image2.png)

The structure in Figure 3 has a constant geometry; the connections between memory locations are identical in each FFT stage. Since it is not in-place and requires bit-reversal, it is inconvenient for software implementation, but can be attractive for a highly parallel hardware implementation because the connections between stages can be hardwired. An analogous structure exists that has bit-reversed inputs and in-order outputs.

Figure 3: This constant-geometry structure has the same interconnect pattern from stage to stage. This structure is sometimes useful for special hardware.
Figure 3 (image3.png)

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks