蝶形運算

蝶形運算

蝶形運算,2點DFT運算稱為蝶形運算,而整個FFT就是由若干級疊代的蝶形運算組成,而且這種算法採用原位運算,故只需N個存儲單元2. ∑∑(2)式(2)是FFT基4頻域抽取算法的基本運算單元,一般稱為蝶形運算.

基本介紹

  • 中文名:蝶形運算
  • 外文名: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)

相關詞條

熱門詞條

聯絡我們