Blog

Fast Fourier Transform in C++ using KFR

In this article I’ll show you how to use Fast Fourier Transform in Digital Signal Processing and how to apply forward and inverse FFT on complex and real data using the KFR framework.

Version 1.2.0 has been released: real FFT, FFT plan caching, build times reduced

New features and notable changes:

How C++14 and C++17 help to write faster (and better) code. Real world examples

Writing high performance code is always a difficult task. Pure algorithms are not always a good fit for the real world architectures. Once having begun to speed up all these pure algorithms, we quickly find that some implementation is pretty fast on one architecture, but terrible slow on another while second implementation outperform the first one in some contexts losing speed in all the rest. Numerous big and small optimizations for each of supported architectures can quickly bloat our code and waste our time.

Compile-time arguments and function wrappers

Passing values in C++ as a template arguments has some inflexibilities. For example, if template function has been wrapped into a functor class, there are no ways to pass some value as a template argument.

Example: FIR filter in C++

The following example shows how to apply FIR filter to audio data using KFR framework. #include <kfr/all.hpp> using namespace kfr; int main(int argc, char** argv) { // static array (like std::array) to hold the taps univector<double, 15> taps; // initialize window function // we pass tap count to window_hann function // window_hann does not calculate window functions // but creates object representing hann window expression_pointer<double> hann = to_pointer(window_hann(taps.size())); // FIR filter design using window method // frequency = 0.

Version 1.0 is now available

Today KFR framework has been updated to v1.0.0 and has reached a stable release. Nearly 200 commits have been pushed since the previous version and lots of improvements and fixes landed in this release.

What's new in KFR 1.0

ARM NEON support New in 1.0 One of the most significant features added since the previous version is full ARM NEON support. All algorithms bundled with KFR 1.0 already optimized for armv7, armv7s and aarch64 (arm64). Intel SSE2..4.2 and AVX1..2 KFR produces code optimized for latest Intel and AMD processors as well as for legacy ones. Generic implementation New in 1.0 In addition to optimized ones, generic implementation of vector functions is available for all other architectures.

Basic expression tutorial

The expression is the central entity of KFR framework. Input expressions can be read from and output expressions can be written to. Class can be an input and output expression at same time. univector is an example of such class. Data type of an input expressions can be determined by calling value_type_of. However, not all expressions have their types specified. In such cases value_type_of will return special type generic. Size (length) of an expression also can be specified or not.

Biquad filters in C++ using KFR

Digital biquad filters and biquad filter design functions are implemented in the KFR framework starting from the first version.

Biquad algorithm uses the Transposed Direct Form II which reduces the quantization errors in the floating point calculations.