A Fast Algorithm for the Computation of Radix-4 Two-Dimensional Fourier Transform and its Parallel Impementation

摘要

In this study, we propose a fast algorithm for computing radix-4 two-dimensional Fourier transformthat is suitable for implementation on a parallel architecture. Our algorithm is derived in this paper from a Cooleydecimation-in-time algorithm by using an appropriate indexing process. It is proved that the number ofmultiplications necessary to compute our proposed algorithm is significantly reduced while the number ofadditions remains almost identical to that of Cooley 2D FFT`s. Comparison results show the good performanceof the proposed 2D FFT algorithm against the row-column FFT transform.