The term *fast Fourier transform* (FFT) refers to an efficient
implementation of the discrete Fourier transform (DFT) for highly
composite^{A.1} transform
lengths
. When computing the DFT as a set of
inner products of
length
each, the computational complexity is
. When
is an integer power of 2, a Cooley-Tukey FFT algorithm delivers
complexity
, where
denotes the log-base-2 of
, and
means ``on the order of
''.
Such FFT algorithms were evidently first used by Gauss in 1805
[31] and rediscovered in the 1960s by Cooley and Tukey
[17].

In this appendix, a brief introduction is given for various FFT algorithms. A tutorial review (1990) is given in [23]. Additionally, there are some excellent FFT ``home pages'':

Pointers to FFT software are given in §A.7.

- Mixed-Radix Cooley-Tukey FFT

- Prime Factor Algorithm (PFA)
- Rader's FFT Algorithm for Prime Lengths
- Bluestein's FFT Algorithm
- Fast Transforms in Audio DSP
- Related Transforms

- FFT Software

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

当前网页内容, 由 大妈 ZoomQuiet 使用工具: ScrapBook :: Firefox Extension 人工从互联网中收集并分享;

内容版权归原作者所有;

本人对内容的有效性/合法性不承担任何强制性责任.

若有不妥, 欢迎评注提醒:

或是邮件反馈可也:

askdama[AT]googlegroups.com

点击注册~> 获得

订阅 substack 体验古早写作:

关注公众号, 持续获得相关各种嗯哼:

关于 ~ DebugUself with DAMA ;-)

粤ICP备18025058号-1

公安备案号: 44049002000656 ...::