- #1
dimensionless
- 462
- 1
Homework Statement
Given a discrete Fourier transform, create a fast Fourier transform.
Homework Equations
The DFT:
[tex]X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n} \quad \quad k = 0, \dots, N-1[/tex]
The Attempt at a Solution
I've heard about split-radix and Cooley-Tukey, but I'm missing the underlying principle. There are a lot of redundant calculations somewhere in the DFT. Where are they? How do I go about optimizing this darn thing? By the way, this isn't really a HW question.