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 = require('ooura');

// Set up an input signal of size 8;
let input = new Float64Array([1,2,3,4,1,2,3,4]);

// Set up the FFT object and use a helper to generate an output array
// of correct length and type.
let oo = new ooura(input.length, {"type":"real", "radix":4});
let output = oo.scalarArrayFactory();

//helper to get single sided complex arrays
let re = oo.vectorArrayFactory();
let im = oo.vectorArrayFactory();

//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 processing
oo.fft(input.buffer, re.buffer, im.buffer);   //populates re and im from input
oo.ifft(output.buffer, re.buffer, im.buffer); //populates output from re and im

// look at the results and intermediate representation
console.log("ip = " + input);
console.log("re = " + re);
console.log("im = " + im);
console.log("op = " + output);

Usage: complex

Complex FFT is also possible with this package. Simply initialise the FFT object specifying a complex type FFT.

var ooura = require('ooura');

// Set up an input signal real and imag components
let reInput = new Float64Array([1,2,3,4]);
let imInput = new Float64Array([2,3,4,5]);

// Set up the fft object and the empty arrays for transform results
let oo = new ooura(reInput.length*2, {"type":"complex", "radix":4});
let reOutput = new Float64Array(oo.size/2);
let imOutput = new Float64Array(oo.size/2);
let reBack = new Float64Array(oo.size/2);
let imBack = new Float64Array(oo.size/2);

//do some FFTing in both directions
//note: reference underlying array buffers for in-place processing
oo.fft(reInput.buffer, imInput.buffer, reOutput.buffer, imOutput.buffer);   //populates re and im from input
oo.ifft(reOutput.buffer, imOutput.buffer, reBack.buffer, imBack.buffer); //populates output from re and im

// look at the results and intermediate representation
console.log("real input = " + reInput);
console.log("imag input = " + imInput);

console.log("re transformed = " + reOutput);
console.log("im transformed = " + imOutput);

console.log("re inverse transformed = " + reBack);
console.log("im inverse transformed = " + imBack);

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 = require('ooura');
const nfft = 32;
let oo = new ooura(nfft, {"type":"complex", "radix":4} );
let data = Float64Array.from(Array(nfft), (e,i)=>i+1);
console.log(data);
oo.fftInPlace(data.buffer);
console.log(data);
oo.ifftInPlace(data.buffer);
console.log(data); // Notice the fast in-place methods do not scale the output
console.log(data.map(x=>x*2/oo.size)); // ... but that is simple to do manually

Coding Style

The codebase is linted during testing using XO, but with 2 overrides:

1. 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.
2. 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.