離散傅立葉變換（discrete fourier transform，dft）及其快速實現(xiàn)，即快速傅立葉變換（fastfourier transform，fft），在數(shù)字信號處理中扮演著重要的角色。

　　目前已經(jīng)以多種形式發(fā)明（和再發(fā)明）了多種dft和fft算法。正如heideman等人^[100]所指出的，我們知道高斯就用過一種我們今天稱之為cooley－tukey fft的fft類型算法。在本章中，將簡要地討論圖中總結(jié)的最重要的算法。

　　圖 dft和fft算法的分類

　　在此要沿用burrus[111]提出的術(shù)語學體系，burrus簡單地根據(jù)fft算法的輸入輸出序列之間的（多維）索引映射關(guān)系對之進行了分類。所以我們將所有（沒有使用多維索引映射的）算法都稱為dft算法，盡管其中一些算法具有非常簡單的計算量，如winograd dft算法。dft和fft算法不是“孤立”的：大多數(shù)算法的有效實現(xiàn)通常都是dft和fft算法組合的結(jié)果。例如：rader質(zhì)數(shù)算法和good－thomas fft的組合就產(chǎn)生了著名的vlsi實現(xiàn)。該文獻提供了許多fft設(shè)計的示例。我們發(fā)現(xiàn)，用pdsp和asic的fft實現(xiàn)^{[112，113，114，115，116，117]}已經(jīng)發(fā)展到可以用fpga實現(xiàn)一維^{[118，119，120，]}和二維^{[43，121]}變換了。

　　歡迎轉(zhuǎn)載，信息來源維庫電子市場網(wǎng)（www.dzsc.com）