Butterfly Based FFT Architecture Using Open-Source EDA Tools
Samuvel, Shelcia Carolyn (2026)
2026
Master's Programme in Computing Sciences and Electrical Engineering
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
Hyväksymispäivämäärä
2026-05-22
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202605165698
https://urn.fi/URN:NBN:fi:tuni-202605165698
Tiivistelmä
"A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa" [26]. Essentially, it tells us what frequencies exist in a signal and how strong they are. It is used in audio processing, communications, image compression, and any system that needs fast frequency analysis. Software implemented FFT on a CPU is flexible but slow for real-time use cases, making the hardware implementations essential.
This thesis presents the complete designed, implemented, simulated, verified, and synthesized a fixed-point radix-2 iterative 256-point FFT hardware accelerator using only open-source EDA tools. The architecture is based on a single reusable butterfly unit driven by a finite state machine (FSM) controller, enabling area-efficient iterative computation across all eight stages of the radix-2 decimation-in-time (DIT) algorithm [27]. All arithmetic operations are performed in 16-bit signed Q1.15 fixed-point format with per-stage arithmetic right-shift scaling to prevent overflow.
The designed architecture is implemented in hardware description language called Verilog and simulated using Icarus Verilog. The hardware simulation completes successfully with the done flag asserted at 23,095 ns (2,310 clock cycles at 100 MHz), with the FSM correctly transitioning through IDLE, LOAD, COMPUTE, and DONE states. Functional verification confirms that the hardware correctly identifies the frequency content of the input signal, with peak energy detected at frequency bins 245 and 244 - adjacent to the expected bins 246 and 10 - consistent with the known 1 bin offset introduced by cumulative per-stage scaling in a block-scaled fixed-point FFT.
Fixed-Point Precision Analysis using the Q1.15 format produces a Signal-to-Noise Ratio (SNR) of 98.37 dB and a Mean Squared Error (MSE) of 1.63 * 10^-8. These values are in excellent agreement with the theoretical limit of 98.1 dB for 16-bit arithmetic. Logic synthesis using Yosys reports a total of 43,139 technology-independent logic cells, of which 9,750 cells represent the computational logic (butterfly, FSM, ROM, and glue); the remaining 33,389 cells arise from Yosys expanding the data RAM register array into discrete D flip-flops, an artefact that would not appear in an ASIC or FPGA flow using compiled SRAM. At 100 MHz, the design achieves a throughput of approximately 43,346 FFT frames per second.
The entire design flow of this architecture uses exclusively open-source tools. Icarus Verilog for RTL simulation, GTKWave for waveform analysis, and Yosys for logic synthesis which provides a fully reproducible, cost-free hardware development methodology.
This thesis presents the complete designed, implemented, simulated, verified, and synthesized a fixed-point radix-2 iterative 256-point FFT hardware accelerator using only open-source EDA tools. The architecture is based on a single reusable butterfly unit driven by a finite state machine (FSM) controller, enabling area-efficient iterative computation across all eight stages of the radix-2 decimation-in-time (DIT) algorithm [27]. All arithmetic operations are performed in 16-bit signed Q1.15 fixed-point format with per-stage arithmetic right-shift scaling to prevent overflow.
The designed architecture is implemented in hardware description language called Verilog and simulated using Icarus Verilog. The hardware simulation completes successfully with the done flag asserted at 23,095 ns (2,310 clock cycles at 100 MHz), with the FSM correctly transitioning through IDLE, LOAD, COMPUTE, and DONE states. Functional verification confirms that the hardware correctly identifies the frequency content of the input signal, with peak energy detected at frequency bins 245 and 244 - adjacent to the expected bins 246 and 10 - consistent with the known 1 bin offset introduced by cumulative per-stage scaling in a block-scaled fixed-point FFT.
Fixed-Point Precision Analysis using the Q1.15 format produces a Signal-to-Noise Ratio (SNR) of 98.37 dB and a Mean Squared Error (MSE) of 1.63 * 10^-8. These values are in excellent agreement with the theoretical limit of 98.1 dB for 16-bit arithmetic. Logic synthesis using Yosys reports a total of 43,139 technology-independent logic cells, of which 9,750 cells represent the computational logic (butterfly, FSM, ROM, and glue); the remaining 33,389 cells arise from Yosys expanding the data RAM register array into discrete D flip-flops, an artefact that would not appear in an ASIC or FPGA flow using compiled SRAM. At 100 MHz, the design achieves a throughput of approximately 43,346 FFT frames per second.
The entire design flow of this architecture uses exclusively open-source tools. Icarus Verilog for RTL simulation, GTKWave for waveform analysis, and Yosys for logic synthesis which provides a fully reproducible, cost-free hardware development methodology.