How does the Cooley-Tukey-Algorithm work?

Question

I have tried to understand the Cooley Tukey Algorithm for some time. I read many articles and watched some videos like these:
https://www.youtube.com/watch?v=iTMn0Kt18tg
https://www.youtube.com/watch?v=h7apO7q16V0
https://www.youtube.com/watch?v=E8HeD-MUrjY
https://www.youtube.com/watch?v=mPVtovydY1k
(Source: YouTube)
First my background: I know how the normal Fourier Transform, the DFT, Laplace and so on work. I would be able to explain them to other people and have no problems with complex numbers. I programmed the DFT many times and was able to program a Spectrum-Analyzer where you put in an audio file and it outputs a spectrogram. (Just by using DFT but very limited Frequency range) I use Python. Here is an example DFT in Python:

import numpy
import matplotlib.pyplot


frequency = 4
samples_power = 6
f_min = 0
f_max = 10

samples = 2**samples_power
signal = numpy.sin(frequency*2*numpy.pi*numpy.linspace(0,1,samples))

f, t = numpy.meshgrid(numpy.linspace(f_min,f_max,samples) ,numpy.linspace(0,1,samples))
n = f*t

dft_matrix = 1/numpy.sqrt(numpy.shape(n)[0])*numpy.power(numpy.e,-2*numpy.pi*1j*n)

dft = numpy.sum(signal*dft_matrix,axis=1)
amplitude = numpy.abs(dft)
phase = numpy.arctan(dft.imag/dft.real)

matplotlib.pyplot.plot(numpy.linspace(f_min,f_max,samples),amplitude)
matplotlib.pyplot.xlabel("Frequency (Hz)")
matplotlib.pyplot.ylabel("Energy / Amplitude")
matplotlib.pyplot.show()

But this gets very slow very soon. I want to learn how the FFT works, so that I can use it. What I know about it, that is has something to do with the "nth root of unity". And even and odd indexes are separated into two separate matrices. There are some redundancies in the DFT, if you analyze just integer frequencies. They are all at 0 in the middle. Even and odd frequencies also cross zero on different fractions. And the Cooley-Tukey-Algorithm/FFT makes use of it.

What I dont understand:
-the connection between all these things (zero points on different fractions, even and odd, nth root of unity ...)
-what seperating even and odd indexes does
-what axis is split into even and odd and what happens with the other because everyone seems only to be talking about one axis.
-what points are not used in the smaller matrices
-if the even and odd matrices are multiplied with the even and odd indexes of the signal
-what operations have to be done with the two resulting vectors to get the output
-what frequencies are used/allowed and if they have to be in a specific order

How does the Cooley Tukey Algorithm Work?

I need it explained in right order with logical connections and as much detail as possible (especially in Math). I would appreciate it, if someone could do that. Thanks for the answers in advance!

Answer 1

I found a great Video on Youtube from a German University:
https://www.youtube.com/watch?v=HFlIIIi5cEM
(don't really need audio because the drawings are self-explaining, but you can use subtitles if you want)
And this lecture from Rensselaer Polytechnic Institute:
https://www.youtube.com/watch?v=1mVbZLHLaf0
(Source Youtube)

Now I know what the missing puzzle piece was. It is the "Twiddle Factors" or how you want to call them. I didn't know three things:

1. Why you need them at all
2. Why they are power of $k$
3. What happens with the other side of the Matrix

The German guy explains it very good by drawing the DFT-Matrix.

Why do you need them?
-> Because you can just calculate the DFT of the even rows and by multiplying it with $W_N^k$ you get the odd rows for "free"

Why are they a Power of $k$?
-> The further right you look at the DFT-Matrix, the bigger the $W_N^{kn}$ gets, and the twiddle factors have to get bigger too

What about the other side?
-> In even row's the other side is the same, and in odd row's it's the opposite. If you would calculate an $N=8$ Matrix this would mean that for as an example the first row (even, in the 8x8) you add samples 0 to 3 and 4 to 7 and then multiply the length-4 vector by the first row of the 4x4 Matrix and you have just calculated the first frequency. For the odd rows (in the 8x8), you would subtract samples 0 to 3 - 4 to 7 and multiply the resulting length-4 vector by the twiddle factors. Then multiply the vector by the first row of the 4x4 and suprise, you just got the the second frequency.

It is so easy, you just need the right teacher. And in the Internet it is really hard to find someone who's explaining something the way you understand it. Thankfully I did.

Answer 2

I think the FFT trick becomes obvious once you notice that the DFT of $x(n)1_{2|n}$ (setting to $0$ the odd samples, assuming the signal has even length $N$) is $\frac{X(k)+X(k+N/2)}2$, the DFT of $x(n)1_{2\ \nmid\ n}$ is $\frac{X(k)-X(k+N/2)}2$.

So we can compute the (length $N/2$) DFT of $x(2n)$ and $x(2n+1)$ separately and mix them at the end.

In practice it is a bit more complicated (when $N$ isn't a power of $2$, and there are also some optimizations to compute the $N$th roots of unity) but the idea is there.