Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
You might be interested in this article. –  J. M. Sep 23 '11 at 10:08

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
In general, the twiddles are of the form $\exp(-2i\pi k/\mathrm{radix})$... –  J. M. Sep 23 '11 at 10:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.