![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Time_Signal_of_Five_Term_Cosine_Series.png/640px-Time_Signal_of_Five_Term_Cosine_Series.png&w=640&q=50)
快速傅里叶变换
快速計算序列的離散傅立葉變換或其逆變換的方法 / 维基百科,自由的 encyclopedia
快速傅里叶变换(英语:Fast Fourier Transform, FFT),是快速计算序列的离散傅里叶变换(DFT)或其逆变换的方法[1]。傅里叶分析将信号从原始域(通常是时间或空间)转换到频域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏(大多为零)因子之积来快速计算此类变换。[2] 因此,它能够将计算DFT的复杂度从只用DFT定义计算需要的 ,降低到
,其中
为数据大小。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Time_Signal_of_Five_Term_Cosine_Series.png/640px-Time_Signal_of_Five_Term_Cosine_Series.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/DFTs_of_Five_Term_Cosine_Series.png/640px-DFTs_of_Five_Term_Cosine_Series.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/Zoomed_DFTs_of_Five_Term_Cosine_Series.png/640px-Zoomed_DFTs_of_Five_Term_Cosine_Series.png)
快速傅里叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及,但早在1805年就已推导出来。[3] 1994年美国数学家吉尔伯特·斯特朗把FFT描述为“我们一生中最重要的数值算法”[4],它还被IEEE科学与工程计算期刊列入20世纪十大算法。[5]