# Connexions

You are here: Home » Content » Split-radix FFT Algorithms

### 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?

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

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

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

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 i , which actually requires only additions. By mixing radix-2 and radix-4 computations appropriately, an algorithm of lower complexity than either can be derived.

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.

Xk= n =0N21x2ne(i2π×(2n)kN)+ n =0N41x4n+1e(i2π(4n+1)kN)+ n =0N41x4n+3e(i2π(4n+3)kN)= DFT N 2 x2n+ W N k DFT N 4 x4n+1+ W N 3 k DFT N 4 x4n+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.

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.

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 ON3log 2 N O N 3 2 N 43Nlog 2 N389N+6+291M 4 3 N 2 N 38 9 N 6 2 9 1 M Nlog 2 N3N+4 N 2 N 3 N 4
Additions ONlog 2 N O N 2 N 83Nlog 2 N169N+2+291M 8 3 N 2 N 16 9 N 2 2 9 1 M 3Nlog 2 N3N+4 3 N 2 N 3 N 4

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

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

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

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?

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