Fast Fourier Transform from Scratch (opens in new tab)

FPGA Horizons London- October 6th and 7th 2026 - get Tickets here.The $99 Artix UltraScale+ Explorer Board - learn more hereA few weeks ago we looked at implementing a DFT from scratch as part of the labs for the DSP for FPGA course I am developing. The DFT worked nicely; however, we finished by noting that it does not scale well.For a DFT of size N, we need N² complex multiplications, which means a 1024-point DFT requires over a million of them.This is where the Fast Fourier Transform (FFT) com