For simplicity, we shall consider a two dimensional transform, which might be used as part of an image processing algorithm (for example). The results derived here can easily be extended to more dimensions. The definitions of the DFT and IDFT of a 2D Nx by Ny array, indexed by (nx,ny), where nx=0..Nx-1 and ny = 0..Ny-1, are as follows:
As before, the ranges of the frequency domain indices are kx=0..Nx-1 and ny = 0..Ny-1.
As with the 1D transforms, periodicity applies to both the 'frequency domain' data F and 'time domain' data f (2D time??). It is also possible to prove that the 2D IDFT really is an inverse 2D DFT, using the same technique we used for the 1D transforms (see Annex A).
It should be apparent that the 2D DFT can be evaluated by performing separate 1D DFT's on the rows and columns of the 2D array. To convince yourself, consider this re-arrangement of the 2D DFT definition:
Both of these expressions are simply 1D DFT's. Of course, it makes no difference whether you DFT the rows or the columns first. This principal can be extended to DFT's any number of dimensions.
The only real difficulty with 'in-place' multi-dimensional FFT's is that we can't use a 1D FFT routine which requires the array elements to be adjacent in memory. We need an FFT that allows the element spacing to be passed as a parameter. It isn't too hard to modify most FFT routines to allow this. An easier (but marginally slower) alternative would be to copy the relevent row or column data to a smaller buffer prior to transform and then copy the transformed the result back.
If we suppose that Nx and Ny are regular powers of 2, we could use one or other of the two Radix 2 FFT algorithms to perform the 1D DFT's. The number of butterflies C'(N) required by an N point 1D FFT was worked out earlier:
So, the number required by the 2D FFT using 1D FFT's on rows and columns is given by:
The 2D Radix 2 FFT would require the same number of butterflies as as a single 1D Radix 2 FFT of NxNy points. It's easy to see that this result can be extended to any number of dimensions.
©1999 - Engineering Productivity Tools Ltd.