快速付里葉變換:一、快速付里葉變換FFT
有 限 長 序 列? 通 過 離 散 傅 里 葉 變 換 (D F T) 將 其 頻 域? 離 散 化 成 有 限 長 序 列 . 但 其 計算 量 太 大, 很 難 實 時 地 處 理 問 題?? , 因 此 引 出 了 快 速? 傅 里 葉 變 換(FFT) .
?FFT 并 不 是 一 種 新 的 變 換 形 式 ,它 只 是 DFT 的 一 種 快 速 算 法 . 并 且 根 據 對 序 列 分 解 與 選 取 方 法 的 不 同 而 產 生 了 FFT 的 多 種 算 法 .
?FFT在離散傅里葉反變換?? 、 線 性 卷 積 和 線 性 相 關 等 方 面 也 有 重 要 應 用.。
二、FFT產生故事
????? 當時加文(Garwin)在自已的研究中極需要一個計算付里葉變換的快速方法。他注意到圖基(J.W.Turkey)正在寫有關付里葉變換的文章，因此詳細詢問了圖基關于計算付里葉變換的技術知識。圖基概括地對加文介紹了一種方法，它實質上就是后來的著名的庫利(Cooley J.W)圖基算法。在加文的迫切要求下，庫利很快設計出一個計算機程序。1965年庫利--圖基在<計算數學>、Mathematic of Computation 雜志上發表了著名的“機器計算付里級數的一種算法”文章，提出一種快速計算DFT的方法和計算機程序--揭開了FFT發展史上的第一頁，促使FFT算法產生原因還有1967年至1968年間FFT的數字硬件制成，電子數字計算機的條件， 使DFT的運算大簡化了。
三、本章主要內容
1.直接計算DFT算法存在的問題及改進途徑。
2.多種DFT算法(時間抽取算法DIT算法，頻率抽取算法DIF算法，線性調頻Z變換即CZT法)
3.FFT的應用