離散傅立葉變換（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）