A modified split-radix FFT with fewer arithmetic operations

by Steven G. Johnson and Matteo Frigo.

IEEE Transactions on Signal Processing, volume 55, number 1, Jan 2007, pages 111-119
[Full text]


Recent results by Van Buskirk et al. have broken the record set by Yavne in 1968 for the lowest exact count of real additions and multiplications to compute a power-of-two discrete Fourier transform (DFT). Here, we present a simple recursive modification of the split-radix algorithm that computes the DFT with asymptotically about 6% fewer operations than Yavne, matching the count achieved by Van Buskirk's program generation framework. We also discuss the application of our algorithm to real-data and real-symmetric (discrete cosine) transforms, where we are again able to achieve lower arithmetic counts than previously published algorithms.

This page maintained by: Matteo Frigo. Last updated: Sun Jun 21 09:29:38 2009