Page 16-49
convolution: For Fourier transform applications, the operation of convolution
is defined as
∫
⋅
⋅
−
⋅
=
.
)
(
)
(
2
1
)
)(
*
(
ξ
ξ
ξ
π
d
g
x
f
x
g
f
The following property holds for convolution:
F{f*g} = F{f}
⋅
F{g}.
Fast Fourier Transform (FFT)
The Fast Fourier Transform is a computer algorithm by which one can
calculate very efficiently a discrete Fourier transform (DFT). This algorithm
has applications in the analysis of different types of time-dependent signals,
from turbulence measurements to communication signals.
The discrete Fourier transform of a sequence of data values {x
j
}, j = 0, 1,
2, …, n-1, is a new finite sequence {X
k
}, defined as
∑
−
=
−
=
⋅
−
⋅
=
1
0
1
,...,
2
,
1
,
0
),
/
2
exp(
1
n
j
j
k
n
k
n
kj
i
x
n
X
π
The direct calculation of the sequence X
k
involves n
2
products, which would
involve enormous amounts of computer (or calculator) time particularly for
large values of n. The Fast Fourier Transform reduces the number of
operations to the order of n
⋅
log
2
n. For example, for n = 100, the FFT
requires about 664 operations, while the direct calculation would require
10,000 operations. Thus, the number of operations using the FFT is reduced
by a factor of 10000/664
≈
15.
The FFT operates on the sequence {x
j
} by partitioning it into a number of
shorter sequences. The DFT’s of the shorter sequences are calculated and
later combined together in a highly efficient manner. For details on the
algorithm refer, for example, to Chapter 12 in Newland, D.E., 1993, “An
