Digital Signal Processing Reference
In-Depth Information
Unfortunately, the true speed of the FFT technique cannot be realized on a
general-purpose processor that many users will be using to filter waveforms. As
mentioned previously, the general-purpose processor will not have the option of
bit-reversed addressing or manipulation of complex numbers in two memory
locations. Therefore, the true efficiency of the FFT algorithm cannot be
demonstrated on a general-purpose processor.
However, Proakis and Manolakis have discussed the theoretical efficiencies
of this process that we can review at this point. They have determined that the
number of complex multiplications required per output point can be determined by
(9.16). Recognizing that there are four real multiplications needed for each
complex multiplication, and also recognizing that for convolution there are
M
real
multiplications needed for each output point, a comparison can be made in Table
9.3. In the table, the left-hand column represents the number of data points
N
in
the FFT. The top row gives the various numbers of filter coefficients used
M
.
Within the table are given the number of real multiplications per output point
necessary for the calculation of the FFT. These numbers should be compared to
the
M
value, which represents the number of calculations per output point for the
convolution method. Not all filter applications should consider the FFT approach
as depicted in column 2 (
M
= 32). In the best case, the FFT approach would
require 41 real multiplications to the convolution approach of 32. However, it is
apparent that as the number of filter coefficients increase, the FFT approach can
provide real efficiencies. A second point to recognize is that the number of points
in the FFT should also be considered when setting up the filtering system. In
general, it appears that the size of the FFT should be set to approximately 8 times
the number of coefficients used in the filter.
N
⋅
log
2
(
2
⋅
N
)
c
=
(9.16)
L
Table 9.3
Number of Real Multiplications per Output Point
N=FFT size
M=32
M=64
M=128
M=256
M=512
64
54
-
-
-
-
128
43
64
-
-
-
256
41
48
72
-
-
512
43
46
54
80
-
1,024
46
47
51
59
88
2,048
49
50
52
55
64
4,096
53
53
54
56
60
8,192
57
56
57
58
60
