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.