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 N_y=2, N_x=N/2, so f is decomposed as h:

and F is decomposed as H:

If we disregard scaling, the decomposed column transform is:

which simplifies to:

Similarly, the decomposed twiddle/row transform is:

which simplifies to:

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

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

This is the decomposition used in the DIF algorithm.

DIT Decomposition.

Let N_y=N/2, N_x=2, so f is decomposed as h:

and F is decomposed as H:

If we disregard scaling, the decomposed column transform is:

which simplifies to:

Similarly, the decomposed twiddle/row transform is:

which simplifies to:

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

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 2^p point transform into 2 rows and 2^p-1 columns you get the DIF algorithm. Decomposing into 2^p-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