离散傅立叶变换（Discrete Fourier Transform，DFT）及其快速实现，即快速傅立叶变换（FastFourier Transform，FFT），在数字信号处理中扮演着重要的角色。
目前已经以多种形式发明（和再发明）了多种DFT和FFT算法。正如Heideman等人[100]所指出的，我们知道高斯就用过一种我们今天称之为Cooley－Tukey FFT的FFT类型算法。在本章中，将简要地讨论图中总结的重要的算法。
图 DFT和FFT算法的分类
在此要沿用Burrus[111]提出的术语学体系，Burrus简单地根据FFT算法的输入输出序列之间的（多维）索引映射关系对之进行了分类。所以我们将所有（没有使用多维索引映射的）算法都称为DFT算法，尽管其中一些算法具有非常简单的计算量，如Winograd DFT算法。DFT和FFT算法不是“孤立”的：大多数算法的有效实现通常都是DFT和FFT算法组合的结果。例如：Rader质数算法和Good－Thomas FFT的组合就产生了的VLSI实现。该文献提供了许多FFT设计的示例。我们发现，用PDSP和ASIC的FFT实现[112，113，114，115，116，117]已经发展到可以用FPGA实现一维[118，119，120，]和二维[43，121]变换了。
欢迎转载，信息来源维库电子市场网（www.dzsc.com）
免责声明: 凡注明来源本网的所有作品，均为本网合法拥有版权或有权使用的作品，欢迎转载，注明出处。非本网作品均来自互联网，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。
