The DOI matches its Crossref record; 44 of the 45 references it cites were found in a registry or an index.
A Modified Split-Radix FFT With Fewer Arithmetic Operations
Abstract
Recent results by Van Buskirk 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
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Therefore, unlike the case of the DFT that can be self-factored to obtain FFT algorithms [19,20,21], we are generally unable to factorize the DVM to obtain a self-contained and radix-2 factorization, leading to an FFT-like algorithm.”
From Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications (2024) · cites this paper as [21]
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
The Design and Implementation of FFTW3
Frigo, M., & Johnson, S. G. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840301 · Cited by 5,086
Self-citationThe On-Line Encyclopedia of Integer Sequences
Sloane, N. J. A. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73086-6_12 · Cited by 3,348
JPEG: Still Image Data Compression Standard
Pennebaker, W. B., & Mitchell, J. L. (1992) · Medical Entomology and Zoology · Cited by 2,351
Discrete Cosine Transform: Algorithms, Advantages, Applications
Rao, K. R., Yip, P. C. Y., & Britaňák, V. (1990) · Cited by 1,873
JPEG: Still image data compression standard
Sebestyen, I. (1993) · Computer Standards & Interfaces · doi:10.1016/0920-5489(93)90038-s · Cited by 1,772
Computational Frameworks for the Fast Fourier Transform
Loan, C. F. V. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970999 · Cited by 1,292
Fast fourier transforms: A tutorial review and a state of the art
Duhamel, P., & Vetterli, M. (1990) · Signal Processing · doi:10.1016/0165-1684(90)90158-u · Cited by 1,155
Signal processing with lapped transforms
Malvar, H. S. (1992) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,025
Flagged first, then by citations
1 of the 45 references couldn’t be matched to a known paper.
Research works printed but not linked: 4
- van buskirk, 2004, Usenet posts
- knuth, 1998, Seminumerical Algorithms, 2
- plonka, 0, Split-radix algorithms for discrete trigonometric transforms
- volynets, 1993, algorithms of the hartley fast transformation with conjugate pairs, Radioelectron Comm Syst, 36, 57
Cited by
Sorted by citations
Fast Algorithms for Signal Processing
Blahut, R. E. (2010) · doi:10.1017/cbo9780511760921 · Cited by 274
TOWARD EARLY-WARNING DETECTION OF GRAVITATIONAL WAVES FROM COMPACT BINARY COALESCENCE
Cannon, K. C., Cariou, R., Chapman, A., Crispin‐Ortuzar, M., Fotopoulos, N., Frei, M., Hanna, C., Kara, E., Keppel, D., Liao, L., et al. (2012) · The Astrophysical Journal · doi:10.1088/0004-637x/748/2/136 · Cited by 261
Fürer, M. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250800 · Cited by 246
Arts, L. P. A., & van den Broek, E. L. (2022) · Nature Computational Science · doi:10.1038/s43588-021-00183-z · Cited by 238
Fürer, M. (2009) · SIAM Journal on Computing · doi:10.1137/070711761 · Cited by 217
Metadata
- Authors
- Johnson, S. G., & Frigo, M.
- Affiliations
- Massachusetts Institute of Technology (US)
- IBM Research - Austin (US)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2007-01
- Volume
- 55
- Issue
- 1
- Pages
- 111-119
- ISSN
- 1053-587X (ISSN-L)
- OpenAlex
- W2135031801
- Cited by
- 380
- References
- 45
- Citations by year
- 2026: 4 · 2025: 14 · 2024: 18 · 2023: 13 · 2022: 23 · 2021: 26 · 2020: 27 · 2019: 15 · 2018: 16 · 2017: 12 · 2016: 19 · 2015: 24 · 2014: 26 · 2013: 19 · 2012: 20
- FWCI
- 27.97
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Signal Processing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Digital Filter Design and Implementation
- Physical Sciences › Mathematics › Applied Mathematics › Mathematical Analysis and Transform Methods
- Physical Sciences › Engineering › Electrical and Electronic Engineering › Advanced Electrical Measurement Techniques
- Keywords
- split-radix FFT, discrete Fourier transform, recursive algorithm, discrete cosine transform, algorithm optimization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
