fft help

I am a high school student, senior, and I am intrested in fft. The only
problem is that the mathmatics are over my head. I am a ham radio operator
and fluent in Java, could someone help me with the mathmatics of fft

andrewjj20

"Josh" <andrewjj20@yahoo.com> wrote in message
news:B1h1b.592$_5.36242@news1.telusplanet.net...
> I am a high school student, senior, and I am intrested in fft. The only
> problem is that the mathmatics are over my head. I am a ham radio operator
> and fluent in Java, could someone help me with the mathmatics of fft
>
> andrewjj20

Josh,

Here is a viewpoint that may help you.  Not to introduce even more math, but
to simplify the math that you have to deal with.......  Starting with the
Fourier Transform:

    +inf
F(w)=int[f(t)*e^(-jwt) dt]
    -inf

This is the Fourier Transform - not yet the discrete form that is the fft.
"int" means "the integral of" here.  That's just a fancy way of saying "a
sum of all these things here...."

Note that this gives a function of frequency "w".
We can simplify the expression somewhat this way:
      +inf
F(w0)=int[f(t)*e^(-jw0t) dt]
      -inf

Now we are only solving for a single frequency "w0".  Now F(w0) isn't a
function, it's simply a number (OK, complex number).
This number is obtained by multiplying f(t) over all time by e^-jw0t and
integrating the result.
It measures how well f(t) resembles e^-jw0t.
You may note that e^-jx = cosx-jsinx so this really measures how much f(t)
aligns with cosw0t and how much f(t) aligns with sinw0t.

As different values of w0 are chosen, you get different measures of f(t)
that tell you "how much does f(t) look like this one? - how much energy is
at this frequency?"

So, now you can look at F(w) as a continuum of those kinds of measurements -
one for each frequency over all frequencies.

The fft is a little simpler in that it doesn't use integrals (which I've
always had a harder time visualizing than sums) - rather it uses sums, so
I'm happy with that.

I am assuming that you have the formula for an fft or a discrete Fourier
Transform (they are are same thing except the Fastft=fft is a particular
implementation).

Look at that formula now.....
       N+1
F(kW)=sum[f(nT)*e^-j*kW*nT]  0<=k<=N+1,  0<=n<=N+1
      n=0

N+1
sum[stuff]  means the sum of "stuff" for values of "stuff" from n=0 to
n=N+1.
n=0

Think of it this way:
Pick a value of k and compute the sum over all values of n.  This gives the
result for kW.
Then pick another value of k, etc. etc.

First of all, instead of continuous f(t), we started with a sampled version
f(nT) where T is the sample interval and n is the sample number.  If you've
been talking fft, then you've been talking about sampled data, right?

And, instead of an infinite series, we will limit the series of samples to
be a finite length series.

Similarly, instead of continuous F(w), we will have a sampled version F(nW)
where W is the sample interval in frequency and n is the sample number.

If there are N+1 samples in time, there will be N+1 samples in frequency
with N intervals over the span in each case.

If the time samples extend over NT seconds, then the frequency sample
interval W=1/NT radians per second.

If the sampling frequency is NW then the time sample interval is 1/NW
seconds.

Example:
We will sample in time at 10kHz.  This makes T=1/10^4=0.0001
We will sample for 2 seconds.
(2/0.0001) + 1 = 20,001 samples = N+1 (we need to count the sample at time
zero, thus the +1)

When we take the discrete Fourier Transform or the Fast version of it:
the sample rate is still 10kHz.
The frequency interval is 1/2 seconds = 0.5 radians per second.
There are 20,001 samples in frequency.

Per the Nyquist criterion, we should not sample f(t) unless it has
substantially no energy at 1/2 the sampling frequency or greater.
So, in this case the f(t) that we sample should have a bandwidth of under
5kHz.
4kHz might be a decent practical upper limit.

I hope this helps.  Ask more questions and I'll try to focus on them.  There
are lots of things you might do that would avoid too much math:
- one is: look at Fourier Transform "pairs" that show the time and frequency
domain plots side by side.  This gives some insight.  Wide in time, narrow
in frequency.  Narrow in time, wide in frequency. etc. etc.  Square pulse in
time, sin(w)/w shape in frequency.  sin(t)/t shape in time, lowpass (square)
in frequency.  Single sample in time, flat magnitude in frequency.  Constant
in time, single value at zero frequency "dc".

Fred
AC7VR

Josh <andrewjj20@yahoo.com> wrote in message news:<B1h1b.592$_5.36242@news1.telusplanet.net>...
> I am a high school student, senior, and I am intrested in fft. The only
> problem is that the mathmatics are over my head. I am a ham radio operator
> and fluent in Java, could someone help me with the mathmatics of fft
> 
> andrewjj20

I don't know where you study, but "high school" makes me think about 
the general level of maths that a 14 to 16 year-old would be expected 
to know...

Based on that, I make the following assumptions on your maths knowledge:

- You do know vector calculus
- You don't know complex numbers
- You do know trigonometry 
- You don't know exponential functions

Before we start on the FFT (or, more presicely, the DFT, the Discrete 
Fourier Transform) let's just recap some basic vector calculus. 

You know that any point in 3D space can be expressed by a triplet of 
numbers, the (x,y,z) coordinates. Formally, the coordinates of a point 
can also be thought of as a "recipe" to construct a vector extending 
from the origo to that point:

   v'=x*i'+y*j'+z*k'                                         (1)

where the hyphen "'" marks a vector quantity and i', j' and k' are the 
basis vectors in a orthonormal coordinate system. The vector can be 
expressed in coefficient notation as

   v'= [x, y, z]                                             (2)

where it is understood that the first coefficient says how much the 
basis vector i' contributes to v', the second coefficient says how much
j' contributes to v', etc. 
 
Once we have this recipe we can do all sorts of things with v'. When we 
make geographical maps we essentially draw an image of the (x,y) plane on 
a piece of paper, and forgets about the z numbers. We can enlarge the 
vector by multiplying the coordinates with some factor. 

If somebody owns a rectangular piece of land with the long edges pointing 
in the north-east direction, it is very convenient to use latitudes 
(aligned east-west) and longitudes (aligned north-south) to find the 
place on a map. But if you want to, say, but up a new building there, 
it may be more convenient to say that a corner should be "five metres 
from this long edge and ten meters from that short edge". So we use
two different sets of "basis vectors", either those aligned with the 
map, or those aligned with the land boundaries. There are methods to 
convert from one set of basis vectors to the other. Such conversions 
are called "transforms" in mathematical lingo. 

In short, once we know how to express the vector v' in terms of the basis 
vectors i', j' and k', a lot of things that seems complicated become easy.
Such "things" are called "transforms". This is essentially the line of 
thoughts that is at the bottom of the DFT (I'll explain the difference 
between the DFT and the FFT in a moment). 

A signal d[n] is essentially a sequence of N numbers, call each number 
d(n), indexed from 0 to N-1. (BTW, note how I use the square brackets 
"[" and "]" to distinguish the sequence from the individual numbers s(n) 
that make up the sequence. This notational convention may be troublesome
in the beginning). One can write out the sequence as 

  d[n]=[d(0),d(1),...,d(N-1)].                                    (3)

If you compare this sequence of numbers with (2) above, you see that 
it looks a lot like a vector written out on coefficient form, but that 
there are a lot more coefficients in d[n] than in the vector v' in (2).

Now, the concept of a "vecor" is not confined to 3D space. Maths tells 
us (but this is maths *way* above the high school level) that any sequence
of N numbers can be treated as a vector in N dimensional space. Don't be 
afraid if you find this overwhelming. This is stuff that belongs on the 
university level, and it does take quite a bit of time to get used to.
 
If you trust me on this, it turns out that one can choose what basis 
vectors we want to use to represent our vector (remember the patch of 
land; we use the map coordinates or the boundary coordinates as we
find appropriate).

At last we are approaching what you ask about. It turns out that it 
is very convenient to express signals in terms of "waves", or "sinusoidals".
A "sinusoidal" is a sequence of numbers that behaves much like a sine 
function with angular frequency w, i.e.

   s[n]=[sin(w*0),sin(w*1),...,sin(w*(N-1))].                   (4)

This isn't entirely correct, as one really needs the cosine function 
as well, 

   c[n]=[cos(w*0),cos(w*1),...,cos(w*(N-1))]                    (5)

but for the time being I ignore the cosine component.

It turns out that if you choose the frequencies w carefully, and get 
enough of them, it is possible to make up a new set of basis vectors
that completely describes the signal d[n]. The reason we want to do this, 
is that it is very easy to describe (in terms of maths) what happens to 
one sinusoidal when it is sent through an electronic circuit. Which means 
that the basic way of analyzing what a circuit does to a signal amounts to

- Express the signal in terms of sinusoidals and send each sinusoidal 
  through the circuit
- See what happens to the different sinusoidals when sent through 
  the circuit (different thinghs may happen to different sinusoidals)
- At the output, take all those sinusoidals and build a "normal"
  sequence from it

The process of expressing any sequence of numbers in terms of sinusoidals 
is called a "Discrete Fourier Transform". "Discrete" because the sequence 
of numbers is discrete (as opposed to continuous functions), "Fourier"
after the guy who first examined these types of techniques in detail, 
and "Transform" because we convert from one way of looking at the signal 
to another. Now, "FFT" stands for "Fast Fourier Transform" and is one method
of doing the computations (there are several) that is particularily fast. 
The relation between the two is like "sum" and "addition": "Addition" is 
the method of computation that produces a "sum".

So, the DFT transforms the sequence d[n]. What comes out of the process is 
a "spectrum", i.e. a sequence of numbers, 

   D[k]=[D(0),D(1),...,D(N-1)].                                     (6)

I mentioned in passing that you need "enough sinusoidals" to express the 
signal. The frequencies of these sinusoidals are termed w_k, so the number 
D(k) expresses how much of the sinusoidal of frequency w_k that goes into 
the sequence (exactly the same way that the number x in (2) above expresses
how much of the basis vector i' is needed to make the vector v'). And do 
note how the term "inner product" is used. It's exactly the same way, and 
has exactly the same meaning, as in 3D geometry.

And that's basically it. I have omitted a couple of details, though.
The maths becomes a lot more easy if you express the sinusoidals in terms
of complex exponentials. There are certain rules that determines how 
to choose the frequencies w_k etc, but that's technicalities. I have 
made an effort to give an impression of the big picture, based on the 
general level of knowledge I assume (rightly or wrongly) that you have.
Apart from the technicalities, the big hurdle is the extension of the 
"vector" concept from 3D to N dimensional space. It takes time to get 
used to, but I don't really see why it should be more difficult than 
accepting that the square root of -1 exists, which is the basis for 
complex numbers.

Rune

Josh wrote:

> 
so, knowing that theory, if I have have a waveform of n samples, how can I
change it from amplitude and time to frequency and amplitude.

this comming school year I plan to take calculus, but I have taken every
high school physics class available, and after that I plan on going into
computer engineering, university courses.

andrewjj20

"Josh" <andrewjj20@yahoo.com> wrote in message
news:sVt1b.3545$_5.69106@news1.telusplanet.net...
> Josh wrote:
>
> >
> so, knowing that theory, if I have have a waveform of n samples, how can I
> change it from amplitude and time to frequency and amplitude.
>
> this comming school year I plan to take calculus, but I have taken every
> high school physics class available, and after that I plan on going into
> computer engineering, university courses.
>
> andrewjj20

Josh,

It depends on what tools you have at your disposal.  You might Google on
"fft java" and come up with:
http://www.isip.msstate.edu/projects/speech/software/demonstrations/applets/
util/spectrum/v2.1/FFT.java
or some other.

Once you get the complex frequency samples using a program like this, you
will need to compute the absolute value to get the amplitude.

Fred

Josh <andrewjj20@yahoo.com> wrote in message news:<B1h1b.592$_5.36242@news1.telusplanet.net>...
> I am a high school student, senior, and I am intrested in fft. The only
> problem is that the mathmatics are over my head. I am a ham radio operator
> and fluent in Java, could someone help me with the mathmatics of fft
> 
> andrewjj20

On a related topic, not being extremely mathematics literate myself
(no calculus yet), I got a pretty good foundation on DSP by reading
the online book at http://www.dspguide.com/ . It's a very good book
for those who are starting from zero knowledge, and takes you to a
level of being able to design your own stuff.   And you can view it
online for free, with the opportunity to order a hardcopy version of
the book if you like it.

While it explains everything up to the FFT (correlation, DFT, etc.),
when it comes to the FFT it doesn't get heavily into the math, but
merely breaks down the whole and explains the basic parts of it.

It gives some sample code for the DFT, FFT, filters, etc; but the
emphasis is on using the code to help further your understanding of
the subject; it's not a book full of ready-to-use programming
material.