Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » DSPA » Decimation-in-time (DIT) Radix-2 FFT

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.
 

Decimation-in-time (DIT) Radix-2 FFT

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

Summary: The radix-2 algorithms are the simplest FFT algorithms. The decimation-in-time (DIT) radix-2 FFT recursively partitions a DFT into two half-length DFTs of the even-indexed and odd-indexed time samples. The outputs of these shorter FFTs are reused to compute many outputs, thus greatly reducing the total computational cost.

The radix-2 decimation-in-time and decimation-in-frequency fast Fourier transforms (FFTs) are the simplest FFT algorithms. Like all FFTs, they gain their speed by reusing the results of smaller, intermediate computations to compute multiple DFT frequency outputs.

Decimation in time

The radix-2 decimation-in-time algorithm rearranges the discrete Fourier transform (DFT) equation into two parts: a sum over the even-numbered discrete-time indices n=024N2 n 0 2 4 N 2 and a sum over the odd-numbered indices n=135N1 n 1 3 5 N 1 as in Equation 1:

Xk= n =0N1xne(j2πnkN)= n =0N21x2ne(j2π×(2n)kN)+ n =0N21x2n+1e(j2π(2n+1)kN)= n =0N21x2ne(j2πnkN2)+e(j2πkN) n =0N21x2n+1e(j2πnkN2)= DFT N 2 x0x2xN2+ W N k DFT N 2 x1x3xN1 X k n N 1 0 x n 2 n k N n N 2 1 0 x 2 n 2 2 n k N n N 2 1 0 x 2 n 1 2 2 n 1 k N n N 2 1 0 x 2 n 2 n k N 2 2 k N n N 2 1 0 x 2 n 1 2 n k N 2 DFT N 2 x 0 x 2 x N 2 W N k DFT N 2 x 1 x 3 x N 1
(1)

The mathematical simplifications in Equation 1 reveal that all DFT frequency outputs Xk X k can be computed as the sum of the outputs of two length- N2 N 2 DFTs, of the even-indexed and odd-indexed discrete-time samples, respectively, where the odd-indexed short DFT is multiplied by a so-called twiddle factor term W N k =e(j2πkN) W N k 2 k N . This is called a decimation in time because the time samples are rearranged in alternating groups, and a radix-2 algorithm because there are two groups. Figure 1 graphically illustrates this form of the DFT computation, where for convenience the frequency outputs of the length- N2 N 2 DFT of the even-indexed time samples are denoted Gk G k and those of the odd-indexed samples as Hk H k . Because of the periodicity with N2 N 2 frequency samples of these length- N2 N 2 DFTs, Gk G k and Hk H k can be used to compute two of the length-NN DFT frequencies, namely Xk X k and Xk+N2 X k N 2 , but with a different twiddle factor. This reuse of these short-length DFT outputs gives the FFT its computational savings.

Figure 1: Decimation in time of a length-NN DFT into two length-N2N2 DFTs followed by a combining stage.
Figure 1 (image1.png)

Whereas direct computation of all NN DFT frequencies according to the DFT equation would require N2 N 2 complex multiplies and N2N N 2 N complex additions (for complex-valued data), by reusing the results of the two short-length DFTs as illustrated in Figure 1, the computational cost is now

New Operation Counts

  • 2N22+N=N22+N 2 N 2 2 N N 2 2 N complex multiplies
  • 2N2(N21)+N=N22 2 N 2 N 2 1 N N 2 2 complex additions

This simple reorganization and reuse has reduced the total computation by almost a factor of two over direct DFT computation!

Additional Simplification

A basic butterfly operation is shown in Figure 2, which requires only N2 N 2 twiddle-factor multiplies per stage. It is worthwhile to note that, after merging the twiddle factors to a single term on the lower branch, the remaining butterfly is actually a length-2 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.

Figure 2: Radix-2 DIT butterfly simplification: both operations produce the same outputs
(a) (b)
Figure 2(a) (image2.png) Figure 2(b) (image3.png)

Radix-2 decimation-in-time FFT

The same radix-2 decimation in time can be applied recursively to the two length N2 N 2 DFTs to save computation. When successively applied until the shorter and shorter DFTs reach length-2, the result is the radix-2 DIT FFT algorithm.

Figure 3: Radix-2 Decimation-in-Time FFT algorithm for a length-8 signal
Figure 3 (image4.png)

The full radix-2 decimation-in-time decomposition illustrated in Figure 3 using the simplified butterflies involves M=log 2 N M 2 N stages, each with N2 N 2 butterflies per stage. Each butterfly requires 11 complex multiply and 22 adds per butterfly. The total cost of the algorithm is thus

Computational cost of radix-2 DIT FFT

  • N2log 2 N N 2 2 N complex multiplies
  • Nlog 2 N N 2 N complex adds

This is a remarkable savings over direct computation of the DFT. For example, a length-1024 DFT would require 10485761048576 complex multiplications and 10475521047552 complex additions with direct computation, but only 51205120 complex multiplications and 1024010240 complex additions using the radix-2 FFT, a savings by a factor of 100 or more. The relative savings increase with longer FFT lengths, and are less for shorter lengths.

Modest additional reductions in computation can be achieved by noting that certain twiddle factors, namely Using special butterflies for W N 0 W N 0 , W N N 2 W N N 2 , W N N 4 W N N 4 , W N N 8 W N N 8 , W N 3 N 8 W N 3 N 8 , require no multiplications, or fewer real multiplies than other ones. By implementing special butterflies for these twiddle factors as discussed in FFT algorithm and programming tricks, the computational cost of the radix-2 decimation-in-time FFT can be reduced to

  • 2Nlog 2 N7N+12 2 N 2 N 7 N 12 real multiplies
  • 3Nlog 2 N3N+4 3 N 2 N 3 N 4 real additions

Note:

In a decimation-in-time radix-2 FFT as illustrated in Figure 3, the input is in bit-reversed order (hence "decimation-in-time"). That is, if the time-sample index n n is written as a binary number, the order is that binary number reversed. The bit-reversal process is illustrated for a length- N=8 N 8 example below.

Example 1: N=8

Table 1
In-order index In-order index in binary Bit-reversed binary Bit-reversed index
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7

It is important to note that, if the input signal data are placed in bit-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.

Example FFT Code

The following function, written in the C programming language, implements a radix-2 decimation-in-time FFT. It is designed for computing the DFT of complex-valued inputs to produce complex-valued outputs, with the real and imaginary parts of each number stored in separate double-precision floating-point arrays. It is an in-place algorithm, so the intermediate and final output values are stored in the same array as the input data, which is overwritten. After initializations, the program first bit-reverses the discrete-time samples, as is typical with a decimation-in-time algorithm (but see alternate FFT structures for DIT algorithms with other input orders), then computes the FFT in stages according to the above description.

Ihis FFT program uses a standard three-loop structure for the main FFT computation. The outer loop steps through the stages (each column in Figure 3); the middle loop steps through "flights" (butterflies with the same twiddle factor from each short-length DFT at each stage), and the inner loop steps through the individual butterflies. This ordering minimizes the number of fetches or computations of the twiddle-factor values. Since the bit-reverse of a bit-reversed index is the original index, bit-reversal can be performed fairly simply by swapping pairs of data.

Note:

While of ONlogN O N N complexity and thus much faster than a direct DFT, this simple program is optimized for clarity, not for speed. A speed-optimized program making use of additional efficient FFT algorithm and programming tricks will compute a DFT several times faster on most machines.

/**********************************************************/
/* fft.c                                                  */
/* (c) Douglas L. Jones                                   */
/* University of Illinois at Urbana-Champaign             */
/* January 19, 1992                                       */
/*                                                        */
/*   fft: in-place radix-2 DIT DFT of a complex input     */
/*                                                        */
/*   input:                                               */
/* n: length of FFT: must be a power of two               */
/* m: n = 2**m                                            */
/*   input/output                                         */
/* x: double array of length n with real part of data     */
/* y: double array of length n with imag part of data     */
/*                                                        */
/*   Permission to copy and use this program is granted   */
/*   under a Creative Commons "Attribution" license       */
/*   http://creativecommons.org/licenses/by/1.0/          */
/**********************************************************/
fft(n,m,x,y)
int n,m;
double x[],y[];
{
int i,j,k,n1,n2;
double c,s,e,a,t1,t2;        
         
  
j = 0; /* bit-reverse */
n2 = n/2;
for (i=1; i < n - 1; i++)
{
  n1 = n2;
  while ( j >= n1 )
   {
    j = j - n1;
    n1 = n1/2;
   }
  j = j + n1;
               
  if (i < j)
   {
    t1 = x[i];
    x[i] = x[j];
    x[j] = t1;
    t1 = y[i];
    y[i] = y[j];
    y[j] = t1;
   }
}
                                       
                                           
n1 = 0; /* FFT */
n2 = 1;
                                             
for (i=0; i < m; i++)
{
  n1 = n2;
  n2 = n2 + n2;
  e = -6.283185307179586/n2;
  a = 0.0;
                                             
  for (j=0; j < n1; j++)
   {
    c = cos(a);
    s = sin(a);
    a = a + e;
                                            
    for (k=j; k < n; k=k+n2)
     {
      t1 = c*x[k+n1] - s*y[k+n1];
      t2 = s*x[k+n1] + c*y[k+n1];
      x[k+n1] = x[k] - t1;
      y[k+n1] = y[k] - t2;
      x[k] = x[k] + t1;
      y[k] = y[k] + t2;
     }
   }
}
                                      
return;
}                          

	

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