fixedpoint-fft

A fast, header-only C++ in-place FFT/IFFT library for Microcontrollers, built primarily around fixed-point integer math (int8_t/int16_t/int32_t), with float/double also available as calc types on hardware where they make sense (see Choosing float/double).

Why another FFT library?

There's no shortage of FFT libraries for Arduino already - arduinoFFT, KissFFT, FFTReal, CMSIS-DSP and Espressif's ESP-DSP wrappers among them (see e.g. the driver wrappers in arduino-audio-tools). Nearly all of them share the same two properties, though:

• They compute in float (sometimes double) unconditionally. That's a reasonable default on an FPU-equipped MCU, but on plain AVR (Uno, Nano, Mega - no hardware FPU) every float operation is emulated in software, and each sample costs 4+ bytes of an already scarce 2KB of RAM regardless of how much precision the application actually needs.
• Twiddle factors are generated by calling sin()/cos() at runtime (typically once in setup()), or a table is baked in for one fixed N. Neither avoids the trig call altogether, and the fixed-N table approach doesn't let you change FFT size without regenerating it.

This library exists for the case those don't cover well: an FFT that's genuinely fast and small on 8-bit AVR-class hardware, where the calculation type is a first-class, per-instance choice - not just int16_t because that's what the ADC happens to produce, but int8_t by default for the smallest/fastest option, or int32_t/float/double when the application can afford (or needs) more precision, all through the same API and the same in-place, minimal-RAM engine. Twiddle factors never come from a runtime sin()/cos() call at all - not even once at startup - they're generated fully offline and reconstructed at runtime from a single small flash table that serves every power-of-two FFT size up to its configured maximum. If your board has an FPU (ESP32, Cortex-M4F/M7) or you're building for desktop, the same engine scales up to float/double cleanly - see Choosing float/double.

Features

• No trig calls, ever - for any calc type. Twiddle factors come from a small quarter-wave cosine table generated offline by tools/generate_twiddles.py and checked into the repo; nothing in src/ calls sin()/cos(), no matter which CalcT you pick. For the integer calc types (int8_t/int16_t/int32_t), magnitude() also avoids sqrt() entirely via an integer bit-by-bit square root; the float/double calc types use sqrtf()/sqrt() (<math.h>) there instead, since that's a single hardware instruction on an FPU-equipped target - see Choosing float/double.
• In place. The transform works on exactly two arrays of the calculation type (real + imaginary), length N, and nothing else. You can supply your own static/stack buffers for genuinely zero-heap operation.
• Configurable calculation type. FixedFFT<CalcT> is templated on int8_t (default), int16_t, int32_t, float, or double. int8_t is the fastest and smallest fixed-point option (1 byte/sample instead of 2 or 4), at the cost of ~7 bits of precision. float is worth choosing specifically on MCUs with a hardware single-precision FPU (ESP32/ESP32-S3, ARM Cortex-M4F/M7, ...); double is a desktop-only precision option (native x86-64 hardware double, ~15-17 significant digits) - see Choosing float/double.
• Independent input sample type. FixedFFT<CalcT, InT> takes a second template parameter, InT (defaults to CalcT), naming the type your raw samples are stored as - int8_t, int16_t, int32_t, float, or double, independent of the calculation type. loadReal()/load()/loadHalfSpectrum() rescale from InT into CalcT on the way in, so e.g. FixedFFT<int8_t, int16_t> computes at int8_t speed/RAM while accepting raw int16_t ADC samples directly - no per-call casting or template argument on the load call itself.

Quick start

Forward FFT

FixedFFT<CalcT, InT> takes two template parameters: CalcT is the type all math is performed in, InT (defaults to CalcT) is the type your raw samples are stored as. Naming them independently - e.g. int8_t calc type fed from int16_t ADC/I2S samples, as below - avoids any per-call casting or conversion of your own: loadReal() rescales from InT into CalcT's Qn range on the way in.

#include "FixedFFT.h"

fixedpoint_fft::FixedFFT<int8_t, int16_t> fft;  // int8_t calc type, int16_t input samples

void setup() {
  fft.begin(64);                 // allocates 2 * 64 bytes internally
}

void loop() {
  int16_t samples[64] = { /* ... */ };
  fft.loadReal(samples, 64);     // rescaled from int16_t into Q7; imag cleared to 0
  fft.fft();
  for (int k = 0; k < 32; k++) {
    int8_t mag = fft.magnitude(k);  // no sqrt() call - integer isqrt
  }
}

(If your samples are already in CalcT's own representation, just omit the second template argument - FixedFFT<int8_t> is equivalent to FixedFFT<int8_t, int8_t>.)

For a genuinely zero-heap, fully in-place transform, supply your own buffers instead of letting begin(n) allocate them (these are always CalcT-typed working buffers, regardless of InT):

static int8_t real_buf[64], imag_buf[64];
fft.begin(64, real_buf, imag_buf);

Inverse FFT

You don't need to call fft() first to use ifft() - e.g. to synthesize a time-domain signal from a spectrum you built yourself (a handful of bins set to a magnitude/phase, everything else left at 0). Two methods load a complex-valued spectrum (or signal) directly:

• load(real_in, imag_in, n) loads all n complex bins as given, no assumptions made. Use this when you want full control - e.g. the spectrum is genuinely complex-valued, or you're loading a time-domain signal that already has a nonzero imaginary part.
• loadHalfSpectrum(real_in, imag_in, halfN) loads only the non-redundant half of a spectrum - bins 0..N/2, halfN = N/2 + 1 complex values - and mirrors it into the upper half (bins N/2+1..N-1) via conjugate symmetry (real[N-k] = real[k], imag[N-k] = -imag[k]) before ifft() runs. ifft() only produces a purely real result if the spectrum has this symmetry, so this is the method to use for the common case of synthesizing a real signal from a frequency-domain specification - you only specify N/2 + 1 values instead of building the full symmetric spectrum by hand.

Since a spectrum loaded either way didn't come from this library's fft() (so it has no guaranteed headroom), pass safeScale=true so ifft() applies its adaptive per-stage overflow guard instead of assuming one:

int16_t real_in[33] = {0}, imag_in[33] = {0};  // N/2 + 1 = 33 for N=64
real_in[4] = 12000;                 // a single frequency component at bin 4
fft.loadHalfSpectrum(real_in, imag_in, 33);  // mirrors bins 33..63 automatically
fft.ifft(/*safeScale=*/true);       // inverse transform, in place
for (int i = 0; i < 64; i++) {
  int8_t sample = fft.real(i);      // synthesized time-domain signal
  // fft.imag(i) is ~0 at every sample, by construction
}

See examples/SynthesizeFromSpectrum for a complete sketch.

See examples/ for complete sketches (BasicFFT, ExternalBuffers, InverseFFT, FloatFFT, SpeedTest, SynthesizeFromSpectrum).

For how the library avoids trigonometric calls entirely and how its fixed-point scaling model works, see IMPLEMENTATION.md.

Precision vs. calculation type - know the tradeoff

int8_t (Q7) gives you the smallest memory footprint and the fastest per-butterfly math, but only ~7 bits of precision to start with. Its accuracy holds up fine for peak/frequency detection (bin location) at any supported N, but the round-trip fft()/ifft() precision degrades as N grows, because the fixed 1/N forward attenuation eats further into an already-small budget of bits. As a rough guide from this library's own test suite (test/host_test.cpp):

CalcT	N=16	N=32	N=64	N=128	N=256	N=512	N=1024	N=2048
int8_t	~0.06	~0.17	~0.24	~0.53	~0.99 (unusable)	unusable	unusable	unusable
int16_t	~0.0002	~0.0005	~0.001	~0.002	~0.004	~0.007	~0.016	~0.032
int32_t	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000
float	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000
double	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000	~0.000000

(Round-trip error, normalized to the [-1, 1) Qn range.) int8_t becomes unusable for round trips from N=256 up - the fixed 1/N attenuation has eaten all 7 fractional bits by then, so the numbers there are dominated by noise rather than a meaningful trend. If you need int8_t speed/RAM at larger N, use fft(true)/ifft(true) (adaptive scaling) rather than the defaults, or switch to int16_t. Forward-only spectrum analysis (magnitude/bin detection, no ifft()) is far less sensitive to this and works well with int8_t at any N.

For a detailed performance comparision by processor see this table

Choosing float/double

float is worth it specifically on FPU-equipped MCUs (ESP32/ESP32-S3, ARM Cortex-M4F/M7, ...): a plain float multiply-add is already correctly scaled, so it skips the rescale-by-shift step the integer types need after every complex multiply, and it never needs the saturating overflow guard applied to every butterfly output either - float's huge dynamic range makes that overflow a non-issue, while the integer types' narrow range makes it a real one. That's not a minor saving: on hardware-FPU targets it consistently makes float several times faster than int32_t, not merely comparable to it - e.g. on the ESP32 (Xtensa LX6) an N=64 FFT takes 75.14 µs in float vs. 398.47 µs in int32_t, and even the smaller int16_t calc type (250.49 µs) is well behind. See Performance.md for the full cross-device comparison. As a result, fft() always returns 0 (plain unscaled DFT sum) and magnitude() uses sqrtf() instead of the integer bit-by-bit square root for float. On plain AVR (no FPU), float is emulated in software and much slower than the integer calc types - stick to int8_t/int16_t/int32_t there. See examples/FloatFFT.

double should be avoided on microcontrollers - it's unsupported on AVR and gives no speed benefit over float elsewhere. It's meant for desktop/server builds, where the extra precision (~15-17 significant digits instead of float's ~7) is useful for e.g. host-side reference/ verification work - this library's own test suite uses it that way.

Installation

For Arduino, you can download the library as zip and call include Library -> zip library. Or you can git clone this project into the Arduino libraries folder e.g. with

cd  ~/Documents/Arduino/libraries
git clone https://github.com/pschatzmann/fixedpoint-fft.git

For running the host-side test suite or consuming this library from another CMake project, see CMAKE.md.