Simple FFT and DCT algorithms with reduced number of operations
作者： Martin Vetterli , member Eurasip , Henri J. Nussbaumer
DOI: 10.1016/0165-1684(84)90059-8
关键词: Discrete Fourier transform 、 Bruun's FFT algorithm 、 Bluestein's FFT algorithm 、 Prime-factor FFT algorithm 、 Twiddle factor 、 Fast Fourier transform 、 Discrete cosine transform 、 Split-radix FFT algorithm 、 Algorithm 、 Mathematics
摘要: A simple algorithm for the evaluation of discrete Fourier transforms (DFT) and cosine (DCT) is presented. This approach, based on divide conquer technique, achieves a substantial decrease in number additions when compared to currently used FFT algorithms (30% DFT real data, 15% complex data 25% DCT) keeps same multiplications as best known algorithms. The structure fact that it suited (one does not have take transform two sequences simultaneously anymore) should lead efficient implementations wide range applications.
elsevier.com
sci-hub.se 参考文章(21)
Gerald K Mcauliffe, Fourier digital filter or equalizer and method of operation therefor ,(1970)
D. Kolba, T. Parks, A prime factor FFT algorithm using high-speed convolution IEEE Transactions on Acoustics, Speech, and Signal Processing. ,vol. 25, pp. 281- 294 ,(1977) , 10.1109/TASSP.1977.1162973
R. Yavne, An economical method for calculating the discrete Fourier transform national computer conference. pp. 115- 125 ,(1968) , 10.1145/1476589.1476610
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
G. Bruun, z-transform DFT filters and FFT's IEEE Transactions on Acoustics, Speech, and Signal Processing. ,vol. 26, pp. 56- 63 ,(1978) , 10.1109/TASSP.1978.1163036
N. Ahmed, T. Natarajan, K.R. Rao, Discrete Cosine Transform IEEE Transactions on Computers. ,vol. 23, pp. 90- 93 ,(1974) , 10.1109/T-C.1974.223784
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
C. Runge, H. König, Vorlesungen über Numerisches Rechnen Springer Berlin Heidelberg. ,(1924) , 10.1007/978-3-642-99089-2
C. Rader, N. Brenner, A new principle for fast Fourier transformation IEEE Transactions on Acoustics, Speech, and Signal Processing. ,vol. 24, pp. 264- 266 ,(1976) , 10.1109/TASSP.1976.1162805
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