离散傅立叶变换（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）