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

A New Improved Computation of Two Dimensional Discrete Fourier Transforms (DFT) Using Fast Ploynomial Transform (FPT) Algorithm

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

This paper deals with the computation of two dimensional Discrete Fourier Transforms (N×N, N=2~t) by means of Fast Ploynomical Transform algorithm. First, a discussion is given to the methods for realizing the computation of the two dimensional DFT and a method of FPT is raised, thit is, FFT is used to compute odd DFT of FPT. This method is principly useful for a procesor with mulitiplication hardware.On the basis of the above, an improved method is suggisted after a comprehensive consideration of mulitiplication and plus capcites. This new improved method turns one DFT of Npoints into two DFT of N/2 points by takeing out points, The method can decrease capacities by 5% or so than the former FPT, while the mulitiplication is remained. This FPT algorithm decreases about 50% of mulitiplication and 15% of plus than usually row-arranging algorithm.