快速多项式变换(FPT)算法计算二维离散傅里叶变换(DFT)的一种新的改进方法

本文研究了利用快速多项式变换（FPT）来计算大小为N×N（N=2~t）的二维离散傅里叶变换。本文首先对多项式变换计算二维DFT的实现方案进行了讨论,提出了更利于具有专门乘法硬件处理器计算的FPf实现方案——用FFT法汁算FPT中奇DFT的算法。并在此基础上,通过对乘法和加法的综合考虑,对这种实现方案提出了一种改进方法。这种改进方法通过抽点,将一次N点奇DFT,分解为2次2点DFT,在乘法量基本保持不变下,加法量比原FPT减少5%左右。这种算法比常规的行——列法在乘法上减少约50%,在加法上减少约15%。