第四章快速傅里叶变换 43进一步减少运算量的措施 43.1多类碟形单元运算 1、无关紧要的旋转因子 当L=1时,只有一个旋转因子W=1; ·L=2时,有两个旋转因子W=1和W=-j 对于这两种情况,在DFT中称值为±和±的旋转因子为无关紧要的旋转因 子,蝶形运算可以不进行乘法运算。这样复数乘法运算次数由MN2可以减少为 N 2 进一步,从L=3至L=M级蝶形运算中因为无关紧要的旋转因子存在,如: W0,W等,还可减少复数乘法次数为 2 因此, DIT-FFT的复数乘法次数可以减少为 CM M-2 (M-3)+2 (32) 2、蝶形运算中的特殊复数乘法 般实现一次复数乘法运算需要四次实数乘,两次实数加,但对某些特殊复 数,乘法运算的运算量可以降低。如对形=(1-j)2,与任一复数相乘时, 2(+)(x+m)=2(x+y(x-y) 只需要两次复数加和两次复数乘即可。所以从实数运算考虑,计算N=2“点 DIT-FFT所需实数乘法次数为第四章 快速傅里叶变换 4.3 进一步减少运算量的措施 4.3.1 多类碟形单元运算 1、无关紧要的旋转因子  当 L=1 时，只有一个旋转因子 0 1 WN  ；  L=2 时，有两个旋转因子 0 1 WN  和 4 N W j N   ； 对于这两种情况，在 DFT 中称值为 1 和  j 的旋转因子为无关紧要的旋转因 子，蝶形运算可以不进行乘法运算。这样复数乘法运算次数由 MN/2 可以减少为 2 2    2 M N C M    进一步，从 L=3 至 L=M 级蝶形运算中因为无关紧要的旋转因子存在，如： 0 WN ， N 4 WN 等，还可减少复数乘法次数为 1 3 3 1 2 2 2 2 2 M M L L L L N N  N              (3.1) 因此，DIT-FFT 的复数乘法次数可以减少为 2 2 2 3 2      2 2 2 M N N N C M M              (3.2) 2、蝶形运算中的特殊复数乘法 一般实现一次复数乘法运算需要四次实数乘，两次实数加，但对某些特殊复 数，乘法运算的运算量可以降低。如对   8 2 1 2 N W j N   ，与任一复数相乘时，        2 2 1 2 2       j x jy x y x y     只需要两次复数加和两次复数乘即可。所以从实数运算考虑，计算 2 M N  点 DIT-FFT 所需实数乘法次数为