Fast Fourier Transform
Jay Kickliter
Posts: 446
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?
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
It has a very nice section on FFT...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm
· 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
Cheers!
Paul Rowntree
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.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.
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).
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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
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
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
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.
http://www.syscompdesign.com/tech.htm
The pdf in question is the digital signal analysis title second from the bottom.
Rick
FFT is just a trick to do DTFT really fast...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm
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
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
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.
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.
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
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.