top of page
Adiuvo Engineering & Training logo
MicroZed Chronicles icon

MicroZed Chronicles: Fast Fourier Transform From Scratch

  • Jun 17
  • 6 min read

FPGA Horizons London- October 6th and 7th 2026 - get Tickets here.

The $99 Artix UltraScale+ Explorer Board - learn more here


A 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) comes in. This week we are going to implement an FFT from scratch.


As before, we will keep the size at eight points so the logic remains easy to follow and we can compare the results directly against the DFT example.


First, there is a critical point to make: the FFT is not a different transform. It produces exactly the same result as the DFT.


The FFT, however, exploits the symmetry and periodicity of the twiddle factors to remove redundant calculations. The key observation, popularised by Cooley and Tukey in 1965, is that a DFT of size N can be split into two DFTs of size N/2, one operating on the even samples and one on the odd samples. The two half-size results are then combined using a single set of twiddle-factor multiplications.


Of course, each of those N/2 DFTs can be split again, and we keep splitting until we are left with DFTs of size two, which require no multiplication at all. For our eight-point example, this gives three stages, since eight is two to the power of three.


This recursive splitting is what reduces the complexity from N² down to N log₂ N. For our eight-point example, that is 12 butterfly operations rather than 64 complex multiplications. At 1024 points, it is the difference between over a million complex multiplications and just over five thousand.


The Butterfly


At the heart of the FFT is the butterfly, so called because of the shape it forms when drawn on a signal-flow graph.


The butterfly takes two complex inputs, a and b, multiplies b by a twiddle factor W, and produces two outputs:

a' = a + W × b
b' = a − W × b

One complex multiplication, one addition, and one subtraction produce two outputs from two inputs.


Notice that the multiplication result, W × b, is used twice. This is where the saving over the DFT comes from.


The DFT calculates this product separately for every bin, whereas the FFT calculates it once and reuses it.


For an eight-point FFT we have three stages of four butterflies. In the first stage, the butterflies pair samples which are next to each other in memory. In the second stage, the pairs are separated by two locations, and in the final stage by four.


The twiddle factors also change as we progress. The first stage only uses W₀, which is simply one, while the final stage uses W₀ through W₃.


The twiddle factors themselves are the same points on the unit circle that we calculated for the DFT, spaced at 45-degree intervals and encoded in Q10 format. We only need four of them rather than eight because the butterfly subtraction provides the 180-degree rotation for free.


Bit Reversal

There is one additional consideration. The decimation-in-time algorithm repeatedly splits the samples into even and odd groups. As a result, the samples must be loaded into the working memory in bit-reversed address order.


For an eight-point FFT this means sample one is stored at location four, sample three at location six, and so on, while samples zero, two, five, and seven remain where they are. You can see this by writing the three-bit address backwards. Sample one is 001; reversing it gives 100, which is location four.


The nice thing for FPGA engineers is that bit reversal costs essentially nothing in logic. It is simply a rewiring of the address bits when the samples are written into memory.

Implementation


The RTL follows the same structure as the DFT example. Eight samples are loaded one per clock cycle, the FFT then performs one butterfly per clock cycle for a total of 12 compute cycles, and finally the eight bins are output one per clock along with a bin identifier.


Processing one butterfly per clock keeps the design compact. A single complex multiplier is time-shared across all 12 butterflies, which means four real multipliers in the FPGA.


We could, of course, unroll the stages and pipeline the design for higher throughput. That is exactly what the FFT IP cores do. However, for understanding the algorithm, the time-multiplexed approach is much clearer.


Internally, the working registers are 18 bits wide compared to the 16-bit input. Each butterfly stage can increase the data width by up to one bit, so three stages require two to three bits of headroom depending on the input scaling strategy.


Larger FFTs require a more deliberate approach, either allowing the word width to grow at each stage or scaling the data down as processing progresses. This is why FFT IP cores typically offer both scaled and unscaled modes.


As before, I started with a simple Python script which generates the expected results using the same input samples as the DFT example.

from pathlib import Path

import matplotlib.pyplot as plt
import numpy as np


def main() -> None:
    samples = np.array([4, 3, 0, -3, -4, -3, 0, 3], dtype=float)
    spectrum = np.fft.fft(samples)

    out_dir = Path(__file__).resolve().parents[1] / "docs"
    out_dir.mkdir(parents=True, exist_ok=True)

    fig, ax = plt.subplots(figsize=(7, 3))
    ax.stem(np.arange(len(spectrum)), np.abs(spectrum), basefmt=" ")
    ax.set_title("Reference 8-Point FFT Spectrum")
    ax.set_xlabel("Bin")
    ax.set_ylabel("Magnitude")
    ax.grid(True, alpha=0.3)
    fig.tight_layout()
    fig.savefig(out_dir / "fft_reference.png", dpi=150)

    for k, value in enumerate(spectrum):
        print(f"Bin {k}: Re = {value.real:8.3f}, Im = {value.imag:8.3f}")


if __name__ == "__main__":
    main()

The input is a sampled cosine which falls into bin one, and the Python output confirms this with a magnitude of 16.485 in bins one and seven. Bin seven is the conjugate mirror of bin one, as discussed previously for real-valued inputs.



Running the testbench against the RTL gives bin one as 16 and bin seven as 17, with the small residual in bin three appearing as minus one.



These differences from the floating-point reference arise from the Q10 quantisation of the twiddle factors and the truncation performed after each butterfly multiplication. Bins one and seven differ by one LSB despite being mathematically identical.


The reason for this is that truncation rounds towards negative infinity, and the two bins take slightly different paths through the butterfly network. This is exactly the kind of behaviour you need to understand when verifying fixed-point DSP implementations against floating-point models. We have looked at rounding before here.

The RTL and testbench are available on my GitHub.


Scaling Up

Going from eight points to a more commonly used size such as 1024 changes little conceptually.


The number of stages becomes log₂ N, the butterfly schedule generalises directly from the stage and position counters in the code, and the sample memory becomes a block RAM rather than registers.


What does require more thought is the twiddle-factor ROM, which grows to N/2 entries, and the word-growth strategy discussed above.


It is also worth understanding why this matters even if you never write your own FFT.

When you configure the AMD FFT IP core, you are asked about radix, scaling, and whether you want natural or bit-reversed output ordering.


Every one of those options maps directly onto what we have built here, and knowing what the butterfly is doing makes those configuration decisions informed choices rather than guesses.


FPGA Conference

FPGA Horizons London- October 6th and 7th 2026 - get Tickets here.


FPGA Journal

Read about cutting edge FPGA developments, in the FPGA Horizons Journal or contribute an article.


Workshops and Webinars:

If you enjoyed the blog why not take a look at the free webinars, workshops and training courses we have created over the years. Highlights include:



Boards

Get an Adiuvo development board:

  • Adiuvo Embedded System Development board - Embedded System Development Board

  • Adiuvo Embedded System Tile - Low Risk way to add a FPGA to your design.

  • SpaceWire CODEC - SpaceWire CODEC, digital download, AXIS Interfaces

  • SpaceWire RMAP Initiator - SpaceWire RMAP Initiator,  digital download, AXIS & AXI4 Interfaces

  • SpaceWire RMAP Target - SpaceWire Target, digital download, AXI4 and AXIS Interfaces

  • Other Adiuvo Boards & Projects.


Embedded System Book   

Do you want to know more about designing embedded systems from scratch? Check out our book on creating embedded systems. This book will walk you through all the stages of requirements, architecture, component selection, schematics, layout, and FPGA / software design. We designed and manufactured the board at the heart of the book! The schematics and layout are available in Altium here.  Learn more about the board (see previous blogs on Bring up, DDR validation, USB, Sensors) and view the schematics here.


All words in this blog were written by a human.



bottom of page