# Cooley-Tukey FFT with arbitrary radices

The radix-2 FFT using Cooley-Tukey utilises two interleaved transforms of length $N/2$, and you can see near the bottom of that section that we can find the second half of the original transform by multiplying the twiddle factor by $-1$. (See the fourth paragraph in that section).

Now, let's say we have a higher radix. Say, $3$. The individual interleaves would have length $N/3$, so the first third of the transform would be the 3 terms added together with their respective twiddle factors. What about the second and third thirds of the original transform? How would we combine them?

The twiddle factor is easy to work out: It's just the previous twiddle factor raised to the next power - (with the first raised to the zero power which is why there isn't a twiddle factor there) - however what happens with the sign for the subsequent segments?

Also, how do we generalise the sign of the twiddle factor for arbitrary radices?

(I have a feeling I didn't really ask this question in a clear way - if you don't understand I can re-write it).

-
You might be interested in this article. – J. M. Sep 23 '11 at 10:08

Stop thinking about signs and start thinking about complex numbers. The twiddle factor is an nth root of unity. In the case $n=2$ that's $-1$.
In general, the twiddles are of the form $\exp(-2i\pi k/\mathrm{radix})$... – J. M. Sep 23 '11 at 10:09