The Cooley-Tukey algorithm is nicely understood as a "4 step FFT". Both the decimation in time and decimation in frequency algorithms, and the "bit reversals"

The Cooley-Tukey algorithm is nicely understood as a "4 step FFT". Both the decimation in time and decimation in frequency algorithms, and the "bit reversals" they use, are really just special cases of the more general (and simpler) thing. Say you have an array of size N, where N = P*Q. You can treat your 1D array as a 2D array in row major form. Then the 4 steps are: do vertical FFTs of the columns "twiddle" the data do horizontal FFTs of the rows transpose the array The twiddle step is really just multiplying each element in the array by a complex number. See: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#General_factorizations This breaks the N-size larger FFT into smaller P and Q sized FFTs. If P or Q is factorable, then you can recursively apply the algorithm to perform each of the smaller FFTs. Eventually, you'll reach a base case where you need a different algorithm. For instance, if you get to a factor of 2 or 3, you'll just do the simple DFT. If you get a large prime, there are other approaches. If N is a power of 2, then you can always choose one of P or Q to be 2. These are the decimation in time or decimation in frequency algorithms that most people are taught. I think restricting it to this special case, and jumbling it all up with the "butterfly" diagrams commonly shown really obscures an elegant and easily understood algorithm. If you save all the transposes, and the transposes in the recursions until the end, it ends up being the bit (or digit) reversal you're familiar with. The reason bit reversal seems magical is because it hides the fact that it was really just a bunch of transposes.