Shop OBEX P1 Docs P2 Docs Learn Events
Fast Fourier Transform — Parallax Forums

Fast Fourier Transform

Jay KickliterJay Kickliter Posts: 446
edited 2009-10-17 07:07 in Propeller 1
Has anyone used the FFT code on the Propeller Wiki? Any opinions on it's completeness, functionality?

Also, for a few weeks ago I've been reading as much as I can about FFT, but I still don't quite grasp it. Most articles I read just mention bit reversal, but not why it is necessary to rearrange the time domain samples by the reverse of their original index.

Can anyone point me to a simple, Real FFT example, that I can do by hand on paper?

Comments

  • Mike GreenMike Green Posts: 23,101
    edited 2009-10-05 14:44
    How about starting with the Wikipedia? (en.wikipedia.org/wiki/Fast_Fourier_transform).
  • RaymanRayman Posts: 14,865
    edited 2009-10-05 15:29
    Try looking for "Numerical Recipes in C". I think there's free access on the internet to that...
    It has a very nice section on FFT...

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm
  • Dave HeinDave Hein Posts: 6,347
    edited 2009-10-05 15:31
    Jay Kickliter said...
    ...
    Also, for a few weeks ago I've been reading as much as I can about FFT, but I still don't quite grasp it. Most articles I read just mention bit reversal, but not why it is necessary to rearrange the time domain samples by the reverse of their original index.
    ...
    Why is bit-reversal necessary?· Hmm, I think that's just how the math works out.smile.gif
    · The main reason is the even/odd nature of the basis functions -- sines and cosines.· A function is even if·f(x) = f(-x), and it is odd if·f(x) = -f(-x).· The cosine function is even and the sine function is odd.··The basis functions for an N-length FFT consists of N/2 sine functions and N/2 cosine functions.· The basis functions for an N/2 FFT contain N/4 sine functions and N/4 cosine functions, and so on. ·Another way to do an FFT is to do the bit reversal after performing the computations instead of before.· With this method, the transform coefficients are grouped into even and odd groups.· The bit-reversal step shuffles the coefficients in an order of increasing frequency.

    Look up the Walsh-Hadamard transform and the Fast Walsh-Hadmard transform.· This is a simpler transform that uses only additions and subtractions.· However, it shares many of the same properties as the Fourier transform.· The fast Walsh-Hadamard transform computes the sums and differences of pairs of numbers.· The final orderering is in a hierarchical even/odd order.· The coefficients must be re-ordered by bit-reversing the index·to produce an increasing-frequency order -- just like the FFT.

    Dave
  • TreeLabTreeLab Posts: 138
    edited 2009-10-05 15:48
    Jay, I highly recommend the text written by Press et al in the Numerical Recipes in (insert language of choice) : The Art of Scientific Computing series. I have the Pascal variant, and there are 4 pages of detailed descriptions of FFT before going into the actual code (another page). The bit-reversal is done to simplify the Danielson-Lanczos decomposition and is shown graphically as well. The code comments refer directly to the written text.

    Cheers!
    Paul Rowntree
  • heaterheater Posts: 3,370
    edited 2009-10-05 17:36
    I've been trying to get my head around that bit reversal thing for years. The closest I've come to getting it is watching lectures on Fourier Transform and Fast Fourier Transform by Sunil Kumar from NPTEL on YouTube.
    In his lecture 38 he steps you through it about as easily as possible I think.

    Just go to YouTube and search for "fourier Sunil Kumar".

    You will then discover that India's National Programme on Technology Enhanced Learning (NPTEL) has got more than 4000 lecture videos on line covering everything you ever wanted, maths, computer science, programming, digital design, etc etc. A huge resource.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    For me, the past is not over yet.
  • heaterheater Posts: 3,370
    edited 2009-10-05 18:09
    The magical bit reversal pops out around 30 mins into Sunil Kumars lecture 38.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    For me, the past is not over yet.
  • Dave HeinDave Hein Posts: 6,347
    edited 2009-10-05 18:43
    I guess my first attempt at explaining the bit-reversal didn't make sense, so let me try again.· The discrete fourier transform (DFT) consist of multiplying an NxN matrix times a vector containing N values.· The rows of the NxN matrix consist of sine and cosine functions with frequencies from DC to half the sampling frequency.· The resulting N-point vector consists of·coefficients that represent the "weight"·of each of the sine·and cosine functions.· The original data can be reconstructed by multiplying each coefficient times its sine or cosine function, and adding all the weighted vectors together.· This is the same as performing a matrix multiply using the·inverse DCT·NxN matrix.

    Cooley and Tukey discovered that the DFT could be factored into the product of M sparse matrices, where M is log to the base 2 of N.· Each of the M sparse matrices has only two non-zero elements in each row and each column.· Cooley and Tukey also discovered that the positions of the non-zero elements can be described by bit-reversing the indices.· The bit-reversal results from the way an NxN DFT matrix can be constructed from an (N/2)x(N/2) DFT matrix.· The Cooley and Tukey algorithm is known as the original·Fast Fourier Transform (FFT).
  • AleAle Posts: 2,363
    edited 2009-10-05 18:57
    Well, time to post the link again smile.gifpropeller.wikispaces.org/FFT

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Visit some of my articles at Propeller Wiki:
    MATH on the propeller propeller.wikispaces.com/MATH
    pPropQL: propeller.wikispaces.com/pPropQL
    pPropQL020: propeller.wikispaces.com/pPropQL020
    OMU for the pPropQL/020 propeller.wikispaces.com/OMU
  • BRBR Posts: 92
    edited 2009-10-06 01:55
    Jay:

    The best explanation I've found for FFTs is in "The Scientist and Engineer's Guide to Digital Signal Processing," by Steven W. Smith. The entire book is available online at www.dspguide.com, though I highly recommend picking up a copy of the paper version, too. A great read if you're into that sort of thing.

    Chapter 12.

    BR
  • jazzedjazzed Posts: 11,803
    edited 2009-10-06 06:37
    Rayman said...
    Try looking for "Numerical Recipes in C". I think there's free access on the internet to that...
    It has a very nice section on FFT...
    Hey, I have that in hard-cover! tongue.gif
  • JamesxJamesx Posts: 132
    edited 2009-10-07 13:22
    Regarding the reference to propeller.wikispaces.org/FFT I took a look at this, and I am most intrigued by the possibility of dropping the code from this site into an object and viola: FFT!

    However, I noticed some disclaimers at the bottom of this wiki:

    "Some modifications to get_abs and plot may be then necessary.
    Note: This was tested with pPropellerSim, as of today not yet available with all bugs fixed (rev, max, etc)."


    Has anyone had this working on a real propeller?

    Thanks,

    Jim
  • Jay KickliterJay Kickliter Posts: 446
    edited 2009-10-07 14:24
    Mike, naturally, Wikipedia is the first place I looked, but thanks for the reply. Not to go into details, I have some difficulty reading, so that's why I was asking for a simple to follow example that doesn't leave out any steps. I don't think I'd have any problem understanding it if I could to a whole FFT with paper and pencil.
    Thanks everyone for the replies. BR, Smith's book is awesome, thanks. Ale, that wiki page is what I was referring to in the original post. I had never heard of anybody using i; like Jim, I couldn't tell if it was reliable code or proof of concept.
  • RickBRickB Posts: 395
    edited 2009-10-07 14:51
    Here is a link to an fft explanation that finally alowed me to understand what was really happening. It does not explain the bit reversal question however.

    http://www.syscompdesign.com/tech.htm

    The pdf in question is the digital signal analysis title second from the bottom.

    Rick
  • RaymanRayman Posts: 14,865
    edited 2009-10-07 14:57
    If you really want to understand it, start with the DTFT. This gives the same result as FFT, but is easier to understand...

    FFT is just a trick to do DTFT really fast...

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm
  • JamesxJamesx Posts: 132
    edited 2009-10-07 15:12
    So, for those of you who DO understand fft's, has anyone actually gotten a routine working on a propeller, with specs similar to those on the wiki page?

    I guess I'd rather start with something that works, then try to figure it out, compared with figuring it out first, then writing a routine.

    Jim
  • VIRANDVIRAND Posts: 656
    edited 2009-10-07 23:15
    Here's one that works and one that doesn't. hop.gifrolleyes.gif

    Somebody got the Propeller Wiki code to work with an 8 bit parallel ADC that I don't have.

    I've been trying to get it to work with a Demoboard microphone but it either just flatlines or fails,
    and I made a sloppy mess of it before starting over simply so maybe someone else could please help?
    If it flatlines or works there will be a FFT logo in the top of the monitor otherwise glitch or black screen.

    I've been having trouble sharing the samples between cogs again, even tried DIRB/OUTB/INB.
    No clue what else is wrong, even the working one seems to break easily if I try to sneak other PCM into it.
    Had doubts about same endianness of words and longs in cogs and hub also.

    Post Edited (VIRAND) : 10/7/2009 11:30:14 PM GMT
  • DanicoDanico Posts: 10
    edited 2009-10-08 04:28
    I too have been having trouble coming to grips with getting an FFT working on the prop.· Main problem is coming to terms with how the FFT functions, then looking at the wiki FFT routine, and trying to see how it is implementing it.· So has been a·bit difficult trying to understand the code, when I'm not too confident of the FFT basics!

    Ale does have the FFT code running here - http://forums.parallax.com/showthread.php?p=803389· although I have noticed that there are minor changes between this FFT routine and the one on the wiki.

    ·Just need to have some time to methodically step through the code, and come to terms with it.

    D.
  • VIRANDVIRAND Posts: 656
    edited 2009-10-08 05:38
    Ale's is apparently the "one that Works" I reposted above that needs an External ADC.
    I'd rather not use an extra IC just to play around with the display like the Microphone-to-VGA object's "scope".

    Do we Need 100 Msps for ambient sound?
    1024 samples per 25 to 50 ms... (time-and-frequency perception window), = around 51 Ksps I think.
  • JamesxJamesx Posts: 132
    edited 2009-10-08 10:20
    Danico,

    Thanks for the reference to the fft from Ale. This is what I was looking for.

    The way I was thinking of approaching this was to:
    -set up a source file, say a sine wave signal. Then use this repeated as the data input for the fft.
    -figure out another way to access the output. Ale has this set up as an o-scope application. I would like to export the output, eventually into excel on a pc
    -Once that's all working, I want to test the speed of the fft routine.
    -if I can do the above, learning how things work along the way, the next step would be to provide it with real-time data. This would come from a photodiode in my case.

    Regarding your questions about the sampling rate, I'm not a sound engineer, but seems to me that 50-100 ksps would be plenty for looking at sound (max audible ~ 20 kHz). Figure you'll need to sample at least 2X faster than the fastest signal of interest to avoid aliasing. One other little point: Ale's routine apparently works with 16-bit data, but the adc in his case provides only 8 bits. So I presume the fft routine can accommodate a higher resolution adc that what that sample program is using.

    Jim
  • VIRANDVIRAND Posts: 656
    edited 2009-10-08 11:35
    I think that because multiplication is happening you need double precision.
  • JamesxJamesx Posts: 132
    edited 2009-10-08 13:33
    If you look at the code, it appears that the multiplication steps use 32 bits. That would allow for 16-bit data.
  • Jay KickliterJay Kickliter Posts: 446
    edited 2009-10-08 14:08
    Jim, in additional to nyquest freqency, you need to a low pass filter before the ADC to avoid aliasing.
  • lonesocklonesock Posts: 917
    edited 2009-10-17 07:07
    (warning: self-aggrandizing link to follow [noparse][[/noparse]8^)

    I'm working on a FFT/DCT-like algorithm, that is basically a simplified version of the Walsh Transform.

    http://forums.parallax.com/showthread.php?p=848739

    Jonathan

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    lonesock
    Piranha are people too.
Sign In or Register to comment.