 |
 |
| View previous topic :: View next topic |
| Author |
Message |
PhilWinder
Joined: 16 Apr 2005
Posts: 23
|
| frantically searching for pic C related FFT code. |
 Posted: Tue May 24, 2005 3:32 pm |
 |
|
hey, ive been reading and searching for ages for something, anything that relates to pics and C code for FFT calculations. ive done a bit of reading but its bladdy complicated and ive come to the conclusion that its going to be almost impossible for me to write some code for it. i have seen loads of examples in assembler, but to be honest, i havent got the foggiest.
i did find a reference on the old forum to a person called
Ken on October 13, 2000 post here
having some working fft code for CCS, but it was too far back so all his posts arnt there anymore.
i have also found many fft routines in c, but they are all optimised for computers. not pics (i.e. they use loads of floats and stuff).
anyone that is willing to give me a helping hand is greatly appreciated either in the jest of code, links or advice.
thanks,
phil |
|
 |
rwyoung
Joined: 12 Nov 2003
Posts: 563
Location: Lawrence, KS USA
|
|
| Posted: Wed May 25, 2005 8:15 am |
|
|
How are you at translating FORTRAN to C? And how do you feel about writing your own fixed-point math routines? Likewise creating your own complex number routines?
If you are OK with those it is pretty easy to find FORTRAN implementations of the Cooley-Tukey "decimation in time" and "decimation in frequency" FFT 2-point butterfly algorithms. Not very highly optimized but they do run faster than just a dumb old DFT implementation. I've used them many times in PC software where I needed a quick dose of FFT and it wasn't terribly important that they run in real-time.
They could be a challange to port to a PIC because they are NOT optimized for memory use or fixed-point math. But with a PIC18 and a fast clock you might get something usefull for small data sets.
_________________
Rob Young
The Screw-Up Fairy may just visit you but he has crashed on my couch for the last month! |
|
|
bfemmel
Joined: 18 Jul 2004
Posts: 40
Location: San Carlos, CA.
|
|
| Posted: Wed May 25, 2005 9:07 am |
|
|
You may want to search the TI DSP libraries. TI apps engineers wrote a lot of articles on doing signal processing with fixed point parts. Here is a link to one paper I found there.
http://www.techonline.com/pdf/pavillions/gspx/77.pdf
Likewise the other DSP vendors like AD, Moto and such may have papers on the subject also. I am sure that you will need to do a lot of rework on the C code but it's a start. Hope that helps.
- Bruce |
|
|
AK
Joined: 20 Apr 2004
Posts: 33
|
|
| Posted: Wed May 25, 2005 1:18 pm |
|
|
Try this book "The Scientist and Engineer's Guide to Digital Signal Processing". It's online for free. I believe it has some algorithms that may be useful.
http://www.dspguide.com/ |
|
|
PhilWinder
Joined: 16 Apr 2005
Posts: 23
|
|
| Posted: Thu May 26, 2005 12:22 pm |
|
|
Hi guys, thanks for the replies.
Rwyoung: Thats what my basic problem is. I have found loads of C implamentations of the fft, but they are all written specifically for computer use. All optimised (for example) for "pentium 4" processors. Who uses them anyway ;) I was wondering if anyone had and if they would share their experiences, if not their code.
AK: Already one step ahead of you  ive already (skim) read that book, and you are right, it is a good help for an introduction, but it makes no references to emmbedded systems running a fft. cheers.
bfemmel: That link looks good. Ive never even come accross the website before but it does look promising for background information if nothing else. Unfortunatly i havent looked at the link yet but i will soon. promise. (as soon as the missus stops playing spider solitaire. )
Thanks for the replies. if any of you, or anyone else, has anything else to give then go right ahead.
thanks
phil |
|
|
jbmiller
Guest
|
| fft |
| Posted: Fri May 27, 2005 5:34 am |
|
|
You might want to look at Microchips AN542 Implementation of fft.
I know it's in asm but it might help as every line is commened..
Jay |
|
|
ckielstra
Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands
|
| Re: fft |
| Posted: Fri May 27, 2005 7:48 am |
|
|
| jbmiller wrote: | You might want to look at Microchips AN542 Implementation of fft.
I know it's in asm but it might help as every line is commened..
Jay |
I found another nice asm implementation of an FFT at http://www.piclist.com/techref/microchip/fft/picspect.htm. The author of this program has no good words for the AN542 implementation...
One thing that makes me wonder is why Phil, the original poster of this thread, wants to do FFT on a PIC processor.
There is a reason for so few code examples being available, the PIC processor is not well equipped for this job. For real signal analysis you need a processor with fast arithmetic functions. The PIC18 series is already a large improvement over the PIC16 series in that it now has a 8x8 multiplier which makes it possible to multiply two 8 bit values in a single instruction time. But then compare this to one of the oldest DSP's I know, the Texas Instruments TMS32010 from 1983 (!), which has a 16x16 multiplier. A 16x16 multiply on the PIC18 requires 14 instruction cycles v.s. 1 cycle on the ancient TMS32010.
It is possible to do FFT on a PIC, but because of limited capabilities you will only be able to process (very) low frequency signals. What kind of signals do you want to analyse? |
|
|
sseidman
Joined: 14 Mar 2005
Posts: 159
|
| Re: fft |
| Posted: Fri May 27, 2005 8:35 am |
|
|
| ckielstra wrote: |
One thing that makes me wonder is why Phil, the original poster of this thread, wants to do FFT on a PIC processor.
There is a reason for so few code examples being available, the PIC processor is not well equipped for this job. For real signal analysis you need a processor with fast arithmetic functions. The PIC18 series is already a large improvement over the PIC16 series in that it now has a 8x8 multiplier which makes it possible to multiply two 8 bit values in a single instruction time. But then compare this to one of the oldest DSP's I know, the Texas Instruments TMS32010 from 1983 (!), which has a 16x16 multiplier. A 16x16 multiply on the PIC18 requires 14 instruction cycles v.s. 1 cycle on the ancient TMS32010.
It is possible to do FFT on a PIC, but because of limited capabilities you will only be able to process (very) low frequency signals. What kind of signals do you want to analyse? |
http://www.circuitcellar.com/library/print/0998/Lacoste98/lacoste98.pdf gives a 17F implementation of FFT that calculates 10 FFT's/second on audio signals. I suspect an 18F would do about twice that. Without going back and actually reading, I seem to recall that convolution-- the true strength of DSP's-- is O(N^2), while an FFT is O(NlogN) (with about half the operations being additions), and there are even faster algorithms today-- so the performance hit by using a PIC isn't as bad for an FFT as it would be for a convolution..
Why use a microcontroller instead of a DSP? The only reason I can think of is the wish to stick with development tools you're familiar with and already own. Here's hoping that CCS moves quickly with dsPIC support! Status has been listed as "soon" on their site since before I bought in to the compiler, and the "soon" promise was one of the reasons behind my choice.
Scott |
|
|
PhilWinder
Joined: 16 Apr 2005
Posts: 23
|
|
| Posted: Fri May 27, 2005 10:36 am |
|
|
yeah i think ive come to that conclusion too. Lots of people say its 'possible' but like both of you said, it will be slow.
Im looking to perform fouier analysis on an audio signal so dependant on how fast i could go, 20kHz would be much more than enough.
And scotts nailed it on the head. My (limited) experience is with PICs and only PICs with PBP and CCS C. Thats it. This is why i wanted to exhaust all other avenues before starting a complete new adventure. It would mean starting learning them damn flahsing LED examples all over again  .
I have had a quick look into Microchips dsPICs and i have learnt that i can slightly modify my hardware to program them!! only thing is though, ive never done it before, so i will have to take one step back before i go forward. Hopefully CCS's dsPIC software wont be too long.
Any news on that by the way??? its been on the books for quite a while now. any release dates???
thanks everyone, think ill now explore the dsPIC avenue.
phil |
|
|
ckielstra
Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands
|
|
| Posted: Fri May 27, 2005 10:58 am |
|
|
Thanks for the link, I didn't have this one. Turns out that my link contains the source code belonging to the article you linked.
| Quote: | | I suspect an 18F would do about twice that. |
I don't know all differences between 17F and 18F-series, but both have 16-bit instruction opcodes and a 8x8 hardware mulitplier. The only reason I can find for the 18F to be faster is the 40MHz maximum clock for the PIC18 versus a 33MHz clock for the PIC17 resulting in about 25% performance gain. |
|
|
sseidman
Joined: 14 Mar 2005
Posts: 159
|
|
| Posted: Fri May 27, 2005 11:36 am |
|
|
| ckielstra wrote: |
| Quote: | | I suspect an 18F would do about twice that. |
I don't know all differences between 17F and 18F-series, but both have 16-bit instruction opcodes and a 8x8 hardware mulitplier. The only reason I can find for the 18F to be faster is the 40MHz maximum clock for the PIC18 versus a 33MHz clock for the PIC17 resulting in about 25% performance gain. |
Right you are! Like many, I'm not real familiar with the 17F capabilities. I think I automatically apply 16F limitations without thinking.
Scott |
|
|
Guest
|
|
| Posted: Fri May 27, 2005 4:03 pm |
|
|
| PhilWinder wrote: |
Im looking to perform fouier analysis on an audio signal so dependant on how fast i could go, 20kHz would be much more than enough.
|
You want your sampling rate to be at least twice the maximum frequency. Audio goes up to 20kHz, so you'll want at least 40kHz. You might have meant MHz, but it's a typo that bears correcting.
People with "golden ears" will tell you that you'll want higher sampling rates. |
|
|
sseidman
Joined: 14 Mar 2005
Posts: 159
|
| fine points on sampling theorem--gets a little long! |
| Posted: Fri May 27, 2005 5:01 pm |
|
|
| Anonymous wrote: | | PhilWinder wrote: |
Im looking to perform fouier analysis on an audio signal so dependant on how fast i could go, 20kHz would be much more than enough.
|
You want your sampling rate to be at least twice the maximum frequency. Audio goes up to 20kHz, so you'll want at least 40kHz. You might have meant MHz, but it's a typo that bears correcting.
People with "golden ears" will tell you that you'll want higher sampling rates. |
An engineer would ask why Philwinder wants the FFT in the first place, and what he's going to do with the result. If the application were centered around speech, 20kHz sampling is plenty fast, giving an ideal 10kHz (more realistically, about 8kHz) of signal bandwidth. Telephones don't give you nearly so much bandwidth, less than 3.5kHz, which is why you can have trouble distinguishing "f" from "s" sounds.
The warning is that you need to analog prefilter before you sample. In many cases, especially when you're pushing your hardware to the limit, analog prefiltering is cheaper and easier than upping the sample rate.
There are some pretty good reasons to only sample as fast as you need to. One involves what are you going to do with the fft once you have it. If you want to do any digital filtering, its usually best to sample as slow as you can and still cover the frequency range of interest, as this will make digital filters *much* easier to design and implement. They can have fewer points in the convolution, and they won't ring as much because you can have nice gentle rolloffs in the frequency response instead of precipitous drops. Of course, when you have the data sampled quickly, you can always decimate and then do whatever you want, but then you need to digital filter before decimation to avoid aliasing, and in an embedded system this adds beaucoup processing time. Best to avoid the problem by not sampling too fast. (Bonus points if you can explain why oversampling is good, and not bad, in CD players).
The next question, of course, would be how good does the frequency resolution of the FFT need to be, as this will determine how many data points need to be input into the algorithm, which will dictate how fast the computation can take place. Note that this is another reason to only sample fast enough to cover the bandwidth of interest. For example, a 1024-point fft of a 10kHz signal will have twice the frequency resolution of a 1024-pt fft of a 20kHz signal.
Last consideration would be how often the fft needs to be updated. The concerns are whether you need to keep filling your data buffer while computations are going on, or if you can just periodically sample between computations, and whether there's enough time to get the job done.
I suppose one last fine point would be whether an FFT was best in the first place, or whether a periodogram of some sort, employing averaged fft's of overlapping ensembles, would be more appropriate (it often is).
Scott |
|
|
PhilWinder
Joined: 16 Apr 2005
Posts: 23
|
|
| Posted: Sat May 28, 2005 1:13 pm |
|
|
Hi scott,
They are the questions that i am interested in answering myself. I am going to be taking a fft of a guitar and vocals. not at the same time.
I dont know how many fft points i will take, that will be up to experimentation when i finaly get some code working.
Basically i need to know the power spectrum of the signal then filter bits out. Firstly i just want to do the fft on the uP and use Active analouge filters to do the filtering to help prove a theory correct, but later i will have digital filtering.
the answer for a couple of questions back is yes 20kHz is enough, so therefore you are right in thinking a sample rate of about 40kHz will do fine. (assuming i'm roughly going up to 20kHz [this wont be the case]).
yes scott i would need a analouge (could be digital but theres no point)prefilter to stop alaiasing.
I dont know how many ffts i would take per sec, it depends on how much spare processing time i have!
thanks
phil |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
