FFT Demo — Fast Fourier Transform

The calx FFT module supports arbitrary-length transforms via mixed-radix (radix-2, 3, 5) + Bluestein, with automatic acceleration through SIMD (AVX2/SSE). This page introduces the basic operations through four demos. All output is computed in real time by calx. The source code is provided at the bottom of the page.

Demo 1: Complex FFT (forward and inverse transform)

Applies the FFT to four complex data points and verifies that the inverse transform recovers the original. FFT<C>::fft operates in-place, and FFT<C>::ifft includes $1/N$ normalization.

Input: (1,0) (2,0) (3,0) (4,0) FFT: (10,0) (-2,2) (-2,0) (-2,-2) IFFT: (1,0) (2,0) (3,0) (4,0) ✓ recovered

$X[0] = 1+2+3+4 = 10$ (DC component = sum of all samples). The values after the inverse transform match the input, confirming that the FFT→IFFT round-trip is correct.

Demo 2: Real FFT and spectral analysis

Transforms the 8-point real signal $x = [1, 0, -1, 0, 1, 0, -1, 0]$ (a cosine wave of period 4) using RealFFT and retrieves the amplitude spectrum. The output is compressed to $N/2+1 = 5$ bins by exploiting conjugate symmetry.

Input: 1 0 -1 0 1 0 -1 0 (N=8) Spectrum (N/2+1 = 5 bins): X[0] = (0, 0) |X[0]| = 0 X[1] = (0, 0) |X[1]| = 0 X[2] = (4, 0) |X[2]| = 4 ← peak at frequency 2/8 = 0.25 X[3] = (0, 0) |X[3]| = 0 X[4] = (0, 0) |X[4]| = 0

The input is a cosine wave of period 4, so exactly 2 cycles fit within $N = 8$ samples. Only $X[2]$ is non-zero, which is the expected result. The conjugate symmetry of real signals, $X[N{-}k] = \overline{X[k]}$, means the full information is preserved in just $N/2+1$ bins.

Demo 3: Convolution (FIR filter)

Computes the convolution of two real arrays efficiently using RealFFT::convolve. This is equivalent to applying a FIR filter by convolving a signal with an impulse response. The output size is $|a| + |b| - 1$.

a = [1, 2, 3] b = [4, 5] convolve(a, b) = [4, 13, 22, 15]

Verification: $(1 + 2x + 3x^2)(4 + 5x) = 4 + 13x + 22x^2 + 15x^3$. Convolution and polynomial multiplication are the same operation; FFT::convolve is for complex coefficients, while RealFFT::convolve is optimized for float / double waveforms.

Direct computation is $O(nm)$, but FFT-based convolution is $O((n+m) \log(n+m))$. The advantage of FFT grows larger as the FIR filter gets longer.

Demo 4: Phase spectrum and unwrapping

Retrieves the spectral phase with phase_spectrum, then removes $2\pi$ jumps with unwrap_phase to obtain a continuous phase. This is a necessary preprocessing step for computing group delay $-d\phi/d\omega$ and visualizing phase responses.

Bin: phase (wrapped) phase (unwrapped) [0] 0.000 0.000 [1] -2.356 -2.356 [2] 3.142 3.142 [3] -2.356 -2.356 [4] 0.000 -6.283

phase_spectrum returns the principal value $(-\pi, \pi]$ of std::arg(), causing the phase to jump at $\pm\pi$. Applying unwrap_phase yields a continuous phase response, from which group delay can be computed by differentiation.

Source code and how to run

example_fft_demo.cpp (complete source code)

// example_fft_demo.cpp — FFT demo
#include <math/fft/fft.hpp>
#include <math/fft/fft_utils.hpp>
#include <iostream>
#include <iomanip>
using namespace calx;

int main() {
    using C = std::complex<double>;

    // --- Demo 1: Complex FFT ---
    std::cout << "--- Complex FFT ---\n";
    std::vector<C> data = {1, 2, 3, 4};
    auto orig = data;
    FFT<C>::fft(data);
    std::cout << "FFT: ";
    for (auto& v : data) std::cout << v << " ";
    std::cout << "\n";
    FFT<C>::ifft(data);
    std::cout << "IFFT: ";
    for (auto& v : data) std::cout << v << " ";
    std::cout << "\n";

    // --- Demo 2: Real FFT ---
    std::cout << "\n--- Real FFT ---\n";
    std::vector<double> signal = {1, 0, -1, 0, 1, 0, -1, 0};
    auto spec = RealFFT<double>::fft(signal);
    auto amp = amplitude_spectrum<double>(spec);
    for (size_t i = 0; i < spec.size(); ++i)
        std::cout << "X[" << i << "] = " << spec[i]
                  << "  |X| = " << amp[i] << "\n";

    // --- Demo 3: Convolution ---
    std::cout << "\n--- Convolution ---\n";
    std::vector<double> a = {1, 2, 3}, b = {4, 5};
    auto c = RealFFT<double>::convolve(a, b);
    std::cout << "convolve = ";
    for (auto v : c) std::cout << v << " ";
    std::cout << "\n";

    // --- Demo 4: Phase unwrap ---
    std::cout << "\n--- Phase unwrap ---\n";
    std::vector<double> sig2 = {1, 0.5, 0, -0.5, -1};
    auto spec2 = RealFFT<double>::fft(sig2);
    auto phase = phase_spectrum<double>(spec2);
    auto uphase = unwrap_phase<double>(phase);
    for (size_t i = 0; i < phase.size(); ++i)
        std::cout << std::fixed << std::setprecision(3)
                  << "  [" << i << "] " << phase[i]
                  << "  ->  " << uphase[i] << "\n";

    return 0;
}

For API details, see the FFT API reference.

Build and run

cd calx
mkdir build && cd build
cmake .. -G "Visual Studio 17 2022" -A x64
cmake --build . --config Release --target example-fft-demo
examples\Release\example-fft-demo.exe