Implementation of Radix-4 DIT and Radix-4 DIF FFT in Python

John Bryan

• The digit-reversal algorithm described in [1] is implemented.
  
  
• The radix-4 DIT and radix-4 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 radix-2 DIT and radix-2 DIF, are plotted below.
  
  
• Python implementation.
  
  
• Results
  
  
  
  
• References:
  1. Xiangui Yu, Nan K Loh, and W.C. Miller, "An improved digit-reversal permutation algorithm", 1992.
  2. Eleanor Chu, Alan George, Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms, 1999.
  3. Stack Overflow.
  4. Douglas L. Jones, "Radix-4 FFT Algorithms", 2006.