|
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
|
