The 1D FFT in explicit detail II
There are two special cases of particular importance
Decimation in frequency (DIF) N1=2 N2=N/2 where frequency space is GN( k,f )
Decimation in time (DIT) N1=N/2 N2=2 where time domain is f(m)
These are used in cases where N=2d is a power of 2 and decimations can be applied recursively d times.
You can apply N=2d to a general value of N by taking say N=773 and adding 251 zeros to make it equal to 1024.
This can be wasteful especially in multi dimensional transforms where you waste space in x y and z directions
The binary FFT illustrates issues and has much simpler algebra -- FFTW uses a special purpose compiler to cope with the general case