Generating and Searching Families of FFT Algorithms

Details Generating and Searching Families of FFT Algorithms Generating and Searching Families of FFT Algorithms

2011-03-29

arxiv.org/abs/1103.5740v2

Journal on Satisfiability, Boolean Modeling and Computation, 7:145-187, 2011

Computer Science

Information Theory

Preprint submitted on March 28, 2011, to the Journal on Satisfiability, Boolean Modeling and Computation

Scientific paper

A fundamental question of longstanding theoretical interest is to prove the lowest exact count of real additions and multiplications required to compute a power-of-two discrete Fourier transform (DFT). For 35 years the split-radix algorithm held the record by requiring just 4n log n - 6n + 8 arithmetic operations on real numbers for a size-n DFT, and was widely believed to be the best possible. Recent work by Van Buskirk et al. demonstrated improvements to the split-radix operation count by using multiplier coefficients or "twiddle factors" that are not n-th roots of unity for a size-n DFT. This paper presents a Boolean Satisfiability-based proof of the lowest operation count for certain classes of DFT algorithms. First, we present a novel way to choose new yet valid twiddle factors for the nodes in flowgraphs generated by common power-of-two fast Fourier transform algorithms, FFTs. With this new technique, we can generate a large family of FFTs realizable by a fixed flowgraph. This solution space of FFTs is cast as a Boolean Satisfiability problem, and a modern Satisfiability Modulo Theory solver is applied to search for FFTs requiring the fewest arithmetic operations. Surprisingly, we find that there are FFTs requiring fewer operations than the split-radix even when all twiddle factors are n-th roots of unity.

Affiliated with

Also associated with

No associations

Rating

Generating and Searching Families of FFT Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generating and Searching Families of FFT Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating and Searching Families of FFT Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-164417