Rn(2)=417(M-3)+2(N2=N、1+10 (3.3) 3、基2FFT算法的分类 在基2FFT程序中,若包含了所有旋转因子,则称该算法为一类蝶形单元运 算;若去掉W=土1的旋转因子,则称之为二类蝶形单元运算;若再去掉W=±j 的旋转因子,则称为三类蝶形单元运算若再处理=(1-)2,则称之为四 类蝶形运算。我们将后三种运算称为多类蝶形单元运算 显然,蝶形单元类型越多,编程就越复杂,但当N较大时,乘法运算的减少 量就越可观 4.32旋转因子的生成 在FFT运算中,旋转因子W=cos 丌n M)(),求正弦和余弦函数 值的计算量是很大的。所以编成时,产生旋转因子的方法直接影响运算速度。 种方法是在每级运算中直接产生;另一种方法是在FFT程序开始前预先计算出 WN,m=0,1, 1,存放在数组中,作为旋转因子表,在程序执行过程中直接 査表得到所需旋转因子值,不再计算。这样使运算速度大大提高,其不足之处是 占用内存较多。 4.3.3实序列的FFT算法 在实际工作中,数据一般都是序列。若直接按FFT运算流图计算,就是把x(n) 看成一个虚部为零的复序列进行计算。这就增加了存储量和运算时间。处理该问 题有三种方法 1、用一个N点FFT计算两个N点实序列的FFT,一个实序列作为x(m)的实 部,另一个作为虚部,计算完FT后,根据DFT的共轭对称性,由输出X(k)分 别得到两个实序列的N点DFT    13 2 4 3 2 2 2 10 2 2 2 M N N R M N M                           (3.3) 3、基 2FFT 算法的分类 在基 2FFT 程序中，若包含了所有旋转因子，则称该算法为一类蝶形单元运 算；若去掉 1 r WN  的旋转因子，则称之为二类蝶形单元运算；若再去掉 r W j N   的旋转因子，则称为三类蝶形单元运算；若再处理   2 1 2 r W j N   ，则称之为四 类蝶形运算。我们将后三种运算称为多类蝶形单元运算。 显然，蝶形单元类型越多，编程就越复杂，但当 N 较大时，乘法运算的减少 量就越可观。 4.3.2 旋转因子的生成 在 FFT 运算中，旋转因子 2 2 cos sin m N m m W j N N                 ，求正弦和余弦函数 值的计算量是很大的。所以编成时，产生旋转因子的方法直接影响运算速度。一 种方法是在每级运算中直接产生；另一种方法是在 FFT 程序开始前预先计算出 , 0,1, 1 2 m N N W m    ，存放在数组中，作为旋转因子表，在程序执行过程中直接 查表得到所需旋转因子值，不再计算。这样使运算速度大大提高，其不足之处是 占用内存较多。 4.3.3 实序列的 FFT 算法 在实际工作中，数据一般都是序列。若直接按 FFT 运算流图计算，就是把 x n  看成一个虚部为零的复序列进行计算。这就增加了存储量和运算时间。处理该问 题有三种方法： 1、用一个 N 点 FFT 计算两个 N 点实序列的 FFT，一个实序列作为 x n  的实 部，另一个作为虚部，计算完 FFT 后，根据 DFT 的共轭对称性，由输出 X k  分 别得到两个实序列的 N 点 DFT