Page 201 - Mechanical Engineers' Handbook (Volume 2)

190 Signal Processing
L sF(s) F(s)
L ƒ(t) dt
dƒ(t)
dt s (3)
By convention, functions in the time domain use t as the independent variable and functions
in the Laplace domain use s as the independent variable. For this reason, the Laplace domain
is commonly called the S-domain. The Fourier transform and the Laplace transform are
similar but different in two respects: (1) The Fourier transform integrates the signal over all
time while the Laplace transform integrates for positive times only and (2) the exponent of
the kernel in the Laplace transform is complex with both real and imaginary components
while the exponent in the Fourier transform has imaginary component and no real compo-
nent. By using Euler’s identity, e j cos( ) j sin( ), we see that
F{ƒ(t)} F( ) j
ƒ(t)e dt
ƒ(t) cos( t) dt j

ƒ(t) sin( t) dt
cos( t) j sin( t) . (4)
We approximate the Fourier transform from discrete samples ƒ(k) ↔ F(k), where 0 k
N and F(k) j :
k k
ƒ(i) cos 2 ƒ(i) sin 2 (5)
N 1
N 1
i k
i k
k
i 0 N k i 0 N
However, if the number of points we transform is a composite number and not a prime
number, we can restructure our calculations to eliminate some of the calculations. Further-
more, of the factors that are themselves composite, we can further factor and eliminate more
calculations. For this reason, the most efficient vector sizes are those that are highly com-
posite. As an example, consider the simple case of transforming four points. We can express
Eq. (5) for this case in matrix form as
1 2 2 4 1 3 6 ƒ 2
1
c
1
0
0

c
ƒ
1
1
1

c
1
ƒ

c 2 3 1 3 6 9 ƒ 3
where is the principal root of 1. The nth principal root of 1 is cos(2 /n)+ j sin(2 /n).
We can then factor the matrix into two sparse matrices:
1 2 0 0 1 0 2 0 ƒ 2
c
1
1
0
0
0
1
1
0
0 1
c
0
ƒ
1
1

c
0
ƒ
0
10
0
1
c 2 3 0 0 1 3 01 0 2 ƒ 3
Although it is possible to implement this efficient algorithm—known as the fast Fourier
transform (FFT)—for any vector size that is a composite number, it is most commonly
implemented for vector sizes in which all factors are 2. The effort in evaluating Eq. (5)
increases with the square of the number of points to transform, or O(n ). In contrast, the
2
p
effort for the FFT of order 2 increases proportionately to O(n log(n)). Finally, we can use
the FFT to estimate the power spectral density (PSD) of a given discrete signal by computing
the square of the magnitude of the FFT. The following algorithm describes the method for
computing the Fast Fourier Transform. 1