Looking for an FFT block diagram for programming purposes

[Active8]

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

The military uses the FFT in secret ways and that
is the big secret.
Everytime you see a waterfall display in the
movies you are looking at an FFT machine.
It will compute in real time many discrete
spectrum points on the very same data stream as it comes in
in real time.
That is all I know about it.

Then you should download the SETI software and help them process
FFTs so they can find coherent signals from outer space, contact
your parents, and have them pick you up.

There is a government conspiracy and it has to do with money.
The industry is guarding how it uses this knowledge so
it can make money from it.

The industry took an FFT butterfly and optimised DSP chips to
process FFTs. They ain't worried about you hurting their business
unless you happen to be marketing your own semis.

I do not want to make money from this FFT thing
I just want to analyze some data packets I have
in the cheapest possible manner.
I can not work in the high tech world because I can not get
the security clearances to do so.

Maybe there's hope after all.

This country has black listed
me from such work.

I got the impression you spouted off and made a threat and got the
SS on your ass. So you blacklisted yourself. What ever gave you the
idea that you could excersize your freedoms when working for the
gov't?

This freedom loving country called
the United States of America.

Having a TS is *not* freedom.

Now either you can help me or not if not then get out.

You came to us, dickhead. I like that "do as I say or die" attitude,
but it's better suited for a less educated crowd.

I've given a little though to how to 'splain this shit without math
and the only thing I can say is that "if" in C is "if" in basic,
etc. and you should be able to adapt the code. We could then do
something with the output. Since you haven't so much as tried that,
I thought it would be fun to fuck with you a bit. Like a fly on a
strip

"maxfoo" <maxfooHeadFromButt@punkass.com> Typed in message news:uejf50hn3l7cfqn8vltccetn0280c8ntkh@4ax.com...
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.









Remove "HeadFromButt", before replying by email.

--
Best Regards,
Mike

 

[Active8]

On Wed, 17 Mar 2004 10:17:13 -0500, Greg Neill wrote:

"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

.... as i suspected.

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.

And then flog yourself for threatening POTUS.


--
Best Regards,
Mike

 

[Active8]

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

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

crist on a crutch! The link you were given for Numerical Recipies in
C also points to Numerical Recipies in Fortran. If you understand
those 2 languages, you can figure out how to convert C except maybe
the >> or << oprerator and things like that.

I think you're just f'ing with us.

"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

--
Best Regards,
Mike

 

[Active8]

On Wed, 17 Mar 2004 19:19:31 -0000, Kevin Aylward wrote:

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.

No, it's more like splitting a sum of terms into the sums of even
and odd terms repeatedly until you end up with sums of 2 terms. More
like saying


|c |b |c
INT| = INT| + INT|
|a |a |b


that's not a rearrangement. But WTF, your point is valid. Using it
is where it's at.

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.

Heh, heh, heh...

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.

We had a big abacus

--
Best Regards,
Mike

 

[Active8]

Ken, that's a good attempt you made below at explaining all this
with words. If the OP would search on the right keywords like FFT,
DSP, quadrature, whatever... he'd find a really good site with
illustrations where they've got the sines and cosines drawn in
quadrature along the time axis and they furthur went on to show the
FFT magnitudes in the same fashion.

Maybe someone else has seen it. ISTR The colors red and blue used in
the drawings. Big clue, eh?

On Wed, 17 Mar 2004 15:20:16 +0000 (UTC), Ken Smith wrote:

In article <s8X5c.10$Lf5.309@news-west.eli.net>,
gmv <NoEmail@ThisWay.123> wrote:
The military uses the FFT in secret ways and that
is the big secret.

Yes, and they've asked me nicely not to talk about that stuff so I won't.

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. Even in real life (non-movies) not all water
fall displays are the outputs of real time FFTs. In some cases, the
display is showing the outputs of many sensors side by side.

It will compute in real time many discrete
spectrum points on the very same data stream as it comes in
in real time.

I imagine quite a few people reading this could build one of those. These
days it isn't that hard. Anyone who understands the FFT could come up
with the version that can be stepped in time.


[....]
The industry is guarding how it uses this knowledge so
it can make money from it.

This is true, but it isn't something to worry about. The makers of snack
foods used the FFT in secret ways. You still have the option of eating
carrot sticks instead.

I do not want to make money from this FFT thing

Since the number of points you want is low, you could use the slow FT
method. It is very easy to understand. You may need to only imagine
doing the following. Some people understand things better if they do them
so you may want to actually spend the time.


Assume a list of 8 points represent a sine wave at some frequency you want
to determine. For easier thinking, make this list represent exactly
one full cycle. Call this list A.

Do this:

Note: Chances are you can use a spread sheet for this.

Make another list of values that are a sinewave at the same frequency.
Call this B

Multiply each value in B by the value for the same element of A.

ie: B[N] = B[N] * A[N]

Notice how the positive values in A get multiplied by positive values and
negitive values get multiplied by negitive value. Now total up all of the
new values in B. You get a positive answer. Write down this answer.

Try this same with sine waves at different frequencies so that you get 2
cycles or 3 cycles and try mixing in Cosines. You can make a list of
values for the results fron sines and cosines at each frequency.

Once you understand this, you can then start working towards understanding
the FFT.

Think of a list that is 16 points long instead of 8 points long. Imagine
that this list contains data the represents two cycles of a sine function.
You can do the 8 point FT on the first 8 points just like you did above.
You can also do a 8 point FT on the last 8 points.

Now, think about how the phase of the sinewave could be different if you
only last 8 points, than the phase in the first 8 points.

To combine the FT of the first 8 points with the FT of the last 8 points,
you need to match up the phases. To do this:

Imagine we have a Cosine value of 1 and a Sine value of 0.5. Get a chunk
of graph paper and a sheet of clear plastic or thin paper. Also get a pin
or thumb tack. Place the plastic over the graph paper an stick a pin
through at the (0,0) point. Plot a point for the values on a plastic
over the graph paper like this:

ASCII ART:


. . . . . . . . . . . . < Graph paper
. . . . . . . . . . . .
. . . . . . . . . . . .
0.5 . . . . . . . . . . * . < "*" indicates point
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
0.0 . . . . . . . . . . . .
0.0 1.0



Now rotate the plastic sheet around the pin at (0,0) by lets say 45
degrees CCW. Notice what happens to the Sin anc Cosine values when you do
this.

Now I think you can see how to combine two 8 point FTs to make 8
points of a 16 point FT. You have to adjust each value from the second 8
points and add them to the values in the first 8. These 8 points show how
the sine wave continues from the first 8 points into the second 8 with
a period the fits neatly into 8 sample.

The other 8 values in the FT are made in much the same way but you
subtract instead of adding. These numbers show how the sinewave didn't
come out even in 8 samples.

This is the basic step done several times in the FFT. You start off with
a bunh of 2 sample FTs then combine them into a bunch of 8 sample ones,
then into 16 and so on.

--
Best Regards,
Mike

 

[Mac]

On Wed, 17 Mar 2004 04:59:16 +0000, 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.

Oh, I have many books which cover the FFT in varying degrees of
complexity. And I have enough math to understand it. I have seen two basic
approaches. One is to do everythning in summation notation, and another is
to use the butterfly diagrams (as did Cooley and Tukey).

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.

I actually have a BSEE, which is about 4 years worth of electrical
engineering schooling. It's not that I don't get the FFT at all, it's just
that I don't have a good intuitive feel for it. I've never had that "Aha!"
of total comprehension. Probably I'll go back and look at it again in a
year or two and I'll have my "Aha!"

And I have implemented the simple radix 2 version of the algorithm by
studying some fortran code in one of my textbooks. I timed it against
LabVIEW's FFT, and my version took about twice as long as LabVIEW's for
all the sizes I tried. I considered that successful for my purposes. If I
need a fast implementation, I'll get the fastest FFT in the West.

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


Best regards,
Spehro Pefhany

Thanks for the links. I really should get _Numerical Recipes in C_.

--Mac

 

[gmv]

Hi all you out there in computerland.

As an example to show you what I am looking
for I found a great little program.
The only trouble is that this program will
not cover my frequencies of my interest which
are 1/100Hz to 10Hz.


http://www.qsl.net/dl4yhf/spectra1.html#download


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


"gmv" <NoEmail@ThisWay.123> Typed in message news:bxK5c.7$HU3.6194@news-west.eli.net...

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

 

[gmv]

That makes good sense since I know what I want is
at least 1024 butterfly operations on each and every
frequency I wish to find in my data.
Thanks for the tip.


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



"Mike" <mike@nospam.com> Typed in message news:1caxtw1qnnefq.74vllin6rg20.dlg@40tude.net...

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

 

[Ken Smith]

In article <h018c.6$V4.246@news-west.eli.net>, gmv <NoEmail@ThisWay.123> wrote:

Hello,
[...]
I used a hex editor to dissect a wave header and
to copy paste my data under the wave header.
The big pain here was learning the wave header
to get it to work.

Check out the program "sox". It can convert things to *.wav files for
you.

[...]

Maybe one day a decent no-nonsense freeware
FFT program can be had to analyze only files
and not the ten zillion other things they try to do.

They do exist. Usually they are fairly limited about the format of the
data they work with.

--
--
kensmith@rahul.net forging knowledge

 

[gmv]

Hello,

I will tell you guys what I finally did
to solve my problems. I just tried out one of the
FFT programs on the net that would accept wave files
and I converted my raw data file to a 8 bit mono wave file
at a sample rate of 11025 samples per second which was
an increase of 605.5 times the original data sample rate
this let me see the entire spectrum simply by scaling
the resulting frequencies by dividing by 605.5.
I used a hex editor to dissect a wave header and
to copy paste my data under the wave header.
The big pain here was learning the wave header
to get it to work. I was able to play back the
previously subsonic noise and listen to it using WMP9
or MMJB as well as analyze it in the fft.
If I were richer I would have bought a FFT and
done things right but living on disability like I do
I can't afford to do that. It is just pure luck
I can do these things at all.
Maybe one day a decent no-nonsense freeware
FFT program can be had to analyze only files
and not the ten zillion other things they try to do.


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





"gmv" <NoEmail@ThisWay.123> Typed in message news:bxK5c.7$HU3.6194@news-west.eli.net...

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

 

[gmv]

"Ken Smith" <kensmith@violet.rahul.net> Typed in message news:c3q7ie$5tj$1@blue.rahul.net...

In article <h018c.6$V4.246@news-west.eli.net>, gmv <NoEmail@ThisWay.123> wrote:
Hello,
[...]
I used a hex editor to dissect a wave header and
to copy paste my data under the wave header.
The big pain here was learning the wave header
to get it to work.

Check out the program "sox". It can convert things to *.wav files for
you.

I was just looking at that program.
Interesting you should mention it.
I am able to use the wave header I have just fine
with Music Match Jukebox or the FFT program but
if I try to play the raw converted to WAV file under WMP9
it will not work. The error messages given by
WMP9 and other Microsoft products are too damn cryptic
for me to figure out what exactly is wrong with things.

[...]
Maybe one day a decent no-nonsense freeware
FFT program can be had to analyze only files
and not the ten zillion other things they try to do.

They do exist. Usually they are fairly limited about the format of the
data they work with.

It seems to me WAV is a good standard if you can
only convert your RAW data files into WAV in a way that
will be accepted by all general player programs.
When I play my Earthquake files back 600 times
faster a regional Earthquake sounds like something
heavy being dropped if I play it back only 100 times
faster it sounds a lot like thunder.
I would post a WAV file for everyone to hear
but it only plays in MMJB and not WMP9.
I will play around with SOX and see what happens
but I think SOX only converts between different formats
and not RAW 8 bit unsigned integer data files.

--
--
kensmith@rahul.net forging knowledge

 

[Ken Smith]

In article <p3f8c.11$V4.223@news-west.eli.net>,
gmv <NoEmail@ThisWay.123> wrote:
[...]

but I think SOX only converts between different formats
and not RAW 8 bit unsigned integer data files.

*.dat files are text representations of values

*.raw files are files of binary values where you spell out the details

*.ub files are files of 8 bit unsigned binary values

--
--
kensmith@rahul.net forging knowledge

 

[gmv]

Well...live and learn...my dat files are
probably more correctly called .ub .
I found a problem with the WAV header I was making
and that is why things would not work in WMP9.
It seems WMP9 is more finnicky than is other programs
when it comes to WAV file headers.

In any case, my WAV files will now play OK.

It would be nice to have an encyclopedia of file extensions
I have just been inventing them as I go along.

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




"Ken Smith" <kensmith@violet.rahul.net> Typed in message news:c3s62h$2dh$1@blue.rahul.net...

In article <p3f8c.11$V4.223@news-west.eli.net>,
gmv <NoEmail@ThisWay.123> wrote:
[...]
but I think SOX only converts between different formats
and not RAW 8 bit unsigned integer data files.

*.dat files are text representations of values

*.raw files are files of binary values where you spell out the details

*.ub files are files of 8 bit unsigned binary values

--
--
kensmith@rahul.net forging knowledge

 

[Peter Manders]

On Thu, 25 Mar 2004 01:13:06 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

Well...live and learn...my dat files are
probably more correctly called .ub .
I found a problem with the WAV header I was making
and that is why things would not work in WMP9.
It seems WMP9 is more finnicky than is other programs
when it comes to WAV file headers.

In any case, my WAV files will now play OK.

It would be nice to have an encyclopedia of file extensions
I have just been inventing them as I go along.

http://www.wotsit.org

--
Peter Manders
Remove "u" from email address to reply.

"There are three secrets to a successful marriage. Unfortunately nobody knows what they are."

 

[gmv]

"Peter Manders" <news@manders.demon.nul> Typed in message news:dj3560pnsj6ctsr5j2sd41rhl5fces3g64@4ax.com...

On Thu, 25 Mar 2004 01:13:06 GMT, "gmv" <NoEmail@ThisWay.123> wrote:

Well...live and learn...my dat files are
probably more correctly called .ub .
I found a problem with the WAV header I was making
and that is why things would not work in WMP9.
It seems WMP9 is more finnicky than is other programs
when it comes to WAV file headers.

In any case, my WAV files will now play OK.

It would be nice to have an encyclopedia of file extensions
I have just been inventing them as I go along.

http://www.wotsit.org

Why is it the British seem better than us when
it comes to such stuff on the Internet ?
America has lost its competitive spirit.

--
Peter Manders
Remove "u" from email address to reply.

"There are three secrets to a successful marriage. Unfortunately nobody knows what they are."

 

[Rich Grise]

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

"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 suggest you look at section 12 of Numerical Recipes in C.

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

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.

It is not very hard to understand at all; it's just that it's FORTRAN.

If you can't do the arithmetic in this example, then you need to go
back to school. (OK, it's algebra, but still!)

But I'll help with the more obtuse parts.

the "Do <n> X=1,Y" construct is a "do loop." It means "assign the value
1 to the variable X and execute instructions from here to label 10,
then come back, increment X by one, and repeat until X reaches the value
Y, then continue on past line 10."

This can be generalized, of course.

The one in the middle, "Do 30 I=J,N,N1" means that the increment is
N1 rather than 1. (I'm pretty sure that's the case - it'd be easy
enough to check).

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

Yep, I think that's pretty much all there is to it.

As to "well guarded," I think it's a matter of knowing where to
look. And after all, how many people are looking anyway?! ;->

Good Luck!
Rich

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


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

 

[Rich Grise]

"gmv" <NoEmail@ThisWay.123> wrote in message
news:h8M5c.10$HU3.6299@news-west.eli.net...

"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:
....
used to be a military secret.
FFTs? You've got to be kidding.
Don't play games with me you young
whipper snapper.

He's not playing games with you. The plain fact of the matter is,
a Fourier Transform, and since the dawn of the computer age, the
Fast Fourier Transform, has been public knowledge ever since it
was invented. No one is keeping it a secret from you. Now, it
might not be readily available to you if you can't read the
language, but that doesn't mean there's some conspiracy to
keep you from knowing the answer, it simply means that it's your
own responsibility to teach yourself the language it's written in.

The Peking Daily News (or equivalent) might as well be a State
Secret for all I know, because I don't read Chinese. That does
NOT mean that China is conspiring to keep me from finding out
what's going on in downtown Peking.

Anyway, the fact that it's been freely publicly available for so
long makes us suspect that you're either telling a bad joke or
have led a very, very sheltered life. ;-)

Good luck!
Rich

 

[Al]

In article <3b4cc.10435$Zw.5609@nwrddc02.gnilink.net>,
"Rich Grise" <null@example.net> wrote:

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

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



************************ 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 **********************

Should E be set to 6.28319 inside of a do loop? What do you programmers
out there say?

Al

--
There's never enough time to do it right the first time.......

 

[Rich Grise]

"Al" <no.spam@here.com> wrote in message
news:no.spam-243A80.08462505042004@news.verizon.net...

In article <3b4cc.10435$Zw.5609@nwrddc02.gnilink.net>,
"Rich Grise" <null@example.net> wrote:
************************ 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 **********************


Should E be set to 6.28319 inside of a do loop? What do you programmers
out there say?

Al

It doesn't do any harm, but it is an extra load instruction each iteration.
Yes, it probably does make more sense to declare it outside the loop,
or with modern languages, define it as a constant. Don't forget, those
poor roobs writing that Fortran code had to write a line of code, punch
it onto a Hollerith card, take it to the card reader, come back, write
another line of code, punch a card, read it in, etc. etc. etc... And these
machines were hand-cranked!

So you can't blame the guy for putting an initialization inside the loop;
he's lucky he remembered to put it in at all!

Cheers!
Rich

(P.S. what's the smiley for tongue-in-cheek?)

 

[Richard Henry]

"Rich Grise" <null@example.net> wrote in message
news:IVIcc.7485$TS3.3061@nwrddc02.gnilink.net...

Don't forget, those
poor roobs writing that Fortran code had to write a line of code, punch
it onto a Hollerith card, take it to the card reader, come back, write
another line of code, punch a card, read it in, etc. etc. etc... And these
machines were hand-cranked!

I assume you meant this as a joke, but I do recall seeing a hand-operated
card punch machine on a college professor's desk.