An FPT algorithm with a modularized structure for computing two-dimensional discrete Fourier transforms

摘要

The fast polynomial transform (FPT) for computing two-dimensional discrete Fourier transforms is modularized into identical modules. In this new method, only FPTs and fast Fourier transforms of the same length are required. As a consequence, the architecture is more regular and naturally suitable for multiprocessor and VLSI implementations. The modularized FPT algorithms can simplify the problems of control, memory management, load balancing, etc., although more arithmetic operations are needed than with the original ones.