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