Implementation of a 2-D fast Fourier transform on an FPGA-based computing platform

Abstract

The two dimensional fast Fourier transform (FFT) is a useful operation in many digital signal processing applications, but it is often avoided due to its large computational requirements. This thesis presents the implementation and performance figures for the fast Fourier transform on an FPGA-based custom computer. The computation of a 2-D FFT requires O(N²log₂N ) complex floating point arithmetic operations for an NxN image. By implementing the FFT algorithm on a custom computing machine (CCM) called Splash-2, a computation speed of at least 180 Mflops and a speed-up of 23 times over a SPARC-10 workstation is achieved.