FPGA Architecture course · IIIT Bangalore

Radix-2 FFT
on FPGA.

A 128-point Cooley-Tukey FFT on a Basys3, built from DSP48 blocks only with recursive time-multiplexed resource sharing.

Verilog DSP48 Basys3 xc7a35t Vivado 2023 Q12.6 fixed-point Radix-2 DIT 64 / 90 DSPs 103.659 MHz
00 / constraint

The constraint.

every multiplication must go through a DSP48 block

The course assignment was to implement a 128-point 1D FFT on the Basys3 FPGA board. One constraint shaped everything else: every multiplication had to be performed using Xilinx DSP48 IP blocks — not LUT-based multipliers. This is actually the correct way to do it. DSP48 slices are faster, more power-efficient, and have better timing characteristics than equivalent LUT multiplications. The constraint taught the right habit.

The problem: Basys3 carries an Artix-7 xc7a35t with exactly 90 DSP48 slices. A 128-point Radix-2 FFT requires N/2 × log₂(N) = 64 × 7 = 448 complex multiplications per transform. With the DSP48 constraint and a naive fully-parallel implementation, that means 448 DSP instantiations. The board has 90. The obvious implementation doesn't fit.

01 / approach 1

Fully parallel.

all butterfly stages instantiated simultaneously — doesn’t survive synthesis

The natural Radix-2 DIT implementation is fully recursive: 128-point → two 64-point → two 32-point → … → 2-point butterfly stages. In Verilog, "decompose" means instantiate — each level of the recursion creates two copies of the next level, all in parallel. Every butterfly at every stage gets its own DSP48 hardware, all sitting in silicon simultaneously.

approach 1 — synthesis failure
Fully parallel recursive instantiation exceeded the Basys3's 90-DSP limit. Vivado reported over 100% DSP utilization and could not place the design on the target device. The design compiles but cannot be implemented.
90 limit approach 1 — 90+ DSPs (over limit) A1 approach 2 — 64 DSPs (71%) A2
DSP48 utilization — approach 1 exceeds the 90-block limit, approach 2 fits at 71%
02 / approach 2

Time-multiplexing.

one hardware block, reused at every stage

The insight behind approach 1's failure: in a sequential FFT computation, not all stages are active simultaneously. When computing the even-index half-transform, the odd-index hardware sits completely idle — and vice versa. The fully-parallel instantiation was building hardware for computations that never overlap in time.

The solution: build the hardware once, run it multiple times. A fully parallel 8-point FFT fits in 48 DSP48 slices — the largest block that fits comfortably within budget accounting for the combining butterfly operations needed at higher stages. Every level above 8-point time-multiplexes this hardware: run it on the even-indexed inputs, wait, run it on the odd-indexed inputs, wait, then do the combining butterfly operations sequentially.

The recursion applies at every level. A 128-point FFT reuses one 64-point block twice. The 64-point block reuses one 32-point block twice. And so on down to the 8-point base, which is the only level with real parallel hardware underneath.

DSP count — the math
8-point FFT (fully parallel): 48 DSPs — base, always active
16-point adds 1 butterfly: +4 DSPs
32-point adds 1 butterfly: +4 DSPs
64-point adds 1 butterfly: +4 DSPs
128-point adds 1 butterfly: +4 DSPs
────────────────────────────────
Total: 64 DSPs (71% of 90) — fits with 26 to spare
03 / architecture

Architecture.

five levels of recursion, hardware shared across all of them

The hierarchy is bottom-up. The 2, 4, and 8-point FFTs are fully instantiated parallel hardware. Every level from 16-point upward is a sequential state machine that runs the level below it twice and combines the results.

128-pt · time-multiplexed run 64-pt(even) → wait for done → run 64-pt(odd) → wait → 64 sequential butterflies 64-pt · time-multiplexed run 32-pt(even) → wait for done → run 32-pt(odd) → wait → 32 sequential butterflies 32-pt · time-multiplexed run 16-pt(even) → wait for done → run 16-pt(odd) → wait → 16 sequential butterflies 16-pt · time-multiplexed run 8-pt(even) → wait for done → run 8-pt(odd) → wait → 8 sequential butterflies hardware boundary 8-pt FFT · fully parallel hardware · 48 DSP48 2-pt × 2 (even/odd, instantiated) → 4-pt × 2 (even/odd) → 4 butterfly ops 2-pt and 4-pt FFTs · fully parallel · base of recursion time-multiplexed (FSM, sequential) instantiated hardware (parallel)
recursive decomposition — only the 2/4/8-point levels are real parallel hardware. all higher levels are sequential state machines reusing the level below.

Each time-multiplexed level uses an FSM to orchestrate the two half-transform runs. The state machine loads even-indexed inputs, asserts start to the sub-module, waits for its done signal, captures outputs into registers, reloads with odd-indexed inputs, runs again, then sequences through the combining butterfly operations one per clock cycle using a counter.

Twiddle factors (complex roots of unity) are precomputed and stored as hardcoded assign statements — effectively a ROM with no runtime computation. Q12.6 fixed-point arithmetic: 18-bit total to match the DSP48 input width, 6 fractional bits, 12 integer bits. Inputs are scaled by 64 before entry and outputs scaled back down after.

04 / results

Results.

64 DSP48 used (of 90)
103.7 MHz max frequency
2566 cycles per transform
Q12.6 fixed-point precision
metricvaluenote
DSP48 utilization64 / 9071% — 26 slices to spare
clock period (target)10ns100 MHz
worst negative slack0.353nstiming closed comfortably
max achievable frequency103.659 MHzfrom WNS + period
latency per 128-pt FFT2566 cycles25.66µs @ 100MHz
precisionQ12.6 (18-bit)6 fractional bits
output accuracy — Q12.6 vs Python float64

Both behavioral simulation and ILA capture from the physical Basys3 board were compared against Python's numpy.fft.fft(). The outputs match with a ~1–3% relative error — expected, not a bug. Float64 has 52 mantissa bits; Q12.6 has 6 fractional bits. The quantization error is understood and bounded.

The comparison also confirmed that the time-multiplexing FSM produces the correct Cooley-Tukey output order — a non-trivial check given that the even/odd split and sequential combining stages had to preserve the bit-reversal permutation correctly.

05 / post-submission

Post-submission.

a DSP48 parameter we hadn’t looked at during the course

After submission, looking at the Vivado timing reports revealed something we hadn't touched during development: DSP48 blocks have configurable internal pipeline registers — AREG, BREG, and PREG in the IP configuration. By default these are enabled. Each active pipeline register adds a stage of latency to every DSP48 operation but allows higher clock frequencies by breaking long combinational paths.

Since butterfly operations run sequentially — one per clock, waiting for the DSP result before starting the next — those extra pipeline cycles accumulate across hundreds of operations. Disabling the output pipeline register (PREG=0) dropped the latency from 2566 to 561 cycles. Same architecture, same Verilog, one IP configuration change.

DSP pipeline registers ON
2566 cycles
25.66µs @ 100MHz · submitted version
DSP pipeline registers OFF
561 cycles
5.61µs @ 100MHz · 4.6× improvement
the tradeoff
Pipeline registers in DSP48 exist to help timing closure — they let the synthesizer meet frequency targets by breaking long combinational paths through the multiply-accumulate chain. With them off, the critical path through the DSP is longer, and you may not close timing at high frequencies on a larger design. In this case, the critical path was elsewhere (WNS was 0.353ns with registers on), so there was margin to spare.

The lesson: DSP48 pipeline configuration is a real latency/frequency tradeoff knob, not a fixed property of the architecture. Know your IP settings before assuming the synthesis tool made the right call.

Repository: github.com/avnlk/radix2-fft-using-dsp48-on-fpga ↗

next writeupReverse engineering an ASIC →from GDS polygons to a Star Battle puzzle