Understanding the radix-2 FFT recursive algorithm

The recursive implementation of the radix-2 Decimation-In-Frequency algorithm can be understood using the following two figures.

The first one refers to pushing the stack phase, while the second one illustrates the popping the stack phase.


Figure I



Figure II

In particular, the two figures illustrate the Matlab implementation that you may find on our GitHub website:

The above recursive implementation is the counterpart of the iterative implementation of the radix-2 Decimation In Frequency. Please, note that the present recursive one does not require any reverse bit ordering, neither of the input nor of the output sequences.

Leave a Reply

Your email address will not be published. Required fields are marked *