Bottom     Previous     Contents

DIF and DIT Decomposition Revisited.

It can easily be demonstrated that both the DIF and DIT algorithms are just special cases of the general decomposition of composite numbers. Suppose we want an N point DFT of f where N is even.

DIF Decomposition.

Let Ny=2, Nx=N/2, so f is decomposed as h:

equation

equation

equation

and F is decomposed as H:

equation

equation

equation

If we disregard scaling, the decomposed column transform is:

equation

which simplifies to:

equation

equation

Similarly, the decomposed twiddle/row transform is:

equation

which simplifies to:

equation

(The twiddle factor is 1 in the above case.)

equation

In terms of the original 1D arrays, these two equations correspond to even and odd k respectively:

equation

equation

This is the decomposition used in the DIF algorithm.

DIT Decomposition.

Let Ny=N/2, Nx=2, so f is decomposed as h:

equation

equation

equation

and F is decomposed as H:

equation

equation

equation

If we disregard scaling, the decomposed column transform is:

equation

which simplifies to:

equation

equation

Similarly, the decomposed twiddle/row transform is:

equation

which simplifies to:

equation

equation

In terms of the original 1D arrays, these two equations correspond to 'top' and 'bottom' k respectively:

equation

equation

equation

equation

This is the decomposition used in the DIT algorithm.

Conclusion.

What all this shows is that both the Radix 2 DIF and DIT algorithms can be regarded simply as slightly different implementations of the same more general algorithm. The only difference is that if you decompose a 2p point transform into 2 rows and 2p-1 columns you get the DIF algorithm. Decomposing into 2p-1 rows and 2 columns yields the DIT algorithm.

The corresponding butterflies are really just an optimisation which combines multiplication by the generalised twiddle factors and a 2 point FFT into the same operation. In the DIF algorithm butterfly, the twiddle factors (one of which is 1) are applied after the 2 point (column) FFT. In the DIT algorithm butterfly, the twiddle factors (one of which is again 1) are applied before the 2 point (row) FFT.

©1999 - Engineering Productivity Tools Ltd.


Next     Top