Ooura FFT
Ultra fast 1D real/complex FFT with simple interface.
Branch | Master | Develop |
---|---|---|
Circle CI | ||
Appveyor | ||
Travis | ||
Coveralls |
This is a dependency-free Javascript version of Takuya Ooura's FFT algorithms derived from the C/Fortran FFT implementation. I wanted a fast 1D FFT implementation in Javascript, and the Ooura implementation is a very portable and performant FFT implementation that lends itself well to a porting.
Performance
For a wide range of useful FFT sizes, ooura has higher throughput than other Node FFT packages tested. There is still plenty of scope for optimisation road-mapped for future releases (radix-8, split radix). For details on benchmarking, see this dedicated repository.
Correctness
This implementation has been tested using power-of-2 FFT sizes against trusted reference values (however, I accept no responsibility if this trashes your app, or for any other damages). To test yourself, clone the repository from GitHub and run npm install
to install (just to install the test runner), then run npm test
.
Usage: Real
This implementation performs real FFT and inverse-FFT using double precision javascript TypedArray
. Below is an example of typical extraction of the split-complex spectrum, and back conversion to real array.
var ooura = ; // Set up an input signal of size 8;let input = 12341234; // Set up the FFT object and use a helper to generate an output array// of correct length and type.let oo = inputlength "type":"real" "radix":4;let output = oo; //helper to get single sided complex arrayslet re = oo;let im = oo; //do some FFTing in both directions (using the built in helper functions to get senseful I/O)//note: reference underlying array buffers for in-place processingoo; //populates re and im from inputoo; //populates output from re and im // look at the results and intermediate representationconsole;console;console;console;
Usage: complex
Complex FFT is also possible with this package. Simply initialise the FFT object specifying a complex type FFT.
var ooura = ; // Set up an input signal real and imag componentslet reInput = 1234;let imInput = 2345; // Set up the fft object and the empty arrays for transform resultslet oo = reInputlength*2 "type":"complex" "radix":4;let reOutput = oosize/2;let imOutput = oosize/2;let reBack = oosize/2;let imBack = oosize/2; //do some FFTing in both directions//note: reference underlying array buffers for in-place processingoo; //populates re and im from inputoo; //populates output from re and im // look at the results and intermediate representationconsole;console; console;console; console;console;
Usage: in-place (real/complex)
For the ultimate throughput, there are thin wrapper functions around the underlying FFT implementation that performs operations in place on interleaved complex or real buffers. The following example shows the complex FFT forwards and back, outputting the state of the data at each step to the console.
var ooura = ;const nfft = 32;let oo = nfft "type":"complex" "radix":4 ;let data = Float64Array;console;oo;console;oo;console; // Notice the fast in-place methods do not scale the outputconsole; // ... but that is simple to do manually
Coding Style
The codebase is linted during testing using XO, but with 2 overrides:
no-mixed-operators
is disabled. Conventional XO linting requires only one type of arithmetic operator per command unless each operator is explicitly separated using parentheses. For DSP code, this causes a lot of unnecessary verbosity. If you're an engineer with a grasp of the basic order of operations (BODMAS), then redundant parentheses are bad style.one-var
is disabled. I understand the reasoning for this rule, but this code is ported from C, where a common idiom is to declare all variables at the top of each function. Disabling this rule allows the JS and C versions of the code to be more easily comparable.
The spec folder is also excluded from XO linting as part of npm test
due to errors raised in relation to the way that the Jasmine test framework operated. However, it is still recommended to manually run xo --fix spec/*
after modifying unit tests to maintain a level of consistency.