Implementation of Radix4 DIT and Radix4 DIF FFT in Python
John Bryan

The digitreversal algorithm described in [1] is implemented.

The radix4 DIT and radix4 DIF algorithms are implemented and tested for correctness. Multiple length random sequences are input and results are compared to numpy fft results. The execution times for each algorithm, along with those for implemented radix2 DIT and radix2 DIF, are plotted below.

Python implementation.

Results

References:

Xiangui Yu, Nan K Loh, and W.C. Miller, "An improved digitreversal permutation algorithm", 1992.

Eleanor Chu, Alan George, Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms, 1999.

Stack Overflow.

Douglas L. Jones, "Radix4 FFT Algorithms", 2006.