# FFT library in android Sdk [closed]

10.7k Views

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.

• 1
• 1
• What are x and y parameters to fft function? I understand that the input samples should go in the x array, but what's the purpose of y?
• 1
• @Pompair looks like the y array is output table.
• It's like we're having here an iconic "how not to write code" example. One-character variables, useless comments, absolutely no explanations on what is actually happening.
• To finally answer what the array y means: it's the imaginary part of the usually complex input to an FFT. In case of real numbered input the array y has to be filled with 0 prior to each call of fft(). And also a final note concerning licensing: This code is almost identical to the standard implementation of the Cooley/Tukey algorithm from the mid-1960s (e.g. published in "Numerical Recipies in C" as four1.c).

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=x^2+y^2.

Complete explanation: FFT is complex transform, it takes N complex numbers and produces N complex numbers. So x is the real part of the first number, y 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=x^2+y^2.

Also it's important to notice that the Fourier transform, when applied over real numbers, result in symmetrical result (x==x[x.lenth-1]). The data at x[x.length/2] have the data from frequency f=0Hz. x==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 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

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.

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.

@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 a2 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.

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'
}
``````

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)

``````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;
}
``````