FAST FOURIER-TRANSFORMS - A TUTORIAL REVIEW AND A STATE-OF-THE-ART

被引：640
作者：
DUHAMEL, P
VETTERLI, M
机构：
[1] CNET, PAB, RPE, 92131 Issy les Moulineaux, 38-40, Rue du General Leclerc
[2] Dept of EE, CTR, Columbia University, New York, NY 10027, S.W. Mudd Building
来源：
SIGNAL PROCESSING | 1990年 / 19卷 / 04期
关键词：
computational complexity; fast algorithms; Fourier transforms;
D O I：
10.1016/0165-1684(90)90158-U
中图分类号：
TM [电工技术]; TN [电子技术、通信技术];
学科分类号：
0808 ; 0809 ;
摘要：
The publication of the Cooley-Tukey fast Fourier transform (FFT) algorithm in 1965 has opened a new area in digital signal processing by reducing the order of complexity of some crucial computational tasks like Fourier transform and convultion from N2 to N log2, where N is the problem size. The development of the major algorithms (Cooley-Tukey and split-radix FFT, prime factor algorithm and Winograd fast Fourier transform) is reviewed. Then, an attempt is made to indicate the state of the art on the subject, showin the standing of researh, open problems and implementations. © 1990.
引用
收藏
页码：259 / 299
页数：41
相关论文
共 118 条
  • [1] Ahmed, Rao, Orthogonal Transforms for Digital Signal Processing, (1975)
  • [2] Blahut, Fast Algorithms for Digital Signal Processing, (1986)
  • [3] Brigham, The Fast Fourier Transform, (1974)
  • [4] Burrus, Parks, DFT / FFT and Convolution Algorithms, (1985)
  • [5] Burrus, Efficient Fourier transform and convolution algorithms, Advanced Topics in Digital Signal Processing, (1988)
  • [6] Selected Papers in Digital Signal Processing, II, (1975)
  • [7] Programs for digital Signal Processing, (1979)
  • [8] Heideman, Multiplicative Complexity, Convolution and the DFT, (1988)
  • [9] Kung, Whitehouse, Kailath, VLSI and Modern Signal Processing, (1985)
  • [10] McClellan, Rader, Number Theory in Digital Signal Processing, (1979)
12345678910