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.

radix-2_recursive_part_I

Figure I

 

radix-2_recursive_part_II

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 *