SIGNAL PROCESSING - Biomechanics and Motor Control of Human Movement - page 30

of calculations is N 2 . It should be noted that the major expense in computer
time is looking up the sine and cosine values for each of the N angles.

2.2.3 Fast Fourier Transform (FFT)
The Fast Fourier Transform (FFT) became necessary because of the extremely
large number of calculations necessary in the Discrete Fourier Transform.
As early as 1942, Danielson and Lanczos introduced the Danielson-Lanczos
Lemma , which showed that the Discrete Fourier Transform of length N can
be broken into two separate odd and even numbered components of length
N / 2 each. In a similar manner, each N / 2 component can be broken into
two more odd and even numbered components of length N / 4 each, and each
of these can be broken into two more odd and even components of length
N / 8 each. Thus, the basis of the FFT is a data record that must be binary in
length. Therefore, if you collect data files that are not binary in length, the
FFT can only accept the largest binary length file within your data file. For
example, if you collected 1000 data points, the largest binary file length would
be 512 points; thus, 488 points would be wasted. Therefore, it is advisable
to prearrange data collection files to be binary in length; in the case of the
previous example, a data file of 1024 points would be appropriate. With the
advent of computers, many FFT algorithms appeared (Bringham, 1974), and
in the mid-1960s J. W. Cooley and J. W. Tukey at IBM developed what is
probably the best-known FFT algorithm.
One of the major savings in the FFT is to avoid repetitive and time-
consuming calculations especially sines and cosines. If we look at Equations
(2.16) and (2.17), we see that for the fundamental frequency ( n = 1), we must

calculate N sine and N cosine values. For the second harmonic, we recalculate
every second sine and cosine value, and for the third harmonic we recalcu-
late every third sine and cosine value, and so on up to the highest harmonic.
What the FFT does is calculate all sine and cosine values for the fundamental
and this forms a “look-up” table for the fundamental plus all higher harmon-
ics. Further savings are achieved by clustering all the products of x i and
the same sine value, then summing all the x i values, and then carrying out
one product with the sine value. The number of calculations for the FFT

=

N log 2 N , which is considerably less than N 2

for the Discrete Fourier Trans-

form. For example, for N = 4096 and a CPU cycle time of 0.1 μ stheDFT

would take 4096 2 10 − 7

= 1 . 67 s, while the FFT would take 4096 log 2 4096

10 − 7 · = 49 ms.

2.2.4 Applications of Spectrum Analyses
2.2.4.1 Analog-to-Digital Converters. To students not familiar with elec-
tronics, the process that takes place during conversion of a physiological
signal into a digital computer can be somewhat mystifying. A short schematic
description of that process is now given. An electrical signal representing a