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=048…N−4 n 0 4 8 … N 4 , n=159…N−3 n 1 5 9 … N 3 , n=2610…N−2 n 2 6 10 … N 2 and n=3711…N−1 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−(j⁢2⁢π⁢kN) W N k 2 k N , W N 2⁢k W N 2 k , and W N 3⁢k W N 3 k .

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.

Figure 1: Decimation in time of a length-NN DFT into four length-N4N4 DFTs followed by a combining stage.

Radix-4 DIT structure

Due to the periodicity with N4 N 4 of the short-length DFTs, their outputs for frequency-sample kk are reused to compute X⁢k X k , X⁢k+N4 X k N 4 , X⁢k+N2 X k N 2 , and X⁢k+3⁢N4 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).

Figure 2: The radix-4 DIT butterfly can be simplified to a length-4 DFT preceded by three twiddle-factor multiplies.

(a) (b)

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

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.

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.

Content actions

Add:

Collection to:

My Favorites Login Required (?)

'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 Login Required (?)

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

Module to:

My Favorites Login Required (?)

'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 Login Required (?)

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

Footer

This work is licensed by Douglas L. Jones under a Creative Commons Attribution License (CC-BY 1.0), and is an Open Educational Resource.

Last edited by Douglas L. Jones on Sep 18, 2006 9:51 pm -0500.