User Guide

Page 16-49
convolution: For Fourier transform applications, the operation of convolution
is defined as
∫
⋅⋅−⋅= .)()(
2
1
))(*( ξξξ
π
dgxfxgf
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),/2exp(
1
n
j
jk
nknkjix
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