快速付立叶变换(FFT)库利-图基算法的改进

在库利—图基的FFT算法中,每个对偶点的计算都必须用到因子(?),(?)常,(?)是通过比特倒置求得的,但使用倒置的方法求ω~p的p值比较繁琐,本文提出一(?)新的方法,无须倒置,只利用一个递推公式就直接求出ω~p的p值,从而使FFT的运算时间大大减少,在1024个点的FFT运算中,运算时间为原来的1/5,在4096个点的FFT运算中,运算时间为原来的1/10。