Searching \ for '[AVR:] Looking for an AVR FFT tutorial' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/logic/dsps.htm?key=fft
Search entire site for: 'Looking for an AVR FFT tutorial'.

Exact match. Not showing close matches.
PICList Thread
'[AVR:] Looking for an AVR FFT tutorial'
2004\04\18@093453 by Mark Jordan

flavicon
face
       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

flavicon
face
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_OUTmarkTakeThisOuTspamCPOVO.NE        To:     .....PICLISTKILLspamspam@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 listservspamKILLspammitvma.mit.edu with SET PICList DIGEST in the body

2004\04\20@102306 by Mark Jordan

flavicon
face
On 20 Apr 2004 at 8:43, .....Richard.ProsserKILLspamspam.....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
EraseMEpiclist-unsubscribe-requestspam_OUTspamTakeThisOuTmitvma.mit.edu

2004\04\20@170052 by Richard.Prosser

flavicon
face
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
                   <markspamspam_OUTCPOVO.NE        To:     @spam@PICLISTKILLspamspamMITVMA.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.ProsserKILLspamspamPOWERWARE.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
RemoveMEpiclist-unsubscribe-requestTakeThisOuTspammitvma.mit.edu

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

2004\04\20@191117 by Mark Jordan

flavicon
face
On 21 Apr 2004 at 8:52, TakeThisOuTRichard.ProsserEraseMEspamspam_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)/32768-Q2+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
RemoveMEpiclist-unsubscribe-requestspamTakeThisOuTmitvma.mit.edu

2004\04\20@202735 by Richard.Prosser

flavicon
face
Thanks - will have to have a play with it!

RP



On 21 Apr 2004 at 8:52, Richard.ProsserEraseMEspam.....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)/32768-Q2+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
EraseMEpiclist-unsubscribe-requestspammitvma.mit.edu

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

2004\04\21@024050 by Richard.Prosser

flavicon
face
Thanks - will have to have a play with it!

RP



On 21 Apr 2004 at 8:52, RemoveMERichard.Prosserspam_OUTspamKILLspamPOWERWARE.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)/32768-Q2+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
RemoveMEpiclist-unsubscribe-requestTakeThisOuTspamspammitvma.mit.edu

--
http://www.piclist.com hint: To leave the PICList
EraseMEpiclist-unsubscribe-requestspamspamspamBeGonemitvma.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

face
flavicon
face
On Tue, 20 Apr 2004, Mark Jordan wrote:

> On 20 Apr 2004 at 8:43, RemoveMERichard.ProsserKILLspamspamPOWERWARE.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 8-DTMF 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

flavicon
face
       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 8-DTMF 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*Q1-Q2+sample
Move Q1 to Q2
Move Q0 to Q1

After a block of N samples:
MAG = SQRT(Q1^2+Q2^2-Q1*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

picon face
>         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
2-wire,
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

flavicon
face
On 27 Apr 2004 at 16:20, Kenneth Lumia wrote:

{Quote hidden}

       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 half-duplex 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...