Fast Fourier Analysis

Discussion in 'Math' started by KCHARROIS, May 13, 2013.

  1. KCHARROIS

    Thread Starter Member

    Jun 29, 2012
    292
    1
    Hello,

    Recently been looking into making a audio to FFT but I'd like to understand the math alot more before moving on. So say if I have a sine wave signal like the one attached, and I take the same amount of samples it did, twice the max frequency (nyquist) how do you figure the different main frequencies in the signal. Not particularly interested in the harmonics, if theres a full example you guys might know of or would like to help me out figuring the one below that would be great.

    Thanks
     
  2. studiot

    AAC Fanatic!

    Nov 9, 2007
    5,005
    513
    Your pic shows 64 samples over the period which is good for the FFT as you ideally need the number of samples = a power of 2.

    Why would you not want the harmonics? This is what the FFT will give you. You don't need it for the fundamental alone.
     
  3. KCHARROIS

    Thread Starter Member

    Jun 29, 2012
    292
    1
    Sorry, I would like to find the frequencies that are contained in that particular waveform.

    Thanks
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,716
    4,788
    Then take the FFT of the waveform if you want a spectral analysis of it.

    What's the point here? What is it that you are hoping to walk away from this thread having learned?
     
  5. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    Post some values of the 64 points as an example and I will show you what the FFT looks like.
     
  6. KCHARROIS

    Thread Starter Member

    Jun 29, 2012
    292
    1
    My goal is to calculate by hand the frequencies that are withing the signal. Sure I could hook it up to a spectrum analyzer and see the different frequencies but I would like to calculate them by hand. Mr Chip, I've added 64 points containing the voltage and time what do I do next?

    Thanks
     
  7. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    Calculating the FFT by hand is not something I would want to do.
     
  8. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    Sorry, I don't want to spent the time to edit the numbers from your file.
    Please resubmit with just the raw data, no units (V), no other columns.
     
    KCHARROIS likes this.
  9. KCHARROIS

    Thread Starter Member

    Jun 29, 2012
    292
    1
    Here is the updated file.

    Thanks
     
  10. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    Here is the FFT of the data:

    5.4000
    3.6735 + 2.3598i
    5.5301 + 1.8089i
    24.9891 +18.4889i
    -4.4571 - 4.1551i
    -2.9237 - 1.7754i
    -0.8351 - 2.0394i
    0.5287 - 0.7161i
    18.7545 - 0.7450i
    -0.1801 - 0.6023i
    -1.0048 - 0.5298i
    -1.0814 - 0.3137i
    -0.5859 - 0.3834i
    0.1750 + 0.2315i
    0.3741 + 0.3494i
    -0.7541 - 0.5660i
    -0.8000 - 0.9000i
    0.1801 - 1.2694i
    0.2651 + 0.4672i
    -0.1087 - 0.8807i
    1.2193 - 0.5328i
    0.1531 + 0.4608i
    0.6714 - 0.6653i
    0.4180 + 0.0863i
    -0.0545 - 0.2450i
    0.3879 - 0.1258i
    -0.1084 + 0.3079i
    -0.0083 + 0.7581i
    0.4236 + 0.0955i
    0.3731 - 0.6953i
    -0.0922 + 0.0096i
    -0.2222 - 0.6728i
    0.8000
    -0.2222 + 0.6728i
    -0.0922 - 0.0096i
    0.3731 + 0.6953i
    0.4236 - 0.0955i
    -0.0083 - 0.7581i
    -0.1084 - 0.3079i
    0.3879 + 0.1258i
    -0.0545 + 0.2450i
    0.4180 - 0.0863i
    0.6714 + 0.6653i
    0.1531 - 0.4608i
    1.2193 + 0.5328i
    -0.1087 + 0.8807i
    0.2651 - 0.4672i
    0.1801 + 1.2694i
    -0.8000 + 0.9000i
    -0.7541 + 0.5660i
    0.3741 - 0.3494i
    0.1750 - 0.2315i
    -0.5859 + 0.3834i
    -1.0814 + 0.3137i
    -1.0048 + 0.5298i
    -0.1801 + 0.6023i
    18.7545 + 0.7450i
    0.5287 + 0.7161i
    -0.8351 + 2.0394i
    -2.9237 + 1.7754i
    -4.4571 + 4.1551i
    24.9891 -18.4889i
    5.5301 - 1.8089i
    3.6735 - 2.3598i

    Here is the absolute value:

    5.4000
    4.3662
    5.8184
    31.0853
    6.0935
    3.4206
    2.2038
    0.8902
    18.7693
    0.6286
    1.1359
    1.1260
    0.7002
    0.2902
    0.5118
    0.9428
    1.2042
    1.2821
    0.5371
    0.8874
    1.3306
    0.4855
    0.9452
    0.4268
    0.2510
    0.4078
    0.3264
    0.7582
    0.4343
    0.7890
    0.0927
    0.7085
    0.8000
    0.7085
    0.0927
    0.7890
    0.4343
    0.7582
    0.3264
    0.4078
    0.2510
    0.4268
    0.9452
    0.4855
    1.3306
    0.8874
    0.5371
    1.2821
    1.2042
    0.9428
    0.5118
    0.2902
    0.7002
    1.1260
    1.1359
    0.6286
    18.7693
    0.8902
    2.2038
    3.4206
    6.0935
    31.0853
    5.8184
    4.3662

    And here is the plot of the absolute value:

    [​IMG]

    Next comes the interpretation of the results.
     
  11. KCHARROIS

    Thread Starter Member

    Jun 29, 2012
    292
    1
    Great I appreciate you showing me this but how did you get the FFT results and then post them in a graph giving you the frequencies?

    Thanks again
     
  12. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    The data set consists of 64 points. Hence the FFT will be 64 complex numbers.
    Positive frequencies are represented in points 1 to 32.
    Negative frequencies are folded around in points 33 to 64. As you can see the results are the same and hence we can ignore the negative frequencies.

    Next comes the question of scaling on the x-axis.
    There are 32 points, from 0 to 31.
    Your record sample is 16 seconds long. Hence your frequency resolution is 1/16 Hz.
    The first data point in the FFT result is the amplitude at DC = 0Hz.
    The next point is 1/16 Hz.
    The 16th point would be 1Hz.
    The last point would be 31/16 Hz.
     
  13. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    I use MATLAB.

    The code I used in MATLAB is:
    Code ( (Unknown Language)):
    1.  
    2. Y = fft(y);
    3. Z = abs(Y);
    4. plot(Z)
    5.  
     
  14. KCHARROIS

    Thread Starter Member

    Jun 29, 2012
    292
    1
    So its safe to assume that calculating these values are quite complex and doing this with a pic microcontroller in assembly language using basic opcodes will be even more complex. I saw on the web a bunch of people giving out the code to this over audio so I though it be fun to do it myself maybe I'll just try implementing a bunch of bandpass filter then ADC and then output to LED's.

    Thanks again MrChips
     
  15. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    Doing the FFT on a microcontroller is doable. The issues are:

    • size of array
    • memory space
    • speed of microcontroller
    For shortest processing time, one would choose integer arithmetic and not floating point arithmetic.
     
  16. WBahn

    Moderator

    Mar 31, 2012
    17,716
    4,788
    Implementing the FFT algorithm in a PIC would be pretty straightforward if you do it in C and, at audio frequencies, you have a lot of cycles to throw at it.

    The first thing you want to do is understand the DFT algorithm and code that up (on a PC) and then start looking at the FFT implementation, which can be quite a strain to get your mind around the first time. Again, code it up on a PC (in C) and get it working. Then port it to your PIC.
     
  17. MrChips

    Moderator

    Oct 2, 2009
    12,425
    3,359
    The objective is to do it in "real time".

    Human persistence of vision threshold is about 25Hz. This translates to 50ms.
    So your objective is to compute the FFT in within 50ms.

    A 64-point FFT in 50ms is very achievable on a microcontroller.
     
  18. KCHARROIS

    Thread Starter Member

    Jun 29, 2012
    292
    1
    Great thanks for the inspiration looked at the DFT I've done math such as integration and derivatives but I'm not quite sure about this formula below. I'll continue reading for better understanding.

    [​IMG]




    Thanks
     
  19. WBahn

    Moderator

    Mar 31, 2012
    17,716
    4,788
    This is summation, which is tightly related to integration. In fact, integration can be thought of as nothing more than summation performed by taking tiny steps with the integral being the result in the limit as the step size goes to zero.
     
    KCHARROIS likes this.
Loading...