蝶形運算

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)