1.Developing of FFT
Finite sequence of discrete Fourier transform by (DFT) will be separated into its frequency domain are finite sequences. But its calculation is too big, difficult to deal with the problem in real time, it leads to a fast Fourier transform (FFT). In 1965, Cooley and Tukey proposed calculation of discrete Fourier transform (DFT) of the fast algorithm, the DFT computation to reduce the number of orders of magnitude. Since then, the fast Fourier transform (FFT) algorithm will continue in-depth, digital signal processing with this emerging disciplines, with the FFT and the emergence and development of rapid development. Based on the sequence of decomposition and the different selection methods produced a variety of FFT algorithms, the basic algorithm is based 2DIT and base 2DIF. FFT in the Fourier inverse transform, linear convolution and linear correlation also has important applications.
1．FFT的發(fā)展
有限長(zhǎng)序列可以通過(guò)離散傅立葉變換(DFT)將其頻域也離散化成有限長(zhǎng)序列.但其計(jì)算量太大,很難實(shí)時(shí)地處理問(wèn)題,因此引出了快速算法傅立葉變換(FFT). 1965年，Cooley和Tukey提出了計(jì)算離散傅立葉變換（DFT）的快速算法，將DFT的運(yùn)算量減少了幾個(gè)數(shù)量級(jí)。從此，對(duì)快速傅立葉變換（FFT）算法的研究便不斷深入，數(shù)字信號(hào)處理這門(mén)新興學(xué)科也隨FFT的出現(xiàn)和發(fā)展而迅速發(fā)展。根據(jù)對(duì)序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法，基本算法是基２DIT和基２DIF。FFT在離散傅立葉反變換、線性卷積和線性相關(guān)等方面也有重要應(yīng)用。