KissFFT: An Open Source C++ Library for Fast Fourier Transform

KissFFT (full name Keep It Simple, Stupid Fast Fourier Transform) is a lightweight, open-source Fast Fourier Transform (FFT) library written in C. It adheres to the “Keep It Simple” principle, featuring concise code (approximately 500 lines), no external dependencies, making it ideal for resource-sensitive scenarios such as embedded systems and real-time signal processing.

The table below provides a quick overview of the core features of KissFFT:

Feature Dimension	Specific Description
Core Design	Concise code (about 500 lines), follows the “Keep It Simple” principle
License	Uses the BSD license, freely usable for open-source and commercial projects
Data Processing	Supports floating-point and fixed-point (Q15, Q31 format) operations
Algorithm Support	Supports mixed-radix FFT (transform sizes can be multiples of 2, 3, or 5), provides optimizations for complex FFT and real FFT
Platform Compatibility	Written in pure ANSI C, cross-platform (Windows, Linux, macOS, Android, etc.)

🛠️ How to Use KissFFT

Getting and Compiling

You can obtain KissFFT in the following ways:

Clone the source code from the GitHub official repository (https://github.com/mborgerding/kissfft).
On some Linux distributions (like Ubuntu, Debian), you can also install the command-line toolkit named kissfft-tools via the package manager.

After cloning, navigate to the project directory and typically execute make to complete the compilation.

Basic Usage Steps

Using KissFFT in your code generally involves the following steps:

Include Header Files: Depending on your needs, include kiss_fft.h (for complex FFT) or kiss_fftr.h (for real FFT).
Configure FFT: Use the kiss_fft_alloc or kiss_fftr_alloc function to allocate and initialize an FFT configuration structure (kiss_fft_cfg or kiss_fftr_cfg). You need to specify the number of points for the transform and whether to perform a forward transform (time domain to frequency domain) or an inverse transform (frequency domain to time domain).
Execute Transform: Call kiss_fft, kiss_fftr (real forward transform), or kiss_fftri (real inverse transform) functions to perform the FFT computation.
Release Resources: After the computation is complete, use kiss_fft_free or kiss_fftr_free to free the allocated configuration structure.

Code Example

Below is a simple example of using KissFFT to perform a real FFT that calculates the frequency spectrum of a sine wave signal.

#include "kiss_fftr.h"
#include <math.h> // For sinf and M_PI

void example_float_fft() {
    const int N = 1024; // FFT points

    // Allocate FFT configuration (the second parameter 0 indicates forward FFT, 1 indicates inverse FFT)
    kiss_fftr_cfg fft_config = kiss_fftr_alloc(N, 0, NULL, NULL);

    // Prepare input signal (e.g., a 100Hz sine wave, sampling rate 44100Hz)
    kiss_fft_scalar input_signal[N];
    for (int i = 0; i < N; i++) {
        input_signal[i] = sinf(2 * M_PI * 100 * i / 44100.0f);
    }

    // Prepare output buffer (the output of real FFT is N/2+1 complex numbers)
    kiss_fft_cpx spectrum[N/2 + 1];

    // Execute FFT
    kiss_fftr(fft_config, input_signal, spectrum);

    // Calculate magnitude spectrum
    float magnitude[N/2 + 1];
    for (int i = 0; i <= N/2; i++) {
        magnitude[i] = sqrtf(spectrum[i].r * spectrum[i].r + spectrum[i].i * spectrum[i].i);
    }

    // Release resources
    kiss_fftr_free(fft_config);
}

If your MCU does not have an FPU (Floating Point Unit), you need to use fixed-point operations, and you must define FIXED_POINT before including the header files.

#define FIXED_POINT 16 // Use 16-bit fixed-point (Q15 format)
#include "kiss_fftr.h"

void example_fixed_point_fft() {
    const int N = 512;
    const int SCALE_SHIFT = 3; // Scaling factor to prevent overflow

    kiss_fftr_cfg cfg = kiss_fftr_alloc(N, 0, NULL, NULL);

    // Assume this is your ADC collected data
    int16_t adc_data[N] = {...};
    kiss_fft_scalar input_signal[N]; // In fixed-point mode, this is actually int16_t

    // Scale raw ADC data to the range of Q15 format
    for (int i = 0; i < N; i++) {
        input_signal[i] = adc_data[i] >> SCALE_SHIFT;
    }

    kiss_fft_cpx spectrum[N/2 + 1];
    kiss_fftr(cfg, input_signal, spectrum);

    // ... Further processing, note to compensate for scaling in results
    kiss_fftr_free(cfg);
}

⚠️ Usage Considerations

Fixed-point Precision and Dynamic Range: Fixed-point operations are fast, but have limited precision and dynamic range, so be cautious of scaling and overflow issues.
Memory Management: Ensure to correctly call kiss_fft_free and related functions to free memory, especially in applications that require repeated FFTs to avoid memory leaks.
Resource Consumption: On resource-constrained embedded devices, pay attention to how the number of FFT points affects RAM and computation time.
Platform Differences: When calling from platforms like Android via JNI, ensure correct data transfer between Java and Native layers.

💎 Comparison with Other FFT Libraries

When selecting an FFT library, understanding the positioning and pros and cons of KissFFT can help you make better decisions.

Library Name	Main Features	Applicable Scenarios
KissFFT	Lightweight, concise code, no dependencies, cross-platform, supports fixed-point/floating-point	Embedded systems, mobile platforms, resource-constrained or projects requiring quick integration
FFTW	High performance, highly optimized, supports various platforms and transform types	Servers, desktop applications, scientific computing, etc., where performance is critically required
NumPy/SciPy	Python ecosystem, user-friendly interface, high integration	Data analysis and algorithm prototyping in Python environments
MATLAB	Powerful signal processing toolbox, interactive environment	Academic research, algorithm simulation, and teaching

Overall, KissFFT strikes a good balance between simplicity, portability, and resource overhead. It may not be the fastest, but for many applications that do not require extreme performance, it is definitely a “good enough” choice.