What’s Going On with DIT/DIF I

• DIT and DIF have identical computational complexity analyses at the superficial level we did so far

  • We will see some important features when we analyze where the data is stored and issues of good cache use and parallelism

• First we will discuss a way of thinking about binary FFT’s which will make the future discussion much clearer

• Critical idea is to represent indices by their binary representation shown below as d digit words for k and m:

• e.g.

k as a binary word

m as a binary word

Previous slide

Next slide

Back to first slide

View graphic version