Optimizing DFT Homework: Split-Radix & Cooley-Tukey

[dimensionless]

Homework Statement

Given a discrete Fourier transform, create a fast Fourier transform.

Homework 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$$

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.

 

[Redbelly98]

There are a lot of redundant calculations somewhere in the DFT. Where are they?

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)

How do I go about optimizing this darn thing? By the way, this isn't really a HW question.

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/dp/0521431085/?tag=pfamazon01-20

 

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

 

[Redbelly98]

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

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

It also appears as though there could be more redundancies when

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

where M is an integer.

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.