I am trying to formulate an n-dimension algorithm for the Cooley-Tukey FFT. In two dimensions, it is very clear:

$$ Y[k_1 + k_2 n_1] = \sum_{l_2 = 0}^{n_2} \Biggl[ \Biggl( \sum_{l_1 = 0}^{n_1 - 1} X \left[l_1 n_2 + l_2 \right] \omega_{n_1}^{l_2 k_1}\Biggl)\omega_n^{l_2 k_1}\Biggl]\omega_{n_2}^{l_2 k_2} $$

Here is a link on more documentation on this formula: Implementing FFTs in Practice

In the case of 3 dimensions, how would this formula change? So if in the previous example we had $$ N = n_1 * n_2$$

How could I write the formula for $$ N = n_1 * ( n_2 *n_3 )$$

and in the case of n dimensions, how could I general the summations? I am having trouble understanding how the twiddle factors get accounted for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.