What’s Going On with DIT/DIF II
Here of course vector size N = 2d
For DIT, the first step, manipulates (in “butterfly fashion”), the lowest component m0 for time and creates the highest binary digit kd-1 for frequency domain.
Note that most FFT implementation overwrite f[m] by its FFT GN(k,f) as they go along
This implies that we start with f(m) where m labeled like
And end with that start of a recursive FFT labeled like:
Note characteristic bit reversal in storage of GN(k,f)