第四章快速傅里叶变换 43进一步减少运算量的措施 43.1多类碟形单元运算 1、无关紧要的旋转因子 当L=1时,只有一个旋转因子W0=1 L=2时,有两个旋转因子WQ=1和W4=-j; 对于这两种情况,在DFT中称值为±1和±j的旋转因子为无关紧要的旋转因 子,蝶形运算可以不进行乘法运算。这样复数乘法运算次数由MN/2可以减少为 ●进一步,从L=3至L=M级蝶形运算中因为无关紧要的旋转因子存在,如: W,wN等,还可减少复数乘法次数为 (3.1) L=3 L=3 因此, DIT-FFT的复数乘法次数可以减少为 (2)=(M-2)--2|=(M-3)+2 2、蝶形运算中的特殊复数乘法 般实现一次复数乘法运算需要四次实数乘,两次实数加,但对某些特殊复 数,乘法运算的运算量可以降低。如对W=(-∥2,与任一复数相乘时, (1+/)(x+)=2[(x+y)-(x-y) 只需要两次复数加和两次复数乘即可。所以从实数运算考虑,计算N=2M点 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 所需实数乘法次数为