0

I've been trying to find a simple implementation of DFT (or FFT) that results in a peak frequency. However, most implementations I've seen output an array of complex numbers. How does one convert those radix-2 results into a concrete frequency?

For example, the input data I have is a 16 samples of a sine wave function that oscillates between 500 - 2000Hz, like this:

int n = 16;    
double[] input = { 1250, 1537, 1780, 1943, 2000, 1943, 1780, 1537,
            1250, 963, 720, 557, 500, 557, 720, 963 };

Now, I'd assume that the peak frequency from this would be exactly 750 Hz, because (2000 - 500) / 2 = 750.

I'm thinking my sampling rate Fs = 2000 Hz because that is the high limit of oscillation where I'm limiting the sine to. The centre frequency for each bin k is defined as k * Fs / n, therefore my bins are 125 Hz, 250 Hz, 375 Hz, 500 Hz, 625 Hz and 750 Hz. But because my low limit of oscillation was 500 Hz, I'm assuming I need to offset the bins with 500 Hz, thus they become: 750 Hz, 825 Hz, 1000 Hz, 1125 Hz, 1250 Hz, 1375 Hz, 1500 Hz.

Then using jtransforms' DoubleFFT_1D class, I'm getting some FFT data:

DoubleFFT_1D fft = new DoubleFFT_1D(n);
fft.realForward(input);

input variable now contains:

[20000.0, 0.0, -4.547473508864641E-13, -5999.381020591891, 0.0, 0.0, -1.6292522886374172E-14, 1.1183950775908065, 0.0, -0.0, 1.6292522886374172E-14, -0.7488526914476931, 0.0, 0.0, 4.547473508864641E-13, -1.2482683609296146]

Grouping the array values to more understandable form (in light of some information I got elsewhere in SO):

20000.0                                         [sum of input array values]
0.0,                                            [1625 Hz]
-4.547473508864641E-13, -5999.381020591891,     [re1 and im1] [750 Hz]
0.0, 0.0,                                       [re2 and im2] [875 Hz]
-1.6292522886374172E-14, 1.1183950775908065,    [re3 and im3] [1000 Hz]
0.0, -0.0,                                      [re4 and im4] [1125 Hz]
1.6292522886374172E-14, -0.7488526914476931,    [re5 and im5] [1250 Hz]
0.0, 0.0,                                       [re6 and im6] [1375 Hz]
4.547473508864641E-13, -1.2482683609296146      [re7 and im7] [1500 Hz]

Two questions:

  1. Are my assumption regarding the frequency bins correct?
  2. How would I now get the peak frequency from this data by summing up some magnitudes?

Thanks.

Community
  • 1
  • 1
Pompair
  • 7,083
  • 11
  • 60
  • 69

3 Answers3

1

By definition, the output values of your FFT are not the frequencies; the variables (i.e. the axes on the graph) are the frequencies. What you will want to do is find the magnitude of the complex results to get an absolute value, but these aren't frequencies - instead, the x value which yields the largest peak is the frequency you want.

In case you are unsure, the magnitude of a complex number is described on Wikipedia. It is simply the square root of the sum of squares of the real and complex parts, however for finding the maximum you obviously don't need to compute the square root.

devrobf
  • 6,973
  • 2
  • 32
  • 46
1

It's true that once you've figured out the frequencies of your bins, the frequency of the bin with the highest magnitude is close to the peak. But you can do quite a bit better by interpolating. Your peak will almost always be between bins. This site appears to have several good ways to interpolate: http://www.dspguru.com/dsp/howtos/how-to-interpolate-fft-peak

Georgie
  • 2,448
  • 2
  • 17
  • 13
0

For each frequency bin, you should have two values, real (x) and imaginary (y) The sum of squares will give you the magnitude at that frequency:

magnitude = sqrt(x*x + y*y);

Although if you only want to find the peak, you don't need the square root, just find the frequency with the highest

magSquared = x*x + y*y
Neil Townsend
  • 6,024
  • 5
  • 35
  • 52