auroranockert / fft.js

Discrete Fourier Transform in Javascript, it is intended to be reasonably fast.

fft.js

FFT in JavaScript, it works, I think.

No promises, but I tested it against Wolfram Alpha once, and it was reasonably accurate.

There are optimized kernels for prime factors, 2, 3, 4, so if you want high performance, use lengths that are a factor of those.

Notice that the DFT is not normalized, so ifft(fft(x)) / n ~= x

Usage

/* Create a new FFT object */

var fft = new FFT.complex(n, inverse)

/* Output and input should be float arrays (of the right length), type is either 'complex' (default) or 'real' */
fft.process(output, outputOffset, outputStride, input, inputOffset, inputStride, type)

/* Or the simplified interface, which just sets the offsets to 0, and the strides to 1 */
fft.simple(output, input, type)

Installing via npm

You can also install via npm, the name is fft in the registy.

Credits

I was too lazy to calculate the butterflies myself, so they are inspired by kissfft, which is a small library for doing discrete fourier transforms.

fft.js's Issues

npm docs

Could you please update npm package docs?
They seem to be misleading.
Thanks!

Real FFT is broken

Only the 2-butterfly is defined for real FFTs and I am not sure it works. The expected result is that it should work.

RealFFT with stride

Currently we cannot supports strides for the real FFT, since it assumes that complex numbers are packed, this could easily be fixed with some magic.

First, most popular hit for FFT in node.js. Missing some important description of how to use.

var fft = new FFT.complex(n, inverse)

What is the logic when setting n and inverse? n = number of samples? inverse = 1/n?

real.js referenced in test.html

The real.js referenced from test.html is not in the repository.

FFT for N > 4 seems to be incorrect

For this test file:

var FFT = require('fft')

var l = 1 << 5

var input  = new Float32Array(l)
var output = new Float32Array(l + 2)
var fft    = new FFT.RFFT(l)

input[0] = 1;
fft.process(output, input)

console.error([].join.call(output))

Results are:

0.1767766922712326,0,0.14295193552970886,0.00672816252335906,0.1142766922712326,0.02588834799826145,0.0951165109872818,0.05456359311938286,0.0883883461356163,0.0883883461356163,0.0951165109872818,0.12221310287714005,0.1142766922712326,0.1508883535861969,0.14295193552970886,0.1700485348701477,0.1767766922712326,0,0.21060144901275635,-0.00672816252335906,0.2392766922712326,-0.02588834799826145,0.2584368884563446,-0.05456359311938286,0.2651650309562683,-0.0883883461356163,0.2584368884563446,-0.12221310287714005,0.2392766922712326,-0.1508883535861969,0.21060144901275635,-0.1700485348701477,0.1767766922712326,0

While I think they should be uniformly 0.17677669529663687,0.

real.js is untested/unfinished

EDIT: Sorry, I didn't see the open issues tab in github. This is a duplicate.

Refactor complex arithmetic

Use erb to generate the complex arithmetic expressions.

Testing

Testing is currently done manually, this is not very reliable, should semi-automate it.

Not compatible with < IE10

Float32Array is not supported in < IE10. In a perfect world, I'd ask this to be fixed. In a realistic one, I ask that you put the compatibility notice in the readme.