www.piclist.com/techref/logic/dsps.htm?key=fft

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

<spamBeGonemarkKILLspamKILLspamCPOVO.NE To: .....PICLISTspam_OUTMITVMA.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

Please respond

to pic

microcontrolle

r discussion

list

On 20 Apr 2004 at 8:43, spam_OUTRichard.Prosserspam_OUTspam_OUTPOWERWARE.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

TakeThisOuTpiclist-unsubscribe-requestTakeThisOuTEraseMEmitvma.mit.edu

--

http://www.piclist.com hint: To leave the PICList

spampiclist-unsubscribe-requestRemoveMEmitvma.mit.edu

See also: www.piclist.com/techref/logic/dsps.htm?key=fft