Discuss
  • FFT module

FFT module

# Jussi Kalliokoski (13 years ago)

Maybe it would be a good idea to define an FFT module for ES?

I'm thinking something like this (performance aspects as the main concern, the interface could be extended with some sugaring in later discussion if the idea gets some traction):

The FFT interface is served as a class, to allow the implementation to maintain some state, which will give room for optimization. The class takes three arguments, defined as follows:

  • numberOfBins: This is the number of frequency bins for the FFT. Must be a positive integer. Required argument.
  • inverse: A boolean to determine whether the FFT should be doing a forward or a backward transform. Defaults to false (forward).
  • dimensions: A positive integer to determine the amount of dimensions of the signal. Defaults to 1.

The class prototype should have a function called complexToComplex() which takes in six arguments, all required, defined as follows:

  • output: The Array (possibly Typed) to place the output to.
  • outputOffset: The offset from which to start writing to the output Array. Positive integer.
  • outputStride: The stride with which to write to the output Array, e.g. if one, read n0, n1, nN; if two, read n0, n2, n(N * 2). Positive integer.
  • input: The Array (possibly Typed) to read the input from.
  • inputOffset: The offset from which to start reading from the input Array. Positive integer.
  • inputStride: The stride with which to read from the input Array. Positive integer.

This would read complex input and output complex output. In a similar fashion, there should be a function called realToComplex() that would have the same set of arguments, but (surprisingly) it would read real input and output complex. Possibly, we could also add realToReal() and complexToReal(), but the use cases for them are fewer I guess.

These functions could maybe be overloaded to take just two arguments, output and input, so that the offsets would be zero and strides would be one.

The class should also have a static function, called getKernels() which should return an array of the kernels the underlying FFT implementation supports. This is useful for developers to optimize buffer sizes in frequency domain algorithms such as Fast Convolution, so that the implementation doesn't fall back to the slower DFT.

This is obviously a rough shot at it and needs polishing and if we were to include it in the specification at some point, we'll need to be sure to define the exact behaviour of the module.

Credit where due, the interface defined here draws inspiration from JensNockert/fft.js and NumPy's FFT methods.

# Oliver Hunt (13 years ago)

This seems like an ideal candidate for JS implementation first, and then if it becomes sufficiently popular consider it for standardisation (as happened with the JSON object).

Also, a couple of things worth considering are that this is a relatively specific set of functionality, so may be more suited for individual application embedding anyway, and modern JS engines are getting fairly fast, and are only going to get faster.

# Jens Nockert (13 years ago)

This seems like a very application specific addition. Wouldn't it make more sense to add building blocks for building faster DSP operations instead?

Strawmen that popped into my mind,

  1. Typed arrays (strawman:typed_arrays, already available in browsers)
  2. Value objects (strawman:value_objects) for fixed-point and complex number operations

-- Jens Nockert

# Jussi Kalliokoski (13 years ago)

On Sun, May 20, 2012 at 11:47 PM, Oliver Hunt <oliver at apple.com> wrote:

This seems like an ideal candidate for JS implementation first, and then if it becomes sufficiently popular consider it for standardisation (as happened with the JSON object).

Indeed. But I can't see an FFT library gaining quite as much traction as JSON did, heh.

Also, a couple of things worth considering are that this is a relatively specific set of functionality, so may be more suited for individual application embedding anyway, and modern JS engines are getting fairly fast, and are only going to get faster.

Yes, and the fft.js I mentioned is already faster than at least one commonly used FFT implementation written in C++.

# Jussi Kalliokoski (13 years ago)

On Sun, May 20, 2012 at 11:53 PM, Jens Nockert <jens at nockert.se> wrote:

This seems like a very application specific addition. Wouldn't it make more sense to add building blocks for building faster DSP operations instead?

True, it is very application specific. And yes, that would be far more useful, however I think at some point in the foreseeable future there's a place for a built-in module like this as well.

The main reason I decided to bring this idea up is that having a module like this in JS has come up quite a few times in W3C Audio WG discussions.