Fast Fourier Transform in C++ using KFR

In this article I’ll show you how to use the Fast Fourier Transform (FFT) in digital signal processing, and how to apply forward and inverse FFTs to complex and real data using the KFR framework.

Introduction

Fast Fourier Transform (FFT) can be used to perform:

• Convolution (including convolution reverberation)
• Cross-correlation and auto-correlation
• Applying large FIR filters
• Sample rate conversion
• Spectrum visualization
• Large integer multiplication
• and many other algorithms

In many cases, the FFT is the most efficient way to perform each of these algorithms.

Moreover, KFR has one of the most efficient FFT implementations, so you can get a great performance boost of your DSP applications using KFR’s FFT for all of these algorithms.

Differences from other implementations

The KFR implementation of the FFT offers the following:

• is fully optimized for X86, X86-64, ARM and AARCH64 processors
• uses vector intrinsics (if available for the CPU)
• supports both single- and double precision
• can cache internal data between calls to speed up plan creation
• can do forward and inverse FFTs without creating two plans
• can be used for complex-to-complex, real-to-complex and complex-to-real transforms
• does not require measuring execution time at runtime to find an optimal configuration
• has special implementations for FFT sizes up to 256
• has no external dependencies
• is thread-safe
• is written in modern C++
• is open source under the GPL license; commercial licenses are available for proprietary use.

Getting started

For the list of supported compilers and OSes, see the latest README: https://github.com/kfrlib/kfr/blob/main/README.md

1. Download the latest version of KFR:

   https://github.com/kfrlib/kfr/archive/main.zip

2. Add the include folder to your include path.

3. Insert the following line at the beginning of your project’s source code:

#include <kfr/dft.hpp>

KFR is mostly header-only, but the DFT module must be compiled. Build KFR with CMake, then link the DFT library and make sure that the kfr folder inside the include directory is available for inclusion. See the installation docs for details.

Quick example

Complex input

Let’s apply the FFT to the complex input data:

using namespace kfr;
// prepare 256 samples of a complex exponential
univector<complex<double>, 256> data = cexp(
        linspace(0, c_pi<double, 2>, 256) * make_complex(0, 1));
univector<complex<double>, 256> freq;

// do the forward FFT
freq = dft(data);

To perform the inverse FFT do the following:

data = idft(freq);

As a result, the output is the input multiplied by its size (256 in this example). This is a property of the FFT.

To get the original data back, divide the result by its size:

data = idft(freq) / data.size();

Real input

Frequency data is stored in CCS format, as shown in the table below.

Because of symmetry, the second half of the output is not stored.

For an even size, the output contains size/2+1 complex values.

using namespace kfr;
// prepare data (0, 1, 2, ..., 255)
univector<double, 256> data = counter();
univector<complex<double>, 129> freq; // data.size() / 2 + 1

// do the forward FFT
freq = realdft(data);

The inverse FFT expects frequency data in the same CCS format.

To get a purely real output, freq[0] and freq[N/2] must be real numbers.

using namespace kfr;
data = irealdft(freq);
// or to get the properly scaled result:
data = irealdft(freq) / data.size();

Creating FFT plan

The FFT needs twiddle coefficients, which are computed when a plan is created. If the same FFT is performed more than once, it makes sense to store the coefficients and reuse them.

FFT Plan caching

If you are using dft, idft, realdft or irealdft functions, all plans will be kept in memory, so the next call to these functions will reuse the saved data.

You can manually get the plan from the cache (or create one if it is not in the cache):

dft_plan_ptr<T> dft = dft_cache::instance().get(ctype<T>, size);

Cache access is protected by a mutex, so it is thread safe unless KFR is built in single-thread mode.

ctype is a special template variable used only to pass a type to the function.

dft_plan_ptr is an alias for std::shared_ptr<const dft_plan<T>>

To clear all saved plans and free memory, call the clear function:

dft_cache::instance().clear();

As of version 1.3.0, functions convolve and correlate use the cache internally.

Examples using dft_plan

You can create a plan manually without using the cache to get more control over it.

The dft_plan class stores all data needed for the FFT.

The dft_plan constructor takes the FFT size as an argument.

The input and output arguments of execute must be complex<T>* pointers or univector<complex<T>> objects.

You can create a plan and use it as many times as needed. Executing the FFT does not modify the plan’s internal data, so the same plan can be shared between threads, as long as each call uses its own input, output, and scratch buffers.

using namespace kfr;
dft_plan<double> plan(1024);
univector<complex<double>, 1024> in;
univector<complex<double>, 1024> out;
// here fill `in` array with our data (samples)
univector<u8> temp(plan.temp_size);
plan.execute(out, in, temp, false); // direct FFT
// `out` now contains frequencies which have to be processed
plan.execute(in, out, temp, true);  // inverse FFT
// `in` now contains processed data (samples)
...
// process new data
plan.execute(out, in, temp, false); // direct FFT

Real to complex and complex to real transforms using dft_plan_real

using namespace kfr;
dft_plan_real<double> plan(1024); // dft_plan_real for real transform
univector<double, 1024> in;
univector<complex<double>> out(plan.complex_size());
// here fill `in` array with our data (samples)
univector<u8> temp(plan.temp_size);
plan.execute(out, in, temp); // direct FFT
// `out` now contains frequencies which have to be processed
plan.execute(in, out, temp); // inverse FFT
// `in` now contains processed data (samples)

Conclusion

As you can see, using the Fast Fourier Transform with KFR is not difficult. Forward and inverse, complex and real transforms can be performed in a single line of code, with excellent performance and flexibility.

Moreover, KFR’s FFT is in many cases faster than widely used FFT libraries written in C, C++, or other languages.

Reviewed and updated for KFR 7 in Oct 2026.