32

I have recorded an array[1024] of data from my mic on my Android phone, passed it through a 1D forward DFT of the real data (setting a further 1024 bits to 0). I saved the array to a text file, and repeated this 8 times.

I got back 16384 results. I opened the text file in Excel and made a graph to see what it looked like(x=index of array, y=size of number returned). There are some massive spikes (both positive and negative) in magnitude around 110, 232, and small spikes continuing in that fashion until around 1817 and 1941 where the spikes get big again, then drop again.

My problem is that wherever I look for help on the topic it mentions gettng the real and imaginary numbers, I only have a 1D array, that I got back from the method I used from Piotr Wendykier's class:

DoubleFFT_1D.realForwardFull(audioDataArray); // from the library JTransforms.

My question is: What do I need to do to this data to return a frequency? The sound recorded was me playing an 'A' on the bottom string (5th fret) of my guitar (at roughly 440Hz) .

Paul R
  • 208,748
  • 37
  • 389
  • 560
Ben Taliadoros
  • 7,003
  • 15
  • 60
  • 97
  • I thought we covered this in your previous question: [JTransforms FFT in Android from PCM data](http://stackoverflow.com/questions/7649003/jtransforms-fft-in-android-from-pcm-data) ? – Paul R Oct 06 '11 at 13:42
  • I'm wondering what of the results I should be looking at, do I need further calculating? Surely everything would have been handled inside the realFullForward() method? I followed the code through in his class but struggled to see what he was doing to the data (no comments, methods named strangley etc). – Ben Taliadoros Oct 06 '11 at 13:49
  • You haven't actually said what you are trying to achieve, or what the nature of the input signal is, but the FFT is usually just one step in the process, e.g. of generating a power spectrum or spectrogram. – Paul R Oct 06 '11 at 13:54
  • @hotpaw2 also answered this in another of your previous, similar questions: http://stackoverflow.com/questions/7651633/using-fft-in-android - you do actually *read* the answers that people give you, I hope ? – Paul R Oct 06 '11 at 13:55
  • Of course I do but I was confused by the idea I was finding Magnitude, relating that to frequency. – Ben Taliadoros Oct 06 '11 at 14:07
  • Better to ask for clarification in the original question than just keep re-posting the same question over and over again. – Paul R Oct 06 '11 at 14:08
  • Then could you answer in this post below where I have asked for clarification please? – Ben Taliadoros Oct 06 '11 at 14:39
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/4068/discussion-between-ben-taliadoros-and-paul-r) – Ben Taliadoros Oct 06 '11 at 14:51

1 Answers1

53

The complex data is interleaved, with real components at even indices and imaginary components at odd indices, i.e. the real components are at index 2*i, the imaginary components are at index 2*i+1.

To get the magnitude of the spectrum at index i, you want:

re = fft[2*i];
im = fft[2*i+1];
magnitude[i] = sqrt(re*re+im*im);

Then you can plot magnitude[i] for i = 0 to N / 2 to get the power spectrum. Depending on the nature of your audio input you should see one or more peaks in the spectrum.

To get the approximate frequency of any given peak you can convert the index of the peak as follows:

freq = i * Fs / N;

where:

freq = frequency in Hz
i = index of peak
Fs = sample rate in Hz (e.g. 44100 Hz, or whatever you are using)
N = size of FFT (e.g. 1024 in your case)

Note: if you have not previously applied a suitable window function to the time-domain input data then you will get a certain amount of spectral leakage and the power spectrum will look rather "smeared".

To expand on this further, here is pseudo-code for a complete example where we take audio data and identify the frequency of the largest peak:

N = 1024          // size of FFT and sample window
Fs = 44100        // sample rate = 44.1 kHz
data[N]           // input PCM data buffer
fft[N * 2]        // FFT complex buffer (interleaved real/imag)
magnitude[N / 2]  // power spectrum

// capture audio in data[] buffer
// ...

// apply window function to data[]
// ...

// copy real input data to complex FFT buffer
for i = 0 to N - 1
  fft[2*i] = data[i]
  fft[2*i+1] = 0

// perform in-place complex-to-complex FFT on fft[] buffer
// ...

// calculate power spectrum (magnitude) values from fft[]
for i = 0 to N / 2 - 1
  re = fft[2*i]
  im = fft[2*i+1]
  magnitude[i] = sqrt(re*re+im*im)

// find largest peak in power spectrum
max_magnitude = -INF
max_index = -1
for i = 0 to N / 2 - 1
  if magnitude[i] > max_magnitude
    max_magnitude = magnitude[i]
    max_index = i

// convert index of largest peak to frequency
freq = max_index * Fs / N
Paul R
  • 208,748
  • 37
  • 389
  • 560
  • 1
    Thanks so much Paul, I see where that was in previous answers now, I got to run some tests now! thanks – Ben Taliadoros Oct 06 '11 at 13:55
  • by index of peak, do you mean the index of the output array, where the peak in the graph lies? – Ben Taliadoros Oct 06 '11 at 14:08
  • For the code above the index will be the index of the `magnitude` array. – Paul R Oct 06 '11 at 14:10
  • is the magnitude array the one I had returned after putting it through the 1D forward DFT? – Ben Taliadoros Oct 06 '11 at 14:13
  • of do i loop through the array, using index n(even) as real and index n+1 as imaginary, then do sqrt(re*re+im*im) and end up with an array half the size? – Ben Taliadoros Oct 06 '11 at 14:16
  • 1
    Yes, you only want N/2 magnitudes, from N/2 complex values. – Paul R Oct 06 '11 at 15:00
  • 1
    And no, the `fft` array in the example above is the output of your FFT routine. The `magnitude` array is a second array in which you are calculating the magnitudes from the complex FFT output values. – Paul R Oct 06 '11 at 15:01
  • Ok so I understand that for the outputted array data, i take the first two values, i square them, add them together and put them in array magnitude[], lets say. then i take each index of that and multiply each value by sample rate/1024. – Ben Taliadoros Oct 06 '11 at 15:07
  • then will the final array include frequency data? – Ben Taliadoros Oct 06 '11 at 15:08
  • No - you don't need to do that - if you just want to identify the frequency of one or more peaks then you can iterate through the `magnitude` array looking for peak values, and for those peaks you can translate the index `i` of the peak to a frequency using the formula above. – Paul R Oct 06 '11 at 15:13
  • Note - it would *really* help if you took the time to explain what is is that you want to ultimately achieve with your frequency data - e.g. if it's yet another guitar tuner app then you want to do *pitch detection*. – Paul R Oct 06 '11 at 15:15
  • It would use the same function, but its not yet another Tuner. I am making a game which requires a guitarist to hit a particular note at a particular time. Does this change things? – Ben Taliadoros Oct 06 '11 at 15:40
  • Yes it changes things somewhat because what you really want to do is *pitch detection*. There are lots of previous questions on pitch detection on SO already so I suggest you have a read of some of them. You *might* get away with an FFT-based approach for this, but it's not ideal. – Paul R Oct 06 '11 at 15:59
  • in my fft array I have the first half as pcm data then the second as 0's. That was advice from Piotr, the guy who wrote the library. In your pseudo code it looks like they would alternately be [pcm[0]. 0, pcm[1], 0, ... pcm[n], 0]. does this difference matter? – Ben Taliadoros Oct 06 '11 at 16:03
  • My understanding from one of your earlier questions was that the data is supposed to be interleaved real/imag, but if that's not the case then sure, organise it however it needs to be ordered for this particular FFT implementation. – Paul R Oct 06 '11 at 16:04
  • ok sure, so will magnitude[] just be filled with the output from the transform? since i put in 2048 (the last 1024 being all 0's) and got back 2048 numbers all different from those that went in? – Ben Taliadoros Oct 06 '11 at 16:17
  • You get 1024 *complex* values out, so that's 2048 floats. – Paul R Oct 06 '11 at 16:28
  • so my code should differ to yours in this respect: // calculate power spectrum (magnitude) values from fft[] for i = 0 to N / 2 - 1 re = fft[i] im = fft[N/2+i] magnitude[i] = sqrt(re*re+im*im) Because my 0's are all at the end of the array. (BTW thanks for all this help, I really appreciate it) – Ben Taliadoros Oct 06 '11 at 16:32
  • Yes - I don't know the specifics of the FFT that you are using so the ordering of the input and output data will depend on how it's implemented - make sure you have this exactly right though otherwise you will get very confusing results. – Paul R Oct 06 '11 at 17:04
  • Paul. Your explanation is amazingly clear. If I understand, the output of fft() is always arranged in increasing order of frequency. Is this correct? – Peter Dec 07 '13 at 01:54
  • @Peter: not always (e.g. sometimes the output order is "scrambled", i.e. in bit-reversed index order), but most commonly yes. See also: http://stackoverflow.com/questions/4364823/how-to-get-frequency-from-fft-result/4371627#4371627 – Paul R Dec 07 '13 at 07:09
  • @Paul R, I am going through the same issue and I read all the related threads. I am just not sure if I should use RealForward or RealForwardFull or ComplexForward ? any help? – Snake Jul 16 '14 at 06:52
  • @Snake: choice of transform depends on your data and what you want to to do with it. Is your input data purely real (if it's a "real world" signal of some kind then it probably is) ? And what do you want to do with your frequency domain data ? – Paul R Jul 16 '14 at 06:54
  • @Paul R, Yes Data is real and does not have any imaginary values. Similar to the PCM you are talking about above. So if I have the real data in an array. 1) Which method I need to use? 2) Do I pass the array to the FFT as is? – Snake Jul 16 '14 at 06:57
  • And I want to get the frequency corresponding to the highest power – Snake Jul 16 '14 at 06:58
  • In that case I would just use the `float` version of `realForward`: http://wendykierp.github.io/JTransforms/apidocs/org/jtransforms/fft/FloatFFT_1D.html#realForward-float:A- – Paul R Jul 16 '14 at 08:35
  • @Paul R, Thank you. So it is realForward not realForwardFull right? And then I proceed to calculate the magnitude of the power like you mentioned above int he suggested soluton. Also if my data array is of size N. Do I just pass it as is to the method or should I double the size of the array? – Snake Jul 16 '14 at 17:52
  • For realForward you pass in N data points and get N/2 complex output points. – Paul R Jul 17 '14 at 05:39