快速傅立葉變換

.DFT的計算工作量
?兩者的差別僅在指數(shù)的符號和因子1/N. 通常x(n)和?都是復(fù)數(shù),所以計算一個
? X(k)的值需要N次復(fù)數(shù)乘法運(yùn)算,和??? 次
? 復(fù)數(shù)加法運(yùn)算.那么,所有的X(k)就要N2次復(fù)
? 數(shù)乘法運(yùn)算,N(N-1)次復(fù)數(shù)加法運(yùn)算.當(dāng)N很
? 大時,運(yùn)算量將是驚人的,如N=1024,則要完
? 成1048576 次(一百多萬次)運(yùn)算.這樣,難以做到實(shí)時處理.
二.改進(jìn)的途徑
? 1.?? 的對稱性和周期性

???? 利用上述特性,可以將有些項合并,并
將DFT分解為短序列,從而降低運(yùn)算次數(shù),提
高運(yùn)算速度.1965年,庫利(cooley)和圖基
(Tukey)首先提出FFT算法.對于N點(diǎn)DFT,僅需
(N/2)log2N 次復(fù)數(shù)乘法運(yùn)算.例如N=1024=210 時，
需要(1024/2)log2 210 =512*10=5120次。
5120/1048576=4.88% ,速度提高20倍
?按時間抽取(DIT)的FFT算法?????? —庫利-圖基算法
一.算法原理(基2FFT)
(一)N/2點(diǎn)DFT
1.先將??? 按n的奇偶分為兩組作DFT,設(shè)N=2L ,不足時,可補(bǔ)些零。這樣有:
? n為偶數(shù)時:
? n為奇數(shù)時:由于:?
?所以,上式可表示為:
?其中,
2.兩點(diǎn)結(jié)論:
?(1) X (k),X (k)均為N/2點(diǎn)的DFT。
?(2) X(k)=X (k)+W? X (k)只能確定出
?? X(k)的k=?????????? 個；
即前一半的結(jié)果。
3.X(k)的后一半的確定
?同理,
?這就是說,X1(k),X2(k)的后一半,分別
?等于其前一半的值。

????????? 可見,X(k)的后一半，也完全由X1(k), X2 (k)的前一半所確定。
???? *N點(diǎn)的DFT可由兩個N/2點(diǎn)的DFT來計算。

實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算

(1)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):
?????復(fù)加次數(shù):
(2)兩個N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):
?????復(fù)加次數(shù):
(3)N/2個蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù):
?????復(fù)加次數(shù):

??? 例如 N=8 時的DFT,可以分解為兩個
? N/2=4點(diǎn)的DFT.具體方法如下:
?? (1)n為偶數(shù)時,即
? 分別記作: