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
Integrity signals
Registry
Cites
Statistics
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?
Unlike the DFT that can be self-factored to obtain FFT algorithms, we are generally unable to factorize the DVM to obtain a self-contained and radix-2 factorization, leading to an FFT-like algorithm.
“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]
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505 · see citing works
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 · see citing works
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 · see citing works
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 · see citing works
JPEG: Still Image Data Compression Standard
Pennebaker, W. B., & Mitchell, J. L. (1992) · Medical Entomology and Zoology · Cited by 2,351 · see citing works
Discrete Cosine Transform: Algorithms, Advantages, Applications
Rao, K. R., Yip, P. C. Y., & Britaňák, V. (1990) · Cited by 1,873 · see citing works
JPEG: Still image data compression standard
Sebestyen, I. (1993) · Computer Standards & Interfaces · doi:10.1016/0920-5489(93)90038-s · Cited by 1,772 · see citing works
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 · see citing works
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 · see citing works
Signal processing with lapped transforms
Malvar, H. S. (1992) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,025 · see citing works
SPIRAL: Code Generation for DSP Transforms
Puschel, M., Moura, J. M. F., Johnson, J. R., Padua, D., Veloso, M. M., Singer, B. W., Xiong, J., Franchetti, F., Gacic, A., Voronenko, Y., et al. (2005) · Proceedings of the IEEE · doi:10.1109/jproc.2004.840306 · Cited by 826 · see citing works
On computing the discrete Fourier transform
Winograd, S. (1978) · Mathematics of Computation · doi:10.1090/s0025-5718-1978-0468306-4 · Cited by 613 · see citing works
Gentleman, W. M., & Sande, G. (1966) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1464291.1464352 · Cited by 545 · see citing works
Real-valued fast Fourier transform algorithms
Sorensen, H., Jones, D., Heideman, M., & Burrus, C. (1987) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1987.1165220 · Cited by 500 · see citing works
A fast Fourier transform compiler
Frigo, M. (1999) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/301618.301661 · Cited by 445 · see citing works
Self-citationDuhamel, P., & Hollmann, H. D. L. (1984) · Electronics Letters · doi:10.1049/el:19840012 · Cited by 425 · see citing works
Vasconcelos, W. V. (1998) · Algorithms and computation in mathematics · doi:10.1007/978-3-642-58951-5_2 · Cited by 406 · see citing works
A Fast DCT-SQ Scheme for Images
Arai, Y., Agui, T., & Nakajima, M. (1988) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · Cited by 360 · see citing works
Simple FFT and DCT algorithms with reduced number of operations
Vetterli, M., Eurasip, M., & Nussbaumer, H. J. (1984) · Signal Processing · doi:10.1016/0165-1684(84)90059-8 · Cited by 334 · see citing works
The On-Line Encyclopedia of Integer Sequences
Finch, S. R. (2021) · The Mathematical Intelligencer · doi:10.1007/s00283-021-10060-2 · Cited by 301 · see citing works
On Computing the Discrete Fourier Transform
Winograd, S. (1978) · Mathematics of Computation · doi:10.2307/2006266 · Cited by 280 · see citing works
Implementation of "Split-radix" FFT algorithms for complex, real, and real-symmetric data
Duhamel, P. (1986) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1986.1164811 · Cited by 268 · see citing works
On computing the split-radix FFT
Sorensen, H. V., Heideman, M. T., & Burrus, C. S. (1986) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1986.1164804 · Cited by 233 · see citing works
Analysis of linear digital networks
Crochiere, R. E., & Oppenheim, A. V. (1975) · Proceedings of the IEEE · doi:10.1109/proc.1975.9793 · Cited by 201 · see citing works
A new principle for fast Fourier transformation
Rader, C. M., & Brenner, N. (1976) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1976.1162805 · Cited by 155 · see citing works
An economical method for calculating the discrete Fourier transform
Yavne, R. (1968) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1476589.1476610 · Cited by 113 · see citing works
Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
Morgenstern, J. (1973) · Journal of the ACM · doi:10.1145/321752.321761 · Cited by 108 · see citing works
Accuracy of the Discrete Fourier Transform and the Fast Fourier Transform
Schatzman, J. C. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827593247023 · Cited by 108 · see citing works
Fast and numerically stable algorithms for discrete cosine transforms
Plonka, G., & Tasche, M. (2004) · Linear Algebra and its Applications · doi:10.1016/j.laa.2004.07.015 · Cited by 85 · see citing works
Recursive cyclotomic factorization--A new algorithm for calculating the discrete Fourier transform
Martens, J. B. O. S. (1984) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1984.1164395 · Cited by 69 · see citing works
On the number of multiplications necessary to compute a length-2nDFT
Heideman, M. T., & Burrus, C. S. (1986) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1986.1164785 · Cited by 64 · see citing works
A New Radix- $2/8$ FFT Algorithm for Length- $qtimes 2^m$ DFTs
Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2004) · IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications · doi:10.1109/tcsi.2004.834508 · Cited by 48 · see citing works
A new matrix approach to real FFTs and convolutions of length 2 k
Lundy, T., & Buskirk, J. V. (2007) · Computing · doi:10.1007/s00607-007-0222-6 · Cited by 47 · see citing works
Duhamel, P. (1990) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/29.60070 · Cited by 45 · see citing works
Optimality of the Fast Fourier transform
Papadimitriou, C. H. (1979) · Journal of the ACM · doi:10.1145/322108.322118 · Cited by 35 · see citing works
Conjugate pair fast Fourier transform
Kamar, I., & Elcherif, Y. (1989) · Electronics Letters · doi:10.1049/el:19890225 · Cited by 27 · see citing works
Comment: Conjugate pair fast Fourier transform
Krot, A. M., & Minervina, H. B. (1992) · Electronics Letters · doi:10.1049/el:19920721 · Cited by 16 · see citing works
Improved Roundoff Error Analysis for Precomputed Twiddle Factors
Tasche, M., & Zeuner, H. (2002) · Journal of Computational Analysis and Applications · doi:10.1023/a:1012991330474 · Cited by 13 · see citing works
Pan, V. Y. (1986) · Information Processing Letters · doi:10.1016/0020-0190(86)90035-9 · Cited by 12 · see citing works
Comment: Conjugate pair fast Fourier transform
Qian, H., & Zhao, Z.-J. (1990) · Electronics Letters · doi:10.1049/el:19900351 · Cited by 11 · see citing works
Testing multivariate linear functions
Ergün, F. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225167 · Cited by 11 · see citing works
Modified FFTs for fused multiply-add architectures
Linzer, E., & Feig, E. (1993) · Mathematics of Computation · doi:10.1090/s0025-5718-1993-1159169-0 · Cited by 10 · see citing works
Conjugate pair fast Fourier tranform
Gopinath, R. (1989) · Electronics Letters · doi:10.1049/el:19890725 · Cited by 10 · see citing works
Modified FFTs for Fused Multiply-Add Architectures
Linzer, E., & Feig, E. (1993) · Mathematics of Computation · doi:10.2307/2153172 · Cited by 4 · see citing works
Flagged first, then by citations
1 of the 45 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Fast Algorithms for Signal Processing
Blahut, R. E. (2010) · doi:10.1017/cbo9780511760921 · Cited by 274 · see citing works
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 · see citing works
Fürer, M. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250800 · Cited by 246 · see citing works
Arts, L. P. A., & van den Broek, E. L. (2022) · Nature Computational Science · doi:10.1038/s43588-021-00183-z · Cited by 238 · see citing works
Fürer, M. (2009) · SIAM Journal on Computing · doi:10.1137/070711761 · Cited by 217 · see citing works
Kabel, M., Böhlke, T., & Schneider, M. (2014) · Computational Mechanics · doi:10.1007/s00466-014-1071-8 · Cited by 212 · see citing works
Barros, D. J. F., Wilson, S. K., & Kahn, J. M. (2011) · IEEE Transactions on Communications · doi:10.1109/tcomm.2011.112311.100538 · Cited by 155 · see citing works
GW method with the self-consistent Sternheimer equation
Giustino, F., Cohen, M. L., & Louie, S. G. (2010) · Physical Review B · doi:10.1103/physrevb.81.115105 · Cited by 148 · see citing works
Circulant Matrices and Their Application to Vibration Analysis
Olson, B. J., Shaw, S. W., Shi, C., Pierre, C., & Parker, R. G. (2014) · Applied Mechanics Reviews · doi:10.1115/1.4027722 · Cited by 140 · see citing works
End-to-End Energy Modeling and Analysis of Long-Haul Coherent Transmission Systems
Pillai, B. S. G., Sedighi, B., Guan, K., Anthapadmanabhan, N. P., Shieh, W., Hinton, K. J., & Tucker, R. S. (2014) · Journal of Lightwave Technology · doi:10.1109/jlt.2014.2331086 · Cited by 137 · see citing works
Toward Early-Warning Detection Of Gravitational Waves From Compact Binary Coalescence
Weinstein, A. J. (2016) · MPG.PuRe (Max Planck Society) · doi:10.15781/t2752q · Cited by 129 · see citing works
Algebraic Signal Processing Theory: Cooley–Tukey Type Algorithms for Real DFTs
Voronenko, Y., & Püschel, M. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.2006152 · Cited by 126 · see citing works
Fast multiplication and its applications
Bernstein, D. J. (2008) · doi:10.1017/9781139049801.011 · Cited by 125 · see citing works
Frequency Domain Image Translation: More Photo-realistic, Better Identity-preserving
Cai, M., Zhang, H., Huang, H., Geng, Q., Li, Y., & Huang, G. M. (2021) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv48922.2021.01367 · Cited by 122 · see citing works
The Safety of the Blood Supply — Time to Raise the Bar
Snyder, E. L., Stramer, S. L., & Benjamin, R. J. (2015) · New England Journal of Medicine · doi:10.1056/nejmp1500154 · Cited by 92 · see citing works
50 Years of FFT Algorithms and Applications
Kumar, G. G., Sahoo, S. K., & Meher, P. K. (2019) · Circuits Systems and Signal Processing · doi:10.1007/s00034-019-01136-8 · Cited by 83 · see citing works
Fast linear canonical transforms
Healy, J. J., & Sheridan, J. T. (2009) · Journal of the Optical Society of America A · doi:10.1364/josaa.27.000021 · Cited by 83 · see citing works
On the Fixed-Point Accuracy Analysis of FFT Algorithms
Chang, W.-H., & Nguyen, T. Q. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.924637 · Cited by 83 · see citing works
Automotive Holographic Head‐Up Displays
Skirnewskaja, J., & Wilkinson, T. D. (2022) · Advanced Materials · doi:10.1002/adma.202110463 · Cited by 82 · see citing works
Binary Discrete Cosine and Hartley Transforms
Bouguezel, S., Ahmad, M. O., & Swamy, M. N. S. (2012) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2012.2224751 · Cited by 73 · see citing works
MEGADOCK: An All-to-All Protein-Protein Interaction Prediction System Using Tertiary Structure Data
Ohue, M., Matsuzaki, Y., Uchikoga, N., Ishida, T., & Akiyama, Y. (2013) · Protein and Peptide Letters · doi:10.2174/09298665113209990050 · Cited by 72 · see citing works
Marey, M., Dobre, O. A., & Inkol, R. (2012) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2012.041612.111488 · Cited by 72 · see citing works
Müller, V., Kabel, M., Andrä, H., & Böhlke, T. (2015) · International Journal of Solids and Structures · doi:10.1016/j.ijsolstr.2015.02.030 · Cited by 70 · see citing works
Ayala, O., & Wang, L. (2012) · Parallel Computing · doi:10.1016/j.parco.2012.12.002 · Cited by 67 · see citing works
Fritzen, F., & Hodapp, M. (2015) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.5188 · Cited by 67 · see citing works
Nadeau, K. P., Durkin, A. J., & Tromberg, B. J. (2014) · Journal of Biomedical Optics · doi:10.1117/1.jbo.19.5.056013 · Cited by 65 · see citing works
Acharyya, S., Nag, S., & Guha, P. K. (2022) · Analytica Chimica Acta · doi:10.1016/j.aca.2022.339996 · Cited by 65 · see citing works
Molina, M., Muñoz, O., Pascual‐Iserte, A., & Vidal, J. (2014) · IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) · doi:10.1109/pimrc.2014.7136330 · Cited by 59 · see citing works
Type-II/III DCT/DST algorithms with reduced number of arithmetic operations
Shao, X., & Johnson, S. G. (2008) · Signal Processing · doi:10.1016/j.sigpro.2008.01.004 · Cited by 60 · see citing works
Self-citationConvergence of FFT‐based homogenization for strongly heterogeneous media
Schneider, M. (2014) · Mathematical Methods in the Applied Sciences · doi:10.1002/mma.3259 · Cited by 56 · see citing works
A multiresolution time-dependent entropy method for QRS complex detection
Farashi, S. (2015) · Biomedical Signal Processing and Control · doi:10.1016/j.bspc.2015.09.008 · Cited by 55 · see citing works
A Reduced Complexity Transmitter for UF-OFDM
Wild, T., & Schaich, F. (2015) · IEEE Vehicular Technology Conference · doi:10.1109/vtcspring.2015.7145643 · Cited by 54 · see citing works
Canclini, A., Bestagini, P., Antonacci, F., Compagnoni, M., Sarti, A., & Tubaro, S. (2015) · IEEE/ACM Transactions on Audio Speech and Language Processing · doi:10.1109/taslp.2015.2439040 · Cited by 53 · see citing works
Real-time OFDM transmitter beyond 100 Gbit/s
Schmogrow, R., Winter, M., Hillerkuss, D., Nebendahl, B., Ben-Ezra, S., Meyer, J., Dreschmann, M., Huebner, M., Becker, J., Koos, C. G., et al. (2011) · Optics Express · doi:10.1364/oe.19.012740 · Cited by 47 · see citing works
DC-Biased Optical OFDM for IM/DD Passive Optical Network Systems
Sanya, M. F., Djogbe, L., Vianou, A. C., & Aupetit‐Berthelemot, C. (2015) · Journal of Optical Communications and Networking · doi:10.1364/jocn.7.000205 · Cited by 47 · see citing works
Out-Of-Band Radiation in Multicarrier Systems: A Comparison
Baltar, L. G., Waldhauser, D. S., & Nossek, J. A. (2007) · Springer eBooks · doi:10.1007/978-1-4020-6129-5_11 · Cited by 47 · see citing works
Twenty years of ultrawideband: opportunities and challenges
Sipal, V., Allen, B., Edwards, D. J., & Honary, B. (2012) · IET Communications · doi:10.1049/iet-com.2011.0281 · Cited by 45 · see citing works
Luan, J., Hooper, S., Wen, L., & Chen, Y. (2012) · Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields · doi:10.1103/physrevd.85.102002 · Cited by 43 · see citing works
Fast fourier transform algorithms with applications
Gao, S., & Mateer, T. D. (2008) · TigerPrints (Clemson University) · Cited by 43 · see citing works
Type-IV DCT, DST, and MDCT algorithms with reduced numbers of arithmetic operations
Shao, X., & Johnson, S. G. (2008) · Signal Processing · doi:10.1016/j.sigpro.2007.11.024 · Cited by 42 · see citing works
Self-citationEfficient Algorithms for the Discrete Gabor Transform with a Long Fir Window
Søndergaard, P. L. (2011) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-011-9210-5 · Cited by 40 · see citing works
Barros, D. J. F., & Kahn, J. M. (2010) · Journal of Lightwave Technology · doi:10.1109/jlt.2010.2048999 · Cited by 40 · see citing works
Hakkarainen, A., Werner, J., Dandekar, K. R., & Valkama, M. (2016) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2521382 · Cited by 40 · see citing works
World’s Fastest FFT Architectures: Breaking the Barrier of 100 GS/s
Garrido, M., Möller, K., & Kumm, M. (2018) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2018.2886626 · Cited by 40 · see citing works
A raw data simulator for Bistatic Forward-looking High-speed Maneuvering-platform SAR
Meng, Z., Li, Y., Li, C., Xing, M., & Bao, Z. (2015) · Signal Processing · doi:10.1016/j.sigpro.2015.05.008 · Cited by 38 · see citing works
PAPR Reduction of OFDM Signal Through DFT Precoding and GMSK Pulse Shaping in Indoor VLC
Ahmad, R., & Srivastava, A. K. (2020) · IEEE Access · doi:10.1109/access.2020.3006247 · Cited by 37 · see citing works
tcFFT: A Fast Half-Precision FFT Library for NVIDIA Tensor Cores
Li, B., Cheng, S., & Lin, J. (2021) · IEEE International Conference on Cluster Computing (CLUSTER) · doi:10.1109/cluster48925.2021.00035 · Cited by 36 · see citing works
Fixed-Point Analysis and Parameter Selections of MSR-CORDIC With Applications to FFT Designs
Park, S. Y., & Yu, Y. J. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2214218 · Cited by 35 · see citing works
Muñoz-Martín, J. F., Miguelez, N., Castella, R., Fernandez, L., Solanellas, A., Via, P., & Camps, A. (2018) · IEEE International Geoscience and Remote Sensing Symposium (IGARSS) · doi:10.1109/igarss.2018.8519037 · Cited by 35 · see citing works
Healy, J. J., & Sheridan, J. T. (2011) · Journal of the Optical Society of America A · doi:10.1364/josaa.28.000786 · Cited by 34 · see citing works
Low Complexity Implementation of Universal Filtered Multi-Carrier Transmitter
Guo, Z., Liu, Q., Zhang, W., & Wang, S. (2020) · IEEE Access · doi:10.1109/access.2020.2970727 · Cited by 32 · see citing works
A parallel fast multipole method for elliptic difference equations
Liska, S., & Colonius, T. (2014) · Journal of Computational Physics · doi:10.1016/j.jcp.2014.07.048 · Cited by 31 · see citing works
The Fastest Fourier Transform in the South
Blake, A. M., Witten, I. H., & Cree, M. J. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2273199 · Cited by 31 · see citing works
New Parametric Discrete Fourier and Hartley Transforms, and Algorithms for Fast Computation
Bouguezel, S., Ahmad, M., & Swamy, M. N. S. (2010) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2010.2072151 · Cited by 31 · see citing works
Joint Optimization of Signal Design and Resource Allocation in Wireless D2D Edge Computing
Kim, J.-H., Kim, T., Hashemi, M., Brinton, C. G., & Love, D. J. (2020) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom41043.2020.9155510 · Cited by 31 · see citing works
Fast Radix-32 Approximate DFTs for 1024-Beam Digital RF Beamforming
Madanayake, A., Cintra, R. J., Akram, N., Ariyarathna, V., Mandal, S., Coutinho, V. A., Bayer, F. M., Coelho, D. F. G., & Rappaport, T. S. (2020) · IEEE Access · doi:10.1109/access.2020.2994550 · Cited by 31 · see citing works
Out-of-distribution Detection via Frequency-regularized Generative Models
Cai, M., & Li, Y. (2023) · IEEE Winter Conference on Applications of Computer Vision · doi:10.1109/wacv56688.2023.00548 · Cited by 29 · see citing works
Analysis of an FBMC/OQAM scheme for asynchronous access in wireless communications
Mattera, D., Tanda, M., & Bellanger, M. (2015) · EURASIP Journal on Advances in Signal Processing · doi:10.1186/s13634-015-0191-4 · Cited by 29 · see citing works
Partitioned convolution algorithms for real-time auralization
Wefers, F. (2014) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2015-02185 · Cited by 29 · see citing works
Fast Fourier transform using matrix decomposition
Zhou, Y., Cao, W., Liu, L., Agaian, S. С., & Chen, C. L. P. (2014) · Information Sciences · doi:10.1016/j.ins.2014.08.022 · Cited by 28 · see citing works
Frequency Domain Equalization with Minimum Complexity in Coherent Optical Transmission Systems
Leibrich, J., & Rosenkranz, W. (2010) · Optical Fiber Communication Conference · doi:10.1364/ofc.2010.owv1 · Cited by 28 · see citing works
Guaranteed-Stable Sliding DFT Algorithm With Minimal Computational Requirements
Park, C. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2726988 · Cited by 28 · see citing works
Li, X., Salinet, J. L., de Almeida, T. P., Vanheusden, F. J., Chu, G. S., Ng, G. A., & Schlindwein, F. S. (2017) · Computer Methods and Programs in Biomedicine · doi:10.1016/j.cmpb.2017.01.011 · Cited by 27 · see citing works
Interpolative Butterfly Factorization
Li, Y., & Yang, H. (2017) · SIAM Journal on Scientific Computing · doi:10.1137/16m1074941 · Cited by 27 · see citing works
How to Write Fast Numerical Code: A Small Introduction
Chellappa, S., Franchetti, F., & Püschel, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88643-3_5 · Cited by 27 · see citing works
FFT and sparse FFT techniques and applications
Mohapatra, B. N., & Mohapatra, R. K. (2017) · IFIP International Conference on Wireless and Optical Communications Networks (WOCN) · doi:10.1109/wocn.2017.8065859 · Cited by 26 · see citing works
Gao, J., Fei, S., Ho, Y., Matsuda, R., Daiguji, H., & Delaunay, J. (2021) · The Journal of Physical Chemistry C · doi:10.1021/acs.jpcc.1c03351 · Cited by 25 · see citing works
An Efficient Approach for Time-Domain Simulation of Pulse Propagation in Optical Fiber
He, K., & Li, X. (2010) · Journal of Lightwave Technology · doi:10.1109/jlt.2010.2070835 · Cited by 25 · see citing works
Efficient Dealiased Convolutions without Padding
Bowman, J. C., & Roberts, M. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/100787933 · Cited by 25 · see citing works
One-Step Calculation Circuit of FFT and Its Application
Liu, Y., Wang, C., Sun, J., Du, S., & Hong, Q. (2022) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2022.3159803 · Cited by 24 · see citing works
Pérez-Romero, J., Sallent, O., Gelonch, A., Gelabert, X., Klaiqi, B., Kahn, M. L., & Campoy, D. (2023) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2023.3296821 · Cited by 24 · see citing works
AesFA: An Aesthetic Feature-Aware Arbitrary Neural Style Transfer
Kwon, J., Kim, S. Y., Lin, Y., Yoo, S., & Cha, J. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i12.29232 · Cited by 24 · see citing works
Goy, A., & Psaltis, D. (2012) · Optics Express · doi:10.1364/oe.20.022720 · Cited by 23 · see citing works
A Fast Algorithm With Less Operations for Length- $N=q\times 2^{m}$ DFTs
Li, K., Zheng, W., & Li, K. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2379678 · Cited by 23 · see citing works
Dommel, J., Boccolini, G., Raschkowski, L., Jaeckel, S., Thiele, L., Haustein, T., & Prelcic, N. G. (2014) · Advanced Satellite Multimedia Systems Conference and the Signal Processing for Space Communications Workshop (ASMS/SPSC) · doi:10.1109/asms-spsc.2014.6934543 · Cited by 23 · see citing works
Cavalcante, R. L. G., & Yamada, I. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.2011821 · Cited by 23 · see citing works
Wu, J., Wang, L., Yang, G., Senhadji, L., Luo, L., & Shu, H. (2012) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2011.2173386 · Cited by 23 · see citing works
A novel method for fast detection of high-speed targets
Fu, M., Sun, H., Deng, Z., Li, Y., & Zhang, Y. (2020) · Signal Processing · doi:10.1016/j.sigpro.2020.107938 · Cited by 23 · see citing works
Decision-directed iterative methods for PAPR reduction in optical wireless OFDM systems
Azim, A. W., Guennec, Y. L., & Maury, G. (2017) · Optics Communications · doi:10.1016/j.optcom.2016.12.026 · Cited by 22 · see citing works
Performance Analysis of DST-Based Intensity Modulated/Direct Detection (IM/DD) Systems for VLC
Vappangi, S., & Vakamulla, V. M. (2018) · IEEE Sensors Journal · doi:10.1109/jsen.2018.2882378 · Cited by 22 · see citing works
Scintillation event energy measurement via a pulse model based iterative deconvolution method
Deng, Z., Xie, Q., Duan, Z., & Xiao, P. (2013) · Physics in Medicine and Biology · doi:10.1088/0031-9155/58/21/7815 · Cited by 22 · see citing works
On Frequency Offset Estimation for OFDM
Cvetković, Z., Tarokh, V., & Yoon, S. (2013) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2013.012413.120087 · Cited by 22 · see citing works
Identification and validation of stable ARFIMA processes with application to UMTS data
Burnecki, K., & Sikora, G. (2017) · Chaos Solitons & Fractals · doi:10.1016/j.chaos.2017.03.059 · Cited by 22 · see citing works
Burdzik, R., & Khan, D. (2025) · Measurement · doi:10.1016/j.measurement.2025.117314 · Cited by 23 · see citing works
Plonka, G., Potts, D., Steidl, G., & Tasche, M. (2018) · Applied and numerical harmonic analysis · doi:10.1007/978-3-030-04306-3_5 · Cited by 21 · see citing works
Fast IIR Isotropic 2-D Complex Gabor Filters With Boundary Initialization
Bernardino, A. J. M., & Santos-Victor, J. (2006) · IEEE Transactions on Image Processing · doi:10.1109/tip.2006.881995 · Cited by 21 · see citing works
MASS: distance profile of a query over a time series
Zhong, S., & Mueen, A. (2024) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-024-01005-2 · Cited by 20 · see citing works
Molecular dynamics study of water confined in MIL-101 metal–organic frameworks
Fei, S., Hsu, W., Delaunay, J., & Daiguji, H. (2021) · The Journal of Chemical Physics · doi:10.1063/5.0040909 · Cited by 20 · see citing works
Shevgunov, T. Y., Efimov, E., & Guschina, O. (2022) · Sensors · doi:10.3390/s23010215 · Cited by 20 · see citing works
The fast Fourier transform and fast wavelet transform for patterns on the torus
Bergmann, R. (2012) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2012.07.007 · Cited by 20 · see citing works
Lemenkova, P. (2020) · DergiPark (Istanbul University) · Cited by 19 · see citing works
CORDIC based implementation of Fast Fourier Transform
Choudhary, P., & Karmakar, A. (2011) · International Conference on Computer and Communication Technology · doi:10.1109/iccct.2011.6075128 · Cited by 19 · see citing works
Adjustable SAD matching algorithm using frequency domain
Essannouni, F., Thami, R. O. H., Aboutajdine, D., & Salam, A. (2007) · Journal of Real-Time Image Processing · doi:10.1007/s11554-007-0026-0 · Cited by 19 · see citing works
Britaňák, V. (2010) · Signal Processing · doi:10.1016/j.sigpro.2010.09.009 · Cited by 19 · see citing works
Real-Time Perception-Based Clipping of Audio Signals Using Convex Optimization
Defraene, B., van Waterschoot, T., Ferreau, H. J., Diehl, M., & Moonen, M. (2012) · IEEE Transactions on Audio Speech and Language Processing · doi:10.1109/tasl.2012.2210875 · Cited by 19 · see citing works
Iterative Receiver Design for Uplink OFDMA Cooperative Systems
Marey, M., & Dobre, O. A. (2016) · IEEE Transactions on Broadcasting · doi:10.1109/tbc.2016.2606892 · Cited by 19 · see citing works
Scaled Radix-2/8 Algorithm for Efficient Computation of Length-$N=2^{m}$ DFTs
Zheng, W., Li, K., & Li, K. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2310434 · Cited by 19 · see citing works
Perera, S. M., Madanayake, A., & Cintra, R. J. (2020) · IEEE Access · doi:10.1109/access.2020.2970342 · Cited by 18 · see citing works
Efficient fringe image enhancement based on dual-tree complex wavelet transform
Hsung, T.-C., Lun, D. P.-K., & Ng, W. W. L. (2011) · Applied Optics · doi:10.1364/ao.50.003973 · Cited by 18 · see citing works
Bernstein, D. J. (2007) · Springer eBooks · doi:10.1007/978-3-540-77224-8_34 · Cited by 18 · see citing works
- 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
