FFT source code for Stamp?
Archiver
Posts: 46,084
Looking for FFT source code written in Stamp Basic.
Google search returned nothing.
Thanks Vaclav
Google search returned nothing.
Thanks Vaclav
Comments
> Looking for FFT source code written in Stamp Basic.
> Google search returned nothing.
>
You won't find anything, Vaclav. The Stamps are microcontrollers, not signal
processor chips. They do not have the mathematical instructions required to
do a Fourier transform and they do not have enough memory to hold the data.
Gary
transforms (a Hartley transform would probably be the most doable). The math
isn't the problem. The two problems are 1) speed and 2) storage. Even if you
used the scratch pad ram on a BS2P you could only store a few samples and it
would take a lot of time to do the processing.
Instead of trying to point you to a reference on integer FFT, I think it
would be better to ask: "What are you trying to do?"
Al Williams
AWC
* NEW: PAK-Vc -- up to 256 PWM outputs! http://www.al-williams.com/pak5.htm
>
Original Message
> From: Gary W. Sims [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=skfiSerfoUzHT0akpBWnzFF-iY1OI3E9nVlrCL5zXSfmbJuSHTgHjsIMu-gyw3NkiHv4nU3GSPJnRdJrF7I]simsgw@c...[/url
> Sent: Saturday, October 25, 2003 4:45 PM
> To: basicstamps@yahoogroups.com
> Subject: Re: [noparse][[/noparse]basicstamps] FFT source code for Stamp?
>
>
> From: "aa7ej" <aa7ej@y...>
>
> > Looking for FFT source code written in Stamp Basic.
> > Google search returned nothing.
> >
>
> You won't find anything, Vaclav. The Stamps are
> microcontrollers, not signal processor chips. They do not
> have the mathematical instructions required to do a Fourier
> transform and they do not have enough memory to hold the data.
>
> Gary
>
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the
> Subject and Body of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to
> http://docs.yahoo.com/info/terms/
>
>
>
one simple Basic FFT source code and immediately realized that a)
Stamp won't do floating-point arithmetic b) there in not
enough "registers" to do the math anyway.
I am not sure that I want to write integer subroutines to do floating
point conversion, but I will check the manual again to see if it is
possible. Maybe some kind of math coprocessor or Basic Stamp as math
coprocessor would work.
My application is to analyze short acoustic signal bursts and than
track (filter) specific frequency and the processing speed is not
that important.
I will search for Hartley transfer but would appreciate more info.
Thanks Vaclav
>
> I am not sure that I want to write integer subroutines
> to do floating point conversion, [noparse][[/noparse]...]
I know I don't, but it would just be work for me. I shouldn't insist you
won't find it entertaining. I'm designing a power supply and my
brother-in-law keeps saying "Sheez, why don't you just buy one?" The
difference is I never designed a supply before. Always bought one or hired
somebody to do it. So it's fun now that I'm retired. You'll have to decide
which category this falls into for you. Because you probably can hang enough
stuff off the side of the Stamp to do this if speed is really not important.
(I'd say "certainly" but you might claim it was cheating if I suggested
adding a radio link to the nearest Pentium desktop<g>.)
> Maybe some kind of math coprocessor or Basic Stamp as math
> coprocessor would work.
>
This definitely. Parallax has one on sale right now for $25 that is intended
for use with the Stamps. Ironically, I believe it was Al Williams who
designed it. Ironically, because it was Al who just said:
> Actually, the Stamp could probably do many of the integer FFT-type
> transforms (a Hartley transform would probably be the most doable).
I'm sure he's right, but I seriously doubt you could get an answer before
next week using unsigned 16-bit operations and a 4 kHz to 12 kHz clock.
That's just intuition, and maybe seriously flawed since I never played with
FFT's either after school, at least not personally, and Al clearly has.
Nevertheless, my own approach would be to make the Stamp the conductor for a
small band of side chips. First, I'd add a math co-processor and an EEPROM
sized for the job so you're not always worried about overrunning your code
space.
> My application is to analyze short acoustic signal bursts and than
> track (filter) specific frequency and the processing speed is not
> that important.
>
Unless this is completely for fun, you might consider two alternatives as
well: analog processing of the signal; and a different digital processor
that acts as a black box analyzer. The second option would mean not even
getting the Stamp involved in directing the steps of the analysis. Just let
it handle routing, and the control activity associated with gathering the
signal and responding to the results of analysis.
The feasibility of the analog processing option depends on what specifically
you are doing, but we used analog processing for many purposes well into the
era of mini-computers. Well, maybe not "well into" but at least up to the
start of that era. I think we only had them around for legacy support by the
time we started buying Vax minis. Nevertheless, analog is a powerful
technique. You'd be surprised how much processing a $5 op-amp variant can
do.
Incidentally. Before someone suggests "why bother with the Stamp if you buy
all those other chips?" let me note something from experience. That "vital
analysis function" that dominates thinking at the start of a development
rarely turns out to be the stumbling block. The vital piece always seems to
work fine in a test situation, but putting it to use wraps it in so many
layers of practical issues that it turns out to be ten percent of the
trouble and cost. Sometimes one percent. The remainder of the project is
where all the work comes, and that's where the Stamp will shine because most
of the work has been done for you already.
Gary
> that is intended for use with the Stamps. Ironically, I
> believe it was Al Williams who designed it. Ironically,
> because it was Al who just said:
Two points. First, I noticed on the Parallax site that they are showing the
PAK-9 and PAK-10 as discontinued. This simply means Parallax is not carrying
them anymore. They are still available from us and our other distributors --
they aren't going anywhere.
Second, keep in mind that it would be very difficult and slow to do even a
Hartley transform or an integer FFT on the Stamp. I think it would be
possible, but not very practical because of the speed and memory
constraints. So I'm not seriously suggesting you spend much time
investigating the Hartley unless you are doing something that I don't
understand (for example, reading 32 samples once an hour and wanting to do
an FFT on them -- something low bandwidth like that).
Al Williams
AWC
*New kits: http://www.al-williams.com/kits.htm
memory and computation intensive for the Stamp. Convolution has to
pass multiple times through the (large) data array. An external math
chip like the pak would be limited by communication with the already
slow stamp. (Of course, unless Al comes out with a pak that receives
the array of data and a few milliseconds later spits out the DFT!)
I did have an application where the Stamp sufficed. This involved
several transponders, that "beeped" at intervals of several seconds.
Each had its own regular beep rate, none the same. All signals came
in overlapping into one Stamp pin. So over the long term there was a
long series of zeros and ones due to the mingled beeps. The
objective was to determine which were present during each period of
10 minutes. That was problem that could be solved with a DFT, but I
did not want to have to store the sequence of zeros and ones in an
array, nor face a convolution at the end. So I came up with a scheme
to work in the time domain. In real time the Stamp accumulated the
intervals between successive beeps (not just the immediate interval
to the last beep, but going back several seconds in time, so each new
beep could enter data into several accumulators). The result,
available immediately at the end of the interval, was like a DFT, in
that the rates that were present had high counts in their period
accumulators, while alias frequencies were spread out low. It took
some careful choice of the transponder beep rates, which we also
controlled.
-- Tracy
>Second, keep in mind that it would be very difficult and slow to do even a
>Hartley transform or an integer FFT on the Stamp. I think it would be
>possible, but not very practical because of the speed and memory
>constraints. So I'm not seriously suggesting you spend much time
>investigating the Hartley unless you are doing something that I don't
>understand (for example, reading 32 samples once an hour and wanting to do
>an FFT on them -- something low bandwidth like that).
algorithms were written which performed transforms "in place" to
conserve memory. Some of these "butterfly transforms" have been adapted
for PIC use. I recall seeing assembly code for one of these in an
application note on the Microchip site.
Dennis
Original Message
From: Tracy Allen [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=VnP-l2SRwSi1jDKmG2BEVNXA8IoSHecnvDqrFgPmvXupXBxYuT4rz8fRrGsYqPXR_PZdJWsXzfXW3v4tKg]tracy@e...[/url
Sent: Sunday, October 26, 2003 12:11 PM
To: basicstamps@yahoogroups.com
Subject: RE: [noparse][[/noparse]basicstamps] Re: FFT source code for Stamp?
I'd agree with Al, that even the DFT using integer transforms is too
memory and computation intensive for the Stamp. Convolution has to
pass multiple times through the (large) data array. An external math
chip like the pak would be limited by communication with the already
slow stamp. (Of course, unless Al comes out with a pak that receives
the array of data and a few milliseconds later spits out the DFT!)
I did have an application where the Stamp sufficed. This involved
several transponders, that "beeped" at intervals of several seconds.
Each had its own regular beep rate, none the same. All signals came
in overlapping into one Stamp pin. So over the long term there was a
long series of zeros and ones due to the mingled beeps. The
objective was to determine which were present during each period of
10 minutes. That was problem that could be solved with a DFT, but I
did not want to have to store the sequence of zeros and ones in an
array, nor face a convolution at the end. So I came up with a scheme
to work in the time domain. In real time the Stamp accumulated the
intervals between successive beeps (not just the immediate interval
to the last beep, but going back several seconds in time, so each new
beep could enter data into several accumulators). The result,
available immediately at the end of the interval, was like a DFT, in
that the rates that were present had high counts in their period
accumulators, while alias frequencies were spread out low. It took
some careful choice of the transponder beep rates, which we also
controlled.
-- Tracy
>Second, keep in mind that it would be very difficult and slow to do
>even a Hartley transform or an integer FFT on the Stamp. I think it
>would be possible, but not very practical because of the speed and
>memory constraints. So I'm not seriously suggesting you spend much time
>investigating the Hartley unless you are doing something that I don't
>understand (for example, reading 32 samples once an hour and wanting to
>do an FFT on them -- something low bandwidth like that).
To UNSUBSCRIBE, just send mail to:
basicstamps-unsubscribe@yahoogroups.com
from the same email address that you subscribed. Text in the Subject
and Body of the message will be ignored.
Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
which is often what FFT is for, you can take the approach of constructing
band-pass filters (which are relatively simple RC circuits) to filter
frequency distribution before the ADC. I've done similar stuff to this
before.
On Sat, 25 Oct 2003, Al Williams wrote:
> Actually, the Stamp could probably do many of the integer FFT-type
> transforms (a Hartley transform would probably be the most doable). The math
> isn't the problem. The two problems are 1) speed and 2) storage. Even if you
> used the scratch pad ram on a BS2P you could only store a few samples and it
> would take a lot of time to do the processing.
>
> Instead of trying to point you to a reference on integer FFT, I think it
> would be better to ask: "What are you trying to do?"
>
> Al Williams
> AWC
> * NEW: PAK-Vc -- up to 256 PWM outputs! http://www.al-williams.com/pak5.htm
>
>
> >
Original Message
> > From: Gary W. Sims [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=EKTktJBgzPA82oxZpTjlhTiwVoOpJ6pbmwEOGU2Wq-xr_lr4zlBiTvkhASn1SV6qQGzObVuoLUZMRl08_A8]simsgw@c...[/url
> > Sent: Saturday, October 25, 2003 4:45 PM
> > To: basicstamps@yahoogroups.com
> > Subject: Re: [noparse][[/noparse]basicstamps] FFT source code for Stamp?
> >
> >
> > From: "aa7ej" <aa7ej@y...>
> >
> > > Looking for FFT source code written in Stamp Basic.
> > > Google search returned nothing.
> > >
> >
> > You won't find anything, Vaclav. The Stamps are
> > microcontrollers, not signal processor chips. They do not
> > have the mathematical instructions required to do a Fourier
> > transform and they do not have enough memory to hold the data.
> >
> > Gary
> >
> >
> >
> > To UNSUBSCRIBE, just send mail to:
> > basicstamps-unsubscribe@yahoogroups.com
> > from the same email address that you subscribed. Text in the
> > Subject and Body of the message will be ignored.
> >
> >
> > Your use of Yahoo! Groups is subject to
> > http://docs.yahoo.com/info/terms/
> >
> >
> >
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and Body
of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
Sean T. Lamont, CTO / Chief NetNerd, Abstract Software, Inc. (ServNet)
Seattle - Bellingham - Vancouver - Portland - Everett - Tacoma - Bremerton
email: lamont@a... WWW: http://www.serv.net
"Do not fear mistakes, There Are None" - Miles Davis
On Sun, 26 Oct 2003, aa7ej wrote:
> I should have known better than posting this request here. I found
> one simple Basic FFT source code and immediately realized that a)
> Stamp won't do floating-point arithmetic b) there in not
> enough "registers" to do the math anyway.
>
> I am not sure that I want to write integer subroutines to do floating
> point conversion, but I will check the manual again to see if it is
> possible. Maybe some kind of math coprocessor or Basic Stamp as math
> coprocessor would work.
>
> My application is to analyze short acoustic signal bursts and than
> track (filter) specific frequency and the processing speed is not
> that important.
>
> I will search for Hartley transfer but would appreciate more info.
> Thanks Vaclav
>
>
>
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and Body
of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
Sean T. Lamont, CTO / Chief NetNerd, Abstract Software, Inc. (ServNet)
Seattle - Bellingham - Vancouver - Portland - Everett - Tacoma - Bremerton
email: lamont@a... WWW: http://www.serv.net
"Do not fear mistakes, There Are None" - Miles Davis
> > > Sent: Saturday, October 25, 2003 4:45 PM
> > > To: basicstamps@yahoogroups.com
> > > Subject: Re: [noparse][[/noparse]basicstamps] FFT source code for Stamp?
> > >
> > >
> > > From: "aa7ej" <aa7ej@y...>
> > >
> > > > Looking for FFT source code written in Stamp Basic.
> > > > Google search returned nothing.
If you are talking about Fourier transforms, have you looked at Parallax'
Optascope. One of the things is does is give you a crystal-clear real time
display of FFT.
Sid Weaver
W4EKQ
Port Richey, FL
[noparse][[/noparse]Non-text portions of this message have been removed]
> If you are talking about Fourier transforms, have you looked at
Parallax'
> Optascope. One of the things is does is give you a crystal-clear
real time
> display of FFT.
Search on Parallax site returned "Optascope is not in current product
inventory". So what exactly is it or was it? If it did FFT using
Stamp I am definetly interested how they did it.
I just don't see how can it be done with the integer math and with
limited number of registers.
Anyway,
appreciate all the comments and suggestions so far. I am considering
an analog approach, but the stumblimg block is still the math.
Have one question for the group, forgot who mentioned it, but there
must be a difference between "integral" Hartley transform
and "integer" transform. The info I read said that the difference
between Fourier and Hartley is using special "integral".
(I am no math genius and this FFT stuff will take a while to digest.)
As far as other hardware options I am looking at old TMS320C5X
evaluation board and cosidereing using it as a digital preprocessor
to whatever will do the math without unnecessary complications.
Using Basic Stamp2 was just convenient because I got one running even
with blown 5V regulator ! ( Are they suppose to be overload proof?
But not foolproof!)
Personally I would prefer processor in C development enviroment,
which is no guarantee that it would do the math better.
Thanks Vaclav
aa7ej@y... writes:
> Search on Parallax site returned "Optascope is not in current product
> inventory". So what exactly is it or was it? If it did FFT using
> Stamp I am definetly interested how they did it.
>
Just went to Parallax site, searched for Optascope and it came right up. If
you can't find it, try searching for "Understanding Signals". Optascope does
not use a Stamp. It plugs into a USB port on your PC and runs from its own
software.
Sid
[noparse][[/noparse]Non-text portions of this message have been removed]
>> If you are talking about Fourier transforms, have you looked at
>Parallax'
>> Optascope. One of the things is does is give you a crystal-clear
>real time
>> display of FFT.
>
>Search on Parallax site returned "Optascope is not in current product
>inventory". So what exactly is it or was it? If it did FFT using
>Stamp I am definetly interested how they did it.
The optascope is a tool that Parallax sells to help people learn
about signals and also helps with troubleshooting circuits that might
be made with a Stamp. It is an oscilloscope front end that uses your
PC as its display and control interface.
>I just don't see how can it be done with the integer math and with
>limited number of registers.
Right, forget it!! Especially if you want to "analyze short acoustic
bursts and then track a specific frequency".
>
>Anyway,
>appreciate all the comments and suggestions so far. I am considering
>an analog approach, but the stumblimg block is still the math.
If you need to detect the presence of certain frequencies, a phase
lock loop like the 8-pin LMC567 might serve your purpose. This chip
is often referred to as a "tone decoder".
>
>
>Have one question for the group, forgot who mentioned it, but there
>must be a difference between "integral" Hartley transform
>and "integer" transform. The info I read said that the difference
>between Fourier and Hartley is using special "integral".
>(I am no math genius and this FFT stuff will take a while to digest.)
There are hundreds of closely related algorithms out there for
computing transforms, where the input is a time series and the output
is a representation of the frequencies present. The Fourier
transform and Hartley start out as transforms in integral Calculus
involving continuous functions of time into frequency. On a
computer, those become summations over a set of digital samples taken
at discrete time into a set of discrete frequencies. (DFT=discrete
fourier transform) The digital values could be represented either
as floating point or as long integers. The computations are intense,
and a sequence of length N takes N^2 multiplications. Since these
transforms are so important in signals processing, and there is need
for real time results (i.e., radar, sonar), a horde of mathematicians
have expended effort to find short cuts. For example, the fast
fourier transform (FFT) reduces the number of multiplications to N
lg2 N. The constraint is that the length of the sequence has to be
fixed at a power of 2, or related algorithms that require the
sequence length to be highly composite. They work by breaking the
long sequence up into a nested problem of many short sequences. For
a sequence length of 1024, N^2=1048576, while N lg2 N = 10240. That
is a big difference, especially for an "integer" processor that does
not have a dedicated floating point unit. In small processors, memory
usage is also an issue. Some algorithms gain speed by setting up
extra memory arrays and moving a lot of data around in memory
(sorting, permuting), while other algorithms try to minimize the
memory requirements, even if it means a hit in speed.
There are other algorithms (usually called NTTs or number theoretic
transforms) that require the sequence length to be a prime number, or
a product of co-prime factors, and these are able to shave even more
off of the processing time. For example, hardware transform boxes
can be made that operate efficiently when the sequence length is a
Fermat prime, (N = 2^2^b+1), for example, 257 or 65537.
But none of that really helps make it feasible on the Stamp!
-- Tracy
appreciate your transform notes. As I said, I am no math guru and as
always have bitten off more than I can chew.
This LMC567 looks promising. I looks like I could use the Stamp to
control the VCO and get go / no go output, easy readable using Stamp.
I'll take closer look.
Vaclav
Original Message
From: "Sean T. Lamont .lost." <lamont@a...>
To: <basicstamps@yahoogroups.com>
Sent: Monday, October 27, 2003 2:29 PM
Subject: RE: [noparse][[/noparse]basicstamps] FFT source code for Stamp?
>
> If you want to do soemthing like frequency distribution of an analog wave,
> which is often what FFT is for, you can take the approach of constructing
> band-pass filters (which are relatively simple RC circuits) to filter
> frequency distribution before the ADC. I've done similar stuff to this
> before.
>
> On Sat, 25 Oct 2003, Al Williams wrote:
>
> > Actually, the Stamp could probably do many of the integer FFT-type
> > transforms (a Hartley transform would probably be the most doable). The
math
> > isn't the problem. The two problems are 1) speed and 2) storage. Even if
you
> > used the scratch pad ram on a BS2P you could only store a few samples
and it
> > would take a lot of time to do the processing.
> >
> > Instead of trying to point you to a reference on integer FFT, I think it
> > would be better to ask: "What are you trying to do?"
> >
> > Al Williams
> > AWC
> > * NEW: PAK-Vc -- up to 256 PWM outputs!
http://www.al-williams.com/pak5.htm
> >
> >
> > >
Original Message
> > > From: Gary W. Sims [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=nrwyg34xnt38u7315WBgnnLnoKPEeUk_GYAJmaDt1vJiUnWxgcH_G_kKsWZKMwP8JuqJydBpf1-lgC0BzTwM]simsgw@c...[/url
> > > Sent: Saturday, October 25, 2003 4:45 PM
> > > To: basicstamps@yahoogroups.com
> > > Subject: Re: [noparse][[/noparse]basicstamps] FFT source code for Stamp?
> > >
> > >
> > > From: "aa7ej" <aa7ej@y...>
> > >
> > > > Looking for FFT source code written in Stamp Basic.
> > > > Google search returned nothing.
> > > >
> > >
> > > You won't find anything, Vaclav. The Stamps are
> > > microcontrollers, not signal processor chips. They do not
> > > have the mathematical instructions required to do a Fourier
> > > transform and they do not have enough memory to hold the data.
> > >
> > > Gary
> > >
> > >
> > >
> > > To UNSUBSCRIBE, just send mail to:
> > > basicstamps-unsubscribe@yahoogroups.com
> > > from the same email address that you subscribed. Text in the
> > > Subject and Body of the message will be ignored.
> > >
> > >
> > > Your use of Yahoo! Groups is subject to
> > > http://docs.yahoo.com/info/terms/
> > >
> > >
> > >
> >
> >
> > To UNSUBSCRIBE, just send mail to:
> > basicstamps-unsubscribe@yahoogroups.com
> > from the same email address that you subscribed. Text in the Subject
and Body of the message will be ignored.
> >
> >
> > Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
> >
> >
> >
>
> Sean T. Lamont, CTO / Chief NetNerd, Abstract Software, Inc. (ServNet)
> Seattle - Bellingham - Vancouver - Portland - Everett - Tacoma - Bremerton
> email: lamont@a... WWW: http://www.serv.net
> "Do not fear mistakes, There Are None" - Miles Davis
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and
Body of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
>> --- In basicstamps@yahoogroups.com, Newzed@a... wrote:
>> If you are talking about Fourier transforms, have you looked at
>> Parallax' Optascope. One of the things is does is give you a
>> crystal-clear real time display of FFT.
>
> Search on Parallax site returned "Optascope is not in current
> product inventory".
Try http://makeashorterlink.com/?M2F812D56, but as someone said, this is an
oscilloscope. It will help you build circuits but it won't do the FFT "on"
the Stamp for you.
Gary