Noise FFT

Additional

Language
Java
Version
N/A
Created
Jun 24, 2017
Updated
Nov 8, 2019 (Retired)
Owner
Pär Nils Amsen (paramsen)
Contributors
Pär Nils Amsen (paramsen)
DaKeks
2
Activity
Badge
Generate
Download
Source code

Noise

A FFT computation library for Android

Noise is an Android wrapper for kissfft, a FFT implementation written in C. Noise features an api that is designed to be easy to use, and familiar for Android devs. (JNI bindings are available as well)

Sample app

Watch Noise compute FFT in real time from your microphone, the sample app is on Google Play!

Get started

Add jitpack.io repo to your root build.gradle:

allprojects {
    repositories {
        //...
        maven { url "https://jitpack.io" }
    }
}

Include in Android project:

implementation 'com.github.paramsen:noise:2.0.0'

Instructions

This lib is a Kotlin wrapper for kissfft, consult the kissfft readme if you want more information about the internal FFT implementation.

Noise supports computing DFT from real and imaginary input data.

Real input

Instantiate, this example is configured to compute DFT:s on input arrays of size 4096.

Noise noise = Noise.real(4096) //input size == 4096

Invoke the FFT on some input data.

float[] src = new float[4096];
float[] dst = new float[4096 + 2]; //real output length equals src+2

// .. fill src with data

// Compute FFT:
    
float[] fft = noise.fft(src, dst);
    
// The result array has the pairs of real+imaginary floats in a one dimensional array; even indices
// are real, odd indices are imaginary. DC bin is located at index 0, 1, nyquist at index n-2, n-1
    
for(int i = 0; i < fft.length / 2; i++) {
    float real = fft[i * 2];
    float imaginary = fft[i * 2 + 1];
    
    System.out.printf("index: %d, real: %.5f, imaginary: %.5f\n", i, real, imaginary);
}

Imaginary input

This example is configured to compute DFT:s on input arrays of size 8192 (4096 [real, imaginary] pairs).

Noise noise = Noise.imaginary(8192) //input size == 8192

In order to compute a DFT from imaginary input, we need to structure our real+imaginary pairs in a flat, one dimensional array. Thus the input array has pairs of real+imaginary like; float[0] = firstReal, float[1] = firstImaginary, float[2] = secondReal, float[3] = secondImaginary..

float[] imaginaryInput = new float[8192];
    
// fill imaginaryInput with data (pairs is an array of pairs with [real, imaginary] objects):
    
for(int i = 0; i < pairs.length; i++) {
    imaginaryInput[i * 2] = pairs[i].real;
    imaginaryInput[i * 2 + 1] = pairs[i].imaginary;
}
    
// Compute the FFT with imaginaryInput:
    
float[] fft = noise.fft(realInput);
    
// The output array has the pairs of real+imaginary floats in a one dimensional array; even indices
// are real, odd indices are imaginary. DC bin is located at index 0, 1, nyquist at index n/2-2, n/2-1
    
for(int i = 0; i < fft.length / 2; i++) {
    float real = fft[i * 2];
    float imaginary = fft[i * 2 + 1];
    
    System.out.printf("index: %d, real: %.5f, imaginary: %.5f\n", i, real, imaginary);
}

Output

Both the real and imaginary implementations produce an array of real and imaginary pairs, in a flat, one dimensional structure.
Thus each even and odd index is a pair of a real and imaginary numbers, we could convert the result array to an array of pairs to better show the relation like:

float[] fft = noise.fft(input);
    
Pair<Float, Float>[] pairs = new Pair<>[fft.length / 2];
    
for(int i = 0; i < fft.length / 2; i++) {
    float real = fft[i * 2];
    float imaginary = fft[i * 2 + 1];
    
    pairs.add(new Pair(real, imaginary));
}

Sample code

I've written a sample app in Kotlin which computes FFT:s on the real time microphone signal. It features some cool Rx solutions for mic integration that might be interesting in themselves. It's on Google Play and the source can be found in the sample module.

Performance tests

The following tests measure the average FFT computation time over 1000 computations for an array of length 4096. Run on a new S8+ and an old LG G3 for comparison.

Samsung S8+:

Optimized Imaginary:   0.32ms
Optimized Real:        0.32ms
Threadsafe Imaginary:  0.38ms
Threadsafe Real:       0.48ms

LG G3:

Optimized Imaginary:   0.76ms
Optimized Real:        0.72ms
Threadsafe Imaginary:  1.02ms
Threadsafe Real:       1.33ms

Tests

The implementation has been tested for compliance with the kissfft C library; for the same input, equal output is given. The tests in the Android test suite that assures that equal output is computed by loading a pre defined data set and asserting the result against a precomputed result.
The precomputed result is generated by the C test suite that runs kissfft directly in C++.

Development

Setup

Kissfft is not bundled in the source of this repository for many reasons, I have resided to let a git module script initiate it with a manual step.

Setup steps are:

  1. Run git submodule init; git submodule update in project root
  2. Check that kissfft exists in noise/src/native/kissfft

Release

There's a Gradle task that generates the README.md from template and git tags the current commit with the version number. JitPack builds on push of the tag.

Release steps are:

  1. Bump version in noise/build.gradle
  2. Run ./gradlew release in project root (generates readme)
  3. Push generated readme changes to repo
  4. Wait for JitPack to build

License

Noise is licensed under the Apache 2.0.
Kissfft is licensed under the Revised BSD License.