2011/11/01 by Steve Haynal, Heidi Haynal · 1 citation
Computer Science · Engineering · #Numerical Methods and Algorithms #Formal Methods in Verification #VLSI and FPGA Design Techniques
paper · pdf · doi:10.3233/sat190084
openalex publication_date 2011/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 2 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 and Lundy 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.