当采用M次FFT时，由N=2^M求得M=logN，运算流图有M级蝶形，每一级都由N/2个蝶形运算构成，这样每一级蝶形运算都需要N/2次复数乘法和N次复数加法。M级运算共需要复数乘法次数为C=N/2*M,复数加法次数为C=N*M。
当N值较大时，FFT减少运算量的特点表现的越明显。 3.4.1 FT的运算规律 3.4.1.1 原位运算
1、N=2^M的FFT共M级运算，每级有N/2蝶形原位计算，当数据输入到存储器以后，每一组蝶形运算后，结果仍然存放在这同一组存储器的同一位置，不需要另辟存储空间，直接最后输出。
2、同一级的蝶形运算每个蝶形运算的输入数据对其他级输入没有影响。 3.4.1.2 倒序运算的规律
输入序列先按自然顺序存入存储单元,然后经变址运算来实现倒位序排列,用J表示倒序的十进制数，对N=2^M，M位的二进制数从左到右各位数权值位N/2，N/4，N/8……2，1。因此，最高位加1相当于J+N/2。
1、如果最高位为0，则直接得到下一个倒序值，J+N/2； 2、最高位为1，则最高位为0(J-N/2)，次高位加1(J+N/4)。 3、类推，直到最后一位二进制数字。 例如 ，N=8时如下图5所示：
表1 码位倒序（N=8）
第 10 页 共 23页