# Optimizing a DFT

1. Aug 1, 2008

### dimensionless

1. The problem statement, all variables and given/known data
Given a discrete Fourier transform, create a fast Fourier transform.

2. Relevant equations
The DFT:
$$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n} \quad \quad k = 0, \dots, N-1$$

3. 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.

2. Aug 1, 2008

### Redbelly98

Staff Emeritus
Since we are taking sines and cosines of the expression

2*pi*k*n/N

the redundancies are the values of k and n where

k1*n1 (mod N) = k2*n2 (mod N)

It's covered in a chapter of Numerical Recipes in C (or Pascal, or Fortran) by Press, Flannery, Teukolsky and Vetterling.
https://www.amazon.com/Numerical-Recipes-C-Scientific-Computing/dp/0521431085

3. Aug 4, 2008

### dimensionless

Can you tell me what is meant by (mod N)?

It also appears as though there could be more redundancies when

k1*n1/N = k2*n2/N+M

where M is an integer.

4. Aug 4, 2008

### Redbelly98

Staff Emeritus
It's explained here:
http://en.wikipedia.org/wiki/Modular_arithmetic

Yes, exactly. Or equivalently,

k1*n1 = k2*n2 + M*N

In other words, k1*n1 and k2*n2 differ by an integer multiple of N. This can also be written as I did before, in terms of (mod N) notation.

There are even more redundancies, for example

$$\cos[2 \pi \ k1 \ n1 \ / \ N] = \cos[2 \pi (N - k1 \ n1) \ / \ N] \ \rightarrow \ k2 \ n2 = N - k1 \ n1$$

$$\cos[2 \pi \ k1 \ n1 \ / \ N] = -\cos[2 \pi \ ( N/2 \pm k1 \ n1 ) \ / \ N] \ \rightarrow \ k2 \ n2 = N/2 \ \pm \ k1 \ n1$$

I.e. each value of cos(...), or it's negative, occurs 4 times during each period. And similarly for sin(...)

And that's not all:

$$\cos[2 \pi \ k1 \ n1 \ / \ N] = \sin[2 \pi \ (N/4 - k1 \ n1) \ / \ N ] \ \rightarrow \ k2 \ n2 = N/4 - k1 \ n1$$

I.e. there are redundancies between the sin(...) and cos(...) terms as well.

Essentially, you just need to evaluate cos(...) for 1/4 of a period, and all other cos(...) and sin(...) terms will appear in that list.