快速傅立葉變換
快速計算序列的離散傅立葉變換或其逆變換的方法 / 維基百科,自由的 encyclopedia
快速傅立葉變換(英語:Fast Fourier Transform, FFT),是快速計算序列的離散傅立葉變換(DFT)或其反轉換的方法[1]。傅立葉分析將訊號從原始域(通常是時間或空間)轉換到頻域的表示或者逆過來轉換。FFT會通過把DFT矩陣分解為稀疏(大多為零)因子之積來快速計算此類變換。[2] 因此,它能夠將計算DFT的複雜度從只用DFT定義計算需要的 ,降低到 ,其中 為數據大小。
快速傅立葉變換廣泛的應用於工程、科學和數學領域。這裏的基本思想在1965年才得到普及,但早在1805年就已推導出來。[3] 1994年美國數學家吉爾伯特·斯特朗把FFT描述為「我們一生中最重要的數值演算法」[4],它還被IEEE科學與工程計算期刊列入20世紀十大演算法。[5]