Why Approximate the DFT at All?#

For an $N$-point DFT,

the straightforward implementation contains many complex multiplications.

For only eight points, this is not a huge problem on a modern FPGA. But the exercise becomes interesting when the design goal changes from:

“Can the FPGA calculate this?”

to:

“Can the transform be expressed using cheaper hardware primitives while preserving the spectral information that matters?”

The ADFT architecture I implemented uses coefficient approximations that reduce the transform to combinations of:

1
addition
2
subtraction
3
right shifts
4
routing
5
registers

For example:

The main ADFT core therefore requires no general-purpose multipliers.

That distinction is important. A constant coefficient that happens to be easy to express in binary is not really a “multiplication problem” anymore. It is an architecture problem.

Start with a Software Reference You Trust#

Before building the HDL design, I generated several complex-valued test cases in MATLAB and compared the ADFT response with an FFT reference.

The cases covered three useful spectral situations:

1
Case A - DC plus bin-aligned tones
2
Case B - off-bin tones with spectral leakage
3
Case C - multiple bin-aligned tones with unequal amplitudes

The per-bin energy metric was:

where $a_k$ and $b_k$ are the real and imaginary components of each frequency bin.

The point of the MATLAB stage was not to prove that an FFT works.

It gave me a golden reference that stayed unchanged while the hardware implementation evolved.

Later, when something went wrong in Simulink or on the FPGA, I could ask:

Is this an approximation effect, a fixed-point effect, a pipeline-alignment error, or a hardware integration error?

Without a software reference, those failure modes are difficult to separate.

Lesson 1 - A Hardware-Friendly Algorithm Still Needs a Hardware Architecture#

The mathematical transform does not specify:

• where registers go;
• how wide intermediate values should be;
• when all outputs become valid;
• which paths must be delayed;
• how input samples are framed.

Those decisions belong to the architecture.

The HDL Coder interface used sixteen fixed-point inputs:

1
8 real samples
2
8 imaginary samples

and produced sixteen outputs:

1
8 real frequency components
2
8 imaginary frequency components

The explicit 16-input / 16-output mapping made it easier to compare the mathematical transform, Simulink model, and generated HDL.

I found this explicit mapping useful because it prevented the interface from hiding too much.

Each signal corresponded to a specific part of the complex vector, so debugging a wrong output bin remained manageable.

A simplified design flow was:

I deliberately keep the Mermaid syntax simple here because it is also much more portable across renderers.

Lesson 2 - Pipelining Is Not Just Adding Registers#

My first hardware version was functionally correct but had long combinational paths.

Several add/subtract operations could be traversed within one clock period. That created a critical path dominated by chained arithmetic.

The unoptimised critical-path estimate was about:

After pipelining and delay balancing, the post-implementation path was reduced to approximately:

The corresponding routed maximum clock frequency increased from roughly:

to:

The result was more than a 2x increase in achievable frequency without changing the transform arithmetic itself.

The arithmetic is similar in both designs; the important difference is how the combinational work is segmented by registers.

The lesson was that pipelining has at least three separate jobs.

1
adder -> adder -> shift -> adder -> register

1
adder -> register
2
shift -> register
3
adder -> register

1
input frame
2
    ↓
3
pipeline latency
4
    ↓
5
valid output frame

Lesson 3 - Registers Are Cheap Only If You Remember What They Cost#

The pipelined version retained the same basic arithmetic:

1
56 adders/subtractors
2
8 static shift operators
3
0 multipliers in the ADFT core

but the register count increased substantially because of pipeline staging and delay balancing.

That is exactly the expected trade-off:

I used to think of pipelining mainly as a performance technique.

This project made me think of it as a resource exchange:

spend registers and latency to buy timing margin.

That framing is much more useful when comparing architectures.

Lesson 4 - Fixed-Point Design Is Part of the Algorithm#

The input samples were represented with a 16-bit fixed-point format using 12 fractional bits.

The difficult part was not writing:

1
Q1.12

in a block parameter.

The difficult part was making sure intermediate arithmetic did not quietly destroy the spectrum.

I considered several issues:

• growth after addition;
• temporary guard bits;
• truncation points;
• rounding mode;
• overflow behaviour;
• final output compatibility with MATLAB.

A useful model is:

where $F$ is the number of fractional bits.

Increasing $F$ improves precision, but only until the total word length becomes the limiting factor.

In my numerical sweep, the spectral mean-squared error decreased rapidly as fractional precision increased and reached approximately:

at 12 fractional bits.

The precision sweep helped turn a word-length choice into a measurable engineering decision rather than a guess.

This is one of the fixed-point habits I now value most:

Do not choose a format only because it “looks precise enough.” Sweep it against a reference and measure the error.

Lesson 5 - FPGA-in-the-Loop Is More Useful Than I Expected#

Simulation can confirm the Simulink model.

Synthesis can confirm that the design maps to hardware.

But neither alone proves that the generated FPGA implementation produces the exact sample stream expected by the software model.

That is where FPGA-in-the-loop verification became useful.

MATLAB supplied the fixed-point inputs, the Nexys 4 executed the ADFT hardware, and the returned outputs were compared with the delayed software reference.

The error was evaluated as:

After compensating for the pipeline latency, the error remained zero across the verification window.

Both baseline and optimised designs were compared against the same software reference after compensating for hardware latency.

The key phrase there is after compensating for latency.

Without aligning the streams, even a perfectly correct pipelined design appears wrong.

That reinforced a recurring FPGA lesson for me:

Correct values at the wrong clock cycle are still incorrect hardware behaviour.

Lesson 6 - Timing Reports Tell You More Than “Pass” or “Fail”#

It is tempting to treat timing analysis as binary:

1
timing passed
2
timing failed

But the more useful question is:

What physical structure created the critical path?

In the unoptimised version, the dominant path passed through several arithmetic operations before reaching a register.

That told me exactly what to optimise.

After pipelining, the longest path was reduced to roughly one arithmetic stage between registers.

The main timing comparison was:

The important observation is that the frequency gain did not come from replacing the algorithm.

It came from changing the spatial and temporal structure of the same arithmetic.

Lesson 7 - Verification Should Follow the Same Test Cases Across Every Layer#

I reused the same representative spectra across:

1
MATLAB
2
Simulink functional simulation
3
FPGA-in-the-loop
4
standalone FPGA testing

That consistency was extremely valuable.

Representative spectra were kept consistent across software and hardware verification.

Changing test signals at every stage makes each verification step individually interesting but weakens the end-to-end argument.

Using the same cases lets you trace one expected behaviour through the entire toolchain:

1
known input spectrum
2
      ↓
3
software ADFT
4
      ↓
5
fixed-point Simulink
6
      ↓
7
generated HDL
8
      ↓
9
FPGA-in-the-loop
10
      ↓
11
physical board

This is a verification strategy I would reuse in future hardware projects.

Lesson 8 - A Standalone FPGA System Needs Much More Than the Compute Core#

Once the ADFT itself worked, the final task was turning it into a standalone spectrum-sensing pipeline.

The complete signal path was:

The ROM stored pre-generated complex samples.

The SIPO registers converted sequential samples into the 8-sample parallel frame expected by the transform.

The power block calculated:

and then classified each bin relative to the maximum energy.

The thresholds used were:

Finally, the eight seven-segment digits represented the eight frequency bins.

Each digit used a simple visual encoding:

1
top segment    -> High
2
middle segment -> Mid
3
bottom segment -> Low

I like this architecture because every block has a narrow responsibility.

The ADFT does not know anything about seven-segment displays.

The display driver does not know anything about Fourier transforms.

That separation made the standalone design much easier to debug.

Lesson 9 - The Peripheral Logic Can Be Small but Still Define the Product#

The complete system used only a small fraction of the Artix-7 fabric.

The final implementation occupied roughly:

1
1896 LUTs       ~2.99%
2
1991 flip-flops ~1.57%
3
1 BRAM tile
4
16 DSP slices in the power-computation stage

The ADFT core itself remained multiplierless; the DSP slices in the complete design were associated with the later power calculation.

This distinction matters.

When describing an FPGA design, saying:

“The system uses DSP slices”

is not the same as saying:

“The transform requires multipliers.”

Architecture-level resource attribution is more informative than quoting only a top-level utilisation number.

On-Board Results Made the Design Feel Real#

The final system ran on the Nexys 4 without MATLAB continuously controlling it.

The eight seven-segment displays provide a coarse but immediate view of the relative energy distribution across the eight frequency bins.

The three test cases produced the expected Low/Mid/High patterns on the board.

At that point the system had become:

1
ROM
2
 -> SIPO
3
 -> ADFT
4
 -> power
5
 -> classification
6
 -> display

with deterministic timing inside one FPGA clock domain.

This final integration was important because a transform core that passes a unit test is not yet a useful embedded signal-processing system.

The interfaces around it determine whether it can actually consume data and expose a meaningful result.

What I Would Change in a Second Version#

1
input_valid
2
input_ready
3
output_valid

1
transform size
2
word length
3
fractional length
4
pipeline depth

1
dynamic power
2
static power
3
energy per frame
4
throughput per watt

1
ADC
2
RF front end
3
DMA/data stream

Final Thoughts#

This project changed how I think about FPGA optimisation.

At first, the most interesting idea seemed to be the multiplierless ADFT itself.

By the end, I found the architectural lessons more valuable:

• a hardware-friendly equation is only the beginning;
• pipelining is a deliberate exchange between timing, latency, and registers;
• delay balancing is just as important as inserting registers;
• fixed-point precision should be measured, not guessed;
• verification has to account for time as well as value;
• resource reports are most useful when interpreted by module;
• a compute core becomes useful only after it is integrated into a complete data path.

The biggest lesson I kept is:

FPGA performance often improves not because the arithmetic changes, but because the same arithmetic is reorganised in space and time.

That idea now influences how I look at DSP accelerators, hardware pipelines, and almost any architecture intended for real-time FPGA implementation.