平行六边形区域上的快速离散傅立叶变换

1.引言快速傅立叶变换(FFT)是公认的二十世纪最重要的十个算法之一[1],它在信号处理、多媒体压缩、模式识别、计算化学等众多领域有着广泛的应用[2].考虑如下形式的离散傅立叶变换(DFT):这里叫ωN=e2π/Ni,N=2m.1965年提出的Cooley—Tukey算法[3]通过divide—and—conquer的策略将上式分成m步逐次计算,最后总的浮点运算次数由8N2次降为5Nlog2N-6N