The Discrete Fourier Transform of length (where is Even) can be rewritten as the sum of two Discrete Fourier Transforms, each of length . One is formed from the Even-numbered points; the other from the Odd-numbered points. Denote the th point of the Discrete Fourier Transform by . Then

**References**

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T.
*Numerical Recipes in C: The Art of Scientific Computing.* Cambridge, England: Cambridge University Press,
pp. 407-411, 1989.

© 1996-9

1999-05-24