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

# 2 Theory

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(N2) 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 218 = 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, N1 = 2 and N2 = N / N1 = N/2 and the resultant two point summation in the center expands easily (4:

 (3)

Likewise, for the radix-4 algorithm N1 = 4 and N2 = 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