Exact match. Not showing close matches.
PICList
Thread
'[AVR:] Looking for an AVR FFT tutorial'
2004\04\18@093453
by
Mark Jordan
Hi,
I'm looking for a tutorial on how to write a FFT routine
in assembler language for the AVR AtMega uP.
Have found one dealing with the Goertzel algorithm and
it works very nice.
Google shows me zillions of FFT links, but nothing using
an AVR.
Thanks for any help.
Mark Jordan

http://www.piclist.com hint: The PICList is archived three different
ways. See http://www.piclist.com/#archives for details.
2004\04\19@165242
by
Richard.Prosser

Hi Mark,
I don't have a tutorial, but may be able to assist with sample code. (and
other help if required)
I am working on one of these at the moment. Have just about got it working
OK  am aiming at using it in an entry in the Circuit Cellar Contest.
Basic details are:
Using Atmega323. (or AtMega32)
64 sample x 10bit (results in 32 output frequency bins. e.g 8KHz sampling
will result in a resolution of ~125Hz)
Conversion time ~20mS on a 3.6864 MHz clock (Slightly dependent on signal
complexity as I only calculate the magnetude square root if the frequency
component is significant)
 I am aiming for speed rather than size
RAM Memory requirement (hopefully) < 300 bytes. (Using same array for
input, calculation & output  am still working on this & have yet to decide
which arrangement suits me best)
Flash Memory requirement is about 3k or so for the FFT module.
I am using the BASCOM environment for debugging & simulation & have found
some problems with their multiply directives, although that now appears
fixed.If I can use the mulsu & muls directives I may be able to shave a few
100uS more off the conversion time.
I am also thinking of writing an 8 bit version, possibly for up to 128
samples in length. As this will use the 8 bit multiply directive for most
multiplies, then program operation should be similar in speed to the 10 bit
64 sample version .
I can send you more info if required, but note that this is still "in
process" so there are probably bugs etc. hanging around.
I have also offered a copy to Mark for inclusion in a BASCOM library so it
may turn up there in a little while.
Right now I'm trying to tie the bits together so I can get a FFT or
spectrograph type display on an LCD, so I can monitor what is going on in
realtime & see if the thing is actually working as advertised.
Richard P
Mark Jordan
<spam_OUTmarkTakeThisOuTCPOVO.NE To: .....PICLISTKILLspam@spam@MITVMA.MIT.EDU
T> cc:
Sent by: pic Subject: [AVR:] Looking for an AVR FFT tutorial
microcontrolle
r discussion
list
<PICLIST@MITVM
A.MIT.EDU>
19/04/04 02:30
Please respond
to pic
microcontrolle
r discussion
list
Hi,
I'm looking for a tutorial on how to write a FFT routine
in assembler language for the AVR AtMega uP.
Have found one dealing with the Goertzel algorithm and
it works very nice.
Google shows me zillions of FFT links, but nothing using
an AVR.
Thanks for any help.
Mark Jordan

http://www.piclist.com hint: The PICList is archived three different
ways. See http://www.piclist.com/#archives for details.

http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listservKILLspammitvma.mit.edu with SET PICList DIGEST in the body
2004\04\20@102306
by
Mark Jordan

On 20 Apr 2004 at 8:43, .....Richard.ProsserKILLspam.....POWERWARE.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
EraseMEpiclistunsubscriberequestspam_OUTTakeThisOuTmitvma.mit.edu
2004\04\20@170052
by
Richard.Prosser

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 (reordering, "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
<markspam_OUTCPOVO.NE To: @spam@PICLISTKILLspamMITVMA.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, KILLspamRichard.ProsserKILLspamPOWERWARE.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
RemoveMEpiclistunsubscriberequestTakeThisOuTmitvma.mit.edu

http://www.piclist.com hint: To leave the PICList
spamBeGonepiclistunsubscriberequestspamBeGonemitvma.mit.edu
2004\04\20@191117
by
Mark Jordan

On 21 Apr 2004 at 8:52, TakeThisOuTRichard.ProsserEraseMEspam_OUTPOWERWARE.COM wrote:
> 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.
Thanks, that seems to be a very good example!
> 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.
I do the eight filters at every sample. When I reach N samples,
I compute the eight magnitudes and get the two DTMF frequencies. The
whole process used less than 20mS at 4MHz clock.
>
> Incidentally, I'd be interested in looking at you Goertzel implementation
> if possible!
Here is a MACRO I used at every sample, based on that article at:
http://www.embedded.com/story/OEG20020819S0057
;
; At every sample, calculate for each frequency:
;
; Q0 = (coeff*Q1)/32768Q2+sample
; Move Q1 to Q2
; Move Q0 to Q1
;
.macro SAMPLE ; Q1l,Q1h,Q2l,Q2h,Coeff
ldi auxl, LOW(@4)
ldi auxh, HIGH(@4)
lds matl, @0
lds math, @1
muls math, auxh ; (signed)Q1h * (signed)Coeffh
movw genl, prdl
mul matl, auxl ; Q1l * Coeffl
mov intemp, prdh
mulsu auxh, matl ; (signed)Coeffh * Q1l
sbc genh, zero
add intemp, prdl
adc genl, prdh
adc genh, zero
mulsu math, auxl ; (signed)Q1h * Coeffl
sbc genh, zero
add intemp, prdl
adc genl, prdh
adc genh, zero ; (Q1*Coeff)>>16
lsl genl
rol genh ; (Q1*Coeff)<<1
lds auxl, @2
lds auxh, @3
sub genl, auxl
sbc genh, auxh ; Sub Q2
add genl, XL
adc genh, XH ; Add current sample
sts @0, genl
sts @1, genh ; Q1 = Q0
sts @2, matl ; Q2 = Q1
sts @3, math
.endmacro ; 45 clock cycles
;
;
; After N samples, calculate for each frequency:
;
; MAG = SQRT(Q1*Q1+Q2*Q2(Q1*Q2*coeff)/32768)
;
Mark Jordan

http://www.piclist.com hint: To leave the PICList
RemoveMEpiclistunsubscriberequestTakeThisOuTmitvma.mit.edu
2004\04\20@202735
by
Richard.Prosser

Thanks  will have to have a play with it!
RP
On 21 Apr 2004 at 8:52, Richard.ProsserEraseME.....POWERWARE.COM wrote:
> 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.
Thanks, that seems to be a very good example!
> 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.
I do the eight filters at every sample. When I reach N samples,
I compute the eight magnitudes and get the two DTMF frequencies. The
whole process used less than 20mS at 4MHz clock.
>
> Incidentally, I'd be interested in looking at you Goertzel implementation
> if possible!
Here is a MACRO I used at every sample, based on that article at:
http://www.embedded.com/story/OEG20020819S0057
;
; At every sample, calculate for each frequency:
;
; Q0 = (coeff*Q1)/32768Q2+sample
; Move Q1 to Q2
; Move Q0 to Q1
;
.macro SAMPLE ; Q1l,Q1h,Q2l,Q2h,Coeff
ldi auxl, LOW(@4)
ldi auxh, HIGH(@4)
lds matl, @0
lds math, @1
muls math, auxh ; (signed)Q1h *
(signed)Coeffh
movw genl, prdl
mul matl, auxl ; Q1l * Coeffl
mov intemp, prdh
mulsu auxh, matl ; (signed)Coeffh * Q1l
sbc genh, zero
add intemp, prdl
adc genl, prdh
adc genh, zero
mulsu math, auxl ; (signed)Q1h * Coeffl
sbc genh, zero
add intemp, prdl
adc genl, prdh
adc genh, zero ; (Q1*Coeff)>>16
lsl genl
rol genh ; (Q1*Coeff)<<1
lds auxl, @2
lds auxh, @3
sub genl, auxl
sbc genh, auxh ; Sub Q2
add genl, XL
adc genh, XH ; Add current
sample
sts @0, genl
sts @1, genh ; Q1 = Q0
sts @2, matl ; Q2 = Q1
sts @3, math
.endmacro ; 45 clock cycles
;
;
; After N samples, calculate for each frequency:
;
; MAG = SQRT(Q1*Q1+Q2*Q2(Q1*Q2*coeff)/32768)
;
Mark Jordan

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

http://www.piclist.com hint: To leave the PICList
RemoveMEpiclistunsubscriberequestEraseMEEraseMEmitvma.mit.edu
2004\04\21@024050
by
Richard.Prosser

Thanks  will have to have a play with it!
RP
On 21 Apr 2004 at 8:52, RemoveMERichard.Prosserspam_OUTKILLspamPOWERWARE.COM wrote:
> 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.
Thanks, that seems to be a very good example!
> 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.
I do the eight filters at every sample. When I reach N samples,
I compute the eight magnitudes and get the two DTMF frequencies. The
whole process used less than 20mS at 4MHz clock.
>
> Incidentally, I'd be interested in looking at you Goertzel implementation
> if possible!
Here is a MACRO I used at every sample, based on that article at:
http://www.embedded.com/story/OEG20020819S0057
;
; At every sample, calculate for each frequency:
;
; Q0 = (coeff*Q1)/32768Q2+sample
; Move Q1 to Q2
; Move Q0 to Q1
;
macro SAMPLE ; Q1l,Q1h,Q2l,Q2h,Coeff
ldi auxl, LOW(@4)
ldi auxh, HIGH(@4)
lds matl, @0
lds math, @1
muls math, auxh ; (signed)Q1h *
(signed)Coeffh
movw genl, prdl
mul matl, auxl ; Q1l * Coeffl
mov intemp, prdh
mulsu auxh, matl ; (signed)Coeffh * Q1l
sbc genh, zero
add intemp, prdl
adc genl, prdh
adc genh, zero
mulsu math, auxl ; (signed)Q1h * Coeffl
sbc genh, zero
add intemp, prdl
adc genl, prdh
adc genh, zero ; (Q1*Coeff)>>16
lsl genl
rol genh ; (Q1*Coeff)<<1
lds auxl, @2
lds auxh, @3
sub genl, auxl
sbc genh, auxh ; Sub Q2
add genl, XL
adc genh, XH ; Add current
sample
sts @0, genl
sts @1, genh ; Q1 = Q0
sts @2, matl ; Q2 = Q1
sts @3, math
endmacro ; 45 clock cycles
;
;
; After N samples, calculate for each frequency:
;
; MAG = SQRT(Q1*Q1+Q2*Q2(Q1*Q2*coeff)/32768)
;
Mark Jordan

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

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

http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: >uP ONLY! [EE]:,[OT]: >Other [BUY]:,[AD]: >Ads
2004\04\27@002338
by
Scott Dattalo

On Tue, 20 Apr 2004, Mark Jordan wrote:
> On 20 Apr 2004 at 8:43, RemoveMERichard.ProsserKILLspamPOWERWARE.COM wrote:
>
> > I don't have a tutorial, but may be able to assist with sample code. (and
> > other help if required)
<snip>
> 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?
The Goertzel algorithm and an FFT will produce identical results assuming
of course that the Goertzel algorithm is generating all the frequencies.
The difference is efficiency. If there are N frequencies, then the fft
will take N*log2(N) units of time where as the Goertzel algorithm will
take roughly N*N units. However, as mentioned in other portions of this
thread, the Goertzel algorithm has the advantage that the individual
frequencies can be tuned.
In some sense, you can view the Goertzel algorithm as a narrow band pass
filter. I strongly suspect that if you use this concept as guide that it
would be possible to design an extremely optimal filter bank for filtering
the 8DTMF frequencies. For example, the first stage can split the signal
into highs and lows. Each of these streams are then split again. Finally,
those four streams are split. You may wish to look up info on multirate
filtering.
> Do you know of some page describing the FFT process like that
> one on the Goertzel algorithm?
I guess that depends on what you mean by 'like', but you could look at:
http://www.dattalo.com/technical/theory/dtmf.html
Scott

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2004\04\27@140719
by
Mark Jordan

Hi Scott, thanks for your reply. Comments below.
On 26 Apr 2004 at 21:19, Scott Dattalo wrote:
> In some sense, you can view the Goertzel algorithm as a narrow band pass
> filter. I strongly suspect that if you use this concept as guide that it
> would be possible to design an extremely optimal filter bank for filtering
> the 8DTMF frequencies. For example, the first stage can split the signal
> into highs and lows. Each of these streams are then split again. Finally,
> those four streams are split. You may wish to look up info on multirate
> filtering.
As I have mentioned, I did the DTMF decoding using the information
from the URL below. I can detect DTMF tones in less than 18mS on an
ATMega8 running at 3.58MHz with very good dinamic range and precision.
> > Do you know of some page describing the FFT process like that
> > one on the Goertzel algorithm?
>
> I guess that depends on what you mean by 'like', but you could look at:
> http://www.dattalo.com/technical/theory/dtmf.html

The Goertzel algorithm can be implemented as follows:
At every sample:
Q0 = coeff*Q1Q2+sample
Move Q1 to Q2
Move Q0 to Q1
After a block of N samples:
MAG = SQRT(Q1^2+Q2^2Q1*Q2*coeff)

I would like to see the same description on how to implement
the FFT process. I'm not interested in DTMF decoding. Thas was
just an example and an excellent exercise.
What I want to design is an 8 or 16 tone AFSK modem.
With the Goertzel algorithm I can do the decoding in less
than 20mS using the same ATMega8 running at 8MHz. My doubt is if
the FFT process would give me advantages such as decoding speed
or better error rate.
Thanks,
Mark Jordan

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
2004\04\27@162157
by
Kenneth Lumia

> What I want to design is an 8 or 16 tone AFSK modem.
> With the Goertzel algorithm I can do the decoding in less
> than 20mS using the same ATMega8 running at 8MHz. My doubt is if
> the FFT process would give me advantages such as decoding speed
> or better error rate.
Mark,
Timeout. Just as a side note, you may want to rethink using an ATmega8 to
build a working 8 or 16 tone AFSK modem (assuming you want it to work
in the "real" world). There is just not enough horsepower there to do
a good enough job. Specifically, have you thought about the baud rate
(and sampling/processing time required) for the receiver, the equalizer and
tap updates that go with it, the AGC, phase corrector, jitter tracker,
slicer
and the transmitter side including txfilter. Oh and if it is supposed to be
2wire,
don't forget the near and far end echo cancellers and their tap updates.
Way too much runtime.
Note that the above is not meant to dishearten your desire to learn, but
just a dose of datacom reality.
Ken
{Original Message removed}
2004\04\27@174513
by
Mark Jordan

On 27 Apr 2004 at 16:20, Kenneth Lumia wrote:
{Quote hidden}> > What I want to design is an 8 or 16 tone AFSK modem.
> > With the Goertzel algorithm I can do the decoding in less
> > than 20mS using the same ATMega8 running at 8MHz. My doubt is if
> > the FFT process would give me advantages such as decoding speed
> > or better error rate.
>
> Mark,
>
> Timeout. Just as a side note, you may want to rethink using an ATmega8 to
> build a working 8 or 16 tone AFSK modem (assuming you want it to work
> in the "real" world). There is just not enough horsepower there to do
> a good enough job. Specifically, have you thought about the baud rate
> (and sampling/processing time required) for the receiver, the equalizer and
> tap updates that go with it, the AGC, phase corrector, jitter tracker,
> slicer
> and the transmitter side including txfilter. Oh and if it is supposed to be
> 2wire,
> don't forget the near and far end echo cancellers and their tap updates.
> Way too much runtime.
>
> Note that the above is not meant to dishearten your desire to learn, but
> just a dose of datacom reality.
>
> Ken
>
Hi Ken,
I know all you are talking about. Worked five years on a Data
Telecom company. Not exactly doing modem design, but I learnt all
that process.
Well, I'm sorry, I didn't give all the details of what I'm
planning to do.
Imagine a halfduplex low speed modem, something in the order
of 50 or 100 baud. The 8 or 16 tones won't be transmitted all at
the same time. Just one or two like an AFSK or DTMF signal.
I think the ATMega8 has enough power to decode such a low
speed signal.
Thanks,
Mark Jordan

http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics
More... (looser matching)
 Last day of these posts
 In 2004
, 2005 only
 Today
 New search...