What output should I see from getFft?

Question

Ok, so I'm working on creating an Android visualization application. The problem is that I get the form of the getFft () method, not a jive with what, according to Google, should produce. I traced the source code to C ++, but I am not familiar enough with C ++ or FFT to understand what is going on.

I will try to include everything I need here:

(Java) Visualizer.getFft (byte [] fft)

/** * Returns a frequency capture of currently playing audio content. The capture is a 8-bit * magnitude FFT. Note that the size of the FFT is half of the specified capture size but both * sides of the spectrum are returned yielding in a number of bytes equal to the capture size. * {@see #getCaptureSize()}. * <p>This method must be called when the Visualizer is enabled. * @param fft array of bytes where the FFT should be returned * @return {@link #SUCCESS} in case of success, * {@link #ERROR_NO_MEMORY}, {@link #ERROR_INVALID_OPERATION} or {@link #ERROR_DEAD_OBJECT} * in case of failure. * @throws IllegalStateException */ public int getFft(byte[] fft) throws IllegalStateException { synchronized (mStateLock) { if (mState != STATE_ENABLED) { throw(new IllegalStateException("getFft() called in wrong state: "+mState)); } return native_getFft(fft); } } 

(C ++) Visualizer.getFft (uint8_t * fft)

 status_t Visualizer::getFft(uint8_t *fft) { if (fft == NULL) { return BAD_VALUE; } if (mCaptureSize == 0) { return NO_INIT; } status_t status = NO_ERROR; if (mEnabled) { uint8_t buf[mCaptureSize]; status = getWaveForm(buf); if (status == NO_ERROR) { status = doFft(fft, buf); } } else { memset(fft, 0, mCaptureSize); } return status; } 

(C ++) Visualizer.doFft (uint8_t * fft, uint8_t * waveform)

 status_t Visualizer::doFft(uint8_t *fft, uint8_t *waveform) { int32_t workspace[mCaptureSize >> 1]; int32_t nonzero = 0; for (uint32_t i = 0; i < mCaptureSize; i += 2) { workspace[i >> 1] = (waveform[i] ^ 0x80) << 23; workspace[i >> 1] |= (waveform[i + 1] ^ 0x80) << 7; nonzero |= workspace[i >> 1]; } if (nonzero) { fixed_fft_real(mCaptureSize >> 1, workspace); } for (uint32_t i = 0; i < mCaptureSize; i += 2) { fft[i] = workspace[i >> 1] >> 23; fft[i + 1] = workspace[i >> 1] >> 7; } return NO_ERROR; } 

(C ++) fixedfft.fixed_fft_real (int n, int32_t * v)

 void fixed_fft_real(int n, int32_t *v) { int scale = LOG_FFT_SIZE, m = n >> 1, i; fixed_fft(n, v); for (i = 1; i <= n; i <<= 1, --scale); v[0] = mult(~v[0], 0x80008000); v[m] = half(v[m]); for (i = 1; i < n >> 1; ++i) { int32_t x = half(v[i]); int32_t z = half(v[n - i]); int32_t y = z - (x ^ 0xFFFF); x = half(x + (z ^ 0xFFFF)); y = mult(y, twiddle[i << scale]); v[i] = x - y; v[n - i] = (x + y) ^ 0xFFFF; } } 

(C ++) fixedfft.fixed_fft (int n, int32_t * v)

 void fixed_fft(int n, int32_t *v) { int scale = LOG_FFT_SIZE, i, p, r; for (r = 0, i = 1; i < n; ++i) { for (p = n; !(p & r); p >>= 1, r ^= p); if (i < r) { int32_t t = v[i]; v[i] = v[r]; v[r] = t; } } for (p = 1; p < n; p <<= 1) { --scale; for (i = 0; i < n; i += p << 1) { int32_t x = half(v[i]); int32_t y = half(v[i + p]); v[i] = x + y; v[i + p] = x - y; } for (r = 1; r < p; ++r) { int32_t w = MAX_FFT_SIZE / 4 - (r << scale); i = w >> 31; w = twiddle[(w ^ i) - i] ^ (i << 16); for (i = r; i < n; i += p << 1) { int32_t x = half(v[i]); int32_t y = mult(w, v[i + p]); v[i] = x - y; v[i + p] = x + y; } } } } 

If you made it through all this, you are amazing! So my problem is when I call the java getFft () method, I get negative values ​​that should not exist if the returned array is intended to represent a value. So my question is: what do I need to do so that the array represents a value?

EDIT: It looks like my data may actually be Fourier coefficients. I poked on the net and found this . The "Start Function FFT" applet displays a graphical representation of the coefficients, and this is a nice picture of what happens when I draw data from getFft (). So, a new question: is this my data? and if so, how do I go from coefficients to spectral analysis?

Answer 1

FFT does not only produce magnitude; it also produces a phase (the output for each sample is a complex number). If you need a value, then you need to explicitly calculate it for each output sample, like re*re + im*im , where re and im are the real and imaginary components of each complex number, respectively.

<y> Unfortunately, I don’t see anywhere in your code where you work with complex numbers, so you may need to rewrite it. C>

UPDATE

If I had to guess (after looking at the code), I would say that the real components were with even indices, and the odd components were with odd indices. To get the values ​​you need to do something like:

 uint32_t mag[N/2]; for (int i = 0; i < N/2; i++) { mag[i] = fft[2*i]*fft[2*i] + fft[2*i+1]*fft[2*i+1]; } 

Answer 2

Possible explanation of why you see negative values: byte is a data type signed in Java. All values ​​greater 1000 0000 or equal to 1000 0000 ₂ are interpreted as negative integers.

If we know that it is expected that all values ​​will be in the range [0..255] , then we will compare the values ​​with a larger type and filter the upper bits:

 byte signedByte = 0xff; // = -1 short unsignedByte = ((short) signedByte) & 0xff; // = 255 

Answer 3

“Capture is an FFT with an 8-bit value,” probably means that the return values ​​have an 8-bit value, not the values ​​themselves.

According to Jason

For real signals, such as you have sound processing, a negative output will mirror the positive frequencies.

Android 2.3 Visualizer - understanding getFft () problems