C code for FFT of sine wave

Discussion in 'Programmer's Corner' started by tojeena, Dec 7, 2011.

  1. tojeena

    Thread Starter Active Member

    May 2, 2009
    118
    0
    Hi i need the code in assemble language or C code for finding the FFT of Sine wave..Please help me
     
  2. t06afre

    AAC Fanatic!

    May 11, 2009
    5,939
    1,222
    Writing a DFT algorythm is easy, it's basically just 2 stupid loops, one inside the other. Depending on the length of your array it might be good enough to just write a DFT vi. FFT might be faster, but there's more coding, which in turn means more things to potentially go wrong. Also, it seems that the fastest FFT method depends on your dataset.

    Each frequency component is the result of a dot product of the time-domain signal with the complex exponential at that frequency and is given by the following equation.
    [​IMG]
    The DC component is the dot product of x(n) with [cos(0) – jsin(0)], or with 1.0.
    The first bin, or frequency component, is the dot product of x(n) with cos(2πn/N) – jsin(2πn/N). Here, cos(2πn/N) is a single cycle of the cosine wave, and sin(2πn/N) is a single cycle of a sine wave.
    In general, bin k is the dot product of x(n) with k cycles of the cosine wave for the real part of X(k) and the sine wave for the imaginary part of X(k).
    This should also help http://en.wikipedia.org/wiki/Discrete_Fourier_transform
     
  3. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    This is in regards to using an MCU with a DAC to produce a sine wave?

    I personally would be hard coding into an array what I calculated with pen and paper using: SINǾ (theto) x VP

    This data can be manipulated in software to make changes.
     
  4. codehead

    Member

    Nov 28, 2011
    56
    11
    You'd get better help with a better explanation of what you need. You don't even say what assembly language, for instance. Also, it would help to know the purpose—are you really trying to just get the FFT of only a sine wave? There are plenty of FFTs in C on the web.
     
  5. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    What is FFT?
     
  6. codehead

    Member

    Nov 28, 2011
    56
    11
    Fast Fourier Transform. It's a DFT (Discrete Fourier Transform, as in discrete time—useful for processing samples in the digital domain in other words), that has been optimized by eliminating some redundant calculations so that as the number of samples doubles, the required calculations don't (they are related to the log of that number, so it's a huge win for longer transforms).

    The forward transform moves time domain samples to the frequency domain (converts a series of samples equally spaced in time to frequency values), and the inverse transform goes the other direction.

    It works like this:

    http://www.earlevel.com/main/2002/08/31/a-gentle-introduction-to-the-fft/

    For anyone not getting the time/frequency domain references, this page show how you can set the frequency domain values with sliders (each corresponds to a sine wave at 1x, 2x, 3x...) and the time domain view of the waveform that corresponds to it:

    http://www.earlevel.com/main/1996/11/14/the-fourier-series/
     
    Last edited: Dec 7, 2011
    cheezewizz likes this.
  7. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    I see.

    What would be some practical applications for FFT?
     
  8. codehead

    Member

    Nov 28, 2011
    56
    11
    A few examples:

    • You could generate arbitrary cyclic waveforms (similar to the Fourier demonstration with sliders that I showed you). It's much faster to use an FFT to make that waveform that to similarly build a waveform by calculating and adding up harmonic sine waves. You could make a musical instrument with oscillators made like this, and even morph between them for dynamic sounds.

    • You could make a spectrum analyzer—converting incoming samples to a harmonic spectrum for viewing.

    • Some things are more efficient to do in the frequency domain. For instance, (circular) convolution in the time domain is multiplication in the frequency domain. If you're sampling audio at 48 kHz and want to convolve it with a 6-second impulse response of a cathedral for an awesome reverb, that's 288,000 multiplies/adds for each input sample, or nearly 14 billion MACs a second—twice for stereo—and times any additional overhead for the loop. Instead, you can convert the input samples to the frequency domain, do the convolutions as multiplies (other overhead involved as well, but still a huge win), and convert it back to the time domain to play out on your speakers.n

    Note that a DFT/FFT is just a snapshot—it's focused on taking apart one cycle into its component harmonics (Fourier discovered this while looking at how heat propagated through and iron ring!). The real world doesn't line itself up nicely in cycles that complete over a number of sample known in advance, and different sounds with difference wave lengths can overlap. Fortunately, you can morph a stream of these snapshots, overlapping, and convert arbitrary sound between time and frequency in sort of the same way that we watch fluid motion from a series of still pictures in movies.
     
  9. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    So there are no real 'practical' applications that would interest a normal person then?
     
  10. joeyd999

    AAC Fanatic!

    Jun 6, 2011
    2,689
    2,750
    I use FFT quite frequently for noise analysis. Lots of times, noise an a signal looks "random", but passing it through an FFT often shows discrete peaks that correspond to noise sources in other parts of the system. This assists in making changes that attenuate interference from those parts of the system.
     
  11. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    LOL I said for 'normal' people.

    You know the other 99% of the population who live normal lives?
     
  12. codehead

    Member

    Nov 28, 2011
    56
    11
    ROFL—I take it you're joking. The FFT is one of the most widely used numerical algorithms on the planet. It's used in image processing (ever seen Photoshop?) music and recording gear of many types, video, electronics test gear.

    But it depends on what you mean by "normal". Certainly, "normal" (if you mean average) people have no interest in this website.
     
  13. codehead

    Member

    Nov 28, 2011
    56
    11
    BTW, I just did a search of the forums here and came up with 1,418 hits for "FFT"...for the web, google comes up with 25,600,000...
     
  14. MrChips

    Moderator

    Oct 2, 2009
    12,446
    3,362
    I have used the FFT to analyze the stock market.
    The FFT is a common tool in speech recognition.
    You could not do CT and MRI scans without FFT.
     
  15. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    Well at least that's something.

    Magnetic Resonance Imagining (that much is true I do have a bit of an interest in medicine) -- we can diagnose with almost 100% certainty, but cannot cure even 1% of cancer with any real absolute certainty.

    Most things show up on a CT scan that are within 1mm. In Australia, we don't bother with MRI much, because the benefits don't out weigh the risks and the associated costs when a CT scan can usually suffice.
     
  16. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    Oh normal average people have an interest my friend, believe me they do.
     
  17. MrChips

    Moderator

    Oct 2, 2009
    12,446
    3,362
    CT scans uses X-ray radiation. MRI scans do not use ionizing radiation.
     
  18. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    If you have ever done any metal work in your life, then you are at potential risk with having some complications after having an MRI scan.

    An MRI scan requires a more qualified person to operate, and it can take an hour to do an abdominal scan as opposed to a few mintutes for a CT with contrast.
     
  19. T.Jackson

    New Member

    Nov 22, 2011
    328
    14
    Either way, say no to anything besides painkillers if you ever get cancer.

    The scans are pointless, unless you are willing to consent to prolonged misery.
     
  20. MrChips

    Moderator

    Oct 2, 2009
    12,446
    3,362
    Too bad you don't know what you are taking about. You remind me of Yako.
     
Loading...