0
$\begingroup$

I can't find step by step explanation of the FFT algorithm. Why it is faster than common DFT?
As I understand, we calculate DFT for $X$, and for $Y$, then merge them and got the final DFT.

$\endgroup$
  • $\begingroup$ "we calculate DFT for X, and for Y, then merge them and got the final DFT": no, you are confusing the 2D DFT and the FFT. $\endgroup$ – Yves Daoust Jan 21 at 20:58
1
$\begingroup$

I can't find step by step explanation of the FFT algorithm

The explanation and pseudocode for the Cooley-Tukey Algorithm on Wikipedia helped me implement my own. Though keep in mind that Cooley-Tukey is not the only FFT algorithm, there are also alogorithms that can deal with prime sizes, for example.

Why it is faster than common DFT?

I think you are mixing concepts here. DFT is the transform, FFT is a class of algorithms that can calculate it with fewer operations than by naively carrying out all the multiplications and sums.

$\endgroup$
0
$\begingroup$

I think a full explanation here will be very long..

You can take a look at "Introduction to Algorithms, By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein".

That book is the holy bible for algorithms.. I guess you can get a pdf free (and illegal?) from the web. I got the third edition, take a look from page 906 and on, you will find very nice explanations! If you still have issues you are welcome here

$\endgroup$
0
$\begingroup$

The DFT can be seen as a matrix/vector product, where the matrix elements are certain roots of unity and the vector is made of the input values. When applied "by brute force", it takes $T(n)=\Theta(n^2)$ operations.

The FFT is a more efficient method, based on an observation: if you split the input in two halves and take the respective FFTs, you can obtain the global FFT by combining the coefficients in pairs, and this step takes $\Theta(n)$ operations. This leads to the recurrence

$$T(2n)=2T(n)+\Theta(n)$$ that has the solution $T(n)=\Theta(n\log n)$. For large $n$, this is a significant saving.

$\endgroup$

Your Answer

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

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