** Next:** 3 Implementation
**Up:** Implementation and Comparison of
** Previous:** 1 Introduction

The standard definition of the discrete Fourier transform of an input
sequence *x*[*n*] of length *N* is [2, (9.38)]:

| |
(1) |

It requires *O*(*N*^{2}) operations to calculate, as the summation from
to *N*-1 needs to be completed for each index *k*, of which there are
*N* indices. By way of example, given a 2^{18} = 262144 point
sequence and a instruction time of the DFT would require
to calculate. As
early as 1942, Danielson and Lanczos (as reported in
[3, p.408]) proved that a DFT of an N-point sequence could
be shown to equal the sum of two *N*/2 point sequences. This result
enabled James Cooley and John Tukey to develop their formulation of
the DFT (2), writing :

| |
(2) |

Given the ranges in (3):

For the radix-2 case, *N*_{1} = 2 and *N*_{2} = *N* / *N*_{1} = *N*/2 and the
resultant two point summation in the center expands easily (4:

| |
(3) |

Likewise, for the radix-4 algorithm *N*_{1} = 4 and *N*_{2} = *N* / 4. The
center summation expands to four terms, resulting in
(5):

| |
(4) |

** Next:** 3 Implementation
**Up:** Implementation and Comparison of
** Previous:** 1 Introduction

*Mike Andrews *

6/29/1998