Connexions

You are here: Home » Content » Radix-4 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

Summary: The decimation-in-time (DIT) radix-4 FFT recursively partitions a DFT into four quarter-length DFTs of groups of every fourth time sample. The outputs of these shorter FFTs are reused to compute many outputs, thus greatly reducing the total computational cost. The radix-4 decimation-in-frequency FFT groups every fourth output sample into shorter-length DFTs to save computations. The radix-4 FFTs require only 75% as many complex multiplies as the radix-2 FFTs.

The radix-4 decimation-in-time and decimation-in-frequency fast Fourier transforms (FFTs) gain their speed by reusing the results of smaller, intermediate computations to compute multiple DFT frequency outputs. The radix-4 decimation-in-time algorithm rearranges the discrete Fourier transform (DFT) equation into four parts: sums over all groups of every fourth discrete-time index n=048N4 n 0 4 8 N 4 , n=159N3 n 1 5 9 N 3 , n=2610N2 n 2 6 10 N 2 and n=3711N1 n 3 7 11 N 1 as in Equation 1. (This works out only when the FFT length is a multiple of four.) Just as in the radix-2 decimation-in-time FFT, further mathematical manipulation shows that the length-NN DFT can be computed as the sum of the outputs of four length- N4 N 4 DFTs, of the even-indexed and odd-indexed discrete-time samples, respectively, where three of them are multiplied by so-called twiddle factors W N k =e(i2πkN) W N k 2 k N , W N 2k W N 2 k , and W N 3k W N 3 k .

Xk= n =0N1xne(i2πnkN)= n =0N41x4ne(i2π×(4n)kN)+ n =0N41x4n+1e(i2π(4n+1)kN)+ n =0N41x4n+2e(i2π(4n+2)kN)+ n =0N41x4n+3e(i2π(4n+3)kN)= DFT N 4 x4n+ W N k DFT N 4 x4n+1+ W N 2 k DFT N 4 x4n+2+ W N 3 k DFT N 4 x4n+3 X k n N 1 0 x n 2 n k N n N 4 1 0 x 4 n 2 4 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 2 2 4 n 2 k N n N 4 1 0 x 4 n 3 2 4 n 3 k N DFT N 4 x 4 n W N k DFT N 4 x 4 n 1 W N 2 k DFT N 4 x 4 n 2 W N 3 k DFT N 4 x 4 n 3
(1)

This is called a decimation in time because the time samples are rearranged in alternating groups, and a radix-4 algorithm because there are four groups. Figure 1 graphically illustrates this form of the DFT computation.

Due to the periodicity with N4 N 4 of the short-length DFTs, their outputs for frequency-sample kk are reused to compute Xk X k , Xk+N4 X k N 4 , Xk+N2 X k N 2 , and Xk+3N4 X k 3 N 4 . It is this reuse that gives the radix-4 FFT its efficiency. The computations involved with each group of four frequency samples constitute the radix-4 butterfly, which is shown in Figure 2. Through further rearrangement, it can be shown that this computation can be simplified to three twiddle-factor multiplies and a length-4 DFT! The theory of multi-dimensional index maps shows that this must be the case, and that FFTs of any factorable length may consist of successive stages of shorter-length FFTs with twiddle-factor multiplications in between. The length-4 DFT requires no multiplies and only eight complex additions (this efficient computation can be derived using a radix-2 FFT).

If the FFT length N=4M N 4 M , the shorter-length DFTs can be further decomposed recursively in the same manner to produce the full radix-4 decimation-in-time FFT. As in the radix-2 decimation-in-time FFT, each stage of decomposition creates additional savings in computation. To determine the total computational cost of the radix-4 FFT, note that there are M=log 4 N=log 2 N2 M 4 N 2 N 2 stages, each with N4 N 4 butterflies per stage. Each radix-4 butterfly requires 33 complex multiplies and 88 complex additions. The total cost is then

• 3N4log 2 N2=38Nlog 2 N 3 N 4 2 N 2 3 8 N 2 N complex multiplies (75% of a radix-2 FFT)
• 8N4log 2 N2=Nlog 2 N 8 N 4 2 N 2 N 2 N complex adds (same as a radix-2 FFT)

The radix-4 FFT requires only 75% as many complex multiplies as the radix-2 FFTs, although it uses the same number of complex additions. These additional savings make it a widely-used FFT algorithm.

The decimation-in-time operation regroups the input samples at each successive stage of decomposition, resulting in a "digit-reversed" input order. That is, if the time-sample index n n is written as a base-4 number, the order is that base-4 number reversed. The digit-reversal process is illustrated for a length- N=64 N 64 example below.

Example 1: N = 64 = 4^3

Table 1
Original Number Original Digit Order Reversed Digit Order Digit-Reversed Number
0 000 000 0
1 001 100 16
2 002 200 32
3 003 300 48
4 010 010 4
5 011 110 20

It is important to note that, if the input signal data are placed in digit-reversed order before beginning the FFT computations, the outputs of each butterfly throughout the computation can be placed in the same memory locations from which the inputs were fetched, resulting in an in-place algorithm that requires no extra memory to perform the FFT. Most FFT implementations are in-place, and overwrite the input data with the intermediate values and finally the output. A slight rearrangement within the radix-4 FFT introduced by Burrus allows the inputs to be arranged in bit-reversed rather than digit-reversed order.

A radix-4 decimation-in-frequency FFT can be derived similarly to the radix-2 DIF FFT, by separately computing all four groups of every fourth output frequency sample. The DIF radix-4 FFT is a flow-graph reversal of the DIT radix-4 FFT, with the same operation counts and twiddle factors in the reversed order. The output ends up in digit-reversed order for an in-place DIF algorithm.

Exercise 1

How do we derive a radix-4 algorithm when N=4M2 N 4 M 2 ?

Solution

Perform a radix-2 decomposition for one stage, then radix-4 decompositions of all subsequent shorter-length DFTs.

References

1. C.S. Burrus. (1988, July). Unscrambling for fast DFT algorithms. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-36(7), 1086-1089.

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