蝶形运算，2点DFT运算称为蝶形运算,而整个FFT就是由若干级迭代的蝶形运算组成,而且这种算法采用原位运算,故只需N个存储单元2. ∑∑(2)式(2)是FFT基4频域抽取算法的基本运算单元,一般称为蝶形运算.。

　　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,向前每推进一列，间距减少一半。