HP 48GII, Руководство пользователя, Страница: 527 / 864

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