Looking for an FFT block diagram for programming purposes

[gmv]

Hello,
I have powerbasic for DOS and I want to
make a number crunching FFT program but
do not understand the math involved.
I need to see a block diagram of how the
calculations are carried out.
Anyone that offer such a thing
for free is welcome to post this thread.
I will share my program freely via my personal
web site once it is compiled.
By number crunching I am not talking
graphical readout here, just good
old fashioned numbers.


--
Sincerely,
gmv
address munged, no emails
too many spams & Scams & Viruses

 

[Gareth]

gmv wrote:

Hello,
I have powerbasic for DOS and I want to
make a number crunching FFT program but
do not understand the math involved.
I need to see a block diagram of how the
calculations are carried out.
Anyone that offer such a thing
for free is welcome to post this thread.
I will share my program freely via my personal
web site once it is compiled.
By number crunching I am not talking
graphical readout here, just good
old fashioned numbers.

I suggest you look at section 12 of Numerical Recipes in C.

http://lib-www.lanl.gov/numerical/bookcpdf.html

It has a good explaination of FFTs and some example code. Obviously the
code is in C not Basic, but it is well explained so you can probably
work out a Basic version even if you don't know any C.

--
-----------------------------------------------------------------------
To reply to me directly:

Replace privacy.net with: totalise DOT co DOT uk and replace me with
gareth.harris

 

[John Larkin]

On Tue, 16 Mar 2004 21:42:31 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

Hello,
I have powerbasic for DOS and I want to
make a number crunching FFT program but
do not understand the math involved.
I need to see a block diagram of how the
calculations are carried out.
Anyone that offer such a thing
for free is welcome to post this thread.
I will share my program freely via my personal
web site once it is compiled.
By number crunching I am not talking
graphical readout here, just good
old fashioned numbers.

Do you really want to write it yourself? If you google "powerbasic
fft" there's lots of stuff out there, free or not. I've used a couple
myself.

John

 

[gmv]

"Gareth" <me@privacy.net> Typed in message news:c37tf6$24m4fo$1@ID-211380.news.uni-berlin.de...

gmv wrote:

Hello,
I have powerbasic for DOS and I want to
make a number crunching FFT program but
do not understand the math involved.
I need to see a block diagram of how the
calculations are carried out.
Anyone that offer such a thing
for free is welcome to post this thread.
I will share my program freely via my personal
web site once it is compiled.
By number crunching I am not talking
graphical readout here, just good
old fashioned numbers.


I suggest you look at section 12 of Numerical Recipes in C.

http://lib-www.lanl.gov/numerical/bookcpdf.html

It has a good explaination of FFTs and some example code. Obviously the
code is in C not Basic, but it is well explained so you can probably
work out a Basic version even if you don't know any C.

--
-----------------------------------------------------------------------
To reply to me directly:

Replace privacy.net with: totalise DOT co DOT uk and replace me with
gareth.harris

I understand and will have a look
what I have found follows:


************************ cut *********************
N2=N
Do 10 K=1,M
N1=N2
N2=N2/2
E=6.28319
A=0
Do 20 J=1,N2
C=cos(A)
S=-sin(A)
A=J*E
Do 30 I=J,N,N1
L=I+N2
XT=X(I)-X(L)
X(I)=X(I)+X(L)

YT=Y(I)-Y(L)
Y(I)=Y(I)+Y(L)

X(L)=XT*C-YT*S
Y(L)=XT*S+YT*C
30 Continue
20 Continue
10 Continue

Notes: M=LOG2(N)
X=real
Y=imaginary
XT & YT are temporary
X(L) & Y(L) are the final arrays
input or output will be bit reversed
***************** cut **********************

I do not understand this, maybe you can explain some of it.

If this is all there is to a FFT routine
then why has it been so well guarded.



--
Sincerely,
gmv
address munged, no emails
too many spams & Scams & Viruses

 

[gmv]

Anything I can understand and have the ability to carry
out when it comes to academic stuff I will do myself.
But I manytimes need outsiders like you to
show me the way.
I have trouble wading through the muck in google
to get what I am after that is why I am here.
I have yet someone to post the exact answer
which I am 100% sure is out there.
The government has put the fear of god into
those that know the answer because this stuff
used to be a military secret.

--
Sincerely,
gmv
address munged, no emails
too many spams & Scams & Viruses

"John Larkin" <jjlarkin@highSNIPlandTHIStechPLEASEnology.com> Typed in message news:n7ue501cneoo835se3g4gi4633hs77eeiu@4ax.com...

On Tue, 16 Mar 2004 21:42:31 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

Hello,
I have powerbasic for DOS and I want to
make a number crunching FFT program but
do not understand the math involved.
I need to see a block diagram of how the
calculations are carried out.
Anyone that offer such a thing
for free is welcome to post this thread.
I will share my program freely via my personal
web site once it is compiled.
By number crunching I am not talking
graphical readout here, just good
old fashioned numbers.

Do you really want to write it yourself? If you google "powerbasic
fft" there's lots of stuff out there, free or not. I've used a couple
myself.

John

 

[John Larkin]

On Tue, 16 Mar 2004 22:48:33 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

Anything I can understand and have the ability to carry
out when it comes to academic stuff I will do myself.
But I manytimes need outsiders like you to
show me the way.
I have trouble wading through the muck in google
to get what I am after that is why I am here.
I have yet someone to post the exact answer
which I am 100% sure is out there.
The government has put the fear of god into
those that know the answer because this stuff
used to be a military secret.

FFTs? You've got to be kidding.

John

 

[gmv]

"John Larkin" <jjlarkin@highSNIPlandTHIStechPLEASEnology.com> Typed in message news:7g1f501r1m5j641u328lga5k68nvlf9n4i@4ax.com...

On Tue, 16 Mar 2004 22:48:33 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

Anything I can understand and have the ability to carry
out when it comes to academic stuff I will do myself.
But I manytimes need outsiders like you to
show me the way.
I have trouble wading through the muck in google
to get what I am after that is why I am here.
I have yet someone to post the exact answer
which I am 100% sure is out there.
The government has put the fear of god into
those that know the answer because this stuff
used to be a military secret.

FFTs? You've got to be kidding.

John

Don't play games with me you young
whipper snapper.


--
Sincerely,
gmv
address munged, no emails
too many spams & Scams & Viruses

 

[Ken Smith]

In article <bxK5c.7$HU3.6194@news-west.eli.net>,
gmv <NoEmail@ThisWay.123> wrote:

Hello,
I have powerbasic for DOS and I want to

Too bad it isn't a Sinclair ZX81. If have a FFT in Sinclair ZX81 code.

--
--
kensmith@rahul.net forging knowledge

 

[gmv]

"Gareth" <me@privacy.net> Typed in message news:c37tf6$24m4fo$1@ID-211380.news.uni-berlin.de...

gmv wrote:

Hello,
I have powerbasic for DOS and I want to
make a number crunching FFT program but
do not understand the math involved.
I need to see a block diagram of how the
calculations are carried out.
Anyone that offer such a thing
for free is welcome to post this thread.
I will share my program freely via my personal
web site once it is compiled.
By number crunching I am not talking
graphical readout here, just good
old fashioned numbers.


I suggest you look at section 12 of Numerical Recipes in C.

http://lib-www.lanl.gov/numerical/bookcpdf.html

It has a good explaination of FFTs and some example code. Obviously the
code is in C not Basic, but it is well explained so you can probably
work out a Basic version even if you don't know any C.

I downloaded and looked over everything
but it is using math above high school algebra
I need it explained in plain English and not
Math Language. I do not want to become a math expert
I just want to analyze some data. Maybe I can post
my data and some interested soul will do the
analysis for me that way we both might
learn something new. I just know the final
condensed routine is sickningly simple.
I find it disturbing that people are guarding
information in this manner.
I need the final result in plain English
and that is all I am saying here.
It must be in a form that can be programmed
into any language and not converted.
I do not want to buy any new software to do this
because I already have the tools on my machine.
I do not want to take a college course.
But like everything technical the security people are
trying to keep things secret and we must all fight
this secrecy and the people who control it.
Either someone is serious about helping me here
or please do not post to this thread.
I have witnessed the complex condensed so anyone can understand
and that is exactly what I am looking for
with the FFT routine.
This junk I see on the internet are all for University grads
not for the common man.


--
Sincerely,
gmv
address munged, no emails
too many spams & Scams & Viruses

--
-----------------------------------------------------------------------
To reply to me directly:

Replace privacy.net with: totalise DOT co DOT uk and replace me with
gareth.harris

 

[gmv]

I want plain English description of a FFT routine
not a bunch of psychobable.
Something the whole world can understand.

--
Sincerely,
gmv
address munged, no emails
too many spams & Scams & Viruses



"Ken Smith" <kensmith@violet.rahul.net> Typed in message news:c385nv$53h$2@blue.rahul.net...

In article <bxK5c.7$HU3.6194@news-west.eli.net>,
gmv <NoEmail@ThisWay.123> wrote:
Hello,
I have powerbasic for DOS and I want to

Too bad it isn't a Sinclair ZX81. If have a FFT in Sinclair ZX81 code.

--
--
kensmith@rahul.net forging knowledge

 

[Tim Auton]

"gmv" <NoEmail@ThisWay.123> wrote:
[snip]

I do not want to become a math expert
I just want to analyze some data. Maybe I can post
my data and some interested soul will do the
analysis for me that way we both might
learn something new. I just know the final
condensed routine is sickningly simple.
I find it disturbing that people are guarding
information in this manner.
I need the final result in plain English
and that is all I am saying here.

They are not guarding the information. The information is out there,
you simply don't have the maths or programming training to understand
it. That's fine. How you expect to use a tool you don't understand I
have no idea, but that's not my problem.

It must be in a form that can be programmed
into any language and not converted.
I do not want to buy any new software to do this
because I already have the tools on my machine.
I do not want to take a college course.
But like everything technical the security people are
trying to keep things secret and we must all fight
this secrecy and the people who control it.

You can learn all you need to write your own FFT routines in any
number of languages for free from the Internet (not as good as a book
or a course, but good enough). You unwillingness to learn the language
of mathematics on which fourier analysis is based or the programming
languages freely available code you have been directed to does *not*
make it a secret. It's just hard.

Either someone is serious about helping me here
or please do not post to this thread.

I am seriously trying to help you, as are others. It's highly unlikely
anybody is going to write a lengthy tutorial just for you. People are
generous, but not that generous.

You say you have Fortran and BASIC available to you.

Here is a library which can be used in Fortran. It is written in C,
but as it is a library you don't even need to look at the source code
(but you can if you like). It has good documentation and links to
explanatory material on FFTs.

http://www.fftw.org/

Here is some code apparently in BASIC that performs DFTs (not quite
FFTs, but you get the same result). I've not tried it myself, but it
appears to be close to what you want.

http://www.programmersheaven.com/zone6/cat28/3809.htm


Tim
--
Love is a travelator.

 

[Greg Neill]

"gmv" <NoEmail@ThisWay.123> wrote in message news:XjN5c.13$HU3.6302@news-west.eli.net...

I want plain English description of a FFT routine
not a bunch of psychobable.
Something the whole world can understand.

An FFT is a mathematical transformation from
the time domain to the frequency domain.

That's it.

If you don't have the maths to understand it,
well, there's not much anyone other than you
can do about it.

As the expression goes, if you have something
to say, write an equation. If you have nothing
to say, write an essay.

 

[gmv]

"Tim Auton" <tim.auton@uton.[groupSexWithoutTheY]> Typed in message news:it8f50hl6sb31dgkjs6oakh0k9j4pm3r5i@4ax.com...

"gmv" <NoEmail@ThisWay.123> wrote:
[snip]
I do not want to become a math expert
I just want to analyze some data. Maybe I can post
my data and some interested soul will do the
analysis for me that way we both might
learn something new. I just know the final
condensed routine is sickningly simple.
I find it disturbing that people are guarding
information in this manner.
I need the final result in plain English
and that is all I am saying here.

They are not guarding the information. The information is out there,
you simply don't have the maths or programming training to understand
it. That's fine. How you expect to use a tool you don't understand I
have no idea, but that's not my problem.

It must be in a form that can be programmed
into any language and not converted.
I do not want to buy any new software to do this
because I already have the tools on my machine.
I do not want to take a college course.
But like everything technical the security people are
trying to keep things secret and we must all fight
this secrecy and the people who control it.

You can learn all you need to write your own FFT routines in any
number of languages for free from the Internet (not as good as a book
or a course, but good enough). You unwillingness to learn the language
of mathematics on which fourier analysis is based or the programming
languages freely available code you have been directed to does *not*
make it a secret. It's just hard.

Either someone is serious about helping me here
or please do not post to this thread.

I am seriously trying to help you, as are others. It's highly unlikely
anybody is going to write a lengthy tutorial just for you. People are
generous, but not that generous.

You say you have Fortran and BASIC available to you.

Here is a library which can be used in Fortran. It is written in C,
but as it is a library you don't even need to look at the source code
(but you can if you like). It has good documentation and links to
explanatory material on FFTs.

http://www.fftw.org/

Here is some code apparently in BASIC that performs DFTs (not quite
FFTs, but you get the same result). I've not tried it myself, but it
appears to be close to what you want.

http://www.programmersheaven.com/zone6/cat28/3809.htm


Tim
--
Love is a travelator.

I am not a young man and I am coerced
by this country to be on anti-psychotic drugs.
These drugs I am on are not conducive to good learning
because they affect my mind in ways that
destroy my ability to concentrate on learning.
If you have never had a run in with the security
people like the secret service you lack the
capacity to understand just how nasty your
very own country can really be.
What I need is something I can understand at my own
level of current understanding or a fully
functional FFT program that will take
my raw data files to produce a readout.
If you can not help me to analyze my raw data
in one way or another without special foreknowledge
then none of you can be of any help to me.
Thanks just the same. I will check out your sites
but i expect to see just more of the same kind of
language geared only for the University types.
Universities are places for people that have not been
damned by the security peoples like I have been.


--
Sincerely,
gmv
address munged, no emails
too many spams & Scams & Viruses

Love is unabridged Freedoms.

 

[gmv]

"Greg Neill" <gneillREM@OVE.THIS.netcom.ca> Typed in message news:CCO5c.15699$E71.990399@news20.bellglobal.com...

"gmv" <NoEmail@ThisWay.123> wrote in message news:XjN5c.13$HU3.6302@news-west.eli.net...
I want plain English description of a FFT routine
not a bunch of psychobable.
Something the whole world can understand.

An FFT is a mathematical transformation from
the time domain to the frequency domain.

That's it.

If you don't have the maths to understand it,
well, there's not much anyone other than you
can do about it.

You can provide a block diagram that shows
how to do the programming if you don't know
how to show FFT in this way I will fully understand.
Most of you eggheads can't speak to the common man.
Your minds are blinded by all that bright math.
You might also take my data and run your own
FFT on it and provide me with the results
but i think you lack the ability to do this.
I am trying to do something here that should by
all rights be incredibly simple but it seems
I am dealing with the CIA here that can muck up
a wet dream.

As the expression goes, if you have something
to say, write an equation. If you have nothing
to say, write an essay.

 

[Greg Neill]

"gmv" <NoEmail@ThisWay.123> wrote in message news:28P5c.2$Lf5.134@news-west.eli.net...

You can provide a block diagram that shows
how to do the programming if you don't know
how to show FFT in this way I will fully understand.
Most of you eggheads can't speak to the common man.
Your minds are blinded by all that bright math.
You might also take my data and run your own
FFT on it and provide me with the results
but i think you lack the ability to do this.
I am trying to do something here that should by
all rights be incredibly simple but it seems
I am dealing with the CIA here that can muck up
a wet dream.

You've pretty much managed to insult everyone who
might be able to help you. No one here owes you
anything. One begs for charity, not demands it.

 

[Ben Bradley]

In
alt.lang.powerbasic,comp.lang.basic.powerbasic,sci.electronics.design
"gmv" <NoEmail@ThisWay.123> wrote:

Hello,
I have powerbasic for DOS and I want to
make a number crunching FFT program but
do not understand the math involved.

{ snip, causing a step function in the quote cascade }

I understand and will have a look
what I have found follows:


************************ cut *********************
N2=N
Do 10 K=1,M
N1=N2
N2=N2/2
E=6.28319
A=0
Do 20 J=1,N2
C=cos(A)
S=-sin(A)

C JUST A NOTE ABOUT er, sorry, having a keypunch flashback.
C Just a note about these variables C and S, they are known
C in FFT's as "twiddle factors" - I don't completely follow
C this code and how things are done in it but to get faster
C execution calculate the C and S values in an earlier loop
C and save them in arrays for accessing in a complex-number
C "butterfly calculation" below.

A=J*E

C Hmm, E is two pi, J is an integer from 1 to N2, so A will
C always be multiples of two pi - the cosine will always be
C 1 and the sine always zero. I just don't trust the code.
C Never try to follow undocumented code. Toss it and start
C over. Even the variable names suck.

Do 30 I=J,N,N1
L=I+N2
XT=X(I)-X(L)
X(I)=X(I)+X(L)

YT=Y(I)-Y(L)
Y(I)=Y(I)+Y(L)

X(L)=XT*C-YT*S
Y(L)=XT*S+YT*C
30 Continue
20 Continue
10 Continue

C ALSO REMEMBER, GOD IS REAL UNLESS DECLARED INTEGER
C (sorry, old FORTRAN joke)

Notes: M=LOG2(N)
X=real
Y=imaginary
XT & YT are temporary
X(L) & Y(L) are the final arrays
input or output will be bit reversed
***************** cut **********************

I do not understand this, maybe you can explain some of it.

I'd write a book, but I already have a few on the topic.

If this is all there is to a FFT routine
then why has it been so well guarded.

Only we experienced and highly trusted DSP engineers know about it,
but I'll tell you a secret URL of an online book that will let you in
on the FFT secrets, if you promise not to tell anyone:
http://www.dspguide.com
Also, there's a Speshul Sooper Seekrit newsgroup where these things
are discussed where you don't have to post to alt.helen.bach to beg
for answers to your questions - it's comp.dsp.

-----
http://mindspring.com/~benbradley

 

[John Larkin]

On Wed, 17 Mar 2004 02:57:02 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

Most of you eggheads can't speak to the common man.
Your minds are blinded by all that bright math.

Good Grief, an FFT *is* math. You seem to want some sort of Zen math
that's not math. You may as well ask for somebody to write down all
the directions for a heart transplant on the back of a cocktail
napkin.

It's weird that nobody would think of asking for plans for a cheap,
simple way to build an airplane, but people ask for the electronic
equivalent all the time.

John

 

[Mac]

On Tue, 16 Mar 2004 22:48:33 +0000, gmv wrote:

Anything I can understand and have the ability to carry
out when it comes to academic stuff I will do myself.
But I manytimes need outsiders like you to
show me the way.
I have trouble wading through the muck in google
to get what I am after that is why I am here.
I have yet someone to post the exact answer
which I am 100% sure is out there.
The government has put the fear of god into
those that know the answer because this stuff
used to be a military secret.

1) Please don't top-post. It makes the conversation difficult to follow.

2) Please don't put anything after a sig indicator except a sig. In the
message I am replying to, the entire thing you responded to was after your
sig, so my newsreader didn't copy it when I hit reply. This is NOT a flaw
in my newsreader, it is a flaw in your post.

The FFT was never a military secret. The two guys who discovered it,
Cooley and Tukey, published it all over the place. It was very exciting
(you can tell from the textbooks written at around that time) and made a
huge impact in the Electrical Engineering world, because a large number of
things which had previously been impractical were suddenly practical.
Obviously it has loads of military applications, but it was never secret.
(Unless you are alleging that the military secretly knew of the
Cooley-Tukey algorithm prior to those two disclosing it. Not impossible,
but not likely, either.)

I have a simple FFT routine written in C. If you want me to post it, I
will (if you can think of somewhere topical). But I will tell you right
now, I have spent many, many hours trying to get a real deep intuitive
understanding of the FFT, and I have never succeeded. I know what it does,
but I don't feel totally comfortable with it anyway. And to tell the
truth, I think most people who use it regularly have never implemented it
and don't necessarily have any better understanding of it than I do.

The FFT function itself is only 30 lines, but there are a number of
supporting functions and structures.

--Mac

 

[Mac]

On Tue, 16 Mar 2004 21:21:15 +0000, Greg Neill wrote:

"gmv" <NoEmail@ThisWay.123> wrote in message
news:XjN5c.13$HU3.6302@news-west.eli.net...
I want plain English description of a FFT routine not a bunch of
psychobable.
Something the whole world can understand.

An FFT is a mathematical transformation from the time domain to the
frequency domain.

That's it.

This totally trivializes the FFT. It might be a good description of a
discrete Fourier transform, but it says nothing about the insight of
Cooley and Tukey which allows people to calculate discrete Fourier
transforms much faster than they ever had before. In other words, the FFT
is a miraculously fast way of calculating discrete Fourier transforms of
data series. The original Cooley-Tukey algorithm only works when the
number of elements in the data series is a power of two (2^n, where n is
an integer), but there are ways around this limitation and variant
algorithms inspired by Cooley's and Tukey's insight.

If you don't have the maths to understand it, well, there's not much
anyone other than you can do about it.

As the expression goes, if you have something to say, write an equation.
If you have nothing to say, write an essay.

--Mac

 

[Spehro Pefhany]

On Tue, 16 Mar 2004 20:37:25 -0800, the renowned "Mac" <foo@bar.net>
wrote:

On Tue, 16 Mar 2004 21:21:15 +0000, Greg Neill wrote:

"gmv" <NoEmail@ThisWay.123> wrote in message
news:XjN5c.13$HU3.6302@news-west.eli.net...
I want plain English description of a FFT routine not a bunch of
psychobable.
Something the whole world can understand.

An FFT is a mathematical transformation from the time domain to the
frequency domain.

That's it.

This totally trivializes the FFT. It might be a good description of a
discrete Fourier transform, but it says nothing about the insight of
Cooley and Tukey which allows people to calculate discrete Fourier
transforms much faster than they ever had before. In other words, the FFT
is a miraculously fast way of calculating discrete Fourier transforms of
data series. The original Cooley-Tukey algorithm only works when the
number of elements in the data series is a power of two (2^n, where n is
an integer), but there are ways around this limitation and variant
algorithms inspired by Cooley's and Tukey's insight.

There is what looks like quite a good and lucid description of the
derivation of the FFT in "Numerical Recipes in C", pages 504-508. This
book, which I paid something like $70 for, has been made available
online for free thanks to the publisher, Cambridge University Press
(link below). They also describe the DFT in that book. I have not
dabbled in the inner workings of the FFT since a friend in grad school
showed me a variation he'd come up with.. many years ago.

Keep in mind that a certain level of math (equivalent to first or
second year university) is *required* to understand the terminology
and the operations.

http://www.library.cornell.edu/nr/


Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com