FFT library in android Sdk

Question

I am working with android project.I need FFT algorithm to process the android accelerometer data.Is there FFT library available in android sdk?

Answer 1

You can use this class, which is fast enough for real time audio analysis

public class FFT {

  int n, m;

  // Lookup tables. Only need to recompute when size of FFT changes.
  double[] cos;
  double[] sin;

  public FFT(int n) {
      this.n = n;
      this.m = (int) (Math.log(n) / Math.log(2));

      // Make sure n is a power of 2
      if (n != (1 << m))
          throw new RuntimeException("FFT length must be power of 2");

      // precompute tables
      cos = new double[n / 2];
      sin = new double[n / 2];

      for (int i = 0; i < n / 2; i++) {
          cos[i] = Math.cos(-2 * Math.PI * i / n);
          sin[i] = Math.sin(-2 * Math.PI * i / n);
      }

  }

  public void fft(double[] x, double[] y) {
      int i, j, k, n1, n2, a;
      double c, s, t1, t2;

      // Bit-reverse
      j = 0;
      n2 = n / 2;
      for (i = 1; i < n - 1; i++) {
          n1 = n2;
          while (j >= n1) {
              j = j - n1;
              n1 = n1 / 2;
          }
          j = j + n1;

          if (i < j) {
              t1 = x[i];
              x[i] = x[j];
              x[j] = t1;
              t1 = y[i];
              y[i] = y[j];
              y[j] = t1;
          }
      }

      // FFT
      n1 = 0;
      n2 = 1;

      for (i = 0; i < m; i++) {
          n1 = n2;
          n2 = n2 + n2;
          a = 0;

          for (j = 0; j < n1; j++) {
              c = cos[a];
              s = sin[a];
              a += 1 << (m - i - 1);

              for (k = j; k < n; k = k + n2) {
                  t1 = c * x[k + n1] - s * y[k + n1];
                  t2 = s * x[k + n1] + c * y[k + n1];
                  x[k + n1] = x[k] - t1;
                  y[k + n1] = y[k] - t2;
                  x[k] = x[k] + t1;
                  y[k] = y[k] + t2;
              }
          }
      }
  }
}

Warning: this code appears to be derived from here, and has a GPLv2 license.

Answer 2

Using the class at: https://www.ee.columbia.edu/~ronw/code/MEAPsoft/doc/html/FFT_8java-source.html

Short explanation: call fft() providing x as you amplitude data, y as all-zeros array, after the function returns your first answer will be a[0]=x[0]^2+y[0]^2.

Complete explanation: FFT is complex transform, it takes N complex numbers and produces N complex numbers. So x[0] is the real part of the first number, y[0] is the complex part. This function computes in-place, so when the function returns x and y will have the real and complex parts of the transform.

One typical usage is to calculate the power spectrum of audio. Your audio samples only have real part, you your complex part is 0. To calculate the power spectrum you add the square of the real and complex parts P[0]=x[0]^2+y[0]^2.

Also it's important to notice that the Fourier transform, when applied over real numbers, result in symmetrical result (x[0]==x[x.lenth-1]). The data at x[x.length/2] have the data from frequency f=0Hz. x[0]==x[x.length-1] has the data for a frequency equals to have the sampling rate (eg if you sampling was 44000Hz than it means f[0] refeers to 22kHz).

Full procedure:

1. create array p[n] with 512 samples with zeros
2. Collect 1024 audio samples, write them on x
3. Set y[n]=0 for all n
4. calculate fft(x,y)
5. calculate p[n]+=x[n+512]^2+y[n+512]^2 for all n=0 to 512
6. to go 2 to take another batch (after 50 batches go to next step)
7. plot p
8. go to 1

Than adjust the fixed number for your taste.

The number 512 defines the sampling window, I won't explain it. Just avoid reducing it too much.

The number 1024 must be always the double of the last number.

The number 50 defines you update rate. If your sampling rate is 44000 samples per second you update rate will be: R=44000/1024/50 = 0.85 seconds.

Answer 3

kissfft is a decent enough library that compiles on android. It has a more versatile license than FFTW (even though FFTW is admittedly better).

You can find an android binding for kissfft in libgdx https://github.com/libgdx/libgdx/blob/0.9.9/extensions/gdx-audio/src/com/badlogic/gdx/audio/analysis/KissFFT.java

Or if you would like a pure Java based solution try jTransforms https://sites.google.com/site/piotrwendykier/software/jtransforms

Answer 4

Use this class (the one that EricLarch's answer is derived from).

Usage Notes

This function replaces your inputs arrays with the FFT output.

Input

• N = the number of data points (the size of your input array, must be a power of 2)
• X = the real part of your data to be transformed
• Y = the imaginary part of the data to be transformed

i.e. if your input is (1+8i, 2+3j, 7-i, -10-3i)

• N = 4
• X = (1, 2, 7, -10)
• Y = (8, 3, -1, -3)

Output

• X = the real part of the FFT output
• Y = the imaginary part of the FFT output

To get your classic FFT graph, you will want to calculate the magnitude of the real and imaginary parts.

Something like:

public double[] fftCalculator(double[] re, double[] im) {
    if (re.length != im.length) return null;
    FFT fft = new FFT(re.length);
    fft.fft(re, im);
    double[] fftMag = new double[re.length];
    for (int i = 0; i < re.length; i++) {
       fftMag[i] = Math.pow(re[i], 2) + Math.pow(im[i], 2);
    }
    return fftMag;
}

Also see this StackOverflow answer for how to get frequencies if your original input was magnitude vs. time.

Answer 5

Yes, there is the JTransforms that is maintained on github here and avaiable as a Maven plugin here.

Use with:

compile group: 'com.github.wendykierp', name: 'JTransforms', version: '3.1'

But with more recent, Gradle versions you need to use something like:

dependencies {
    ... 
    implementation 'com.github.wendykierp:JTransforms:3.1'
}

Answer 6

@J Wang Your output magnitude seems better than the answer given on the thread you have linked however that is still magnitude squared ... the magnitude of a complex number

z = a + ib

is calculated as

|z|=sqrt(a^2+b^2)

the answer in the linked thread suggests that for pure real inputs the outputs should be using a² or a for the output because the values for

a_(i+N/2) = -a_(i),

with b_(i) = a_(i+N/2) meaning the complex part in their table is in the second half of the output table.

i.e the second half of the output table for an input table of reals is the conjugate of the real ...

so z = a-ia giving a magnitude

|z|=sqrt(2a^2) = sqrt(2)a

so it is worth noting the scaling factors ... I would recommend looking all this up in a book or on wiki to be sure.

Answer 7

Unfortunately the top answer only works for Array that its size is a power of 2, which is very limiting.

I used the Jtransforms library and it works perfectly, you can compare it to the function used by Matlab.

here is my code with comments referencing how matlab transforms any signal and gets the frequency amplitudes (https://la.mathworks.com/help/matlab/ref/fft.html)

first, add the following in the build.gradle (app)

implementation 'com.github.wendykierp:JTransforms:3.1'

and here it is the code for for transforming a simple sine wave, works like a charm

    double Fs = 8000;
    double T = 1/Fs;
    int L = 1600;

    double freq = 338;

    double sinValue_re_im[] = new double[L*2]; // because FFT takes an array where its positions alternate between real and imaginary
    for( int i = 0; i < L; i++)
    {
        sinValue_re_im[2*i] = Math.sin( 2*Math.PI*freq*(i * T) ); // real part
        sinValue_re_im[2*i+1] = 0; //imaginary part
    }

    // matlab
    // tf = fft(y1);

    DoubleFFT_1D fft = new DoubleFFT_1D(L);
    fft.complexForward(sinValue_re_im);
    double[] tf = sinValue_re_im.clone();

    // matlab
    // P2 = abs(tf/L);
    double[] P2 = new double[L];
    for(int i=0; i<L; i++){

        double re = tf[2*i]/L;
        double im = tf[2*i+1]/L;
        P2[i] = sqrt(re*re+im*im);
    }

    // P1 = P2(1:L/2+1);
    double[] P1 = new double[L/2]; // single-sided: the second half of P2 has the same values as the first half
    System.arraycopy(P2, 0, P1, 0, L/2);
    // P1(2:end-1) = 2*P1(2:end-1);
    System.arraycopy(P1, 1, P1, 1, L/2-2);
    for(int i=1; i<P1.length-1; i++){
        P1[i] = 2*P1[i];
    }
    // f = Fs*(0:(L/2))/L;
    double[] f = new double[L/2 + 1];
    for(int i=0; i<L/2+1;i++){
        f[i] = Fs*((double) i)/L;
    }