搜索
..............x(0)x(4)x(6)x(1)x(5)x(3)x(7)..x(2)................X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(5)X(6)X(7)W0NW0NW0NW0NW0NW2NW0NW2NX(4)W0NW1NW2NW3NN＝8的FFT运算流图（从左往右共有log2N=3级蝶形运算）第一列第二列第三列原始信号序列该流图的基本运算单元为蝶形运算符号：....WkNAm-1(i)Am-1(j)Am(i)=Am-1(i)+Am-1(j)WkNAm(j)=Am-1(i)-Am-1(j)WkN说明：该蝶式计算结构的左面两路为输入，右上路为相加输出，右下路相减输出，如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头上，当支路上没有标出箭头及系数时，则该支路的传输比为1。式中，m表示第m列迭代，i,j为数据所在的行数。由FFT运算流图可见，每一级都由N/2个蝶形运算构成，N点FFT共有2logN级蝶形运算，FFT的每一级（列）计算都是由N个复数据经N/2个蝶形运算变成了另外N个复数据。任何两个节点i和j的节点变量进行蝶算后，其结果为下一列的i，j两点的节点变量，而和其他节点变量无关。因此，如果所有的kNW的值已预先置存，那末，除了运算的工作单元之外，只用N寄存器就够了。因为每个蝶算是由两个寄存器中取出数据，而计算结果仍存在此二寄存器中，该寄存单元中原存的内容，一经取用即可抹去，不影响以后的计算，每列的N/2个蝶算全做完以后再开始下一列的蝶算。这样，N个寄存器分别存储了每列N个不同行的节点变量。进行蝶形运算的两节点相距的距离及kNW的变化规律：以上述8点FFT为例，第一列蝶形运算只有一种类型:系数081W，参加运算的两个数据点间距为1。第二列有两种类型的蝶形运算：系数分别为0288,WW(就是W04，W14，倍乘后结果),参加蝶形运算的两个数据点的间距等于2。第三列有4种类型的蝶形运算：系数分别是01238888,,,参加蝶形运算的两个数据点的间距等于4。可见，每一列的蝶形类型比前一列增加一倍，参加蝶形运算的两个数据点的间距也增大一倍，最后一列系数用得最多，为4个，即01238888,,,而前一列只用到它偶序号的那一半，即0288,WW，第一列只有一个系数，即081W。上诉结论可以推广到N＝2v的一般情况，规律是第一列只有一种类型的蝶形运算，系数是0NW,以后每列的蝶形类型，比前一列增加一倍，到第2logvN是N/2个蝶形类型，系数是，共N/2个。由后向前每推进一列，则用上述系数中偶数序号的那一半，例如第1v列的系数则为024,,.NNN参加蝶形运算的两个数据点的间距，则是最末一级最大，其值为N/2,向前每推进一列，间距减少一半。符号说明：222cos()sin()jkkNNWekjkNN