If I’d asked you how to implement DFT, what’d you do?

You’d suggest me to take the sum in each polynomials and do them concurrently, fastest right? Wrong.

We can do the sum faster. Remember Merge Sort? So here is the same, we do the sums concurrently, but instead of summing up in O(N)  , we sum in O(lgn)!

That’s it it’s so easy. The rest is just explanation around the algorithms. Hope it will help.

[EDIT] Sorry for misleading, sum up like in merge sort will still be n operations. The key is that we do this in parallel. I assume we know ahead some assumptions regarding the bit rates in our audio systems and the quality of our videos, hence we can implement chips that have those 'power of 2' constant number of inputs.

EDIT: Indeed my previous answer was misleading, since I stated that recursive summation like in merge sort saves calculations and that is of course not true.

What does happen here however is that instead of doing 2N operations on each of the N vectors members (multiplication and summation), we do 2*lg(N) operations, which are caused thanks to recycling of 2 of the previous operations each time from our current and from another, different vector member. If you look at the butterfly diagram, you’ll see that we recycle each time: we reuse 2 of the previous calculations. Instead of doing N of them each time. That yields in 2lgN calculations EACH time instead of N. 

If I’d asked you how to implement DFT, what’d you do?

You’d suggest me to take the sum in each polynomials and do them concurrently, fastest right? Wrong.

We can do the sum faster. Remember Merge Sort? So here is the same, we do the sums concurrently, but instead of summing up in O(N) , we sum in O(lgn)!

That’s it it’s so easy. The rest is just explanation around the algorithms. Hope it will help.

If I’d asked you how to implement DFT, what’d you do?

You’d suggest me to take the sum in each polynomials and do them concurrently, fastest right? Wrong.

We can do the sum faster. Remember Merge Sort? So here is the same, we do the sums concurrently, but instead of summing up in O(N) , we sum in O(lgn)!

That’s it it’s so easy. The rest is just explanation around the algorithms. Hope it will help.

[EDIT] Sorry for misleading, sum up like in merge sort will still be n operations. The key is that we do this in parallel. I assume we know ahead some assumptions regarding the bit rates in our audio systems and the quality of our videos, hence we can implement chips that have those 'power of 2' constant number of inputs.