基本介紹
- 中文名：蝶形運算
- 外文名：butterfly computation /fastFourier transform
- 別稱：快速傅立葉變換（FFT）
- 提出者：J.W.庫利和T.W.圖基
- 提出時間：1965年
- 套用學科：計算算法、信號頻譜計算、系統分析等
- 適用領域範圍：有限長序列
- 運算：2點DFT
- 公式：Wnk =e^-j (2Π/n) *k
- 原則：原位運算
- 特點：快速變換
基本介紹,公式,
基本介紹
1. 2點DFT運算稱為蝶形運算,而整個FFT就是由若干級疊代的蝶形運算組成,而且這種算法採用原位運算,故只需N個存儲單元2. ∑∑(2)式(2)是FFT基4頻域抽取算法的基本運算單元,一般稱為蝶形運算.下一步再將X(4m+i),i=0,1,2,3分解成4個N42序列,疊代r次後完成計算,整個算法的複雜度減少為O(Nlog4N)
第一列蝶形運算只有一種類型:係數，參加運算的兩個數據點間距為1。第二列有兩種類型的蝶形運算：係數分別為 ,參加蝶形運算的兩個數據點的間距等於2。第三列有4種類型的蝶形運算：係數分別是 ,參加蝶形運算的兩個數據點的間距等於4。可見，每一列的蝶形類型比前一列增加一倍，參加蝶形運算的兩個數據點的間距也增大一倍，最後一列係數用得最多，為4個，即 ,而前一列只用到它偶序號的那一半，即，第一列只有一個係數，即。
抗訴結論可以推廣到N=的一般情況，規律是第一列只有一種類型的蝶形運算，係數是 ,以後每列的蝶形類型，比前一列增加一倍，到第是N/2個蝶形類型，係數是，共N/2個。由後向前每推進一列，則用上述係數中偶數序號的那一半，例如第列的係數則為參加蝶形運算的兩個數據點的間距，則是最末一級最大，其值為N/2,向前每推進一列，間距減少一半。
公式
Wnk =e^-j (2Π/n) *k =cos(-(2Π/n)* k)-j*sin((2Π/n)* k)
