A prime factor FFT algorithm using high-speed convolution
作者： D. Kolba , T. Parks
DOI: 10.1109/TASSP.1977.1162973
关键词:
摘要: Two recently developed ideas, the conversion of a discrete Fourier transform (DFT) to convolution and implementation short convolutions with minimum multiplications, are combined give efficient algorithms for long transforms. Three compared in terms number multiplications additions. Timing prime factor fast (FFT) algorithm using high-speed convolution, which was programmed an IBM 370 8080 microprocessor, is presented.
rice.edu参考文章(10)
Bernard Gold, Charles M. Rader, Digital Processing of Signals Digital processing of signals. ,(1983)
C.M. Rader, Discrete Fourier transforms when the number of data samples is prime Proceedings of the IEEE. ,vol. 56, pp. 1107- 1108 ,(1968) , 10.1109/PROC.1968.6477
S. Winograd, On computing the Discrete Fourier Transform. Proceedings of the National Academy of Sciences of the United States of America. ,vol. 73, pp. 1005- 1006 ,(1976) , 10.1073/PNAS.73.4.1005
L. R. Rabiner, B. Gold, C. K. Yuen, Theory and application of digital signal processing ,(1975)
James W. Cooley, John W. Tukey, An algorithm for the machine calculation of complex Fourier series Mathematics of Computation. ,vol. 19, pp. 297- 301 ,(1965) , 10.1090/S0025-5718-1965-0178586-1
H. Silverman, An introduction to programming the Winograd Fourier transform algorithm (WFTA) IEEE Transactions on Acoustics, Speech, and Signal Processing. ,vol. 25, pp. 152- 165 ,(1977) , 10.1109/TASSP.1977.1162924
R. Singleton, An algorithm for computing the mixed radix fast Fourier transform IEEE Transactions on Audio and Electroacoustics. ,vol. 17, pp. 93- 103 ,(1969) , 10.1109/TAU.1969.1162042
R. Agarwal, J. Cooley, New algorithms for digital convolution IEEE Transactions on Acoustics, Speech, and Signal Processing. ,vol. 25, pp. 392- 410 ,(1977) , 10.1109/TASSP.1977.1162981
C. Burrus, Index mappings for multidimensional formulation of the DFT and convolution IEEE Transactions on Acoustics, Speech, and Signal Processing. ,vol. 25, pp. 239- 242 ,(1977) , 10.1109/TASSP.1977.1162938
I. J. Good, The Interaction Algorithm and Practical Fourier Analysis Journal of the royal statistical society series b-methodological. ,vol. 20, pp. 361- 372 ,(1958) , 10.1111/J.2517-6161.1958.TB00300.X