piclist 2004\04\20\170052a >
Thread: Looking for an AVR FFT tutorial
www.piclist.com/techref/logic/dsps.htm?key=fft
BY : Richard.Prosser.....@@spam@POWERWARE.COM

Hi Mark,
The approach I used was to locate a simple FFT example on the net, and
transcribe it into BASCOM (not hard, BASCOM BASIC is not too far from C in
some areas).
Then, once this was working, I split the overall algorithm into the 3 main
parts (re-ordering, "butterfly" and magnitude derivation) and got each part
running separately in assembler. Then optimised the parts for maximum
speed. Put the parts together & got it all working . Along the way I had to
look into integer multiply routines in assembler and fast square roots etc.
That's pretty much where I am now.
The web site I used for my initial code was (I think)
http://www.8052.com/users/steve/FFTC.C  , which is an FFT example for the
8052 micro. He claims 700mS for a 64 sample conversion with a 12MHz clock,
whereas I am running at about 20mS with a <4MHz clock on the atmel chip. I
think the hardware multiply is responsible for a large part if this as
there are something like 384 integer multiply operations in the butterfly
section, plus more in  the magnitude calculation.

As far as comparing the Goertzel algorithm with the FFT I think it is a
question of what you are actually trying to do.
My impression is that the Goertzel algorithm aims at identifying a single
frequency component in a signal, basically using a IIR filter. It is
capable of running more or less "on the fly" once a certain number of
samples have been obtained. However, if you want to identify N frequency
components, then you have to run N processes in parallel. The FFT
implementation runs in a "batch" mode, where you take the samples and then
process them. You can take more samples into another array while
processing, bit you do not get the capability to process a continuous
input.
Once you get above a certain number (Depends on requirements), then an FFT
can become more speed efficient. The G algorithm  revolves around IIR
filters however and  memory (RAM) requirements are significantly less.
The figures I have seen suggest that for DTMF decoding - detection of 8 (or
16? - second harmonic detection is often used to minimise false detects)
tones using a smallish sample size, then there is little to choose in terms
of number of calculations between the 2 methods. The G. algorithm will use
less RAM however.
Another plus for the G. Algorithm is that the coefficients & sampling rate
etc. can be chosen to exactly match the frequencies being sought, whereas
with the FFT, then frequency bins are always a multiple of a base frequency
and so may not always match a range of frequency values. This is
particularly true of DTMF tones which were deliberately chosen not to be
harmonically related. So the frequency components will not fit nicely into
8 bins and sensitivity and/or overall program complexity suffers.
On the other hand, if you are wanting to develop a spectral display of a
signal where you may not know or care about particular tones, , the FFT
methods are preferable to the G. algorithm as all frequency components drop
out of a single process.

Hope this assists

Richard P

Incidentally, I'd be interested in looking at you Goertzel implementation
if possible!

Mark Jordan
<markCPOVO.NE        To:     PICLISTMITVMA.MIT.EDU
T>                    cc:
Sent by: pic          Subject:     Re: [AVR:] Looking for an AVR FFT tutorial
microcontrolle
r discussion
list
<PICLIST@MITVM
A.MIT.EDU>

21/04/04 03:21
to pic
microcontrolle
r discussion
list

On 20 Apr 2004 at 8:43, Richard.ProsserPOWERWARE.COM wrote:

> I don't have a tutorial, but may be able to assist with sample code. (and
> other help if required)

Thanks Richard, I appreciated that.

Have read lots of info about FFT, but still don't get it right.
I found an excelent description of the Goertzel algorithm here:

http://www.embedded.com/story/OEG20020819S0057

Based on that info, I wrote a program to do it using an ATmega8.
It worked nicely detecting DTMF tones! And it is very versatile
and easy to tweak up!
The assembler program used 10bit samples scaled to 12bit and the
coefficients scaled to 14bits. All the multiplys are 16bit.

Well, what I'm trying to design is an 8 or 16 tone AFSK modem.
Based on what I have read, it seems Goertzel is just one form
of calculating the FFT. But will it give me the best results?

Do you know of some page describing the FFT process like that
one on the Goertzel algorithm?

Thanks.
Mark Jordan

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestmitvma.mit.edu

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestmitvma.mit.edu

<OFF0BAAB9D.9724A2AE-ONCC256E7C.006E0E85@psd.invensys.com>