N點有限長序列的離散傅立葉變換

N點有限長序列的離散傅立葉變換，是一種快速算法，能克服時間域與頻率域之間相互轉換的計算障礙，在光譜、大氣波譜分析、數位訊號處理等方面有廣泛套用。

基本介紹

• 中文名：N點有限長序列的離散傅立葉變換
• 類型：快速算法
• 優點：克服時間域與頻率域之間計算障礙
• 套用：光譜、大氣波譜分析等

概述

N點有限長序列的離散傅立葉變換：時域N點序列χ(n)的離散傅立葉變換(DFT)以X(k)表示，定義為

,λ為整數）時,算法的指導思想是將一個N 點序列的DFT分成兩個N/2點序列的DFT,再分成四個N/4點序列的DFT,如此下去,直到變成N/2個兩點序列的DFT。這種快速算法的計算工作量與DFT的直接計算的計算工作量之比約為log2N/(2N),以N=1024為例FFT的計算工作量僅約為DFT直接計算的1/200。