Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Digital Signal Processing: A User's Guide » Split-radix FFT Algorithms

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.
 

Split-radix FFT Algorithms

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

Summary: The split-radix FFT mixes radix-2 and radix-4 decompositions, yielding an algorithm with about one-third fewer multiplies than the radix-2 FFT. The split-radix FFT has lower complexity than the radix-4 or any higher-radix power-of-two FFT.

The split-radix algorithm, first clearly described and named by Duhamel and Hollman in 1984, required fewer total multiply and add operations operations than any previous power-of-two algorithm. (Yavne first derived essentially the same algorithm in 1968, but the description was so atypical that the work was largely neglected.) For a time many FFT experts thought it to be optimal in terms of total complexity, but even more efficient variations have more recently been discovered by Johnson and Frigo.

The split-radix algorithm can be derived by careful examination of the radix-2 and radix-4 flowgraphs as in Figure 1 below. While in most places the radix-4 algorithm has fewer nontrivial twiddle factors, in some places the radix-2 actually lacks twiddle factors present in the radix-4 structure or those twiddle factors simplify to multiplication by −j , which actually requires only additions. By mixing radix-2 and radix-4 computations appropriately, an algorithm of lower complexity than either can be derived.

Figure 1: See Decimation-in-Time (DIT) Radix-2 FFT and Radix-4 FFT Algorithms for more information on these algorithms.
Motivation for split-radix algorithm
radix-2radix-4
(a) (b)
radix-2 (image1.png)radix-4 (image2.png)

An alternative derivation notes that radix-2 butterflies of the form shown in Figure 2 can merge twiddle factors from two successive stages to eliminate one-third of them; hence, the split-radix algorithm requires only about two-thirds as many multiplications as a radix-2 FFT.

Figure 2: Note that these two butterflies are equivalent
(a) (b)
Figure 2(a) (image3.png)Figure 2(b) (image4.png)

The split-radix algorithm can also be derived by mixing the radix-2 and radix-4 decompositions.

DIT Split-radix derivation

X⁢k=∑ n =0N2−1x⁢2⁢n⁢e−(j⁢2⁢π×(2⁢n)⁢kN)+∑ n =0N4−1x⁢4⁢n+1⁢e−(j⁢2⁢π⁢(4⁢n+1)⁢kN)+∑ n =0N4−1x⁢4⁢n+3⁢e−(j⁢2⁢π⁢(4⁢n+3)⁢kN)= DFT N 2 ⁢x⁢2⁢n+ W N k ⁢ DFT N 4 ⁢x⁢4⁢n+1+ W N 3 k ⁢ DFT N 4 ⁢x⁢4⁢n+3 X k n N 2 1 0 x 2 n 2 2 n k N n N 4 1 0 x 4 n 1 2 4 n 1 k N n N 4 1 0 x 4 n 3 2 4 n 3 k N DFT N 2 x 2 n W N k DFT N 4 x 4 n 1 W N 3 k DFT N 4 x 4 n 3
(1)

Figure 3 illustrates the resulting split-radix butterfly.

Figure 3: The split-radix butterfly mixes radix-2 and radix-4 decompositions and is L-shaped
Decimation-in-Time Split-Radix Butterfly
Decimation-in-Time Split-Radix Butterfly (image5.png)

Further decomposition of the half- and quarter-length DFTs yields the full split-radix algorithm. The mix of different-length FFTs in different parts of the flowgraph results in a somewhat irregular algorithm; Sorensen et al. show how to adjust the computation such that the data retains the simpler radix-2 bit-reverse order. A decimation-in-frequency split-radix FFT can be derived analogously.

Figure 4: The split-radix transform has L-shaped butterflies
Figure 4 (image6.png)

The multiplicative complexity of the split-radix algorithm is only about two-thirds that of the radix-2 FFT, and is better than the radix-4 FFT or any higher power-of-two radix as well. The additions within the complex twiddle-factor multiplies are similarly reduced, but since the underlying butterfly tree remains the same in all power-of-two algorithms, the butterfly additions remain the same and the overall reduction in additions is much less.

Table 1: Operation Counts
  Complex M/As Real M/As (4/2) Real M/As (3/3)
Multiplies O⁢N3⁢log 2 N O N 3 2 N 43⁢N⁢log 2 N−389⁢N+6+29⁢−1M 4 3 N 2 N 38 9 N 6 2 9 1 M N⁢log 2 N−3⁢N+4 N 2 N 3 N 4
Additions O⁢N⁢log 2 N O N 2 N 83⁢N⁢log 2 N−169⁢N+2+29⁢−1M 8 3 N 2 N 16 9 N 2 2 9 1 M 3⁢N⁢log 2 N−3⁢N+4 3 N 2 N 3 N 4

Comments

  • The split-radix algorithm has a somewhat irregular structure. Successful progams have been written (Sorensen) for uni-processor machines, but it may be difficult to efficiently code the split-radix algorithm for vector or multi-processor machines.
  • G. Bruun's algorithm requires only N−2 N 2 more operations than the split-radix algorithm and has a regular structure, so it might be better for multi-processor or special-purpose hardware.
  • The execution time of FFT programs generally depends more on compiler- or hardware-friendly software design than on the exact computational complexity. See Efficient FFT Algorithm and Programming Tricks for further pointers and links to good code.

References

  1. P. Duhamel and H. Hollman. (1984, Jan 5). Split-radix FFT algorithms. Electronics Letters, 20, 14-16.
  2. R. Yavne. (1968). An economical method for calculating the discrete Fourier transform. Proc. AFIPS Fall Joint Computer Conf.,, 33, 115-125.
  3. S.G Johnson and M. Frigo. (2006). A modified split-radix FFT with fewer arithmetic operations. IEEE Transactions on Signal Processing, 54,
  4. H.V. Sorensen, M.T. Heideman, and C.S. Burrus. (1986). On computing the split-radix FFT. IEEE Transactions on Signal Processing, 34(1), 152-156.
  5. G. Bruun. (1978, February). Z-Transform DFT Filters and FFTs. IEEE Transactions on Signal Processing, 26, 56-63.

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

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