-
蝶形運算
鎖定
蝶形運算,J.W.庫利和T.W.圖基提出的運算。
- 中文名
- 蝶形運算
- 外文名
- 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,向前每推進一列,間距減少一半。
[1]
蝶形運算公式
Wnk =e^-j (2π/n) *k =cos(2π/n * k)-j*sin(2π/n * k)
- 參考資料
-
- 1. 蝶形運算 .中國知網[引用日期2016-10-19]