Radix-2 Decimation-In-Time Iterative FFT

At the github page, we prove an implementation of the radix-2 Decimation-In-Time FFT in Matlab. The code is an iterative one and considers the scheme in the following figure:



A recursive approach is also possible.

The implementation calculates also the number of performed multiplications and additions and compares it with the theoretical calculations reported in “Number of operation counts for radix-2 FFTs”.

The code is obviously much slower than the highly optimized FFTW exploited by Matlab.

Note also that the twiddle factors omegaa^(interButterflyIndex * 2^(numStages – p)) can be calculated off-line and then restored from a lookup table, but this point is skipped in the mentioned code.

Leave a Reply

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