A new proposed algorithm of arbitrary radix for the computation of the 2D DFT

In this paper, we propose a new approach for computing 2D FFTʹs that are suitable for implementation on a systolic array architecture. Our algorithm is derived in this paper from a Cooley decimation-in-time algorithm by using an appropriate indexing process. It is proved that the number of multiplications necessary to compute our proposed algorithm is signi"cantly reduced while the number of additions remains almost identical to that of conventional 2D FFTʹs. Comparison results show the good performance of the proposed 2D FFT algorithm against the row-column FFT transform