I think I have a bug in my understanding of the complex FFT and it's leading me to get half of my expected frequency.

I'm trying to calculate the frequency of an input signal of known frequency (440Hz) using the FFT. My sampling rate is 8kHz, which is well above the Nyquist rate, and I'm using an analog filter with a knee at 4kHz. I toggle a pin on each sample and measure with the oscilloscope, so I know it's sampling at 8kHz. (maybe I am wrong there?)

EDIT: I have the same results for triangular, square, and sinusoidal inputs. They are created by a 555-Timer and are completely positive (ranging from 0-5V) with a DC offset of around 2.5. Here is an example of the (more-or-less) triangular input (after sampling):

{"2560", "2C00", "3390", "3970", "4000", "4610", "4C30", "51A0", \ "5700", "5C70", "61D0", "65E0", "6BD0", "70A0", "7500", "7980", \ "7DF0", "7FF0", "78C0", "6860", "59E0", "4BC0", "3FE0", "3370", \ "2880", "1E10", "1450", "0AA0", "0230", "01B0", "0A50", "1200", \ "1A10", "2140", "28A0", "2F50", "3650", "3C40", "4300", "4870", \ "4EC0", "5400", "59B0", "5EF0", "6400", "6900", "6DF0", "72A0", \ "7720", "7B70", "7FC0", "7FF0", "7130", "61A0", "53A0", "46A0", \ "3A30", "2E80", "23B0", "1950", "0FE0", "06E0", "FE50", "0540", \ "0D80", "1590", "1D30", "2480", "2BA0", "3230", "3900", "3ED0", \ "4550", "4B60", "5130", "5650", "5C20", "6100", "65D0", "6B30", \ "6FE0", "7480", "7910", "7D30", "7FF0", "7AD0", "6AD0", "5BC0", \ "4E30", "4170", "34F0", "29C0", "1F50", "1550", "0BF0", "0370", \ "0040", "08E0", "1150", "18B0", "2020", "2780", "2E30", "3530", \ "3B40", "4190", "47B0", "4DA0", "5370", "58C0", "5E20", "62D0", \ "6910", "6CD0", "74C0", "7650", "7B30", "7EA0", "7FF0", "73F0", \ "6470", "5600", "47F0", "3BD0", "3000", "2530", "1B30", "1120", \ "08B0", "FFD0", "04C0", "0C80", "1490", "1C40", "2340", "2A70", \ "3140", "3760", "3E10", "4470", "4A20", "4FF0", "55F0", "5B70", \ "6000", "65B0", "6AA0", "6F00", "7410", "7820", "7CF0", "7FF0", \ "7DF0", "6D00", "5E20", "5030", "4340", "3680", "2B80", "20F0", \ "1740", "0D80", "04F0", "FC70", "0780", "0FB0", "17B0", "1F40", \ "2650", "2D30", "3410", "3A60", "4100", "46F0", "4CD0", "5290", \ "5860", "5D10", "6300", "6790", "6C80", "7200", "75F0", "7A40", \ "7EC0", "7FF0", "75D0", "6640", "57B0", "4A60", "3D80", "30B0", \ "22E0", "1CA0", "12D0", "09F0", "0120", "0290", "0B40", "1350", \ "1B40", "2230", "2970", "3000", "3700", "3D70", "4360", "4940", \ "4F50", "5490", "5A40", "5F70", "64B0", "69C0", "6EB0", "72F0", \ "77C0", "7BD0", "7FF0", "7FF0", "6FC0", "60B0", "52A0", "4550", \ "3930", "2D90", "22C0", "18A0", "0F50", "0640", "FE00", "0600", \ "0E60", "1600", "1DD0", "2510", "2C20", "3270", "3970", "3F80", \ "45B0", "4B90", "5170", "56C0", "5C80", "61A0", "66A0", "6B80", \ "70A0", "74D0", "7960", "7DA0", "7FF0", "7900", "69A0", "5A70"}

Triangular input after normalizing to 1.

I set a breakpoint after the ADC has collected all 256 points, and when I graph it one cycle takes around 17 points (ACTUALLY 33). Each point is 1/8000=.000125s, so one period is .004125 , which gives me 242Hz. Not perfect, but also not the cause of my problem. (Edited: I read the period incorrectly. Therefore, the FFT data is correct, but the sampling only gets either half the data or is somehow sampling too slowly. Any ideas?)

If I run an FFT on these datapoints in Mathematica, I get that the 8th bin has the greatest magnitude, which would give a frequency of 8*(8000/256) = 250Hz and half of what I expect. (well, more than half, but the frequency resolution is about 31.25 Hz/bin)

I take the 256 data points and plug them into the first half of a 256-point fractional complex array in the microcontroller. Then I reorder the data so that they are every other point in the array, and fill in 0's for the complex values. Then I run the FFT from the Microchip library and also get bin 8.

Am I using the complex FFT or the bin number incorrectly? If so, could someone please explain where I'm going astray?

EDIT: The following picture is referenced in a comment to Peter K's answer. Complex_DFT_visual

  • 1
    $\begingroup$ Is your input a pure Sinusoid? Can you share your input signal? $\endgroup$
    – Oliver
    Jul 3 '15 at 4:03
  • $\begingroup$ Are you reading two channels on oscilloscope? One I and one Q, only then you are working with a complex input. Otherwise it is just real valued signal and will not give the expected. $\endgroup$
    – learner
    Jul 3 '15 at 20:56
  • $\begingroup$ @Oliver I added the input. $\endgroup$
    – MrUser
    Jul 8 '15 at 19:32
  • $\begingroup$ @learner I and Q on the oscilloscope? From all that I've read, one can add all the data into the real values and set all the complex values to 0. Should I use the Real FFT instead? $\endgroup$
    – MrUser
    Jul 8 '15 at 19:33
  • $\begingroup$ In your plot, I can't see a period of 17 points. Apart from that strange artifact at around index 60, I'd say the period is about 30, i.e. a fundamental frequency of about 267 Hz. $\endgroup$
    – Matt L.
    Jul 9 '15 at 13:19

Your problem is this calculation:


If the bin number is 8, then the frequency of that bin will be 8*(8000/128).

Why? Because the maximum frequency that sampling at 8kHz can show (without aliasing) is 4kHz. So the bin at about N/2 (where N is the number of points in your FFT) will correspond to half the sampling frequency...

The bin at N=256 will correspond to a frequency of -8000/256.

  • $\begingroup$ Using the pic of the ComDFT that I added to my question, if the Re and Im arrays are each N=256 and they are processed IN PLACE, then after the FFT the first 128 elements of each will contain the magnitudes, and these are then squared, summed to the respective element in the complementary array, then rooted to find the 128 magnitudes. So now I have 256 total values, but only the first 128 are useful (because the second half contains the neg freq.) Is that right? Then the last usable value (N/2) should correspond to 4k. Then shouldn't each bin be 4000/128? Thanks for the help. $\endgroup$
    – MrUser
    Jul 9 '15 at 11:35
  • $\begingroup$ I don't think that's right, the FFT bins extend up to the sampling frequency, because you could have complex-valued data with no symmetry in the frequency domain. See also this answer. $\endgroup$
    – Matt L.
    Jul 9 '15 at 11:36
  • $\begingroup$ @MattL. Which is not right? What PeterK. said or my comment? The trouble I'm having here is deciding what exactly N is in the bin calculation fi = i*fs/N since it seems to change in the Complex FFT. The image gives the impression that the Freq domain actually gives 8k at the 128th element (N/2), which would align with PeterK's answer and explain my error. Is it correct though? $\endgroup$
    – MrUser
    Jul 9 '15 at 11:44
  • $\begingroup$ @MrUser: My comment referred to Peter's answer. $N$ is the FFT length, i.e. the number of time domain points over which you compute the sum, which is the same as the number of frequency bins you get. For real-valued time-domain data the frequency bins are symmetric, so you can throw away (approximately) half of them. $\endgroup$
    – Matt L.
    Jul 9 '15 at 11:47
  • $\begingroup$ @MattL. So you're saying that N/2 (128th element) of the frequency arrays should be 4k, and each bin frequency is 8000/256, not 8k with each bin having a density of 8000/128? The N doesn't somehow "change" in the complex DFT, right? (I only say that, because in this case N in the pic above could also just refer to the array size.) $\endgroup$
    – MrUser
    Jul 9 '15 at 12:01

Dumb mistake. I was toggling the pin at 8kHz, which means the sample rate was double that of the pin oscillations. (pin high + pin low = 2 samples, but one pin period.) The FFT and ADC config except the sample rate were actually correct the whole time.

Thank you for all the help. Unfortunately, I have too few reputation points to give anybody an upvote.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.