2
$\begingroup$

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.

$\endgroup$

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.