| Fast Fourier Transform |
A Note About the FFT (Fast Fourier Transform)
We assume that you know
about
Fourier Series. The FFT algorithm does the following.
- Assume that the Fourier
Series - in complex form - is given by the expressions below. Note that you
can use a complex form to represent the coefficients (ak +
jbk). It's the same information, but it turns out that it
is easier to compute the complex form when you program this. It's easier,
and - most importantly - it is faster, and these computations can use a lot
of compute power.
The FFT calculates an
approximation to ak and bk, by doing a
sum. Assume that we have a set of N samples of f(t) - spaced
Dt seconds apart
(so that T = NDt.).
In essence, we are assuming that the record of data we have is one cycle of
a periodic function - even though we have only the one record of length T
seconds. In any event, we can approximate the integral with this sum.
The FFT algorithm is a fast
way to compute the sum.
- CAUTION: Although the
FFT algorithm is available in Mathcad, Matlab and other analysis
programs, that pesky 2/N factor is not always handled the same way in
those computations. In Matlab, the fft function does not put that 2/N
factor in the final result it gives you. More later.
When you use the FFT
algorithm, you will have to remember that frequency information will be lost
if the data is simply stored in an array in a computer program. Instead of
f(nDt),
you will have only a sequence, fn, that has no reference
to the specific times at which the samples were taken. You will have to
keep track of the length of the record and the interval between samples. If
you have done that, then you should find the following.
- The fundamental frequency
is 1/T, so that the kth computed coefficient (assuming
that the array starts at k = 0) is the coefficient of the kth
harmonic.
Example 1
Let us assume that you
take data for two seconds and record that data in a file. Let's also assume
that you get 4000 data points in that two second period. Here are the
conclusions that you can draw from those two facts.
- Since the length of the
data record is two seconds, if you take the FFT you are getting a
Fourier Series for a signal that has a period of two seconds.
- With a period of two
seconds, the fundamental frequency for the data in the data record
is 0.5 Hz.
- Now assume you want to
look for a frequency component in the recorded data, and you want to see
if there is a signal at 100 Hz.
- A signal at 100 Hz is
at a multiple of 200 times the fundamental frequency of 0.5 Hz. In
other words, a 100 Hz signal is the 200th harmonic
of 0.5 Hz.
- The 200th
harmonic will be in the 201st position in the
array returned by the Matlab function.
- You would look in the
201st position in the array to determine the
magnitude of the signal at 100 Hz.
Example 2
Let use imagine you have a
periodic signal. You do the following
- You take data on the signal
(using an oscilloscope, for example) and store the data in a file.
- The length of the data record
is T seconds.
- If the data record is T
seconds long, you can imagine that record repeating over and over again,
and you can imagine that the data record is one period of a periodic
signal. (We know that's not true, but if you do that you can use
Fourier techniques to determine frequencies of signals in the data in
the record.)
- If there is a periodic
signal T seconds long, that signal would have a fundamental of 1/T Hz and 2p/T
rad/sec (angular frequency).
- If there is a sine wave
buried in the data record, it will not have the same frequency as the data
record (unless you record exactly one period of the sine!). Let's
assume that the frequency of the sine wave is "f".)
- At this point we can consider
a specific numerical example.
- Assume that the data
record is 2 seconds long (i.e. T = 2.)
- The fundamental frequency
of the record is 0.5 Hz (i.e. 1/T = 1/2 = 0.5)
- Assume that the sine wave
signal in the record is at 7 Hz. In other words, there would be exactly
14 periods in 2 seconds - the length of the data record.
- We would expect to find a
peak in the computed Fourier coefficients at the 14th
harmonic of the data record.
- The data for the 14th
harmonic would be stored in the 15th array element if
you are using Matlab - since the DC (constant) term is stored in the
first array element. So, you would look in the 15th
array element to find data for a 7 Hz sine wave.
- The next issue you need to
address is how big the 7 Hz sine wave component is. You need to note the
following.
- The algorithm programmed
into Matlab is fft(FileData). That algorithm does not compute the sum
above, given again below.
- The algorithm does not
have the 2/N factor in the computed result, and you have to correct for
that. If you have an oscilloscope that returns 4000 data points, you
would have to divide every computed a and b by 2000 (i.e. 2/4000).
- Now you are ready to
determine how big the 7 Hz sine wave component is. Let's say that you found
that the computation gave you 10,000 at the 15th array
element. Dividing by 2000, you should find that you have a sine wave with
an amplitude of 5.
- If you have a more complex
signal (square wave, triangular wave, short pulse, etc.) those signals would
have harmonics. If you have a 7 Hz signal - not a sine - you would have
harmonics at 14 Hz, 21 Hz, etc. and you would need to look in the
appropriate array element to determine what the size of those components
are.
|
