FFT algorithms for prime transform sizes and their implementations on VAX, IBM3090VF, and IBM RS/6000
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 41 (2) , 638-648
- https://doi.org/10.1109/78.193205
Abstract
Variants of the Winograd fast Fourier transform (FFT) algorithm for prime transform size that offer options as to operational counts and arithmetic balance are derived. Their implementations on VAX, IBM 3090 VF, and IBM RS/6000 are discussed. For processors that perform floating-point addition, floating-point multiplication, and floating-point multiply-add with the same time delay, variants of the FFT algorithm have been designed such that all floating-point multiplications can be overlapped by using multiply-add. The use of a tensor product formulation, throughout, gives a means for producing variants of algorithms matching computer architecturesKeywords
This publication has 15 references indexed in Scilit:
- Modified Winograd FFT algorithm and its variants for transform size N = pk and their implementationsAdvances in Applied Mathematics, 1989
- Algorithms for Discrete Fourier Transform and ConvolutionPublished by Springer Nature ,1989
- Implementation of a prime factor FFT algorithm on CRAY-1Parallel Computing, 1988
- Vectorized mixed radix discrete Fourier transform algorithmsProceedings of the IEEE, 1987
- Implementation of a self-sorting in-place prime factor FFT algorithmJournal of Computational Physics, 1985
- Arithmetic Complexity of ComputationsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1980
- On Computing the Discrete Fourier TransformMathematics of Computation, 1978
- A prime factor FFT algorithm using high-speed convolutionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1977
- On computing the Discrete Fourier TransformProceedings of the National Academy of Sciences, 1976
- Discrete Fourier transforms when the number of data samples is primeProceedings of the IEEE, 1968