Looking for an FFT block diagram for programming purposes

[Richard Henry]

"gmv" <NoEmail@ThisWay.123> wrote in message
news:5vL5c.9$HU3.6301@news-west.eli.net...

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.

I used to work at a place that did FFTs in hardware before the software was
good enough to do them in real time. The FFT algorithm itself was in the
clear and was published in math books (you can read an online xerocopy of it
at http://www.ph.utexas.edu/~itiq/chiu/cooley/). Many of the applications
were well-known (we had college textbooks in the lab that described them).
Some techniques were closely guarded (and may be still: I haven't worked in
the field for over 20 years). What was highly confidential (and probably
still is today) was the input data (for example, high-precision sonobuoy
tapes of Russian submaries recorded on US Navy P3 aircraft (on my favorite
you could see the P3 engine noise every time it passed over the sonobuoy))
and the resulting output data, including pictures of the displays. There
was a little stir there when one of our hardware vendors used the output
chart of a secret tape to show off the capability of their printer in a
magazine ad - I still have a copy of that ad in my geek file.

 

[Richard Henry]

"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.

Here's a link to a block diagram of the "FFT Butterfly" for four data
points:

http://www.ee.calpoly.edu/~fdepiero/fdepiero_dsp_notes/notes%20&%20materials
/DSP%20fft4.pdf

For serious amounts of data (1024 points) the diagram is correspondingly
more complex.

 

[Mike]

On Tue, 16 Mar 2004 21:42:31 GMT, 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.

My reference is Oppenheim and Schafer, "Digital Signal Processing." They
spend chapter 6 discussing FFT algorithms. But that's an expensive book,
the DFT is inherently mathematical, and Oppenheim and Schafer don't shy
away from math.

The same information is available in various places on the web. The thing
you're looking for is called a butterfly diagram, which is a relatively
straightforward way to show the calculations involved in an FFT.

Google for "FFT butterfly". The very first link shows the first couple
steps in the derivation of the FFT, and there's a link to time decimation
block diagrams.

-- Mike --

 

[John Larkin]

On Wed, 17 Mar 2004 15:20:16 +0000 (UTC), kensmith@violet.rahul.net
(Ken Smith) wrote:

Everytime you see a waterfall display in the
movies you are looking at an FFT machine.

This is not true. You are looking at what some special effects guy wipped
together to look mysterious.

What's worse in movies is PPI radar displays; you *never* see one that
looks like anything but a stupid fake.

John

 

[Jim Thompson]

On Wed, 17 Mar 2004 13:54:00 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

I tried that and got some books from Fort Huachuca Arizona.
Those people at Fort Huachuca are all spys and they
are no better than you at explaining things.
The best books I have ever seen are ones from
a company called Diagnostic Retrieval and that
was when I had a Secret Clearance.
I can tell you how these eggheads work when
they make military equipment. They boil down all thier
complex equations into hardware that does all the
work for you. Today we got these computers and all
we need is thier boiled down work to do a lot of nifty things.
The security people are just like you guys complexifying
things so the common man can not have any power
or control.

[snip]

Yep, We have rendered you totally impotent... you can no longer get it
up... you will remain that way until you understand the maths (sic)
for yourself ;-)

...Jim Thompson
--
| James E.Thompson, P.E. | mens |
| Analog Innovations, Inc. | et |
| Analog/Mixed-Signal ASIC's and Discrete Systems | manus |
| Phoenix, Arizona Voice480)460-2350 | |
| E-mail Address at Website Fax480)460-2142 | Brass Rat |
| http://www.analog-innovations.com | 1962 |

John "Peace for our Time" Kerry, Neville Chamberlain of this Century

 

[changling]

"Greg Neill" <gneillREM@OVE.netcom.ca> wrote in news:NZZ5c.155$C87.4954
@weber.videotron.net:

"gmv" <NoEmail@ThisWay.123> wrote in message
news:t8X5c.11$Lf5.309@news-west.eli.net...
Like I said before their drugs have damaged my brain and my body.
I am hooked on them and can not simply stop.
The secret Service had me incarcerated for making veiled threats
against the President and the mental health people
were ordered by a judge to force these drugs on me for a whole year.
I am now hooked on them and can not stop.
Without them I can not sleep. Sleep deprivation
is a form of torture and is used for brainwashing.
You guys really need to learn what your nice
country is capable of doing to you.

We demand that you provide a block diagram showing
how these drugs work. While you're at it, please
diagram the legal system, the secret service, and the
whole mental health system. We demand that you
do this for free, on your own time.

well said. we are waiting

 

[Active8]

On Wed, 17 Mar 2004 04:59:16 GMT, Spehro Pefhany wrote:

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.

Care to expound on that? I've seen a few methods for code
optimization. Always up for a new technique.

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

--
Best Regards,
Mike

 

[Spehro Pefhany]

On Wed, 17 Mar 2004 12:32:46 -0500, the renowned Active8
<reply2group@ndbbm.net> wrote:

On Wed, 17 Mar 2004 04:59:16 GMT, Spehro Pefhany wrote:

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.

Care to expound on that? I've seen a few methods for code
optimization. Always up for a new technique.

No, sorry.

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

 

[John Larkin]

On Tue, 16 Mar 2004 20:26:28 -0800, "Mac" <foo@bar.net> wrote:

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.

I had it explained to me by a guy who really *did* understand it:
"It's just bookkeeping" he said.

John

 

[Kevin Aylward]

John Larkin wrote:

On Tue, 16 Mar 2004 20:26:28 -0800, "Mac" <foo@bar.net> wrote:


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.

Its *nothing* more than rearranging the terms of an equation. There is
nothing qualitatively more to know. It contains no new information than
what's in the basic definition of a Fourier transform.

ally 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.

What would be the point? What's important is understanding what a
(discrete) Fourier transform is and when to apply it. Doing the details
is mundane grunt work.

Having the same knowledge that 10,000's of other people have is a pure
waste of brain storage. Spend the time learning other things that are
both rare, and wanted, e.g. plumbing.

I had it explained to me by a guy who really *did* understand it:
"It's just bookkeeping" he said.

I like to call it "sums". You know, what we did Kindergarten.


Kevin Aylward
salesEXTRACT@anasoft.co.uk
http://www.anasoft.co.uk
SuperSpice, a very affordable Mixed-Mode
Windows Simulator with Schematic Capture,
Waveform Display, FFT's and Filter Design.

"quotes with no meaning, are meaningless" - Kevin Aylward.

 

[Gareth]

gmv wrote:

"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.

If you just want to analyse some data and don't want to understand the
maths you can do FFTs in Microsoft Excel. What is this data anyway?

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

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

 

[Greg Neill]

"gmv" <NoEmail@ThisWay.123> wrote in message news8X5c.5$Lf5.309@news-west.eli.net...

You are not telling me what I need to know here
What I need is 500 discreet spectrum points
on 1024 samples of data showing energy
vs frequency and nothing more but I need to look
at a frequency between 100 seconds in period and
maybe one or ten hertz.
If you have the executable code and know how to use it
why can't you take my raw data and analyze it for me.

Why? What do we owe you? You've been rude and
abnoxious, you refuse to follow proper ettiquette,
yet you demand that people spend time to help you
with a problem that is clearly solvable with a
little research effort on your part.

It would be much safer a thing then me trying to run
a exe file on my machine from outside sources.
I do not know what you mean by top posting.
If you are forcing me to some kind of convention
you need to take a hike because I am through
with following orders here gestapo tactics can
take a hike.

Case in point. Everyone here is a guest. Behave
like an asshole, and you'll get no respect, and no
help.

Your offer just exacerbates a preexisting condition
if it does not solve my problem here without any
fancy conversions. I have no "C" capabilities
and have no intention of learning it when
there are much nicer things like Basic and FORTRAN.

Boo hoo. Your ignorance must be a great comfort.

 

[Greg Neill]

"gmv" <NoEmail@ThisWay.123> wrote in message news:s8X5c.9$Lf5.309@news-west.eli.net...

As I said before the limits of my math are
high school and I need something condensed
so I do not need to know the fancy math.

Then just copy one of the routines you've
already found.

FFT is just a bunch of sines and cosines
put together in mysterious ways.
You too are not the expert I need here.

Clearly, the expert you need is a social worker.

 

[Ben Bradley]

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

You are a bubblehead.
Either answer my question directly
or get out of here.

Thank you for sharing.

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

 

[Mac]

On Wed, 17 Mar 2004 12:03:33 +0000, gmv wrote:

You are not telling me what I need to know here

Maybe I am and you don't realize it.

What I need is 500 discreet spectrum points
on 1024 samples of data showing energy
vs frequency and nothing more but I need to look
at a frequency between 100 seconds in period and
maybe one or ten hertz.
If you have the executable code and know how to use it
why can't you take my raw data and analyze it for me.

For one thing, you haven't asked (at least not in this thread).

Do you have a spreadsheet program? Excel, for example has an FFT function.
If you can get your data into a form that Excel can read, you can get
Excel to do the FFT for you.

[snip]

I do not know what you mean by top posting.

Top-posting is when you reply to someone, but put your reply BEFORE
(above) the text you are replying to. You did it again in this post, by
the way. It is annoying because it forces the reader to read the
conversation out of order.

[snip]

Your offer just exacerbates a preexisting condition
if it does not solve my problem here without any
fancy conversions. I have no "C" capabilities
and have no intention of learning it when
there are much nicer things like Basic and FORTRAN.

Can you write a program in either of those languages which will format
your data into a form which can be read by excel? For example, Excel can
easily read in tab delimited lists. So you could just print the data out,
seperated by tabs.

Then you will be just about home free, assuming you have Excel. If you
don't, maybe you can download the free office suite OpenOffice from
www.openoffice.org. I don't know whether it has an fft routine or not.

--Mac

"Mac" <foo@bar.net> Typed in message newsan.2004.03.17.04.26.23.48223@bar.net...
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 Wed, 17 Mar 2004 05:30:59 +0000, changling wrote:

"gmv" <NoEmail@ThisWay.123> wrote in
news:x0P5c.1$Lf5.178@news-west.eli.net:


"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.

quit taking the drugs and your mind will clear up enough
to be able to understand what the people here are trying
to tell you.

If he is being coerced to take anti-psychotic drugs, it could be because
he is psychotic without them. Even if you are a doctor, which seems
unlikely, you don't know enough about his case to make a recommendation
like that.

--Mac

 

[Mac]

On Wed, 17 Mar 2004 04:07:19 +0000, maxfoo wrote:

On Wed, 17 Mar 2004 00:53:11 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

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

OK, imagine a square wave in the time domain...

If you view that same square wave in the frequency domain
it will look like individual frequencies made up of the
fundamental and the odd harmonics up to infinity...

thats it with no government conspiracy involved.

What you are talking about is the Discrete Fourier Transform. The FFT is
an algorithm for computing this, but it's not the only one. Maybe gmv
should tackle the naive algorithm first, since it is quite simple and
doesn't require anything he didn't learn in highscool.

[snip]

--Mac

 

[Mac]

On Wed, 17 Mar 2004 12:03:37 +0000, gmv wrote:

[top-post moved down]

"changling" <allspam@goeshere.com> Typed in message news:Xns94AF66E4361Ballspamgoesherecom@216.77.188.18...
"gmv" <NoEmail@ThisWay.123> wrote in 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.


not knowing anything about FFT I went to the site that was mentioned
and I was able to make sense of what was there. get off the drugs
and maybe you will too.

[top post moved here]

Like I said before their drugs have damaged my brain and my body.
I am hooked on them and can not simply stop.
The secret Service had me incarcerated for making veiled threats
against the President and the mental health people
were ordered by a judge to force these drugs on me for a whole year.
I am now hooked on them and can not stop.
Without them I can not sleep. Sleep deprivation
is a form of torture and is used for brainwashing.
You guys really need to learn what your nice
country is capable of doing to you.

Actually, I am well aware that if you make threats against the president
of the United States, the Secret Service investigates you. Naturally, if
you end up getting a diagnosis of psychotic, people are going to try to
give you anti-psychotic drugs. No one wants a psychotic running around
loose.

The Secret Service does have a reputation for great earnestness in dealing
with the security of the president, counterfeit money, and, now, some
forms of computer fraud or hacking. I'm not too suprised to hear your
story.

--Mac

 

[Mac]

On Wed, 17 Mar 2004 12:03:35 +0000, gmv wrote:

[top-post fixed by moving reply down]

"Mac" <foo@bar.net> Typed in message
newsan.2004.03.17.04.37.23.689775@bar.net...
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

[top-post moved here]

Don't give me a history lesson.
Give me the block diagram for basic programming.

I wasn't talking to you. I was talking to Greg Neill.

--Mac

 

[Active8]

On Wed, 17 Mar 2004 12:03:35 GMT, gmv wrote:

Don't give me a history lesson.
Give me the block diagram for basic programming.

Programmers don't use block diagrams so you're SOL. If you can't

adapt that routine from Numerical Recipies in C into Basic, you're
FUBAR. Fill an array, pass it to the function with the number of
points and the flag... figure out how to interpret the output which
is explained...

<snip>

--
Best Regards,
Mike