Python Implementation of Radix-4 N=64 DIT FFT with Reduced-size Twiddle table

John Bryan

• The implemented algorithm to use a reduced-size twiddle table is from [1].
  
  
• The twiddle table has nine entries, W^k₆₄, k=0,1,2,...,7,8.
  
  
• Python implementation.
  
  
• The algorithm is tested with random sequence input and compared with numpy fft result to verify correctness.
  
  
  
• Reference:
  1. Teemu Pitkänen, Tero Partanen, and Jarmo Takala, "Low-Power Twiddle Factor Unit for FFT Computation", 2007.